【文章內(nèi)容簡(jiǎn)介】 )=3， 得到正向全標(biāo)三角形 {z1,z2, z3}， 計(jì)算將離開(kāi)三角形而進(jìn)入四面體 。 這樣 ， 還應(yīng)該把正向全標(biāo)三角形叫做它自己的出口 。 第 2章 代數(shù)方程的 Kuhn算法 電子科技大學(xué)計(jì)算機(jī)學(xué)院 顧小豐 計(jì)算的復(fù)雜性 86 32 2022/2/17 進(jìn)口出口分析 (續(xù) 1) 步 2則是降維的情況 ， 一個(gè)負(fù)向全標(biāo)三角形 {z1,z3,z2}是上一步的結(jié)果 。 現(xiàn)在 ， 要取消 z3， 計(jì)算從剩余的 (2,1)棱出去 。 所以應(yīng)該把負(fù)向全標(biāo)三角形 叫做它自己的 進(jìn)口 。 綜上所述 ， (1,2)棱 或 {z1,z3,z2}是該三角形的 進(jìn)口 ， (2,1)棱 或{z1,z2,z3}是該三角形的 出口 。 第 2章 代數(shù)方程的 Kuhn算法 電子科技大學(xué)計(jì)算機(jī)學(xué)院 顧小豐 計(jì)算的復(fù)雜性 86 33 2022/2/17 進(jìn)口出口分析 (續(xù) 2) 步 3的情況，由于維數(shù)沒(méi)有變動(dòng)，所以簡(jiǎn)單得多。對(duì)于一個(gè)四面 體 ， 已經(jīng)有一個(gè)面是全標(biāo)三角形 ， 那么不論第四個(gè)點(diǎn)的標(biāo)號(hào) l(z‘)如 何 ， 都正好和某一個(gè)頂點(diǎn)標(biāo)號(hào)相同 。 這樣同標(biāo)號(hào)替換以后 ， 又得 到一個(gè)全標(biāo)三角形的面 ， 而另外兩個(gè)面 ， 則因都有標(biāo)號(hào)相重而不 是全標(biāo)三角形 。 從四面體的內(nèi)部看來(lái) ， 正向全標(biāo)三角形 {z1,z2,z3}是 進(jìn)口 ， 負(fù)向全標(biāo)三角形 {z1,z3,z2}是 出口 。 把 進(jìn)口 和 出口 統(tǒng)稱為 門(mén) 第 2章 代數(shù)方程的 Kuhn算法 電子科技大學(xué)計(jì)算機(jī)學(xué)院 顧小豐 計(jì)算的復(fù)雜性 86 34 2022/2/17 進(jìn)口出口分析圖示 2 1 1 1 2 3 1 3 2 1 2 3 3 第 2章 代數(shù)方程的 Kuhn算法 電子科技大學(xué)計(jì)算機(jī)學(xué)院 顧小豐 計(jì)算的復(fù)雜性 86 35 2022/2/17 引理 27 引理 27 對(duì)于頂點(diǎn)在集合 {1,2,3}中取標(biāo)號(hào)的一個(gè)標(biāo)號(hào)三角形或四面體 ， 或者它沒(méi)有門(mén) ， 或者它正好有一對(duì)門(mén) ， 一個(gè)是進(jìn)口 ， 一個(gè)是出口 。 第 2章 代數(shù)方程的 Kuhn算法 電子科技大學(xué)計(jì)算機(jī)學(xué)院 顧小豐 計(jì)算的復(fù)雜性 86 36 2022/2/17 引理 27的證明 證明：按照門(mén)的定義，對(duì)于標(biāo)號(hào)的三角形，如果它缺少標(biāo)號(hào) 1或 2， 則它沒(méi)有門(mén) 。 對(duì)于標(biāo)號(hào) 1， 2具備的情況 ， 若沒(méi)有標(biāo)號(hào) 3， 則 (1,2) 棱是進(jìn)口 ， (2,1)棱是出口 ， 另一棱是 (1,l)或 (2,2)不是門(mén) ， 所以正 好是一對(duì)門(mén) 。 若三角形全標(biāo) ， 在負(fù)向的情況 ， {z1,z3,z2}是進(jìn)口 ， (2,1)棱是出口；在正向的情況下 ， (1,2)棱是進(jìn)口 ， {z1,z2,z3}是出 口 。 不論正向負(fù)向 ， 另兩棱均有標(biāo)號(hào) 3， 不是門(mén) 。 所以也正好是一對(duì) 門(mén)。 對(duì)于標(biāo)號(hào)的四面體 ， 如果它缺少任何一個(gè)標(biāo)號(hào) ， 則它沒(méi)有全標(biāo)三 角形的面 ， 是一個(gè)無(wú)門(mén)的四面體 。 若四個(gè)頂點(diǎn)取全了 1,2,3標(biāo)號(hào) ， 則 正好有一對(duì)頂點(diǎn)標(biāo)號(hào)相重 。 這時(shí) ， 以同標(biāo)號(hào)棱為棱的兩個(gè)面三角形均 非全標(biāo) 。 另兩個(gè)面三角形都是全標(biāo)三角形 ， 是一對(duì)被同標(biāo)號(hào)棱撐開(kāi)的 三角形 。 這時(shí) ， 站在四面體內(nèi)部 ， 若一個(gè)全標(biāo)三角形在正面 ， 則另一 個(gè)在背后 。 若一個(gè)是正向全標(biāo)三角形 ， 則另一個(gè)是反向全標(biāo)三角形； 反之亦然?！? 第 2章 代數(shù)方程的 Kuhn算法 電子科技大學(xué)計(jì)算機(jī)學(xué)院 顧小豐 計(jì)算的復(fù)雜性 86 37 2022/2/17 引理 28 引理 28 按照算法 21， 從 ?Qm的每個(gè) (1,2)棱開(kāi)始的計(jì)算 ， 可以一直進(jìn)行下去 。 證明 ：因?yàn)椴徽撚?jì)算走到三角形或四面體 ， 有進(jìn)口就有出口 ， 所以 ， 計(jì)算可以一直進(jìn)行下去 。 ■ 對(duì)于三角形或四面體 ， 計(jì)算若能進(jìn)來(lái) ， 則一定能夠出去 。 所以 ， 今后不說(shuō)進(jìn)入 ， 而說(shuō)計(jì)算通過(guò)一個(gè)三角形或一個(gè)四面體 。 把有門(mén)的三角形和四面體看作是 “ 人 ” ， 兩個(gè)看作是一雙手 。 這樣 ， Kuhn算法的曲線都是由許多人手拉手連起來(lái)的 。 有了這個(gè)比喻 ， 就容易理解 ， 如果曲線會(huì)分叉或打圈 ， 就一定有一些三只手的 “ 人 ” ， 與前面證明的每 “ 人 ” 正好有一雙手矛盾 。 第 2章 代數(shù)方程的 Kuhn算法 電子科技大學(xué)計(jì)算機(jī)學(xué)院 顧小豐 計(jì)算的復(fù)雜性 86 38 2022/2/17 Kuhn算法的收斂性（一） 這一節(jié)我們將證明 ， 按照算法 21從?Qm上每個(gè)標(biāo)號(hào) (1,2)棱開(kāi)始計(jì)算 ， 都收斂到多項(xiàng)式 f的的一個(gè)零點(diǎn) 。 第 2章 代數(shù)方程的 Kuhn算法 電子科技大學(xué)計(jì)算機(jī)學(xué)院 顧小豐 計(jì)算的復(fù)雜性 86 39 2022/2/17 計(jì)算的單純形序列 定義 24 對(duì)于整數(shù) j， 1≤j≤n， 順次記從 ?Qm上第 j條 (1,2)棱 開(kāi)始的計(jì)算所通過(guò)的三角形 （ 二維搜索時(shí) ） 或四面休 （ 三維搜索時(shí) ） 為 σj1,σj2,...,σjk,...， 稱它為第 j個(gè) 計(jì)算的單純形序列 。 按照這種記法 ， σjk可能是一個(gè)三角形 ， 也可能是一個(gè)四面體 。 我們知道 ， 空間不共線的三個(gè)點(diǎn)的凸包是 2維單純形 ， 三角形就是 2維 單純形；空間不共面的四個(gè)點(diǎn)的凸包是 3維單純形 ， 四面體就是 3維單 純形 。 采用上述記法 ， 在需要區(qū)別的時(shí)候 ， 我們用 σ2jk表示它是一個(gè) 2維單純形 ， 即三角形；或?qū)懽?dim(σjk)=2， 即 σjk的維數(shù)為 2， 表明 σjk是一個(gè) 2維單純形 ， 即三角形 。 同樣 ， 表示 σ3jk維單純形 ， 即四面 體； dim(σjk)=3表明 σjk是一個(gè) 3維單純形 ， 即四面體 。 第 2章 代數(shù)方程的 Kuhn算法 電子科技大學(xué)計(jì)算機(jī)學(xué)院 顧小豐 計(jì)算的復(fù)雜性 86 40 2022/2/17 計(jì)算的點(diǎn)序列 定義 25 對(duì)于整數(shù) j， 1≤j≤n， 記 (zj 1,dj 1)為 σj 1的 不在 ?Qm的頂點(diǎn) ， 對(duì)于 k≥2， 當(dāng) dim(σjk)≥dim(σj,k1)時(shí) ， 記 (zjk,djk)為 σjk的不屬于 σj , k 1的頂點(diǎn) ， 當(dāng) dim(σjk)＜ dim(σj,k1)時(shí) ， 記 (zjk,djk)=(zj,k1,dj,k1)。 這樣得到的序列 {(zjk,djk)|k=1,2,...}稱為第 j個(gè) 計(jì)算的點(diǎn)序列 。 如果我們只關(guān) 注該序列在 z平面的投影 ， {zjk}也稱為第 j個(gè)計(jì)算的點(diǎn)序 列 。 第 2章 代數(shù)方程的 Kuhn算法 電子科技大學(xué)計(jì)算機(jī)學(xué)院 顧小豐 計(jì)算的復(fù)雜性 86 41 2022/2/17 定義的說(shuō)明 注意 ， 計(jì)算的單純形序列中的單純形的維數(shù)只可能是 2或 3， 所以 dim(σjk)＜ dim(σj,k1)的情況不可能連續(xù)發(fā)生 。 下面我們還將知道 （ 見(jiàn)推論 21） ， dim(σjk)＜ dim(σj,k1)的情況 ， 只能發(fā)生有限次 ， 即對(duì)于每個(gè)計(jì)算序列 ， 步 2只能執(zhí)行有限多次 。 下面我們先討論一下算法的性狀 。 第 2章 代數(shù)方程的 Kuhn算法 電子科技大學(xué)計(jì)算機(jī)學(xué)院 顧小豐 計(jì)算的復(fù)雜性 86 42 2022/2/17 引理 29 引理 29 若 dim(σjk)=2， 則 σjk?Qm。 這就是說(shuō) ， 二維搜索不會(huì)跑到 ?Qm外面去 。 證明 ： 若不然 ， 存在 j,k使 dim(σjk)=2， 但 σjk?Qm。 按照算法 ，二維搜索只能在 C1平面上發(fā)生 ， 即 σjk?C1， 不妨設(shè) σjk是計(jì)算的單純形序列 σj1,σj2,...中頭一個(gè)位于 ?Qm外的三角形 。 這時(shí) ， 若dim(σj,k1)=2， 則 σj,k1?Qm， 所以 σj,k1和 σjk有一條公共棱在 ?Qm上， 具有標(biāo)號(hào) 1和 2。 若該棱是 (1,2)棱 ， 則它是內(nèi)三角形 σj,k1的進(jìn)口， 與由 σj,k1到 σjk的計(jì)算順序矛盾；若該棱是 (2,1)棱 ， 則與引理 21矛盾 。 若 dim(σj,k1)=3， 按照算法 21（ 步 2） ， σj,k是 ?Qm外一個(gè) {z1,z3,z2}全標(biāo)三角形 ， 與引理 25矛盾 。 ■ 第 2章 代數(shù)方程的 Kuhn算法 電子科技大學(xué)計(jì)算機(jī)學(xué)院 顧小豐 計(jì)算的復(fù)雜性 86 43 2022/2/17 換一個(gè)角度分析進(jìn)口出口 上節(jié)已證明 ， 對(duì)于 T1中的三角形或 T中的四面體 ， 或者它沒(méi)有 門(mén) ， 或者它正好有一對(duì)門(mén) ， 一個(gè)是進(jìn)口 ， 一個(gè)是出口 。 但是 ， 門(mén)之 作為進(jìn)口或作為出口 ， 是相對(duì)于三角形或四面體而言的 。 例如圖 212（ 字母表示頂點(diǎn) ， 腳標(biāo)表示該頂點(diǎn)的標(biāo)號(hào) ） ， B1C2是一個(gè)門(mén) ， 對(duì)于三角形 BAC來(lái)說(shuō) ， 它是出口 ， 對(duì)于三角形 BCD來(lái)說(shuō) ， 它是進(jìn) 口 。 又如 B1C2D3這個(gè)門(mén) ， 對(duì)于三角形 BCD本身來(lái)說(shuō) ， 它是出口 ， 從 二維搜索轉(zhuǎn)入三維搜索的出口；對(duì)于四面體 BCDE來(lái)說(shuō) ， 它是進(jìn) 口 ， 從二維搜索進(jìn)入三維搜索的進(jìn)口 。 再如 B1E2D3這個(gè)門(mén) ， 是 BCDE的出口 ， 又是 BEDF的進(jìn)口 。 如果一個(gè)門(mén)是某個(gè)三角形或四面體的出口 ， 我們稱該三角形或 四面體為這個(gè)門(mén)的 上方單純形 ；如果一個(gè)門(mén)是某個(gè)三角形或四面體 的進(jìn)口 ， 我們稱該三角形或四面體為這個(gè)門(mén)的 下方單純形 。 第 2章 代數(shù)方程的 Kuhn算法 電子科技大學(xué)計(jì)算機(jī)學(xué)院 顧小豐 計(jì)算的復(fù)雜性 86 44 2022/2/17 E 2 A 2 B 1 C 2 D 3 F 2 圖 212 第 2章 代數(shù)方程的 Kuhn算法 電子科技大學(xué)計(jì)算機(jī)學(xué)院 顧小豐 計(jì)算的復(fù)雜性 86 45 2022/2/17 引理 210 引理 210 對(duì)于任何一個(gè)不在 ?Qm上的門(mén) ， 它的上方單純形和下方單純形都是唯一存在的 。 對(duì)于 ?Qm上的門(mén) ， 它就是我們算法的起始棱 ， 相應(yīng)的結(jié)論是：它的下方單純形是唯一存在的 。 第 2章 代數(shù)方程的 Kuhn算法 電子科技大學(xué)計(jì)算機(jī)學(xué)院 顧小豐 計(jì)算的復(fù)雜性 86 46 2022/2/17 引理 210的證明 證明 ：按照門(mén)的定義 ， 它或者是 T1(?,h)中的標(biāo)號(hào)為 1和 2的棱 ， 或者若它是 T1(?,h)中的標(biāo)號(hào)為 1和 2的棱 ， 且不在 ?Qm上 ， 由引理 29可知 ， 它在內(nèi)部 ， 根據(jù) 剖分 T1(?,h)的定義 ， 任何一條棱是且僅是兩個(gè)標(biāo)號(hào)三角形的一條公共邊 ， 因此這 兩個(gè)標(biāo)號(hào)三角形中一個(gè)門(mén)的上方單純形 ， 另一個(gè)是該門(mén)的下方單純形 ， 且唯一 。 若它是 T(?,h)中的全標(biāo)三角形 。 當(dāng)它是 T1(?,h)中的正向全標(biāo)三角形 {z1,z2,z3} 時(shí) ， 它的上方單純形是 T(?,h)中以三角形 z1z2z3為一個(gè)面的四面體 ， 根據(jù)剖分的定 義 ， 這樣的四面體是唯一的 ， 它的下方單純形就是它本身 。 當(dāng)它是 T1(?,h)中的負(fù) 向全標(biāo)三角形 {z1,z3,z2}時(shí) ， 它的上方單純形是它本身 ， 它的下方單純形是 T(?,h)中 以三角形 z1z3z2為一個(gè)面的四面體 ， 這樣的四面體也是唯一的 。 當(dāng)它不在 T1(?,h) 中時(shí) ， 由于任何一個(gè)不在 T1(?,h)中三角形是且僅是兩個(gè)四面體的一個(gè)公共面 ， 因 此這兩個(gè)四面體一個(gè)是門(mén)的上方單純形 ， 另一個(gè)是該門(mén)的下方單純形 。 ■ 第 2章 代數(shù)方程的 Kuhn算法 電子科技大學(xué)計(jì)算機(jī)學(xué)院 顧小豐 計(jì)算的復(fù)雜性 86 47 2022/2/17 引理 211 引理 211 若 (j,k)≠(i,l) ， 則 σ jk≠ σ il。 這就是說(shuō) ， 在剖分并標(biāo)號(hào)的半空間中 ， T1的每個(gè)三角形和 T的每個(gè)四面體 ， 都頂多只允許計(jì)算通過(guò)一次 。 第 2章 代數(shù)方程的 Kuhn算法 電子科技大學(xué)計(jì)算機(jī)學(xué)院 顧小豐 計(jì)算的復(fù)雜性 86 48 2022/2/17 引理 211的證明 證明 ：首先注意， σjk=σil， k＞ 1， l＞ 1蘊(yùn)涵 σj,k1=σi,l1。這只 要對(duì)作為 σ=σjk=σil的進(jìn)口的門(mén)運(yùn)用引理 210：這個(gè)門(mén)的上方單純形 唯一 ， 所以 σj,k1=σi,l1。 若引理不真： σjk=σil。 不妨設(shè) k≤l。 由 σjk=σil， k＞ 1， l＞ 1蘊(yùn) 涵 σj,k1=σi,l1， 可得 σj,1=σi,lk+1。 考慮作為 σj,1的進(jìn)口的門(mén) 。 按照算 法 ， 它是 ?Qm上第