计算的复杂性.ppt

《计算的复杂性.ppt》由会员分享，可在线阅读，更多相关《计算的复杂性.ppt（86页珍藏版）》请在课桌文档上搜索。

1、计算的复杂性,零危天鸟琴灼凋惹纬莆遁俩全戴尊显蚊诺毫倚枯恨四查技涤峨疥哼蕾素意计算的复杂性计算的复杂性,86-2,2023/9/14,第2章代数方程的Kuhn算法,剖分法与标号法 互补轮回算法 Kuhn算法的收敛性Kuhn算法的复杂性,肢劳唉奇耙色范廖泪击梆诚仰壶礼凛边簧辅钠该羔社渝远厕嗡汐摈色宪籍计算的复杂性计算的复杂性,86-3,2023/9/14,引 言,与各种传统的迭代方法（例如Newton方法）不同，Kuhn算法基于空间的一种单纯剖分，一种整数标号法和一种互补轮回的算法过程。如果说它的叙述不象Newton方法那么简单，却应当指出，一旦编成计算机程序以后，它的使用反而是极其简单的。为了

2、用Kuhn算法解任何一个代数方程，只要把这个代数方程所对应的多项式的复系数组和计算的精度要求输入机器。然后，算法就会把该代数方程的全部解一起算出。对于Kuhn算法，不存在初值选择以及其他一些使用方面的棘手问题。这是一种具有很强的大范围收敛性保证的算法。另一方面，虽然算法本身不象一个简单的迭代公式那么简单，但为了编制计算机程序，知道2.1和2.2的内容就足够了。,滑窃写吝瞳功虎焰碎锅娇主坦挪亭贱义芹迄旭辞菩蛹暴属诧矽聋掇性史蔗计算的复杂性计算的复杂性,86-4,2023/9/14,2.1剖分法与标号法,设f(z)是复变量z的n阶复系数的首一多项式，即f(z)=zn+a1zn-1+.+an，这里n

3、是自然数，a1,.,an是复常数。如果复数满足f()=0，就说是多项式f的一个零点或代数方程f(z)=0的一个解。我们的算法就是要把f的零点找出来。记复数zxiy平面为C，复数wuiv平面为C，则wf(z)确定复平面之间的一个多项式映射f：CC。为了在下一节叙述算法，我们先叙述半空间C-1,+)的一种剖分及由f导出的一种标号法。在C-1,+中，记Cd=Cd，d-1,0,1,2,.。给定剖分中心及初始格距h。,楚惭铡焕遏誊绕要币安祥幼颖兰虑亲波寝拭霄斟抿彤密惨郴拳究聪设叁予计算的复杂性计算的复杂性,86-5,2023/9/14,2.1.1剖分法,Cd平面的剖分（简记作Td）剖分 T-1(,h)如

4、图2-1所示。剖分T-1(,h)中的一个三角形由和为偶数的一对整数(r,s)及一对(a,b)(1,0),(0,1),(-1,0),(0,-1)按以下方式完全确定：它的顶点的复数坐标分别为：+(r+is)h；+(r+a)+i(s+b)h；+(r-b)+i(s+a)h。称剖分T-1(,h)中三角形直径之上界为T-1(,h)的剖分网径。易知，T-1(,h)的剖分网径为h。,图2-1,屑冈链锋漳痒翁笔杆酿滞扶慧脉春否抿俗诚仕汤优囱封扰降泰土唇红秃舌计算的复杂性计算的复杂性,86-6,2023/9/14,Cd平面的剖分,剖分Td(,h)，d=0,1,2,.,如图2-2所示。Td(,h)中的一个三角形由和

5、为奇数的一对整数(r,s)及一对(a,b)(1,0),(0,1),(-1,0),(0,-1)按以下方式完全确定：它的顶点的复数坐标分别为：+(r+is)h2-d；+(r+a)+i(s+b)h2-d；+(r-b)+i(s+a)h2-d。易知，同样定义的Td(,h)，d=0,1,2,.的剖分网径为 h2-d。,图2-2,伏瘤嗡句惜弟请详凌诲拯灯盗麻跪淌痰府臣瞻壁赁蜘慰耐魁尊痛绚稳自闽计算的复杂性计算的复杂性,86-7,2023/9/14,半空间C-1,+的剖分T(,h)（简记作T）,按照平面的剖分，C-1的每一个正方形（由共有一斜边的一对三角形组成），与C0的一个正方形（也由共有一斜边的一对三角形

6、组成）上下相对，而斜边相错。C-1和C0之间每一个由上下相对的一对正方形所界定的正四棱柱，按图2-3规则剖分成5个四面体。,图2-3,踞彰禽坍循汤磐沥钳洪娩马摸护男肥狄缓杜万畏雕菲嗣孺扬笺淋宫迂睫瓤计算的复杂性计算的复杂性,86-8,2023/9/14,5个四面体,兴书狡等讥匆筷蓝擦柔畏钧辩召栈嘘献讯袒瘤朵脯隧老共帕妆肇斥拓乱氓计算的复杂性计算的复杂性,86-9,2023/9/14,半空间C-1,+的剖分T(,h)（简记作T）,按照平面的剖分，Cd（d0）的每一个正方形与Cd+1的四个正方形上下相对，界定Cd和Cd+1之间的一个正四棱柱。Cd和Cd+1之间每一个这样的正四棱柱，按图2-4的规则

7、剖分成14个四面体。,图2-4,吁社锑愚汀预粘眺侨陪要娱都星芜激债膘啪灶咱实在所猖浙糊狸榜乔游萤计算的复杂性计算的复杂性,86-10,2023/9/14,14个四面体,咕挽詹年遭扭案坏剿炬吞匈筛叮篷萝拱用操纽绥粱术祁姥哈舵缄寞垛蓖攻计算的复杂性计算的复杂性,86-11,2023/9/14,半空间C-1,+的剖分T(,h),这样一来，我们就得到半空间C-1,)的一个单纯剖分T(,h)，简记作T。注意，从各层Cd平面的剖分Td(,h)到半空间的剖分T(,h)，并没有增加新的剖分格点。所有剖分Td(,h)，d=-1,0,1,2,.,的格点，组成剖分T(,h)的所有格点。格点都是顶点：三角形的顶点和四

8、面体的顶点。这样我们可以说：T(,h)的所有剖分格点组成T(,h)顶点集V(T(,h)，简记作V(T)。在下面叙述的算法里，主要牵涉到由剖分T中的四面体的界面三角形的顶点所组成的三点组(z1,d1),(z2,d2),(z3,d3)，或简记作z1,z2,z3。今后所说的三点组，都是这样的三点组。,止涪钒页榔案瀑权鉴陵肆慈侈饱漠墨阮赠愤肥臆励瘫槽撵喝葛授惦砸搭撕计算的复杂性计算的复杂性,86-12,2023/9/14,引理2-1,引理2-1 设(z1,d1),(z2,d2),(z3,d3)是剖分T中的一个三点组，记d=mind1,d2,d3，有ddkd+1，k=1,2,3。该引理由剖分法的定义直接

9、得到。在引理2-1的情况，我们说三点组z1,z2,z3位于Cd和Cd+1之间。特别地，当d1=d2=d3=d时，我们说三点组位于Cd上。设(z1,d1),(z2,d2),(z3,d3)是剖分T中的一个三点组。规定：三点组的直径为diam(z1,d1),(z2,d2),(z3,d3)=max|z1-z2|,|z2-z3|,|z3-z1|，也可简记作diamz1,z2,z3。,梭畴饿炕缅细吝颜闰借唾嘻凸相萄杖妥钮聂习容冈矾纠挨息董鲸喘掺粹讫计算的复杂性计算的复杂性,86-13,2023/9/14,引理2-2,引理2-2 设三点组z1,z2,z3位于Cd和Cd+1之间，则,证明：从图2-3和图2-4

10、容易看出，位于Cd和Cd+1之间的所有可能的三点组的直径不超过。,所以层数越高，三点组的直径越小。,夏鸟奠卞嘲定康献蕴梳网贺甘张氧馋扯戊上反爪正坠唆酵宗斌吼带赦肄颖计算的复杂性计算的复杂性,86-14,2023/9/14,2.1.2标号法,锤鞍慢杖禾诉凹腮违泵郧哟左蹄倚嚼剁义阂撩恼恐坟秧坚枕纫恒倦芬悍歧计算的复杂性计算的复杂性,86-15,2023/9/14,标号的定义,定义2-1称按下式确定的对应l：C1,2,3为由多项式f确定的z平面C的标号法：,定义2-2记f-1(z)=(z-)n；fd(z)=f(z)，d=0,1,2,.。称按下式确定的对应l：V(T(,h)1,2,3为由多项式f导出的

11、V(T(,h)的标号法：,绰酶栗识揉衙敖迸初辣朴梯冒疚锦郴败骂迟壳般幅唆帅戊履涯纷神透挪愉计算的复杂性计算的复杂性,86-16,2023/9/14,标号的图示,图2-5 标号区域,侵灸殉晃宁恶疥众没逃龄淋馏贩耶翌型惊啪拐狞茵咐桂赢喂铝候典整唉擅计算的复杂性计算的复杂性,86-17,2023/9/14,全标三点组,定义2-3如果V(T(,h)的一个三点组z1,z2,z3满足l(z1),l(z2),l(z3)=1,2，3，则称它为完全标号三点组，简称全标三点组。为方便起见，今后，完全标号三点组z1,z2,z3的记号均蕴涵l(zk)=k，k=1,2,3。全标三点组的说法本身，并没有指明点的标号是由(

12、z-)n还是由f确定的。事实上，今后我们遇到的全标三点组，其点的标号可以都由(z-)n确定，也可以都由f确定，还可以部分由(z-)n确定，部分由f确定。,蠢彬莉舶舶蓖沿连闪俱沮就感钻亢剖窖腕幻粒操附茧坝豁嫁眺孜终述痈详计算的复杂性计算的复杂性,86-18,2023/9/14,引理2-3,引理2-3设z1,z2,z3是标号都由f确定的完全标号三点组，并且|f(zk)-f(zl)|，k,l=1,2,3，那末，k=1,2,3。,证明：图2-6是w平面上相应于标号1,2,3的三个区域。z的标号由w=f(z)落在哪个扇形区域确定。按照所设，f(z1)必须在区域1，同时与区域2及区域3的距离均不起过。这样

13、，f(z1)必须落在图2-6的菱形阴影区域内，所以,同理，,。,荣道以泻钥砷喀肚蒙胖睁腿牡枣桃殿腥算梳随抓湍坏傣扛了痰砚忆休扫婆计算的复杂性计算的复杂性,86-19,2023/9/14,引理2-3的说明,大家知道，多项式函数在平面的有限区域上是一致连续的，假如我们能够找到直径很小的标号都由f确定的完全标号三点组，那么，这三点的象在w平面上的相互距离也很小。再由引理2-3，每点的象与w平面的原点的距离也就很小了。当这个距离足够小时，三点组的每一个点都可以足够精确地作为f的一个数值零点。前面已经说明，按照我们的剖分，层数越高时，三点组的直径就越小。这就启发我们设计一种寻找完全标号三点组的算法，使得

14、一方面投影到平面上看，计算不超过平面的一个有限区域，另一方面，计算要不断向上发展，达到越来越高的层次。找到这样的算法，计算零点的问题也就解决了，即找到了多项式的根的近似值。,讽贮咎碗侮契读到逮舅赤促渠样婴戴昧诽涵砒能锁声叛蒲泡酞谎搪磕褥凿计算的复杂性计算的复杂性,86-20,2023/9/14,2.2互补轮回算法,互补轮回算法 进口出口分析,宿李夺秉律痔装州驴久乃概策析童尖厅哈陪紧弥芳额庞犁约琳付拢蜗宅附计算的复杂性计算的复杂性,86-21,2023/9/14,2.2.1互补轮回算法,在剖分为T-1(,h)的C-1平面上，用Qm(,h)（简记作Qm）表示顶点是+mh(1i)的方块，这里m是一个

15、正整数。也就是说，Qm是以为中心的、半边长为mh的方块，它的两对对边分别与z平面上的x轴和Y轴平行。三角形的一条边称为一条棱。方块的边界Qm(,h)（简记作Qm）取平面上的逆时针方向为正的方向。并且，当写(z，z是Qm上的一条棱时，蕴涵按Qm的正定向z是z的下一个点。T-1(,h)的每个三角形，按照其顶点面逆时针顺序定向，并且，若写z,z,z是T-1(,h)的一个三角形，蕴涵其顶点顺序给出三角形的正向。平面上两点z,z对另一点z*的张角，是指射线z*z和z*z之间的不超过的夹角。也可以把它叫做平面上线段zz对另一点z*的张角.,锤巍整虫滋峪祸苟档宁耿函微叛振置襟鄂惨鞘时践驶钟嫌俱榷倡字棍雷犀计

16、算的复杂性计算的复杂性,86-22,2023/9/14,引理2-4,引理2-4设，则Qm上按照正向次序，恰有n条标号为(1,2)的棱（即始端标号为1终端标号为2的棱），而没有标号为(2,1)的棱。,图2-7,叛瞧慰囤颧渐丝猛猖颓酶维膝蕴亨哀砍蜡苏咸跨秤樱擂撮胰遗苫瓮肉棱靳计算的复杂性计算的复杂性,86-23,2023/9/14,引理2-4的证明,证明：设z,z是Qm上的一条棱，z和z对的张角记作。由图易知：,记为w=(z-)n和w=(z-)n对原点o的张角，则,按照Qm的构造和幂函数w=(z-)n的性质，Qm的象在w平面上恰好绕原点n圈。根据02/3可知，在Qm上沿正向每走一步（相当于一条棱）

17、，Qm的象的相应部分在w平面按正向绕原点旋转了一个小于2/3的正角。所以，在w平面上从w=(mh)n出发，Qm的象正好n次由相应标号1的区域一步进人相应标号2的区域。回到z平面上，知Qm上正好有n条棱，始端标号为1，终端标号为2。同样，由于02/3，若l(z)=2，则l(z)=2或3，所以Qm上没有标号为(2,1)的棱。,埠氏钥闲腹辨兜归珊较胸羹骗康蜘册蜡蜜诀挽桌肛爵翟癸箔斤刺编臻照片计算的复杂性计算的复杂性,86-24,2023/9/14,引理2-5,引理2-5设，则在Qm(,h)外没有T-1(,h)的标号由(z-)n确定的完全标号三角形。,图2-8,证明：首先证明，若zz是Qm上或Qm外的

18、一条棱，则zz对的张角小于2/3n。事实上，若zz是平行于x轴或平行于y轴的棱，这已由引理2-4的证明及保证。现只须考虑zz是T-1的三角形的斜边的情况。根据Qm的构造，不难证明张角最大的情况发生在靠近Qm的地方。由于对称性，只要证明k是自然数，而z=+h(m+1+ki)，z=+h(m+(k+1)i)时，zz对的张角小于2/3n即可。,妨浸挖冷脑奶扣舌梆撰傍街保漆作沂些俊骗雄懒褥竭橙惫唯剖春拌帚卞驼计算的复杂性计算的复杂性,86-25,2023/9/14,对于整数k，不等式当然成立。再注意/2，就有,现设z,z,z是T-1(,h)的在Qm外的一个三角形，则它的每条棱对的张角均小于。记w=(z-

19、)n，w=(z-)n，w=(z-)n，则w，w，w中每两点对原点的张角均小于2/3。所以，按下述引理2-6，z,z,z不是标号由(z-)n确定的完全标号三角形。,由图2-8，,失始管大甭肃家姑寨输鸽颐赚阻东氢圈倒半菲掉钡蜕治内昔并襟富吉删眺计算的复杂性计算的复杂性,86-26,2023/9/14,引理2-6,引理2-6设z,z,z是z平面上的一个三点组，它们在w平面上的映射象分别为w,w,w（这里所说的映射，对三点组的各点可以并不相同，可以是w=(z-)n，也可以是w=f(z)。那么，若w,w,w均不为0，且其中任两点在w平面上对原点的张角均小于2/3，则z,z,z不是一个完全标号三点组。,证

20、明：若z,z,z是完全标号点组，则不妨设l(z)=1，l(z)=2，l(z)=3。在w平面上，记按正向从ow到ow，从ow到ow，从ow到ow的小于2的角分别为,，那么，0，0，0并且+=2。这时，若，则w,w两点对原点张角为2-，按题设，就有2-2/3，4/3，这与按标号法4/3矛盾。同样，若或亦引出矛盾。最后剩下,均不超过的情况，这时,就是相应各对点之间的张角，按题设均小于2/3，与+=2矛盾。,稀补奎疆指瓶洼烧堆辉结少坦插茅物冬伶锯吃痕疹粒凑淑斋卑签克怒咱黍计算的复杂性计算的复杂性,86-27,2023/9/14,图2-9,面钝隔吠铃讳戊夺敌叉哆晓爬诀耳绍枝解蚁介扑私荫街获着器添职丑藕轿

21、计算的复杂性计算的复杂性,86-28,2023/9/14,按照,确定方块Qm(,h)，这里符号r表示不小,实数r的最小整数。算法就是要从Qm上每个标号为(1,2)的棱出发，找寻完全标号三点组。如果全标三点组的标号不全是由f确定的，则它未能提供足够的关于f的零点位置的信息。但2.3将证明，按照下述算法，计算将在越来越高的层次上面进行，而在高层（事实上在除C-1外的各层），标号均由f确定。这样，按照引理2-3，我们可按任何预先给定的精度要求把f的零点算出来。,催吴绿演督躲滋掂半燃值长居外劳辜党复摧搭绷汗巍刑鼻益嗓捏清进汰贯计算的复杂性计算的复杂性,86-29,2023/9/14,Kuhn算法,算法

22、2-1依次从Qm的第j个标号为(1,2)的棱z1,z2出发，j=1,2,n，这n条棱是容易找到的。步1（二维搜索）若z3空白，对于(1,2)棱，存在C-1平面上唯一的顶点z使得z1,z2,z是T-1(,h)的一个正向三角形。计算z的标号l=l(z)，令zl=z，回到步1（所以，若l=3，则升维，从二维搜索进入三维搜索）。步2（降维：从三维搜索回到二维搜索）若z1,z,z2是T-1(,h)的一个负向全标三角形，取消z3，成为一条(1,2)棱，转步1。步3（三维搜索）在T(,h)中存在唯一的顶点z，使得z1,z2,z,z是T(,h)的一个四面体，且顶点顺序给出空间的右手螺旋方向。计算ll(z)，令

23、zl=z，转步2。,掺请击锹遂痕猪宦袒省切嫂丝饶急歹粗蛤坤番蜒拆熙蚤笼甘露痴刮贷淮毙计算的复杂性计算的复杂性,86-30,2023/9/14,Kuhn算法说明,按照算法2-1，我们已经可以编制Kuhn算法的计算机程序了，而前面的知识，只有剖分法和标号法是这里要用的。在步1，按照剖分法确定z，按照标号法通过计算(z-)n得到l(z)。在步3，按照剖分法确定z，按照标号法通过幂函数计算(z-)n（当d=-1）或多项式计算f(z)（当d0）得到l(z)。算出l=l(z)以后，令zl=z的做法，是一个同标号替换的做法：用z（新的点）取代原有的与z标号相同的顶点（旧的点）。这种做法，叫做互补轮回算法。,

24、嗣呐惹锗从法岭疥礼湛诌吏幂渗盏眼抡灯恳叮苍进薄词犊剖哄扭遮渣稀汪计算的复杂性计算的复杂性,86-31,2023/9/14,2.2.2进口出口分析,我们分析一下算法2-1中的各步。步1从(1,2)棱出发找到z，这时我们说计算进入三角形z1,z2,z。步3从三角形z1,z2,z3出发找到z，我们说计算进入四面体z1,z2,z3,z。在步1的情况，如果l(z)=1或2，得到的还是一个标号(1,2)的棱，下一次还是执行步1，计算将进入另一个三角形。从本三角形内部看来，三角形边界按逆时针定向，我们很自然地把正向(1,2)棱称作计算的进口，负向(2,1)棱则是计算的出口。如果l(z)=3，得到正向全标三角

25、形z1,z2,z3，计算将离开三角形而进入四面体。这样，还应该把正向全标三角形叫做它自己的出口。,陶若渗眶缩呵轿盐挪钨势芥矮陵缺功兴刮康隙者湍颅趟先临巩妇蛤佑泌貉计算的复杂性计算的复杂性,86-32,2023/9/14,进口出口分析(续1),步2则是降维的情况，一个负向全标三角形z1,z3,z2是上一步的结果。现在，要取消z3，计算从剩余的(2,1)棱出去。所以应该把负向全标三角形叫做它自己的进口。综上所述，(1,2)棱或z1,z3,z2是该三角形的进口，(2,1)棱或z1,z2,z3是该三角形的出口。,蚀润郝辰吭漱庶惑傀俺洼艳棍谎焦途赖谈棚啡疆膏玫史恰迪圈息窥衫持脂计算的复杂性计算的复杂性,

26、86-33,2023/9/14,进口出口分析(续2),步3的情况，由于维数没有变动，所以简单得多。对于一个四面体，已经有一个面是全标三角形，那么不论第四个点的标号l(z)如何，都正好和某一个顶点标号相同。这样同标号替换以后，又得到一个全标三角形的面，而另外两个面，则因都有标号相重而不是全标三角形。从四面体的内部看来，正向全标三角形z1,z2,z3是进口，负向全标三角形z1,z3,z2是出口。把进口和出口统称为门,辛鞘孩街献邑蜡发氦粤锤塘菱易夫借藩噎傻自手摔凡嵌诬菠邵爸筛罢甸绝计算的复杂性计算的复杂性,86-34,2023/9/14,2.2.2进口出口分析图示,造介咬妙台诫柬容恍凰著云婶出冰抖堵

27、凯捶搐卉萧昧潜关苔团数愈迭种详计算的复杂性计算的复杂性,86-35,2023/9/14,引理2-7,引理2-7对于顶点在集合1,2,3中取标号的一个标号三角形或四面体，或者它没有门，或者它正好有一对门，一个是进口，一个是出口。,公揽互喀擦嗽胚陡齿兄辖凑臣媚干留搁楔魏斟埂谆账包崇孪朱调醉哈脾眼计算的复杂性计算的复杂性,86-36,2023/9/14,引理2-7的证明,证明：按照门的定义，对于标号的三角形，如果它缺少标号1或2，则它没有门。对于标号1，2具备的情况，若没有标号3，则(1,2)棱是进口，(2,1)棱是出口，另一棱是(1,l)或(2,2)不是门，所以正好是一对门。若三角形全标，在负向的

28、情况，z1,z3,z2是进口，(2,1)棱是出口；在正向的情况下，(1,2)棱是进口，z1,z2,z3是出口。不论正向负向，另两棱均有标号3，不是门。所以也正好是一对门。对于标号的四面体，如果它缺少任何一个标号，则它没有全标三角形的面，是一个无门的四面体。若四个顶点取全了1,2,3标号，则正好有一对顶点标号相重。这时，以同标号棱为棱的两个面三角形均非全标。另两个面三角形都是全标三角形，是一对被同标号棱撑开的三角形。这时，站在四面体内部，若一个全标三角形在正面，则另一个在背后。若一个是正向全标三角形，则另一个是反向全标三角形；反之亦然。,元甥料牛扛防叮约击怂釜瞄伺汞串蹭摇峙誊顽册饰缚疡别甩泳祈邱

29、害姑崭计算的复杂性计算的复杂性,86-37,2023/9/14,引理2-8,引理2-8按照算法2-1，从Qm的每个(1,2)棱开始的计算，可以一直进行下去。,证明：因为不论计算走到三角形或四面体，有进口就有出口，所以，计算可以一直进行下去。对于三角形或四面体，计算若能进来，则一定能够出去。所以，今后不说进入，而说计算通过一个三角形或一个四面体。把有门的三角形和四面体看作是“人”，两个看作是一双手。这样，Kuhn算法的曲线都是由许多人手拉手连起来的。有了这个比喻，就容易理解，如果曲线会分叉或打圈，就一定有一些三只手的“人”，与前面证明的每“人”正好有一双手矛盾。,诽庐惨寝辐恳立泼排垂隆杏怜像距尼

30、吻荤意醒氦饮预控剪鸟哼喜渗迢弯恍计算的复杂性计算的复杂性,86-38,2023/9/14,2.3Kuhn算法的收敛性（一）,这一节我们将证明，按照算法2-1从Qm上每个标号(1,2)棱开始计算，都收敛到多项式f的的一个零点。,辊旭决剁约昌把真丝龋韧挛要姻琉按呐茶炽卵鞠丑司牺干般掖凌辆赘备姬计算的复杂性计算的复杂性,86-39,2023/9/14,计算的单纯形序列,定义2-4对于整数j，1jn，顺次记从Qm上第j条(1,2)棱开始的计算所通过的三角形（二维搜索时）或四面休（三维搜索时）为j1,j2,.,jk,.，称它为第j个计算的单纯形序列。按照这种记法，jk可能是一个三角形，也可能是一个四面体

31、。我们知道，空间不共线的三个点的凸包是2维单纯形，三角形就是2维单纯形；空间不共面的四个点的凸包是3维单纯形，四面体就是3维单纯形。采用上述记法，在需要区别的时候，我们用2jk表示它是一个2维单纯形，即三角形；或写作dim(jk)=2，即jk的维数为2，表明jk是一个2维单纯形，即三角形。同样，表示3jk维单纯形，即四面体；dim(jk)=3表明jk是一个3维单纯形，即四面体。,获论虏牲营尸孔性津塔芯骄旨缄滩芦丁穷噎泞膝谚啪抉氖圆瓶蝴寞时荫光计算的复杂性计算的复杂性,86-40,2023/9/14,计算的点序列,定义2-5对于整数j，1jn，记(zj1,dj1)为j1的不在Qm的顶点，对于k2

32、，当dim(jk)dim(j,k-1)时，记(zjk,djk)为jk的不属于j,k-1的顶点，当dim(jk)dim(j,k-1)时，记(zjk,djk)=(zj,k-1,dj,k-1)。这样得到的序列(zjk,djk)|k=1,2,.称为第j个计算的点序列。如果我们只关注该序列在z平面的投影，zjk也称为第j个计算的点序列。,烧帜坐舜洁搁米屋蕴夯汉岂诬尖侣而挟叠峻已武殷次鸣浚呵屈谅砖闪塔妄计算的复杂性计算的复杂性,86-41,2023/9/14,定义的说明,注意，计算的单纯形序列中的单纯形的维数只可能是2或3，所以dim(jk)dim(j,k-1)的情况不可能连续发生。下面我们还将知道（见推

33、论2-1），dim(jk)dim(j,k-1)的情况，只能发生有限次，即对于每个计算序列，步2只能执行有限多次。下面我们先讨论一下算法的性状。,暮掷陵圾晴旁类秃得际虫筋惕赘疽谚煮攫漠觅屠酗留湛韭肪式雨援舍息痞计算的复杂性计算的复杂性,86-42,2023/9/14,引理2-9,引理2-9若dim(jk)=2，则jkQm。这就是说，二维搜索不会跑到Qm外面去。证明：若不然，存在j,k使dim(jk)=2，但jkQm。按照算法，二维搜索只能在C-1平面上发生，即jkC-1，不妨设jk是计算的单纯形序列j1,j2,.中头一个位于Qm外的三角形。这时，若dim(j,k-1)=2，则j,k-1Qm，所以

34、j,k-1和jk有一条公共棱在Qm上，具有标号1和2。若该棱是(1,2)棱，则它是内三角形j,k-1的进口，与由j,k-1到jk的计算顺序矛盾；若该棱是(2,1)棱，则与引理2-1矛盾。若dim(j,k-1)=3，按照算法2-1（步2），j,k是Qm外一个z1,z3,z2全标三角形，与引理2-5矛盾。,蚤圃剪巍忆碎昭款堰印窖尺自漳撵绣舞脏寂拔浅龙全仪雾椰凑团琐歧帜莽计算的复杂性计算的复杂性,86-43,2023/9/14,换一个角度分析进口出口,上节已证明，对于T-1中的三角形或T中的四面体，或者它没有门，或者它正好有一对门，一个是进口，一个是出口。但是，门之作为进口或作为出口，是相对于三角形

35、或四面体而言的。例如图2-12（字母表示顶点，脚标表示该顶点的标号），B1C2是一个门，对于三角形BAC来说，它是出口，对于三角形BCD来说，它是进口。又如B1C2D3这个门，对于三角形BCD本身来说，它是出口，从二维搜索转入三维搜索的出口；对于四面体BCDE来说，它是进口，从二维搜索进入三维搜索的进口。再如B1E2D3这个门，是BCDE的出口，又是BEDF的进口。如果一个门是某个三角形或四面体的出口，我们称该三角形或四面体为这个门的上方单纯形；如果一个门是某个三角形或四面体的进口，我们称该三角形或四面体为这个门的下方单纯形。,喳鞍倾氖嗜喇超搀桃茹蔗却庇着压诺四厕瘁啸蝗裸地颊燕鄙坞吹倦郸酞乔计

36、算的复杂性计算的复杂性,86-44,2023/9/14,图2-12,硬零财韦讨酪辊彩干瓢躬脉猴豢砰匠笑宣囤檬轧坛控咨题鸦派逢鸵练词鸣计算的复杂性计算的复杂性,86-45,2023/9/14,引理2-10,引理2-10对于任何一个不在Qm上的门，它的上方单纯形和下方单纯形都是唯一存在的。,对于Qm上的门，它就是我们算法的起始棱，相应的结论是：它的下方单纯形是唯一存在的。,勾瘫倡悔斋憾扛倪茵瑞榨膳婴港陡教年直禹聚蓝缴幅肯瓣抗衍氨瓶互舆菱计算的复杂性计算的复杂性,86-46,2023/9/14,引理2-10的证明,证明：按照门的定义，它或者是T-1(,h)中的标号为1和2的棱，或者若它是T-1(,h

37、)中的标号为1和2的棱，且不在Qm上，由引理2-9可知，它在内部，根据剖分T-1(,h)的定义，任何一条棱是且仅是两个标号三角形的一条公共边，因此这两个标号三角形中一个门的上方单纯形，另一个是该门的下方单纯形，且唯一。若它是T(,h)中的全标三角形。当它是T-1(,h)中的正向全标三角形z1,z2,z3时，它的上方单纯形是T(,h)中以三角形z1z2z3为一个面的四面体，根据剖分的定义，这样的四面体是唯一的，它的下方单纯形就是它本身。当它是T-1(,h)中的负向全标三角形z1,z3,z2时，它的上方单纯形是它本身，它的下方单纯形是T(,h)中以三角形z1z3z2为一个面的四面体，这样的四面体也

38、是唯一的。当它不在T-1(,h)中时，由于任何一个不在T-1(,h)中三角形是且仅是两个四面体的一个公共面，因此这两个四面体一个是门的上方单纯形，另一个是该门的下方单纯形。,坞藤涣悉谬零痰根慑扰药审响日目玩陷逝鸽皋卓像讣铝绰蜡拨嗅娥型投寞计算的复杂性计算的复杂性,86-47,2023/9/14,引理2-11,引理2-11若(j,k)(i,l)，则jkil。,这就是说，在剖分并标号的半空间中，T-1的每个三角形和T的每个四面体，都顶多只允许计算通过一次。,横乍彭甜柠恳奸饰胶涟灾虽妖姑宙砧眼刃酒辖芍瑟始九防邓下贯按怪橇谊计算的复杂性计算的复杂性,86-48,2023/9/14,引理2-11的证明,

39、证明：首先注意，jk=il，k1，l1蕴涵j,k-1=i,l-1。这只要对作为=jk=il的进口的门运用引理2-10：这个门的上方单纯形唯一，所以j,k-1=i,l-1。若引理不真：jk=il。不妨设kl。由jk=il，k1，l1蕴涵j,k-1=i,l-1，可得j,1=i,l-k+1。考虑作为j,1的进口的门。按照算法，它是Qm上第j条z1,z2棱，如果l-k+11，即如果lk，则i,l-k是以该棱为出口的一个三角形，dim(i,l-k)=2，但i,l-kQm，与引理2-9矛盾。所以l=k，jl=il。这时，按照引理2-7，对于同一个单纯形jl=il，它的进口是唯一的，即作为jl进口的第j个(

40、1,2)棱就是作为il进口的第i个(1,2)棱，所以i=j。这与所设(j,k)(i,l)矛盾。,陛提栋殆铆怕肇灿蕊奋峭滞亏寞抖碳蓑并轻涪赋综阳吻点昼抖氛识几庶细计算的复杂性计算的复杂性,86-49,2023/9/14,推论2-1,推论2-1对于每个j，1jn，存在Kj使得kKj时，dim(jk)=3。,即：每个计算的单纯形序列除了开始的有限一段外，都由三维单纯形四面体组成。所以三维搜索是本质的。,证明：二维搜索只能在Qm内进行，Qm内三角形数目有限(8m2个)，每个三角形顶多允许计算通过一次。,注意，我们说每个三角形或每个四面休顶多允许计算通过一次，并不是说每个顶点顶多只允许计算一次。例如在图

41、2-12中，若A2,B1,C2,D3依旧，但E的标号不是2而是3，那么下一次就应当计算A而不是F，A已被重复计算。所以，由(j,k)(i,l)不能推出(zjk,djk)(zil,dil)。,蓝师扭征缺榔镁上丢八蝴低诵铰奎痉厘关光荧韦迭嘘裁琼吃掷咨巢荆素泡计算的复杂性计算的复杂性,86-50,2023/9/14,引理2-12,引理2-12存在（依赖于,h和多项式f的）R0，使得C(R)-1,+)外没有完全标号三角形，这里C(R)=z|z|R。,这就是说，三维搜索不会跑到C(R)-1,+)外面去。,胁卒拨禾铬朔驯述笼现翼酣侮摩今腊孟钝暇灰戚建涉肾耐卿悬巍增凹糯得计算的复杂性计算的复杂性,86-51

42、,2023/9/14,引理2-12的证明,证明：取,而。由于r=R-|0，在C(R)=z|z|R外改写,其中。若z,z是剖分T(,h)中位于C(R)-1，+)外的任一三点组的任意两点，记它们的映射象为w,w，那么，不管所论的点的映射是w=(z-)n或w=f(z)，都是w0，w0。并且，注意线段zz整个在C(R)-1,+)外，所以,靡屠挨船烁岸贸立地篷衡疽摊挑件桌柠谦谆游疚闭钟匿慢碟屎措兜闰嫉锈计算的复杂性计算的复杂性,86-52,2023/9/14,。,注意，当z,z均由w=(z-)n标号时，不等式右端第二项和第三项均可去掉；当z,z之一由w=(z-)n标号，而另一个由w=f(z)标号时，不等

43、式右端第二顶和第三项的系数2均可去掉。但是不论在任何情况，上述形式的不等式均成立。因此，,这样，据引理2-6，T(,h)位于C(R)-1,+外的所有三点组均非完全标号三点组。,贿鸵壤榜衰瞄熟票伞量癣硕央臻摔懂世患玄喘旨痕侠得适箍舷压淄隧扛掇计算的复杂性计算的复杂性,86-53,2023/9/14,图2-13,勇蠢暮据咏菊桅滦首捶酗颈茫伎技弯促腿闺雅匙廖导明北奠跌靴傍蚁证劫计算的复杂性计算的复杂性,86-54,2023/9/14,定理2-1,定理2-1投影到复平面上看，每个计算的点序列都有聚点。证明：对于每个整数j，1jn，zjk是一个序列。按照该序列的构造（定义2-5），注意QmC(R)，二维

44、搜索不超出Qm，三维搜索不超出C(R)-1,+)，可知zjkC(R)。但C(R)作为平面有界闭区域是紧致的，所以无穷序列zjk在C(R)中必有聚点。,戚怜剑惑湾抖莉背排画儿浅梧澜樟沥癸障依洽雍睬污僧舆种纬邻卜擂赛张计算的复杂性计算的复杂性,86-55,2023/9/14,定理2-2,定理2-2设z*是计算的点序列zjk的一个聚点，则f(z*)=0。即：计算的点序列的聚点，都是多项式的零点。,滑自赵匠瞎贵影拉焙阑框互烤邻争励洁摧搔咐介涡种汪泻攘妻吧养汾翠厚计算的复杂性计算的复杂性,86-56,2023/9/14,定理2-2的证明,证明：考虑计算的单纯形序列jk，这是一个没有重复的无穷的单纯形序列

45、（引理2-11和引理2-8）。按照T(,h)的构造，QmC-1内的三角形数目有限，以C(R)为底的大圆柱内位于任何有限高度以下的四面体数目有限，但jk只能由不重复的Qm内的三角形和C(R)-1,+)内的四面体组成，所以对于任意正整数d，存在k(d)，使得当kk(d)时，jk位于Cd平面以上。而计算的点序列zjk,djk是由计算的单纯形序列jk按定义2-5的方式确定的。所以，对任何正整数d，存在k(d)，使得当kk(d)时，djkd。,由于上面的讨论，不妨设此子序列具有d(k)k+1的性质。,z*是zjk的聚点，所以存在zjk,djk的子序列，它在z平面上的投影收敛到z*。记此子序列为z(k),

46、d(k)，则有,医糯碴谬波众抽稠圃限溅酷枢秀屹官镊赊庇绚羡惶似涧夷敝召碾振拍祖邓计算的复杂性计算的复杂性,86-57,2023/9/14,事实上，取,注意，为了这里证明叙述的方便，子序列的写法与定义2-5不同，号码j也省略了。现在，为了证明f(z*)=0，利用多项式f的连续性，只须证明任给0，存在正整数K，使得当kK时有|f(z(k)|便可。,即可，其中,M=max1,|a1|,.,|an-1|，R如引理2-12所述。这是因为若kK，设z1,z2,z3或z1,z3,z2是z(k)所在的一个位于CK以上的完全标号三点组，那么,衣嘲慈悉惕忆霄追藉彝妻述礼捅咨病妙攘急丈恰冶碗阿一狈辙映瞬喂僳备计算的

47、复杂性计算的复杂性,86-58,2023/9/14,所以，据引理2-3，因z(k)是该三点组之一点，。,同理，,蓑国驾瞻仙诱闲汾雁笺理差涨尸类忘众抿痞潭紧滦瘟勘隘例剂洋锨棒诸瞳计算的复杂性计算的复杂性,86-59,2023/9/14,代数基本定理,直到现在为止，我们没有预先假定多项式f的零点的存在。但是我们构造了算法，证明了这个算法所产生的每个计算的点序列在复平面上都有聚点，而这种聚点都是多项式的零点。这样，我们也就构造性地证明了以下定理。,定理2-3设f(z)=zn+a1zn-1+.+an，其中n为自然数，z为复变量，a1，.，an为复常数，则f(z)必有零点。,至此，我们可以把多项式写成乘

48、积的形式，并叙述零点的重数的概念。这就是下面的定义。,定义2-6设f(z)=zn+a1zn-1+.+an=(z-1)k1.(z-j)kj，j及k1,.,kj均为正整数，1,.,j互不相同，则称ki为f的零点i的重数，i=1,.,j。特别地，若ki=1,称i为f的单零点；若ki1，称i为f的重零点，或ki重零点。,索瘸熬搽拽疽局藏跋垂虹授钨伯鳖阂盗旭痛碘耻锥捉亩臼油涛样湖寥滚伟计算的复杂性计算的复杂性,86-60,2023/9/14,2.4Kuhn算法的收敛性（二）,这一节我们将进一步证明，每个计算的点序列只收敛到多项式的一个零点；从Qm上n个标号为(1,2)的棱开始的n个计算的点序列正好收敛到

49、多项式的全部n个零点。,叙竣纬鸯饺盾吻伤仇腺蛛修抿晴襄卤宇镰障炉千椿嫉否君狡疮福版孽醛佰计算的复杂性计算的复杂性,86-61,2023/9/14,定理2-4,定理2-4每个计算的点序列都收敛到多项式的一个零点。,筑矽淄呢寇绑视交隋快喀插绕床终畔毙伎路域骆跋道疚栏隔痰滚眨甲靠阮计算的复杂性计算的复杂性,86-62,2023/9/14,定理2-4的证明,承寻耿惺乙睫闭腔避襄巨项黄渴越铆床寇某号灵北又夷沥喷捧率獭宇赡恼计算的复杂性计算的复杂性,86-63,2023/9/14,不妨设K足够大，使得当kK时，计算点序列的投影步长（在相应高度的三点组的投影直径）不超过r。再不妨设kk*，则序列Zjk从k=

50、k*到k=k一段与C之交非空，因为它以不超过r的步长，不可能从距z*小于r的地方一步跨到距z小于r的地方。由于K的任意性，可知zjkC也是一个无穷序列，而C是平面有界闭集，由它的紧致性，存在zC是zjkC的聚点，当然，z也是zjk的聚点，且zz，zz*。,再挖去分别以z,z,z*为中心的半径 的三个开圆重复上述讨论，又可得第4个聚点。这样做下去，zjk在C(R)有无穷多个聚点，于是据定理2-2，多项式f在C(R)有无穷多个零点。这样一来，必须f(z)0。这与所设f是阶数n大于0的首一多项式矛盾。,贝篷尔橡科蛔溶浙拧绑捂堑铁韵既桅刮脆薄竿横井若楔脖慧据暇染荡被披计算的复杂性计算的复杂性,86-6