《計(jì)算的復(fù)雜性》PPT課件.ppt

1、計(jì)算的 復(fù)雜性,計(jì)算機(jī)科學(xué)與工程學(xué)院,86 - 2,2021/3/29,第2章代數(shù)方程的Kuhn算法,剖分法與標(biāo)號(hào)法 互補(bǔ)輪回算法 Kuhn算法的收斂性 Kuhn算法的復(fù)雜性,86 - 3,2021/3/29,引 言,與各種傳統(tǒng)的迭代方法（例如Newton方法）不同，Kuhn算法 基于空間的一種單純剖分，一種整數(shù)標(biāo)號(hào)法和一種互補(bǔ)輪回的 算法過(guò)程。如果說(shuō)它的敘述不象Newton方法那么簡(jiǎn)單，卻應(yīng)當(dāng) 指出，一旦編成計(jì)算機(jī)程序以后，它的使用反而是極其簡(jiǎn)單的。 為了用Kuhn算法解任何一個(gè)代數(shù)方程，只要把這個(gè)代數(shù)方程所對(duì) 應(yīng)的多項(xiàng)式的復(fù)系數(shù)組和計(jì)算的精度要求輸入機(jī)器。然后，算法 就會(huì)把該代數(shù)方程的全部

2、解一起算出。對(duì)于Kuhn算法，不存在初 值選擇以及其他一些使用方面的棘手問(wèn)題。這是一種具有很強(qiáng)的 大范圍收斂性保證的算法。另一方面，雖然算法本身不象一個(gè)簡(jiǎn) 單的迭代公式那么簡(jiǎn)單，但為了編制計(jì)算機(jī)程序，知道2.1和2.2 的內(nèi)容就足夠了。,86 - 4,2021/3/29,2.1剖分法與標(biāo)號(hào)法,設(shè)f(z)是復(fù)變量z的n階復(fù)系數(shù)的首一多項(xiàng)式，即 f(z)=zn+a1zn-1+.+an， 這里n是自然數(shù)，a1,.,an是復(fù)常數(shù)。如果復(fù)數(shù)滿足f()=0，就說(shuō)是多項(xiàng)式f的一個(gè)零點(diǎn)或代數(shù)方程f(z)=0的一個(gè)解。我們的算法就是要把f的零點(diǎn)找出來(lái)。 記復(fù)數(shù)zxiy平面為C，復(fù)數(shù)wuiv平面為C，則wf(z)

3、確定復(fù)平面之間的一個(gè)多項(xiàng)式映射f：CC。 為了在下一節(jié)敘述算法，我們先敘述半空間C-1,+)的一種剖分及由f導(dǎo)出的一種標(biāo)號(hào)法。 在C-1,+中，記Cd=Cd，d-1,0,1,2,.。給定剖分中心及初始格距h。,86 - 5,2021/3/29,2.1.1剖分法,Cd平面的剖分（簡(jiǎn)記作Td）剖分 T-1(,h)如圖2-1所示。剖分T-1(,h)中的一個(gè)三角形由和為偶數(shù)的一對(duì)整數(shù)(r,s)及一對(duì)(a,b)(1,0),(0,1),(-1,0),(0,-1)按以下方式完全確定：它的頂點(diǎn)的復(fù)數(shù)坐標(biāo)分別為： +(r+is)h； +(r+a)+i(s+b)h； +(r-b)+i(s+a)h。 稱剖分T-1(

4、,h)中三角形直徑之上界為T-1(,h)的剖分網(wǎng)徑。易知，T-1(,h)的剖分網(wǎng)徑為h。,圖2-1,86 - 6,2021/3/29,Cd平面的剖分,剖分Td(,h)，d=0,1,2,.,如圖2-2所示。Td(,h)中的一個(gè)三角形由和為奇數(shù)的一對(duì)整數(shù)(r,s)及一對(duì)(a,b)(1,0),(0,1), (-1,0),(0,-1)按以下方式完全確定：它的頂點(diǎn)的復(fù)數(shù)坐標(biāo)分別為： +(r+is)h2-d； +(r+a)+i(s+b)h2-d； +(r-b)+i(s+a)h2-d。 易知，同樣定義的Td(,h)，d=0,1,2,. 的剖分網(wǎng)徑為 h2-d。,圖2-2,86 - 7,2021/3/29,半

5、空間C-1,+的剖分T(,h) （簡(jiǎn)記作T）,按照平面的剖分，C-1的每一個(gè)正方形（由共有一斜邊的一對(duì)三角形組成），與C0的一個(gè)正方形（也由共有一斜邊的一對(duì)三角形組成）上下相對(duì)，而斜邊相錯(cuò)。C-1和C0之間每一個(gè)由上下相對(duì)的一對(duì)正方形所界定的正四棱柱，按圖2-3規(guī)則剖分成5個(gè)四面體。,圖2-3,86 - 8,2021/3/29,5個(gè)四面體,86 - 9,2021/3/29,半空間C-1,+的剖分T(,h) （簡(jiǎn)記作T）,按照平面的剖分，Cd（d0）的每一個(gè)正方形與Cd+1的四個(gè)正方形上下相對(duì)，界定Cd和Cd+1之間的一個(gè)正四棱柱。Cd和Cd+1之間每一個(gè)這樣的正四棱柱，按圖2-4的規(guī)則剖分成1

6、4個(gè)四面體。,圖2-4,86 - 10,2021/3/29,14個(gè)四面體,86 - 11,2021/3/29,半空間C-1,+的剖分T(,h),這樣一來(lái)，我們就得到半空間C-1,)的一個(gè)單純剖分T(,h)，簡(jiǎn)記作T。 注意，從各層Cd平面的剖分Td(,h)到半空間的剖分T(,h)，并沒(méi)有增加新的剖分格點(diǎn)。所有剖分Td(,h)，d=-1,0,1,2,.,的格點(diǎn)，組成剖分T(,h)的所有格點(diǎn)。格點(diǎn)都是頂點(diǎn)：三角形的頂點(diǎn)和四面體的頂點(diǎn)。這樣我們可以說(shuō)：T(,h)的所有剖分格點(diǎn)組成T(,h)頂點(diǎn)集V(T(,h)，簡(jiǎn)記作V(T)。 在下面敘述的算法里，主要牽涉到由剖分T中的四面體的界面三角形的頂點(diǎn)所組成

7、的三點(diǎn)組(z1,d1),(z2,d2),(z3,d3)，或簡(jiǎn)記作z1,z2,z3。今后所說(shuō)的三點(diǎn)組，都是這樣的三點(diǎn)組。,86 - 12,2021/3/29,引理2-1,引理2-1 設(shè)(z1,d1),(z2,d2),(z3,d3)是剖分T中的一個(gè)三點(diǎn)組，記d=mind1,d2,d3，有ddkd+1，k=1,2,3。 該引理由剖分法的定義直接得到。 在引理2-1的情況，我們說(shuō)三點(diǎn)組z1,z2,z3位于Cd和Cd+1之間。特別地，當(dāng)d1=d2=d3=d時(shí)，我們說(shuō)三點(diǎn)組位于Cd上。 設(shè)(z1,d1),(z2,d2),(z3,d3)是剖分T中的一個(gè)三點(diǎn)組。規(guī)定：三點(diǎn)組的直徑為 diam(z1,d1),(

8、z2,d2),(z3,d3)=max|z1-z2|,|z2-z3|,|z3-z1|， 也可簡(jiǎn)記作diamz1,z2,z3。,86 - 13,2021/3/29,引理2-2,引理2-2 設(shè)三點(diǎn)組z1,z2,z3位于Cd和Cd+1之間，則,證明：從圖2-3和圖2-4容易看出，位于Cd和Cd+1之間的所有可能的三點(diǎn)組的直徑不超過(guò) 。,所以 層數(shù)越高，三點(diǎn)組的直徑越小。,86 - 14,2021/3/29,2.1.2標(biāo)號(hào)法,86 - 15,2021/3/29,標(biāo)號(hào)的定義,定義2-1稱按下式確定的對(duì)應(yīng)l：C1,2,3為由多項(xiàng)式f確定的z平面C的標(biāo)號(hào)法：,定義2-2記f-1(z)=(z-)n；fd(z)=

9、f(z)，d=0,1,2,.。稱按下式確定的對(duì)應(yīng)l：V(T(,h)1,2,3為由多項(xiàng)式f導(dǎo)出的V(T(,h)的標(biāo)號(hào)法：,86 - 16,2021/3/29,標(biāo)號(hào)的圖示,圖2-5 標(biāo)號(hào)區(qū)域,86 - 17,2021/3/29,全標(biāo)三點(diǎn)組,定義2-3如果V(T(,h)的一個(gè)三點(diǎn)組z1,z2,z3滿足l(z1),l(z2),l(z3)=1,2，3，則稱它為完全標(biāo)號(hào)三點(diǎn)組，簡(jiǎn)稱全標(biāo)三點(diǎn)組。 為方便起見，今后，完全標(biāo)號(hào)三點(diǎn)組z1,z2,z3的記號(hào)均蘊(yùn)涵l(zk)=k，k=1,2,3。 全標(biāo)三點(diǎn)組的說(shuō)法本身，并沒(méi)有指明點(diǎn)的標(biāo)號(hào)是由(z-)n還是由f確定的。事實(shí)上，今后我們遇到的全標(biāo)三點(diǎn)組，其點(diǎn)的標(biāo)號(hào)可以都

10、由(z-)n確定，也可以都由f確定，還可以部分由(z-)n確定，部分由f確定。,86 - 18,2021/3/29,引理2-3,引理2-3設(shè)z1,z2,z3是標(biāo)號(hào)都由f確定的完全標(biāo)號(hào)三點(diǎn)組，并且|f(zk)-f(zl)|，k,l=1,2,3，那末 ，k=1,2,3。,證明：圖2-6是w平面上相應(yīng)于標(biāo)號(hào)1,2,3的三個(gè)區(qū)域。z的標(biāo)號(hào)由w=f(z)落在哪個(gè)扇形區(qū)域確定。按照所設(shè)，f(z1)必須在區(qū)域1，同時(shí)與區(qū)域2及區(qū)域3的距離均不起過(guò)。這樣，f(z1)必須落在圖2-6的菱形陰影區(qū)域內(nèi)，所以,同理，,。,86 - 19,2021/3/29,引理2-3的說(shuō)明,大家知道，多項(xiàng)式函數(shù)在平面的有限區(qū)域上是

11、一致連續(xù)的，假 如我們能夠找到直徑很小的標(biāo)號(hào)都由f確定的完全標(biāo)號(hào)三點(diǎn)組，那 么，這三點(diǎn)的象在w平面上的相互距離也很小。再由引理2-3，每 點(diǎn)的象與w平面的原點(diǎn)的距離也就很小了。當(dāng)這個(gè)距離足夠小時(shí)， 三點(diǎn)組的每一個(gè)點(diǎn)都可以足夠精確地作為f的一個(gè)數(shù)值零點(diǎn)。前面 已經(jīng)說(shuō)明，按照我們的剖分，層數(shù)越高時(shí)，三點(diǎn)組的直徑就越小。 這就啟發(fā)我們?cè)O(shè)計(jì)一種尋找完全標(biāo)號(hào)三點(diǎn)組的算法，使得一方面投 影到平面上看，計(jì)算不超過(guò)平面的一個(gè)有限區(qū)域，另一方面，計(jì)算 要不斷向上發(fā)展，達(dá)到越來(lái)越高的層次。找到這樣的算法，計(jì)算零 點(diǎn)的問(wèn)題也就解決了，即找到了多項(xiàng)式的根的近似值。,86 - 20,2021/3/29,2.2互補(bǔ)輪回算

12、法,互補(bǔ)輪回算法 進(jìn)口出口分析,86 - 21,2021/3/29,2.2.1互補(bǔ)輪回算法,在剖分為T-1(,h)的C-1平面上，用Qm(,h)（簡(jiǎn)記作Qm）表示頂點(diǎn)是+mh(1i)的方塊，這里m是一個(gè)正整數(shù)。也就是說(shuō)，Qm是以為中心的、半邊長(zhǎng)為mh的方塊，它的兩對(duì)對(duì)邊分別與z平面上的x軸和Y軸平行。三角形的一條邊稱為一條棱。方塊的邊界Qm(,h)（簡(jiǎn)記作Qm）取平面上的逆時(shí)針?lè)较驗(yàn)檎姆较颉２⑶?，?dāng)寫(z，z是Qm上的一條棱時(shí)，蘊(yùn)涵按Qm的正定向z是z的下一個(gè)點(diǎn)。T-1(,h)的每個(gè)三角形，按照其頂點(diǎn)面逆時(shí)針順序定向，并且，若寫z,z,z是T-1(,h)的一個(gè)三角形，蘊(yùn)涵其頂點(diǎn)順序給出三角形

13、的正向。 平面上兩點(diǎn)z,z對(duì)另一點(diǎn)z*的張角，是指射線z*z和z*z之間的不超過(guò)的夾角。也可以把它叫做平面上線段zz對(duì)另一點(diǎn)z*的張角.,86 - 22,2021/3/29,引理2-4,引理2-4設(shè) ，則Qm上按照正向次序，恰有n條標(biāo)號(hào)為(1,2)的棱（即始端標(biāo)號(hào)為1終端標(biāo)號(hào)為2的棱），而沒(méi)有標(biāo)號(hào)為(2,1)的棱。,圖2-7,86 - 23,2021/3/29,引理2-4的證明,證明：設(shè)z,z是Qm上的一條棱，z和z對(duì)的張角記作。由圖易知：,記為w=(z-)n和w=(z-)n對(duì)原點(diǎn)o的張角，則,按照Qm的構(gòu)造和冪函數(shù)w=(z-)n的性質(zhì)，Qm的象在w平面上恰好繞原點(diǎn)n圈。根據(jù)02/3可知，在Q

14、m上沿正向每走一步（相當(dāng)于一條棱），Qm的象的相應(yīng)部分在w平面按正向繞原點(diǎn)旋轉(zhuǎn)了一個(gè)小于2/3的正角。所以，在w平面上從w=(mh)n出發(fā)，Qm的象正好n次由相應(yīng)標(biāo)號(hào)1的區(qū)域一步進(jìn)人相應(yīng)標(biāo)號(hào)2的區(qū)域。回到z平面上，知Qm上正好有n條棱，始端標(biāo)號(hào)為1，終端標(biāo)號(hào)為2。 同樣，由于02/3，若l(z)=2，則l(z)=2或3，所以Qm上沒(méi)有標(biāo)號(hào)為(2,1)的棱。,86 - 24,2021/3/29,引理2-5,引理2-5設(shè) ，則在Qm(,h)外沒(méi)有T-1(,h)的標(biāo)號(hào)由(z-)n確定的完全標(biāo)號(hào)三角形。,圖2-8,證明：首先證明，若zz是Qm上或Qm外的一條棱，則zz對(duì)的張角小于2/3n。事實(shí)上，若z

15、z是平行于x軸或平行于y軸 的棱，這已由引理2-4的證明及 保證?，F(xiàn)只須考慮zz是T-1的三角形的斜邊的情況。根據(jù)Qm的構(gòu)造，不難證明張角最大的情況發(fā)生在靠近Qm的地方。由于對(duì)稱性，只要證明k是自然數(shù)，而 z=+h(m+1+ki)，z=+h(m+(k+1)i) 時(shí)，zz對(duì)的張角小于2/3n即可。,86 - 25,2021/3/29,對(duì)于整數(shù)k，不等式當(dāng)然成立。再注意/2，就有,現(xiàn)設(shè)z,z,z是T-1(,h)的在Qm外的一個(gè)三角形，則它的每條棱對(duì)的張角均小于 。記w=(z-)n，w=(z-)n，w=(z-)n，則w，w，w中每?jī)牲c(diǎn)對(duì)原點(diǎn)的張角均小于2/3。所以，按下述引理2-6，z,z,z不是標(biāo)

16、號(hào)由(z-)n確定的完全標(biāo)號(hào)三角形。,由圖2-8，,86 - 26,2021/3/29,引理2-6,引理2-6設(shè)z,z,z是z平面上的一個(gè)三點(diǎn)組，它們?cè)趙平面上的映射象分別為w,w,w（這里所說(shuō)的映射，對(duì)三點(diǎn)組的各點(diǎn)可以并不相同，可以是w=(z-)n，也可以是w=f(z)。那么，若w,w,w均不為0，且其中任兩點(diǎn)在w平面上對(duì)原點(diǎn)的張角均小于2/3，則z,z,z不是一個(gè)完全標(biāo)號(hào)三點(diǎn)組。,證明：若z,z,z是完全標(biāo)號(hào)點(diǎn)組，則不妨設(shè)l(z)=1，l(z)=2，l(z)=3。在w平面上，記按正向從ow到ow，從ow到ow，從ow到ow的小于2的角分別為,，那么，0，0，0并且+=2。 這時(shí)，若，則w,

17、w兩點(diǎn)對(duì)原點(diǎn)張角為2-，按題設(shè)，就有2-2/3，4/3，這與按標(biāo)號(hào)法4/3矛盾。同樣，若或亦引出矛盾。最后剩下,均不超過(guò)的情況，這時(shí),就是相應(yīng)各對(duì)點(diǎn)之間的張角，按題設(shè)均小于2/3，與+=2矛盾。,86 - 27,2021/3/29,圖2-9,86 - 28,2021/3/29,按照,確定方塊Qm(,h)，這里符號(hào)r表示不小,實(shí)數(shù)r的最小整數(shù)。算法就是要從Qm上每個(gè)標(biāo)號(hào)為(1,2)的棱出發(fā)，找尋完全標(biāo)號(hào)三點(diǎn)組。如果全標(biāo)三點(diǎn)組的標(biāo)號(hào)不全是由f確定的，則它未能提供足夠的關(guān)于f的零點(diǎn)位置的信息。但2.3將證明，按照下述算法，計(jì)算將在越來(lái)越高的層次上面進(jìn)行，而在高層（事實(shí)上在除C-1外的各層），標(biāo)號(hào)均由

18、f確定。這樣，按照引理2-3，我們可按任何預(yù)先給定的精度要求把f的零點(diǎn)算出來(lái)。,86 - 29,2021/3/29,Kuhn算法,算法2-1依次從Qm的第j個(gè)標(biāo)號(hào)為(1,2)的棱z1,z2出發(fā)，j=1,2,n，這n條棱是容易找到的。 步1（二維搜索）若z3空白，對(duì)于(1,2)棱，存在C-1平面上唯一的頂點(diǎn)z使得z1,z2,z是T-1(,h)的一個(gè)正向三角形。計(jì)算z的標(biāo)號(hào)l=l(z)，令zl=z，回到步1（所以，若l=3，則升維，從二維搜索進(jìn)入三維搜索）。 步2（降維：從三維搜索回到二維搜索）若z1,z,z2是T-1(,h)的一個(gè)負(fù)向全標(biāo)三角形，取消z3，成為一條(1,2)棱，轉(zhuǎn)步1。 步3（三

19、維搜索）在T(,h)中存在唯一的頂點(diǎn)z，使得z1,z2,z,z是T(,h)的一個(gè)四面體，且頂點(diǎn)順序給出空間的右手螺旋方向。計(jì)算ll(z)，令zl=z，轉(zhuǎn)步2。,86 - 30,2021/3/29,Kuhn算法說(shuō)明,按照算法2-1，我們已經(jīng)可以編制Kuhn算法的計(jì)算機(jī)程序了， 而前面的知識(shí)，只有剖分法和標(biāo)號(hào)法是這里要用的。在步1，按照 剖分法確定z，按照標(biāo)號(hào)法通過(guò)計(jì)算(z-)n得到l(z)。在步3，按照 剖分法確定z，按照標(biāo)號(hào)法通過(guò)冪函數(shù)計(jì)算(z-)n（當(dāng)d=-1）或多 項(xiàng)式計(jì)算f(z)（當(dāng)d0）得到l(z)。算出l=l(z)以后，令zl=z的做 法，是一個(gè)同標(biāo)號(hào)替換的做法：用z（新的點(diǎn)）取代原

20、有的與z標(biāo) 號(hào)相同的頂點(diǎn)（舊的點(diǎn)）。這種做法，叫做互補(bǔ)輪回算法。,86 - 31,2021/3/29,2.2.2進(jìn)口出口分析,我們分析一下算法2-1中的各步。 步1從(1,2)棱出發(fā)找到z，這時(shí)我們說(shuō)計(jì)算進(jìn)入三角形z1,z2,z。步3從三角形z1,z2, z3出發(fā)找到z，我們說(shuō)計(jì)算進(jìn)入四面體z1,z2,z3,z。 在步1的情況，如果l(z)=1或2，得到的還是一個(gè)標(biāo)號(hào)(1,2)的棱，下一次還是執(zhí)行步1，計(jì)算將進(jìn)入另一個(gè)三角形。從本三角形內(nèi)部看來(lái)，三角形邊界按逆時(shí)針定向，我們很自然地把正向(1,2)棱稱作計(jì)算的進(jìn)口，負(fù)向(2,1)棱則是計(jì)算的出口。如果l(z)=3，得到正向全標(biāo)三角形z1,z2,

21、 z3，計(jì)算將離開三角形而進(jìn)入四面體。這樣，還應(yīng)該把正向全標(biāo)三角形叫做它自己的出口。,86 - 32,2021/3/29,進(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是該三角形的出口。,86 - 33,2021/3/29,進(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)如 何，都

22、正好和某一個(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)稱為門,86 - 34,2021/3/29,2.2.2進(jìn)口出口分析圖示,86 - 35,2021/3/29,引理2-7,引理2-7對(duì)于頂點(diǎn)在集合1,2,3中取標(biāo)號(hào)的一個(gè)標(biāo)號(hào)三角形或四面體，或者它沒(méi)有門，或者它正好有一對(duì)門，一個(gè)是進(jìn)口，一個(gè)是出口。,86 - 36,2021/3/29,引理2-7的證明,證明：按照門的定義，對(duì)于標(biāo)號(hào)的三角形，如果它缺少標(biāo)號(hào)1或 2

23、，則它沒(méi)有門。對(duì)于標(biāo)號(hào)1，2具備的情況，若沒(méi)有標(biāo)號(hào)3，則(1,2) 棱是進(jìn)口，(2,1)棱是出口，另一棱是(1,l)或(2,2)不是門，所以正 好是一對(duì)門。若三角形全標(biāo)，在負(fù)向的情況，z1,z3,z2是進(jìn)口， (2,1)棱是出口；在正向的情況下，(1,2)棱是進(jìn)口，z1,z2,z3是出 口。不論正向負(fù)向，另兩棱均有標(biāo)號(hào)3，不是門。所以也正好是一對(duì) 門。 對(duì)于標(biāo)號(hào)的四面體，如果它缺少任何一個(gè)標(biāo)號(hào)，則它沒(méi)有全標(biāo)三 角形的面，是一個(gè)無(wú)門的四面體。若四個(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)棱撐開

24、的 三角形。這時(shí)，站在四面體內(nèi)部，若一個(gè)全標(biāo)三角形在正面，則另一 個(gè)在背后。若一個(gè)是正向全標(biāo)三角形，則另一個(gè)是反向全標(biāo)三角形； 反之亦然。,86 - 37,2021/3/29,引理2-8,引理2-8按照算法2-1，從Qm的每個(gè)(1,2)棱開始的計(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è)四面體。 把有門的三角形和四面體看作是“人”，兩個(gè)看作是一雙手。這樣，Kuhn算法的曲線都是由許多人手拉手連起來(lái)的。有了這個(gè)比喻，就容易理解，如果曲

25、線會(huì)分叉或打圈，就一定有一些三只手的“人”，與前面證明的每“人”正好有一雙手矛盾。,86 - 38,2021/3/29,2.3Kuhn算法的收斂性（一）,這一節(jié)我們將證明，按照算法2-1從Qm上每個(gè)標(biāo)號(hào)(1,2)棱開始計(jì)算，都收斂到多項(xiàng)式f的的一個(gè)零點(diǎn)。,86 - 39,2021/3/29,計(jì)算的單純形序列,定義2-4對(duì)于整數(shù)j，1jn，順次記從Qm上第j條(1,2)棱 開始的計(jì)算所通過(guò)的三角形（二維搜索時(shí)）或四面休（三維搜索時(shí)） 為j1,j2,.,jk,.，稱它為第j個(gè)計(jì)算的單純形序列。 按照這種記法，jk可能是一個(gè)三角形，也可能是一個(gè)四面體。 我們知道，空間不共線的三個(gè)點(diǎn)的凸包是2維單純形

26、，三角形就是2維 單純形；空間不共面的四個(gè)點(diǎn)的凸包是3維單純形，四面體就是3維單 純形。采用上述記法，在需要區(qū)別的時(shí)候，我們用2jk表示它是一個(gè) 2維單純形，即三角形；或?qū)懽鱠im(jk)=2，即jk的維數(shù)為2，表明 jk是一個(gè)2維單純形，即三角形。同樣，表示3jk維單純形，即四面 體；dim(jk)=3表明jk是一個(gè)3維單純形，即四面體。,86 - 40,2021/3/29,計(jì)算的點(diǎn)序列,定義2-5對(duì)于整數(shù)j，1jn，記(zj1,dj1)為j1的 不在Qm的頂點(diǎn)，對(duì)于k2，當(dāng)dim(jk)dim(j,k-1)時(shí)， 記(zjk,djk)為jk的不屬于j,k-1的頂點(diǎn)，當(dāng)dim(jk) dim(

27、j,k-1)時(shí)，記(zjk,djk)=(zj,k-1,dj,k-1)。這樣得到的序列 (zjk,djk)|k=1,2,.稱為第j個(gè)計(jì)算的點(diǎn)序列。如果我們只關(guān) 注該序列在z平面的投影，zjk也稱為第j個(gè)計(jì)算的點(diǎn)序 列。,86 - 41,2021/3/29,定義的說(shuō)明,注意，計(jì)算的單純形序列中的單純形的維數(shù)只可能是2或3，所以dim(jk)dim(j,k-1)的情況不可能連續(xù)發(fā)生。下面我們還將知道（見推論2-1），dim(jk)dim(j,k-1)的情況，只能發(fā)生有限次，即對(duì)于每個(gè)計(jì)算序列，步2只能執(zhí)行有限多次。 下面我們先討論一下算法的性狀。,86 - 42,2021/3/29,引理2-9,引理

28、2-9若dim(jk)=2，則jkQm。 這就是說(shuō)，二維搜索不會(huì)跑到Qm外面去。 證明：若不然，存在j,k使dim(jk)=2，但jkQm。按照算法，二維搜索只能在C-1平面上發(fā)生，即jkC-1，不妨設(shè)jk是計(jì)算的單純形序列j1,j2,.中頭一個(gè)位于Qm外的三角形。這時(shí)，若dim(j,k-1)=2，則j,k-1Qm，所以j,k-1和jk有一條公共棱在Qm上，具有標(biāo)號(hào)1和2。若該棱是(1,2)棱，則它是內(nèi)三角形j,k-1的進(jìn)口，與由j,k-1到j(luò)k的計(jì)算順序矛盾；若該棱是(2,1)棱，則與引理2-1矛盾。 若dim(j,k-1)=3，按照算法2-1（步2），j,k是Qm外一個(gè)z1,z3,z2全標(biāo)

29、三角形，與引理2-5矛盾。,86 - 43,2021/3/29,換一個(gè)角度分析進(jìn)口出口,上節(jié)已證明，對(duì)于T-1中的三角形或T中的四面體，或者它沒(méi)有 門，或者它正好有一對(duì)門，一個(gè)是進(jìn)口，一個(gè)是出口。但是，門之 作為進(jìn)口或作為出口，是相對(duì)于三角形或四面體而言的。例如圖 2-12（字母表示頂點(diǎn)，腳標(biāo)表示該頂點(diǎn)的標(biāo)號(hào)），B1C2是一個(gè)門， 對(duì)于三角形BAC來(lái)說(shuō)，它是出口，對(duì)于三角形BCD來(lái)說(shuō)，它是進(jìn) 口。又如B1C2D3這個(gè)門，對(duì)于三角形BCD本身來(lái)說(shuō)，它是出口，從 二維搜索轉(zhuǎn)入三維搜索的出口；對(duì)于四面體BCDE來(lái)說(shuō)，它是進(jìn) 口，從二維搜索進(jìn)入三維搜索的進(jìn)口。再如B1E2D3這個(gè)門，是 BCDE的出口

30、，又是BEDF的進(jìn)口。 如果一個(gè)門是某個(gè)三角形或四面體的出口，我們稱該三角形或 四面體為這個(gè)門的上方單純形；如果一個(gè)門是某個(gè)三角形或四面體 的進(jìn)口，我們稱該三角形或四面體為這個(gè)門的下方單純形。,86 - 44,2021/3/29,圖2-12,86 - 45,2021/3/29,引理2-10,引理2-10對(duì)于任何一個(gè)不在Qm上的門，它的上方單純形和下方單純形都是唯一存在的。,對(duì)于Qm上的門，它就是我們算法的起始棱，相應(yīng)的結(jié)論是：它的下方單純形是唯一存在的。,86 - 46,2021/3/29,引理2-10的證明,證明：按照門的定義，它或者是T-1(,h)中的標(biāo)號(hào)為1和2的棱，或者若它是 T-1(

31、,h)中的標(biāo)號(hào)為1和2的棱，且不在Qm上，由引理2-9可知，它在內(nèi)部，根據(jù) 剖分T-1(,h)的定義，任何一條棱是且僅是兩個(gè)標(biāo)號(hào)三角形的一條公共邊，因此這 兩個(gè)標(biāo)號(hào)三角形中一個(gè)門的上方單純形，另一個(gè)是該門的下方單純形，且唯一。 若它是T(,h)中的全標(biāo)三角形。當(dāng)它是T-1(,h)中的正向全標(biāo)三角形z1,z2,z3 時(shí)，它的上方單純形是T(,h)中以三角形z1z2z3為一個(gè)面的四面體，根據(jù)剖分的定 義，這樣的四面體是唯一的，它的下方單純形就是它本身。當(dāng)它是T-1(,h)中的負(fù) 向全標(biāo)三角形z1,z3,z2時(shí)，它的上方單純形是它本身，它的下方單純形是T(,h)中 以三角形z1z3z2為一個(gè)面的四面

32、體，這樣的四面體也是唯一的。當(dāng)它不在T-1(,h) 中時(shí)，由于任何一個(gè)不在T-1(,h)中三角形是且僅是兩個(gè)四面體的一個(gè)公共面，因 此這兩個(gè)四面體一個(gè)是門的上方單純形，另一個(gè)是該門的下方單純形。,86 - 47,2021/3/29,引理2-11,引理2-11若(j,k)(i,l)，則jkil。,這就是說(shuō)，在剖分并標(biāo)號(hào)的半空間中，T-1的每個(gè)三角形和T的每個(gè)四面體，都頂多只允許計(jì)算通過(guò)一次。,86 - 48,2021/3/29,引理2-11的證明,證明：首先注意，jk=il，k1，l1蘊(yùn)涵j,k-1=i,l-1。這只 要對(duì)作為=jk=il的進(jìn)口的門運(yùn)用引理2-10：這個(gè)門的上方單純形 唯一，所以

33、j,k-1=i,l-1。 若引理不真：jk=il。不妨設(shè)kl。由jk=il，k1，l1蘊(yùn) 涵j,k-1=i,l-1，可得j,1=i,l-k+1?？紤]作為j,1的進(jìn)口的門。按照算 法，它是Qm上第j條z1,z2棱，如果l-k+11，即如果lk，則i,l-k 是以該棱為出口的一個(gè)三角形，dim(i,l-k)=2，但i,l-kQm，與引理 2-9矛盾。所以l=k，jl=il。這時(shí)，按照引理2-7，對(duì)于同一個(gè)單 純形jl=il，它的進(jìn)口是唯一的，即作為jl進(jìn)口的第j個(gè)(1,2)棱就是 作為il進(jìn)口的第i個(gè)(1,2)棱，所以i=j。這與所設(shè)(j,k)(i,l)矛盾。,86 - 49,2021/3/29,

34、推論2-1,推論2-1對(duì)于每個(gè)j，1jn，存在Kj使得kKj時(shí)， dim(jk)=3。,即：每個(gè)計(jì)算的單純形序列除了開始的有限一段外，都由三 維單純形四面體組成。所以三維搜索是本質(zhì)的。,證明：二維搜索只能在Qm內(nèi)進(jìn)行，Qm內(nèi)三角形數(shù)目有限(8m2 個(gè))，每個(gè)三角形頂多允許計(jì)算通過(guò)一次。,注意，我們說(shuō)每個(gè)三角形或每個(gè)四面休頂多允許計(jì)算通過(guò)一 次，并不是說(shuō)每個(gè)頂點(diǎn)頂多只允許計(jì)算一次。例如在圖2-12中， 若A2,B1,C2,D3依舊，但E的標(biāo)號(hào)不是2而是3，那么下一次就應(yīng)當(dāng)計(jì) 算A而不是F，A已被重復(fù)計(jì)算。所以，由(j,k)(i,l)不能推出 (zjk,djk)(zil,dil)。,86 - 50

35、,2021/3/29,引理2-12,引理2-12存在（依賴于,h和多項(xiàng)式f的） R0，使得C(R)-1, +)外沒(méi)有完全標(biāo)號(hào)三 角形，這里C(R)=z|z|R。,這就是說(shuō)，三維搜索不會(huì)跑到 C(R)-1, +)外面去。,86 - 51,2021/3/29,引理2-12的證明,證明：取,而 。由于r=R-|0，在C(R)=z|z|R外改寫,其中 。若z,z是剖分T(,h)中位于C(R)-1， +)外的任一三點(diǎn)組的任意兩點(diǎn)，記它們的映射象為w,w，那么，不管所論的點(diǎn)的映射是w=(z-)n或w=f(z)，都是w0，w0。并且，注意線段zz整個(gè)在C(R)-1,+)外，所以,86 - 52,2021/3

36、/29,。,注意，當(dāng)z,z均由w=(z-)n標(biāo)號(hào)時(shí)，不等式右端第二項(xiàng)和第三項(xiàng)均可去掉；當(dāng)z,z之一由w=(z-)n標(biāo)號(hào)，而另一個(gè)由w=f(z)標(biāo)號(hào)時(shí)，不等式右端第二頂和第三項(xiàng)的系數(shù)2均可去掉。但是不論在任何情況，上述形式的不等式均成立。因此，,這樣，據(jù)引理2-6，T(,h)位于C(R)-1,+外的所有三點(diǎn)組均非完全標(biāo)號(hào)三點(diǎn)組。,86 - 53,2021/3/29,圖2-13,86 - 54,2021/3/29,定理2-1,定理2-1投影到復(fù)平面上看，每個(gè)計(jì)算的點(diǎn)序列都有聚點(diǎn)。 證明：對(duì)于每個(gè)整數(shù)j，1jn，zjk是一個(gè)序列。按照該序列的構(gòu)造（定義2-5），注意QmC(R)，二維搜索不超出Qm，

37、三維搜索不超出C(R)-1,+)，可知zjkC(R)。但C(R)作為平面有界閉區(qū)域是緊致的，所以無(wú)窮序列zjk在C(R)中必有聚點(diǎn)。,86 - 55,2021/3/29,定理2-2,定理2-2設(shè)z*是計(jì)算的點(diǎn)序列zjk的一個(gè)聚點(diǎn)，則f(z*)=0。 即：計(jì)算的點(diǎn)序列的聚點(diǎn)，都是多項(xiàng)式的零點(diǎn)。,86 - 56,2021/3/29,定理2-2的證明,證明：考慮計(jì)算的單純形序列jk，這是一個(gè)沒(méi)有重復(fù)的無(wú)窮的 單純形序列（引理2-11和引理2-8）。按照T(,h)的構(gòu)造，QmC-1內(nèi)的 三角形數(shù)目有限，以C(R)為底的大圓柱內(nèi)位于任何有限高度以下的四 面體數(shù)目有限，但jk只能由不重復(fù)的Qm內(nèi)的三角形和

38、C(R) -1,+)內(nèi)的四面體組成，所以對(duì)于任意正整數(shù)d，存在k(d)，使得當(dāng) kk(d)時(shí)，jk位于Cd平面以上。而計(jì)算的點(diǎn)序列zjk,djk是由計(jì)算的 單純形序列jk按定義2-5的方式確定的。所以，對(duì)任何正整數(shù)d，存 在k(d)，使得當(dāng)kk(d)時(shí)，djkd。,由于上面的討論，不妨設(shè)此子序列具有d(k)k+1的性質(zhì)。,z*是zjk的聚點(diǎn)，所以存在zjk,djk的子序列，它在z平面上的投影 收斂到z*。記此子序列為z(k),d(k)，則有,86 - 57,2021/3/29,事實(shí)上，取,注意，為了這里證明敘述的方便，子序列的寫法與定義2-5不同，號(hào)碼j也省略了。 現(xiàn)在，為了證明f(z*)=0

39、，利用多項(xiàng)式f的連續(xù)性，只須證明任給0，存在正整數(shù)K，使得當(dāng)kK時(shí)有|f(z(k)|便可。,即可，其中,M=max1,|a1|,.,|an-1|，R如引理2-12所述。這是因?yàn)槿鬹K，設(shè)z1,z2,z3或z1,z3,z2是z(k)所在的一個(gè)位于CK以上的完全標(biāo)號(hào)三點(diǎn)組，那么,86 - 58,2021/3/29,所以，據(jù)引理2-3，因z(k)是該三點(diǎn)組之一點(diǎn)， 。,同理，,86 - 59,2021/3/29,代數(shù)基本定理,直到現(xiàn)在為止，我們沒(méi)有預(yù)先假定多項(xiàng)式f的零點(diǎn)的存在。但是我們構(gòu)造了算法，證明了這個(gè)算法所產(chǎn)生的每個(gè)計(jì)算的點(diǎn)序列在復(fù)平面上都有聚點(diǎn)，而這種聚點(diǎn)都是多項(xiàng)式的零點(diǎn)。這樣，我們也就構(gòu)造

40、性地證明了以下定理。,定理2-3設(shè)f(z)=zn+a1zn-1+.+an，其中n為自然數(shù)，z為復(fù)變量，a1，.，an為復(fù)常數(shù)，則f(z)必有零點(diǎn)。,至此，我們可以把多項(xiàng)式寫成乘積的形式，并敘述零點(diǎn)的重?cái)?shù)的概念。這就是下面的定義。,定義2-6設(shè)f(z)=zn+a1zn-1+.+an=(z-1)k1.(z-j)kj，j及k1,.,kj均為正整數(shù)，1,.,j互不相同，則稱ki為f的零點(diǎn)i的重?cái)?shù)，i=1,.,j。特別地，若ki=1,稱i為f的單零點(diǎn)；若ki1，稱i為f的重零點(diǎn)，或ki重零點(diǎn)。,86 - 60,2021/3/29,2.4Kuhn算法的收斂性（二）,這一節(jié)我們將進(jìn)一步證明，每個(gè)計(jì)算的點(diǎn)序列

41、只收斂到多項(xiàng)式的一個(gè)零點(diǎn)；從Qm上n個(gè)標(biāo)號(hào)為(1,2)的棱開始的n個(gè)計(jì)算的點(diǎn)序列正好收斂到多項(xiàng)式的全部n個(gè)零點(diǎn)。,86 - 61,2021/3/29,定理2-4,定理2-4每個(gè)計(jì)算的點(diǎn)序列都收斂到多項(xiàng)式的一個(gè)零點(diǎn)。,86 - 62,2021/3/29,定理2-4的證明,86 - 63,2021/3/29,不妨設(shè)K足夠大，使得當(dāng)kK時(shí)， ，計(jì)算點(diǎn)序列的投影步長(zhǎng)（在相應(yīng)高度的三點(diǎn)組的投影直徑）不超過(guò)r。再不妨設(shè)kk*，則序列Zjk從k=k*到k=k一段與C之交非空，因?yàn)樗圆怀^(guò)r的步長(zhǎng)，不可能從距z*小于r的地方一步跨到距z小于r的地方。 由于K的任意性，可知zjkC也是一個(gè)無(wú)窮序列，而C是平面

42、有界閉集，由它的緊致性，存在zC是zjkC的聚點(diǎn)，當(dāng)然，z也是zjk的聚點(diǎn)，且zz，zz*。,再挖去分別以z,z,z*為中心的半徑 的三個(gè)開圓重復(fù)上述討論，又可得第4個(gè)聚點(diǎn)。這樣做下去，zjk在C(R)有無(wú)窮多個(gè)聚點(diǎn)，于是據(jù)定理2-2，多項(xiàng)式f在C(R)有無(wú)窮多個(gè)零點(diǎn)。這樣一來(lái)，必須f(z)0。這與所設(shè)f是階數(shù)n大于0的首一多項(xiàng)式矛盾。,86 - 64,2021/3/29,組合的Stokes定理,下面，我們先對(duì)沒(méi)有重零點(diǎn)的情況證明n個(gè)計(jì)算的點(diǎn)序列正好收斂到多項(xiàng)式的n個(gè)零點(diǎn)，然后再推廣到一般情況。為此要作若干準(zhǔn)備。 定理2-5設(shè)Q是平面有界區(qū)域（連通或不連通），剖分成為有限個(gè)具有正的定向的三角形

43、，各頂點(diǎn)的標(biāo)號(hào)為1或2或3。稱Q上的(1,2)標(biāo)號(hào)棱和Q內(nèi)的標(biāo)號(hào)為(1,3,2)的三角形為Q的進(jìn)口（源）；Q上的(2,1)標(biāo)號(hào)棱和Q內(nèi)的標(biāo)號(hào)為(1,2,3)的三角形為Q的出口（淵）。那么，對(duì)于Q，進(jìn)口的數(shù)目和出口的數(shù)目相等。,86 - 65,2021/3/29,組合的Stokes定理的證明,證明：據(jù)所設(shè)，Q內(nèi)三角形數(shù)目及Q上棱的數(shù)目都有限，所以進(jìn)口的數(shù)目和出口的數(shù)目當(dāng)然有限， 對(duì)于每個(gè)進(jìn)口，若它是Q上的(1,2)標(biāo)號(hào)棱，則由它出發(fā)執(zhí)行算法2-1中的步1；若它是Q內(nèi)的標(biāo)號(hào)(1,3,2)的三角形，則取消標(biāo)號(hào)為3的頂點(diǎn)后，開始執(zhí)行步1。這樣做下去，或者找到Q內(nèi)一個(gè)標(biāo)號(hào)(1,2,3)三角形；或者互補(bǔ)輪

44、迴過(guò)程將超出Q，在通過(guò)Q超出Q的地方將給出一個(gè)(2,1)標(biāo)號(hào)棱。所以，從每個(gè)進(jìn)口出發(fā)的步1互補(bǔ)輪迴過(guò)程，都以找到一個(gè)出口結(jié)束。 由于引理2-7及引理2-10，互補(bǔ)輪迴過(guò)程按進(jìn)退兩個(gè)方向都是唯一決定的。所以，對(duì)于每個(gè)出口，反方向執(zhí)行步1（對(duì)(1,2,3)標(biāo)號(hào)三角形要先取消標(biāo)號(hào)為3的頂點(diǎn)），同樣必終止于一個(gè)進(jìn)口，這就完成了定理的證明。,86 - 66,2021/3/29,圖2-15,86 - 67,2021/3/29,組合的Stokes定理的說(shuō)明,注意，定理2-5中的Q比算法中的Qm一般得多，我們可以對(duì)任何剖分為三角形的平面有限區(qū)域進(jìn)行觀察，不管各頂點(diǎn)怎樣隨機(jī)地得到1或2或3的號(hào)碼，總是進(jìn)口等于出

45、口。圖2-15是一個(gè)例子，其中表示進(jìn)口，表示出口。注意，對(duì)于組合的Stokes定理，平面上的曲邊三角形也是允許的。 由定理2-1，定理2-2，以及定理2-3，已經(jīng)可以將多項(xiàng)式改寫為：,這里1,2,.,n是代數(shù)基本定理保證的多項(xiàng)式f的n個(gè)精確零點(diǎn)。,86 - 68,2021/3/29,引理2-13,引理2-13設(shè)j是多項(xiàng)式f(z)的一個(gè)單零點(diǎn)，1jn。則頂多只有一個(gè)計(jì)算的點(diǎn)序列收斂到j(luò)。,86 - 69,2021/3/29,附近， f近似于一個(gè)線性函數(shù)，近似于復(fù)平面的以z=j為中心的乘以常數(shù)因子,w=f(z)計(jì)算|argf(z)|所引起的誤差小于/24；用,引理2-13的證明,證明：在z=j附近

46、，,。即在z=j,的旋轉(zhuǎn)。所以，存在以z=j為中心的半徑足夠,小的圓域，對(duì)這個(gè)圓域內(nèi)的任兩點(diǎn)，用,代替,代替w=f(z)計(jì)算|argf(z)/f(z)|引起的誤,差小于/12（下面第三章引理3-1將具體給出小圓域半徑的一個(gè)估計(jì)）。,86 - 70,2021/3/29,在剖分為Td的Cd平面上，設(shè)z=j所在的一個(gè)三角形是，與有共同頂點(diǎn)的所有三角形的點(diǎn)集并的凸包為T()。當(dāng)d足夠大因而剖分足夠細(xì)時(shí)，總可以使得T()整個(gè)位于上述小圓域內(nèi)。我們要證明，小圓域內(nèi)有且只有一個(gè)完全標(biāo)號(hào)三角形，且其定向?yàn)檎?記T()的邊界為T，易知T的每一條棱對(duì)的每一點(diǎn)的張角都在,之間。所以T的,的象在w平面上按正向繞原點(diǎn)

47、，每,一步(相當(dāng)于T的一條棱)所轉(zhuǎn)過(guò)的角在,之間。這樣，T的w=f(z),象在w平面上按正向繞原點(diǎn)，每一步所轉(zhuǎn)過(guò)的角在,和,之間。所以，按照標(biāo)號(hào)法，T上正好有一個(gè)標(biāo)號(hào)(1,2)的,棱，沒(méi)有標(biāo)號(hào)(2,1)的棱。根據(jù)組合的Stokes定理，T()內(nèi)正向全標(biāo)形比負(fù)向全標(biāo)形正好多一個(gè)。,86 - 71,2021/3/29,下面證明小圓域內(nèi)沒(méi)有負(fù)向全標(biāo)形。 考慮w平面上決定標(biāo)號(hào)的三個(gè)頂角各為 的扇形在z平面上以z=j為中心的小圓域內(nèi)關(guān)于 的逆象。我們有圖2-17，其中(1)表示標(biāo)號(hào)肯定為1的扇形區(qū)域，(1,2)表示標(biāo)號(hào)可能是1或2的扇形區(qū)域，等等。顯然，的頂角為，不包括邊界；的頂角為。,86 - 72,

48、2021/3/29,圖2-16,圖2-17,86 - 73,2021/3/29,設(shè)z1,z2,z3是圓域內(nèi)一個(gè)負(fù)向全標(biāo)三角形。若至少有兩點(diǎn)在中（圖2-17中A,B,C三種情形），則必有一角大于，與剖分矛盾；在只有一點(diǎn)在的情形，若一點(diǎn)在相鄰的，另一點(diǎn)在對(duì)面的（圖2-17中的D），則必有一內(nèi)角大于；若另兩點(diǎn)分別在相鄰的兩個(gè)中（圖2-17中的E），則必有一內(nèi)角大于，都與剖分矛盾；在三點(diǎn)都不在的情形，如果三點(diǎn)在不同的，則它不是負(fù)向全標(biāo)形。所以必有兩點(diǎn)在同一。,綜上所述，只剩下兩點(diǎn)在同一，第三點(diǎn)在與此不相鄰的區(qū)域的情形需要討論。不妨設(shè)z2,z3(2,3)，z1(3,1)(1)(1,2)。,86 - 74

49、,2021/3/29,若jz1z3z2，則z1，與剖分矛盾。所以jz1z3z2。由對(duì)稱性，不妨設(shè)z2,j在z1z3兩側(cè)。z1z3與(3,1)(1)(1,2)的邊界的交點(diǎn)為z?？紤]沿通過(guò)j的射線，令z3向j移動(dòng)，z2背向j移動(dòng)（圖2-18），這是一個(gè)使z2zz3增大的過(guò)程，顯然有上界。所以z1z2zz3。若z3=，則z2z3=z1z3jz3，所以jz2z3，zz3j- ，這就引出 zjz3+jz3z 的矛盾。若z2=，則z2z3=z1z2z2j，z2z3jz2jz3 ，引出jz2z3的矛盾。,86 - 75,2021/3/29,所以，圓域內(nèi)沒(méi)有負(fù)向全標(biāo)等腰直角三角形。這樣，據(jù)組合的Stokes定

50、理，T()內(nèi)有且只有一個(gè)全標(biāo)三角形，其定向?yàn)檎?再設(shè)zz”是圓域內(nèi)T()外的任一棱，易知zz”對(duì)j（在內(nèi))的張角不超過(guò)，所以f(z)，f(z”)對(duì)原點(diǎn)的張角不超過(guò) 。因此，據(jù)引理2-6，圓域內(nèi)T()外沒(méi)有全標(biāo)三角形。 至此，我們證明了，當(dāng)d足夠大因而剖分足夠細(xì)時(shí)，以z=j為中心的上述小圓域內(nèi)總是有且只有一個(gè)全標(biāo)三角形，并且它是正向全標(biāo)三角形 這樣，按照算法，頂多只有一個(gè)計(jì)算的單純形序列能無(wú)限接近j。所以，頂多只有一個(gè)計(jì)算的點(diǎn)序列收斂到j(luò)。,86 - 76,2021/3/29,引理2-13的說(shuō)明,注意，引理的證明排除了小圓域內(nèi)有任何負(fù)向完全標(biāo)號(hào)的等腰直角三角形的可能性，即使該三角形不是剖分中的

51、三角形。 最后，還需要有關(guān)于多項(xiàng)式零點(diǎn)是多項(xiàng)式系數(shù)的連續(xù)函數(shù)的下述引理。,86 - 77,2021/3/29,引理2-14,引理2-14首一多項(xiàng)式的零點(diǎn)，是多項(xiàng)式系數(shù)的連續(xù)函數(shù)。,86 - 78,2021/3/29,證明：回憶定義2-6，設(shè)f(z)=zn+a1zn-1+.+an=(z-1)k1.(z-j)kj，1,.,j互不相同，j及k1,.,kj均為正整數(shù)。當(dāng)然，k1+.+kj=n。 對(duì)于任何m，1mj，可取0，使得在z|z-m|內(nèi)m是唯一的零點(diǎn)。根據(jù)復(fù)變函數(shù)論中的幅角原理，有,引理2-14的證明,注意上式左端是整數(shù)，而右端是系數(shù)a1,.,an的連續(xù)函數(shù)。所以當(dāng)a1,.,an變化很小時(shí)，上述積分保持不變，也就是說(shuō)當(dāng)a1,.,an變化很小時(shí)，z|z-m|內(nèi)多項(xiàng)式的零點(diǎn)數(shù)目（按重?cái)?shù)計(jì)算）保持km不變。,最后，根據(jù)足夠小的任意性，就證明了首一多項(xiàng)式的零點(diǎn)是它的系數(shù)的連續(xù)函數(shù)。,86 - 79,2021/3/29,引理2-15,引理自然可以推廣到一般多項(xiàng)式的情況：設(shè)f(