版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
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)檎姆较颉2⑶?,?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(
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 松花粉膳食補(bǔ)充劑相關(guān)項(xiàng)目實(shí)施方案
- 各個(gè)班組安全培訓(xùn)試題B卷附答案
- 斜口虎鉗手工具項(xiàng)目可行性實(shí)施報(bào)告
- 電子課程設(shè)計(jì)家用風(fēng)扇
- 機(jī)械cadcam底板課程設(shè)計(jì)
- 深基坑課程設(shè)計(jì)體會(huì)
- 電子課程設(shè)計(jì)電子秤
- 2024年物流機(jī)器人項(xiàng)目立項(xiàng)申請(qǐng)報(bào)告模范
- 2024年懸掛式離子風(fēng)機(jī)項(xiàng)目規(guī)劃申請(qǐng)報(bào)告模范
- 和服襯領(lǐng)半領(lǐng)相關(guān)項(xiàng)目實(shí)施方案
- 2024時(shí)事政治考試題庫(kù)(100題)
- 2024年新人教版七年級(jí)上冊(cè)英語(yǔ)全冊(cè)教學(xué)課件(新版教材)
- 2024年秋新北師大版七年級(jí)上冊(cè)數(shù)學(xué)教學(xué)課件 4.1.1 線段、射線、直線
- 商用插畫授權(quán)合同范本
- 2024至2030年中國(guó)輔助生殖行業(yè)發(fā)展監(jiān)測(cè)及投資戰(zhàn)略規(guī)劃報(bào)告
- 第二十四節(jié) 潔凈手術(shù)室凈化空調(diào)工程方案及施工方法
- 北師大版一年級(jí)六認(rèn)識(shí)圖形 單元整體作業(yè)設(shè)計(jì)
- (正式版)SH∕T 3548-2024 石油化工涂料防腐蝕工程施工及驗(yàn)收規(guī)范
- 國(guó)際飛機(jī)租賃合同范本
- AQ 1011-2005 煤礦在用主通風(fēng)機(jī)系統(tǒng)安全檢測(cè)檢驗(yàn)規(guī)范(正式版)
- 二次抵押貸款合同
評(píng)論
0/150
提交評(píng)論