《计算的复杂性》PPT课件.ppt

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

1、第第2 2章代数方程的章代数方程的KuhnKuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性第第2 2章代数方程的章代数方程的KuhnKuhn算法算法 剖分法与剖分法与标标号法号法 互互补轮补轮回算法回算法 KuhnKuhn算法的收算法的收敛敛性性KuhnKuhn算法的复算法的复杂杂性性2/10/20232/10/202386-286-22 2第第2 2章代数方程的章代数方程的KuhnKuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性引引 言言 与与各各种种传传统统的的迭迭代代方方法法（例例如如N

2、Ne ew wt to on n方方法法）不不同同，K Ku uh hn n算算法法基基于于空空间间的的一一种种单单纯纯剖剖分分，一一种种整整数数标标号号法法和和一一种种互互补补轮轮回回的的算算法法过过程程。如如果果说说它它的的叙叙述述不不象象N Ne ew wt to on n方方法法那那么么简简单单，却却应应当当指指出出，一一旦旦编编成成计计算算机机程程序序以以后后，它它的的使使用用反反而而是是极极其其简简单单的的。为为了了用用K Ku uh hn n算算法法解解任任何何一一个个代代数数方方程程，只只要要把把这这个个代代数数方方程程所所对对应应的的多多项项式式的的复复系系数数组组和和计计算

3、算的的精精度度要要求求输输入入机机器器。然然后后，算算法法就就会会把把该该代代数数方方程程的的全全部部解解一一起起算算出出。对对于于K Ku uh hn n算算法法，不不存存在在初初值值选选择择以以及及其其他他一一些些使使用用方方面面的的棘棘手手问问题题。这这是是一一种种具具有有很很强强的的大大范范围围收收敛敛性性保保证证的的算算法法。另另一一方方面面，虽虽然然算算法法本本身身不不象象一一个个简简单单的的迭迭代代公公式式那那么么简简单单，但但为为了了编编制制计计算算机机程程序序，知知道道2 2.1 1和和2 2.2 2的内容就足够了。的内容就足够了。2/10/20232/10/202386-3

4、86-3第第2 2章代数方程的章代数方程的KuhnKuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性2.12.1剖分法与标号法剖分法与标号法 设设f(z)f(z)是复变量是复变量z z的的n n阶复系数的阶复系数的首一多项式首一多项式，即，即f(z)=zf(z)=zn n+a+a1 1z zn-1n-1+.+a+.+an n，这这里里n n是是自自然然数数，a a1 1,.,.,a an n是是复复常常数数。如如果果复复数数满满足足f()=0f()=0，就就说说是是多多项项式式f f的的一一个个零零点点或或代代数数方方程程f(z)=0f(z)=0

5、的的一个解。我们的算法就是要把一个解。我们的算法就是要把f f的零点找出来。的零点找出来。记记复复数数z zx xiyiy平平面面为为C C，复复数数w wu uiviv平平面面为为C C，则则w wf(z)f(z)确定复平面之间的一个多项式映射确定复平面之间的一个多项式映射f f：CCCC。为为了了在在下下一一节节叙叙述述算算法法，我我们们先先叙叙述述半半空空间间C-1,+)C-1,+)的一种剖分及由的一种剖分及由f f导出的一种标号法。导出的一种标号法。在在C-1,+C-1,+中中，记记C Cd d=Cd=Cd，d d-1,0,1,2,.-1,0,1,2,.。给给定剖分中心定剖分中心及初始

6、格距及初始格距h h。2/10/20232/10/202386-486-4第第2 2章代数方程的章代数方程的KuhnKuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性剖分法剖分法 Cd平平面面的的剖剖分分（简简记记作作Td）剖剖分分 T-1(,h)如如图图2-1所所示示。剖剖分分T-1(,h)中中的的一一个个三三角角形形由由和和为为偶偶数数的的一一对对整整数数(r,s)及及一一对对(a,b)(1,0),(0,1),(-1,0),(0,-1)按按以以下下方方式式完完全全确确定定：它它的的顶顶点点的的复复数坐标分别为：数坐标分别为：+(r+is)h；

7、+(r+a)+i(s+b)h；+(r-b)+i(s+a)h。称称剖剖分分T-1(,h)中中三三角角形形直直径径之之上上界界为为T-1(,h)的的剖剖分分网网径径。易易知知，T-1(,h)的的剖分网径为剖分网径为h。图图2-1 2-1 2/10/20232/10/202386-586-5第第2 2章代数方程的章代数方程的KuhnKuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性Cd平面的剖分平面的剖分 剖剖分分Td(,h)，d=0,1,2,.,如如图图2-2所所示示。Td(,h)中中的的一一个个三三角角形形由由和和为为奇奇数数的的一一对对整整数数(

8、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 2/10/20232/10/202386-686-6第第2 2章代数方程的章代数方程的KuhnKuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性半空间半空间C-1,+的剖分的剖分

9、T(,h)（简记作（简记作T）按按照照平平面面的的剖剖分分，C-1的的每每一一个个正正方方形形（由由共共有有一一斜斜边边的的一一对对三三角角形形组组成成），与与C0的的一一个个正正方方形形（也也由由共共有有一一斜斜边边的的一一对对三三角角形形组组成成）上上下下相相对对，而而斜斜边边相相错错。C-1和和C0之之间间每每一一个个由由上上下下相相对对的的一一对对正正方方形形所所界界定定的的正正四四棱棱柱柱，按按图图2-3规则剖分成规则剖分成5个四面体。个四面体。图2-3 2/10/20232/10/202386-786-7第第2 2章代数方程的章代数方程的KuhnKuhn算法算法电子科技大学计算机学

10、院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性5个四面体个四面体2/10/20232/10/202386-886-8第第2 2章代数方程的章代数方程的KuhnKuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性半空间半空间C-1,+的剖分的剖分T(,h)（简记作（简记作T）按按照照平平面面的的剖剖分分，Cd（d0）的的每每一一个个正正方方形形与与Cd+1的的四四个个正正方方形形上上下下相相对对，界界定定Cd和和Cd+1之之间间的的一一个个正正四四棱棱柱柱。Cd和和Cd+1之之间间每每一一个个这这样样的的正正四四棱棱柱柱，按按图图2-

11、4的的规规则则剖剖分成分成14个四面体。个四面体。图2-4 2/10/20232/10/202386-986-9第第2 2章代数方程的章代数方程的KuhnKuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性14个四面体个四面体2/10/20232/10/202386-1086-10第第2 2章代数方程的章代数方程的KuhnKuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性半空间半空间C-1,+的剖分的剖分T(,h)这这样样一一来来，我我们们就就得得到到半半空空间间C-1,)的的一一个个单单纯纯剖剖分分

12、T(,h)，简简记作记作T。注注意意，从从各各层层Cd平平面面的的剖剖分分Td(,h)到到半半空空间间的的剖剖分分T(,h)，并并没没有有增增加加新新的的剖剖分分格格点点。所所有有剖剖分分Td(,h)，d=-1,0,1,2,.,的的格格点点，组组成成剖剖分分T(,h)的的所所有有格格点点。格格点点都都是是顶顶点点：三三角角形形的的顶顶点点和和四四面面体体的的顶顶点点。这这样样我我们们可可以以说说：T(,h)的的所所有有剖剖分分格格点点组组成成T(,h)顶顶点点集集V(T(,h)，简记作，简记作V(T)。在在下下面面叙叙述述的的算算法法里里，主主要要牵牵涉涉到到由由剖剖分分T中中的的四四面面体体

13、的的界界面面三三角角形形的的顶顶点点所所组组成成的的三三点点组组(z1,d1),(z2,d2),(z3,d3)，或或简简记记作作z1,z2,z3。今后所说的三点组，都是这样的三点组。今后所说的三点组，都是这样的三点组。2/10/20232/10/202386-1186-11第第2 2章代数方程的章代数方程的KuhnKuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性引理引理2-1引引理理2-12-1 设设(z(z1 1,d,d1 1),(z),(z2 2,d,d2 2),(z),(z3 3,d,d3 3)是是剖剖分分T T中中的的一一个个三三点点组

14、，记组，记d=mindd=mind1 1,d,d2 2,d,d3 3，有，有ddddk kd+1d+1，k=1,2,3k=1,2,3。该引理由剖分法的定义直接得到。该引理由剖分法的定义直接得到。在在引引理理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-z

15、2|,|z2-z3|,|z3-z1|，也可简记作也可简记作diamz1,z2,z3。2/10/20232/10/202386-1286-12第第2 2章代数方程的章代数方程的KuhnKuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性引理引理2-2引理引理2-22-2 设三点组设三点组zz1 1,z,z2 2,z,z3 3 位于位于C Cd d和和C Cd+1d+1之间，则之间，则证证明明：从从图图2-3和和图图2-4容容易易看看出出，位位于于Cd和和Cd+1之间的所有可能的三点组的直径不超过之间的所有可能的三点组的直径不超过 。所以所以层数越高，

16、三点组的直径越小。层数越高，三点组的直径越小。2/10/20232/10/202386-1386-13第第2 2章代数方程的章代数方程的KuhnKuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性标标号法号法 2/10/20232/10/202386-1486-14第第2 2章代数方程的章代数方程的KuhnKuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性标标号号的定义的定义定定义义2-12-1称称按按下下式式确确定定的的对对应应l：C1,2,3为为由由多多项项式式f确确定定的的z平面平面C的的标号法

17、标号法：定定义义2-22-2记记f-1(z)=(z-)n；fd(z)=f(z)，d=0,1,2,.。称称按按下下式式确确定定的的对对应应l：V(T(,h)1,2,3为为由由多多项项式式f导导出出的的V(T(,h)的的标号法标号法：2/10/20232/10/202386-1586-15第第2 2章代数方程的章代数方程的KuhnKuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性标标号号的图示的图示 图图2-5 2-5 标号区域标号区域2/10/20232/10/202386-1686-16第第2 2章代数方程的章代数方程的KuhnKuhn算法算法电

18、子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性全标三点组全标三点组 定定义义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。全全标标三三点点组组的的说说法法本本身身，并并没没有有指指明明点点的的标标号号是是由由(z-(z-)n n还还是是由由f f确确定定的的。事事实实上上，今今后

19、后我我们们遇遇到到的的全全标标三三点点组组，其其点点的的标标号号可可以以都都由由(z-(z-)n n确确定定，也也可可以以都都由由f f确确定定，还还可可以部分由以部分由(z-(z-)n n确定，部分由确定，部分由f f确定。确定。2/10/20232/10/202386-1786-17第第2 2章代数方程的章代数方程的KuhnKuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性引理引理2-3引引理理2-32-3设设zz1 1,z,z2 2,z,z3 3 是是标标号号都都由由f f确确定定的的完完全全标标号号三三点点组组，并并且且|f|f(z(zk

20、 k)-f(z)-f(zl l)|)|，k,l=1,2,3k,l=1,2,3，那末，那末 ，k=1,2,3k=1,2,3。证证明明：图图2-6是是w平平面面上上相相应应于于标标号号1,2,3的的三三个个区区域域。z的的标标号号由由w=f(z)落落在在哪哪个个扇扇形形区区域域确确定定。按按照照所所设设，f(z1)必必须须在在区区域域1，同同时时与与区区域域2及及区区域域3的的距距离离均均不不起起过过。这这样样，f(z1)必须落在图必须落在图2-6的菱形阴影区域内，所以的菱形阴影区域内，所以 同理，同理，。2/10/20232/10/202386-1886-18第第2 2章代数方程的章代数方程的K

21、uhnKuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性引理引理2-32-3的说明的说明 大家知道，多项式函数在平面的有限区域上是一致连续的，假大家知道，多项式函数在平面的有限区域上是一致连续的，假如如我我们们能能够够找找到到直直径径很很小小的的标标号号都都由由f确确定定的的完完全全标标号号三三点点组组，那那么么，这这三三点点的的象象在在w平平面面上上的的相相互互距距离离也也很很小小。再再由由引引理理2-3，每每点点的的象象与与w平平面面的的原原点点的的距距离离也也就就很很小小了了。当当这这个个距距离离足足够够小小时时，三三点点组组的的每每一一个

22、个点点都都可可以以足足够够精精确确地地作作为为f的的一一个个数数值值零零点点。前前面面已已经经说说明明，按按照照我我们们的的剖剖分分，层层数数越越高高时时，三三点点组组的的直直径径就就越越小小。这这就就启启发发我我们们设设计计一一种种寻寻找找完完全全标标号号三三点点组组的的算算法法，使使得得一一方方面面投投影影到到平平面面上上看看，计计算算不不超超过过平平面面的的一一个个有有限限区区域域，另另一一方方面面，计计算算要要不不断断向向上上发发展展，达达到到越越来来越越高高的的层层次次。找找到到这这样样的的算算法法，计计算算零零点的问题也就解决了，即找到了多项式的根的近似值。点的问题也就解决了，即找

23、到了多项式的根的近似值。2/10/20232/10/202386-1986-19第第2 2章代数方程的章代数方程的KuhnKuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性2.2互补轮回算法互补轮回算法 互补轮回算法互补轮回算法 进口出口分析进口出口分析 2/10/20232/10/202386-2086-20第第2 2章代数方程的章代数方程的KuhnKuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性互补轮回算法互补轮回算法 在在剖剖分分为为T-1(,h)的的C-1平平面面上上，用用Qm(,h)（简

24、简记记作作Qm）表表示示顶顶点点是是+mh(1i)的的方方块块，这这里里m是是一一个个正正整整数数。也也就就是是说说，Qm是是以以 为为中中心心的的、半半边边长长为为mh的的方方块块，它它的的两两对对对对边边分分别别与与z平平面面上上的的x轴轴和和Y轴轴平平行行。三三角角形形的的一一条条边边称称为为一一条条棱棱。方方块块的的边边界界Qm(,h)（简简记记作作Qm）取取平平面面上上的的逆逆时时针针方方向向为为正正的的方方向向。并并且且，当当写写(z，z是是Qm上上的的一一条条棱棱时时，蕴蕴涵涵按按Qm的的正正定定向向z是是z的的下下一一个个点点。T-1(,h)的的每每个个三三角角形形，按按照照其

25、其顶顶点点面面逆逆时时针针顺顺序序定定向向，并并且且，若若写写z,z,z是是T-1(,h)的的一一个个三三角角形形，蕴蕴涵涵其其顶顶点点顺顺序给出三角形的正向。序给出三角形的正向。平平面面上上两两点点z,z对对另另一一点点z*的的张张角角，是是指指射射线线z*z和和z*z之之间间的的不不超过超过的夹角。也可以把它叫做的夹角。也可以把它叫做平面上线段平面上线段zz对另一点对另一点z*的张角的张角.2/10/20232/10/202386-2186-21第第2 2章代数方程的章代数方程的KuhnKuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性引理引

26、理2-4 引引理理2-4设设 ，则则Qm上上按按照照正正向向次次序序，恰恰有有n条条标标号号为为(1,2)的的棱棱（即即始始端端标标号号为为1终终端端标标号号为为2的的棱棱），而而没没有有标标号号为为(2,1)的棱。的棱。图2-7 2/10/20232/10/202386-286-22222第第2 2章代数方程的章代数方程的KuhnKuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性引理引理2-4的证明的证明 证证明明：设设z,z是是Qm上上的的一一条条棱棱，z和和z对对 的的张张角角记记作作。由图易知：。由图易知：记记为为w=(z-)n和和w=(

27、z-)n对原点对原点o的张角，则的张角，则 按按照照Qm的的构构造造和和幂幂函函数数w=(z-)n的的性性质质，Qm的的象象在在w平平面面上上恰恰好好绕绕原原点点n圈圈。根根据据02/3可可知知，在在Qm上上沿沿正正向向每每走走一一步步（相相当当于于一一条条棱棱），Qm的的象象的的相相应应部部分分在在w平平面面按按正正向向绕绕原原点点旋旋转转了了一一个个小小于于2/3的的正正角角。所所以以，在在w平平面面上上从从w=(mh)n出出发发，Qm的的象象正正好好n次次由由相相应应标标号号1的的区区域域一一步步进进人人相相应应标标号号2的的区区域域。回回到到z平平面面上上，知知 Qm上正好有上正好有n

28、条棱，始端标号为条棱，始端标号为1，终端标号为，终端标号为2。同同样样，由由于于02/3，若若l(z)=2，则则l(z)=2或或3，所所以以 Qm上上没没有标号为有标号为(2,1)的棱。的棱。2/10/20232/10/202386-2386-23第第2 2章代数方程的章代数方程的KuhnKuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性引理引理2-5 引引理理2-5设设 ，则则在在Qm(,h)外外没没有有T-1(,h)的的标号由标号由(z-)n确定的完全标号三角形。确定的完全标号三角形。图图2-8 证证明明：首首先先证证明明，若若zz是是Qm上

29、上或或Qm外外的的一一条条棱棱，则则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/3n2/3n即可。即可。2/10/20232/10/2

30、02386-2486-24第第2 2章代数方程的章代数方程的KuhnKuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性对对于整数于整数k，不等式当然成立。再注意，不等式当然成立。再注意/2，就有，就有 现现设设z,z,z是是T-1(,h),h)的的在在 Q Qm外外的的一一个个三三角角形形，则则它它的的每每条条棱棱对对 的的张张角角均均小小于于 。记记w=(z-)n，w=(z-)n，w=(z-)n，则则w，w，w中中每每两两点点对对原原点点的的张张角角均均小小于于2/3。所所以以，按按下下述述引引理理2-6，z,z,z不是不是标标号由号由(z-)

31、n确定的完全确定的完全标标号三角形。号三角形。由图由图2-82-8，2/10/20232/10/202386-2586-25第第2 2章代数方程的章代数方程的KuhnKuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性引理引理2-6引引理理2-6设设z,z,z是是z平平面面上上的的一一个个三三点点组组，它它们们在在w平平面面上上的的映映射射象象分分别别为为w,w,w（这这里里所所说说的的映映射射，对对三三点点组组的的各各点点可可以以并并不不相相同同，可可以以是是w=(z-)n，也也可可以以是是w=f(z)。那那么么，若若w,w,w均均不不为为0，且

32、且其其中中任任两两点点在在w平平面面上上对对原原点点的的张张角角均均小小于于2/3，则，则z,z,z不是一个完全标号三点组。不是一个完全标号三点组。证证明明：若若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矛盾。同矛盾。同样样，若，若或或亦引

33、出矛盾。最后剩下亦引出矛盾。最后剩下,均不超均不超过过的情况，的情况，这时这时,就是相就是相应应各各对对点之点之间间的的张张角，按角，按题设题设均小于均小于2/3，与，与+=2矛盾。矛盾。2/10/20232/10/202386-2686-26第第2 2章代数方程的章代数方程的KuhnKuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性图图2-92/10/20232/10/202386-2786-27第第2 2章代数方程的章代数方程的KuhnKuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性按照按照确

34、定方确定方块块Qm(,h),h)，这这里符号里符号 r r 表示不小表示不小实实数数r的的最最小小整整数数。算算法法就就是是要要从从 Q Qm上上每每个个标标号号为为(1,2)的的棱棱出出发发，找找寻寻完完全全标标号号三三点点组组。如如果果全全标标三三点点组组的的标标号号不不全全是是由由f确确定定的的，则则它它未未能能提提供供足足够够的的关关于于f的的零零点点位位置置的的信信息息。但但2.3将将证证明明，按按照照下下述述算算法法，计计算算将将在在越越来来越越高高的的层层次次上上面面进进行行，而而在在高高层层（事事实实上上在在除除C-1外外的的各各层层），标标号号均均由由f确确定定。这这样样，按

35、按照照引引理理2-3，我我们们可可按按任任何何预预先先给给定的精度要求把定的精度要求把f的零点算出来。的零点算出来。2/10/20232/10/202386-2886-28第第2 2章代数方程的章代数方程的KuhnKuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性Kuhn算法算法算算法法2-1 依依次次从从 Qm的的第第j个个标标号号为为(1,2)的的棱棱z1,z2出出发发，j=1,2,n，这，这n条棱是容易找到的。条棱是容易找到的。步步1（二二维维搜搜索索）若若z3空空白白，对对于于(1,2)棱棱，存存在在C-1平平面面上上唯唯一一的的顶顶点点

36、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)的的一一个个四四面面体体，且且顶顶点点顺顺序序给给

37、出出空空间间的的右右手手螺螺旋旋方方向向。计算计算ll(z)，令，令zl=z，转步转步2。2/10/20232/10/202386-2986-29第第2 2章代数方程的章代数方程的KuhnKuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性Kuhn算法说明算法说明 按照算法按照算法2-1，我们已经可以编制，我们已经可以编制Kuhn算法的计算机程序了，算法的计算机程序了，而而前前面面的的知知识识，只只有有剖剖分分法法和和标标号号法法是是这这里里要要用用的的。在在步步1，按按照照剖剖分分法法确确定定z，按按照照标标号号法法通通过过计计算算(z-)n得得

38、到到l(z)。在在步步3，按按照照剖剖分分法法确确定定z，按按照照标标号号法法通通过过幂幂函函数数计计算算(z-)n（当当d=-1）或或多多项项式式计计算算f(z)（当当d0）得得到到l(z)。算算出出l=l(z)以以后后，令令zl=z的的做做法法，是是一一个个同同标标号号替替换换的的做做法法：用用z（新新的的点点）取取代代原原有有的的与与z标标号相同的顶点（旧的点）。这种做法，叫做号相同的顶点（旧的点）。这种做法，叫做互补轮回算法互补轮回算法。2/10/20232/10/202386-3086-30第第2 2章代数方程的章代数方程的KuhnKuhn算法算法电子科技大学计算机学院电子科技大学计

39、算机学院 顾小丰顾小丰计算的复杂性计算的复杂性进口出口分析进口出口分析我们分析一下算法我们分析一下算法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，计计算算将将进进入入另另一一个个三三角角形形。从从本本三三角角形形

40、内内部部看看来来，三三角角形形边边界界按按逆逆时时针针定定向向，我我们们很很自自然然地地把把正正向向(1,2)棱棱称称作作计计算算的的进进口口，负负向向(2,1)棱棱则则是是计计算算的的出出口口。如如果果l(z)=3，得得到到正正向向全全标标三三角角形形z1,z2,z3，计计算算将将离离开开三三角角形形而而进进入入四四面面体体。这这样样，还还应应该该把把正正向向全全标标三三角角形形叫叫做做它它自自己的己的出口出口。2/10/20232/10/202386-3186-31第第2 2章代数方程的章代数方程的KuhnKuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂

41、性计算的复杂性进口出口分析进口出口分析(续续1)步步2则则是是降降维维的的情情况况，一一个个负负向向全全标标三三角角形形z1,z3,z2是是上上一一步步的的结结果果。现现在在，要要取取消消z3，计计算算从从剩剩余余的的(2,1)棱棱出出去去。所所以以应应该该把把负向全标三角形负向全标三角形叫做它自己的叫做它自己的进口进口。综综上上所所述述，(1,2)棱棱或或z1,z3,z2是是该该三三角角形形的的进进口口，(2,1)棱棱或或z1,z2,z3是该三角形的是该三角形的出口出口。2/10/20232/10/202386-3286-32第第2 2章代数方程的章代数方程的KuhnKuhn算法算法电子科技

42、大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性进口出口分析进口出口分析(续续2)步步3的情况，由于维数没有变动，所以简单得多。对于一个四面的情况，由于维数没有变动，所以简单得多。对于一个四面体体，已已经经有有一一个个面面是是全全标标三三角角形形，那那么么不不论论第第四四个个点点的的标标号号l(z)如如何何，都都正正好好和和某某一一个个顶顶点点标标号号相相同同。这这样样同同标标号号替替换换以以后后，又又得得到到一一个个全全标标三三角角形形的的面面，而而另另外外两两个个面面，则则因因都都有有标标号号相相重重而而不不是是全全标标三三角角形形。从从四四面面体体的的内内部部看

43、看来来，正正向向全全标标三三角角形形z1,z2,z3是是进口进口，负向全标三角形负向全标三角形z1,z3,z2是是出口出口。把把进口进口和和出口出口统称为统称为门门 2/10/20232/10/202386-3386-33第第2 2章代数方程的章代数方程的KuhnKuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性进口出口分析图示进口出口分析图示2/10/20232/10/202386-3486-34第第2 2章代数方程的章代数方程的KuhnKuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性引理引理2

44、-7 引引理理2-7对对于于顶顶点点在在集集合合1,2,3中中取取标标号号的的一一个个标标号号三三角角形形或或四四面面体体，或或者者它它没没有有门门，或或者者它它正正好好有有一一对门，一个是进口，一个是出口。对门，一个是进口，一个是出口。2/10/20232/10/202386-3586-35第第2 2章代数方程的章代数方程的KuhnKuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性引理引理2-7的证明的证明证明：按照门的定义，对于标号的三角形，如果它缺少标号证明：按照门的定义，对于标号的三角形，如果它缺少标号1 1或或2 2，则则它它没没有有门

45、门。对对于于标标号号1 1，2 2具具备备的的情情况况，若若没没有有标标号号3 3，则则(1 1,2 2)棱棱是是进进口口，(2 2,1 1)棱棱是是出出口口，另另一一棱棱是是(1 1,l l)或或(2 2,2 2)不不是是门门，所所以以正正好好是是一一对对门门。若若三三角角形形全全标标，在在负负向向的的情情况况，z z1 1,z z3 3,z z2 2 是是进进口口，(2 2,1 1)棱棱是是出出口口；在在正正向向的的情情况况下下，(1 1,2 2)棱棱是是进进口口，z z1 1,z z2 2,z z3 3 是是出出口口。不不论论正正向向负负向向，另另两两棱棱均均有有标标号号3 3，不不是是

46、门门。所所以以也也正正好好是是一一对对门。门。对对于于标标号号的的四四面面体体，如如果果它它缺缺少少任任何何一一个个标标号号，则则它它没没有有全全标标三三角角形形的的面面，是是一一个个无无门门的的四四面面体体。若若四四个个顶顶点点取取全全了了1 1,2 2,3 3标标号号，则则正正好好有有一一对对顶顶点点标标号号相相重重。这这时时，以以同同标标号号棱棱为为棱棱的的两两个个面面三三角角形形均均非非全全标标。另另两两个个面面三三角角形形都都是是全全标标三三角角形形，是是一一对对被被同同标标号号棱棱撑撑开开的的三三角角形形。这这时时，站站在在四四面面体体内内部部，若若一一个个全全标标三三角角形形在在

47、正正面面，则则另另一一个个在在背背后后。若若一一个个是是正正向向全全标标三三角角形形，则则另另一一个个是是反反向向全全标标三三角角形形；反之亦然。反之亦然。2/10/20232/10/202386-3686-36第第2 2章代数方程的章代数方程的KuhnKuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性引理引理2-8 引引理理2-8按按照照算算法法2-12-1，从从 Q Qm m的的每每个个(1,2)(1,2)棱棱开开始始的的计算，可以一直进行下去。计算，可以一直进行下去。证证明明：因因为为不不论论计计算算走走到到三三角角形形或或四四面面体体，有

48、有进进口口就就有有出出口，所以，计算可以一直进行下去。口，所以，计算可以一直进行下去。对对于于三三角角形形或或四四面面体体，计计算算若若能能进进来来，则则一一定定能能够够出出去去。所所以以，今今后后不不说说进进入入，而而说说计计算算通通过过一一个个三三角角形形或一个四面体。或一个四面体。把把有有门门的的三三角角形形和和四四面面体体看看作作是是“人人”，两两个个看看作作是是一一双双手手。这这样样，KuhnKuhn算算法法的的曲曲线线都都是是由由许许多多人人手手拉拉手手连连起起来来的的。有有了了这这个个比比喻喻，就就容容易易理理解解，如如果果曲曲线线会会分分叉叉或或打打圈圈，就就一一定定有有一一些

49、些三三只只手手的的“人人”，与与前前面面证证明明的每的每“人人”正好有一双手矛盾。正好有一双手矛盾。2/10/20232/10/202386-3786-37第第2 2章代数方程的章代数方程的KuhnKuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性2.32.3KuhnKuhn算法的收敛性（一）算法的收敛性（一）这这一一节节我我们们将将证证明明，按按照照算算法法2-1从从 Qm上上每每个个标标号号(1,2)棱棱开开始始计计算算，都都收敛到多项式收敛到多项式f的的一个零点。的的一个零点。2/10/20232/10/202386-3886-38第第2

50、2章代数方程的章代数方程的KuhnKuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性计算的单纯形序列计算的单纯形序列定义定义2-4对于整数对于整数j，1jn，顺次记从，顺次记从 Qm上第上第j条条(1,2)棱棱开始的计算所通过的三角形（二维搜索时）或四面休（三维搜索时）开始的计算所通过的三角形（二维搜索时）或四面休（三维搜索时）为为j1,j2,.,jk,.，称它为第，称它为第j个个计算的单纯形序列计算的单纯形序列。按按照照这这种种记记法法，jk可可能能是是一一个个三三角角形形，也也可可能能是是一一个个四四面面体体。我我们们知知道道，空空间间不不共