计算的复杂性

1、第第2 2章代数方程的章代数方程的kuhnkuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性86 - 86 - 2 22021-10-212021-10-21第第2 2章代数方程的章代数方程的kuhnkuhn算法算法 剖分法与标号法剖分法与标号法 互补轮回算法互补轮回算法 kuhnkuhn算法的收敛性算法的收敛性kuhnkuhn算法的复杂性算法的复杂性第第2 2章代数方程的章代数方程的kuhnkuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性86 - 86 - 3 32021-10-212021-1

2、0-21引引 言言 与各种传统的迭代方法（例如与各种传统的迭代方法（例如newtonnewton方法）不同，方法）不同，kuhnkuhn算法算法基于空间的一种单纯剖分，一种整数标号法和一种互补轮回的基于空间的一种单纯剖分，一种整数标号法和一种互补轮回的算法过程。如果说它的叙述不象算法过程。如果说它的叙述不象newtonnewton方法那么简单，却应当方法那么简单，却应当指出，一旦编成计算机程序以后，它的使用反而是极其简单的。指出，一旦编成计算机程序以后，它的使用反而是极其简单的。为了用为了用kuhnkuhn算法解任何一个代数方程，只要把这个代数方程所对算法解任何一个代数方程，只要把这个代数方程

3、所对应的多项式的复系数组和计算的精度要求输入机器。然后，算法应的多项式的复系数组和计算的精度要求输入机器。然后，算法就会把该代数方程的全部解一起算出。对于就会把该代数方程的全部解一起算出。对于kuhnkuhn算法，不存在初算法，不存在初值选择以及其他一些使用方面的棘手问题。这是一种具有很强的值选择以及其他一些使用方面的棘手问题。这是一种具有很强的大范围收敛性保证的算法。另一方面，虽然算法本身不象一个简大范围收敛性保证的算法。另一方面，虽然算法本身不象一个简单的迭代公式那么简单，但为了编制计算机程序，知道单的迭代公式那么简单，但为了编制计算机程序，知道2.12.1和和2.22.2的内容就足够了。

4、的内容就足够了。 第第2 2章代数方程的章代数方程的kuhnkuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性86 - 86 - 4 42021-10-212021-10-212.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，就说，就说是多

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

6、cd d=c=cdd，d d-1,0,1,2,.-1,0,1,2,.。给。给定剖分中心定剖分中心及初始格距及初始格距h h。第第2 2章代数方程的章代数方程的kuhnkuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性86 - 86 - 5 52021-10-212021-10-212.1.12.1.1剖分法剖分法 cd平面的剖分（简记作平面的剖分（简记作td）剖分剖分 t-1(,h)如图如图2-1所示。所示。剖分剖分t-1(,h)中的一中的一个三角形由和为偶数的一对整数个三角形由和为偶数的一对整数(r,s)及一及一对对(a,b)(1,0),(0,

7、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 y x z h x y图图2-1 2-1 第第2 2章代数方程的章代数方程的kuhnkuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性86 - 86 - 6 62021-10-212

8、021-10-21cd平面的剖分平面的剖分 剖分剖分td(,h)，d=0,1,2,.,如图如图2-2所示。所示。td(,h)中的一个三角形由和为奇数的一中的一个三角形由和为奇数的一对整数对整数(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 y x z h2-d

9、x y图2-2 第第2 2章代数方程的章代数方程的kuhnkuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性86 - 86 - 7 72021-10-212021-10-21半空间半空间c-1,+的剖分的剖分t(,h) （简记作（简记作t）按照平面的剖分，按照平面的剖分，c-1的每的每一个正方形（由共有一斜边的一个正方形（由共有一斜边的一对三角形组成），与一对三角形组成），与c0的一的一个正方形（也由共有一斜边的个正方形（也由共有一斜边的一对三角形组成）上下相对，一对三角形组成）上下相对，而斜边相错。而斜边相错。c-1和和c0之间每之间每一个由上

10、下相对的一对正方形一个由上下相对的一对正方形所界定的正四棱柱，按图所界定的正四棱柱，按图2-3规则剖分成规则剖分成5个四面体。个四面体。 c0 c-1 图2-3 第第2 2章代数方程的章代数方程的kuhnkuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性86 - 86 - 8 82021-10-212021-10-215个四面体个四面体 e c a d h g b f e a d b e d h g e g b f e d g b c d g b e c d h g b f e c d h g b e d h g b 第第2 2章代数方程的章代数

11、方程的kuhnkuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性86 - 86 - 9 92021-10-212021-10-21半空间半空间c-1,+的剖分的剖分t(,h) （简记作（简记作t）按照平面的剖分，按照平面的剖分，cd（d0）的每一个正方形）的每一个正方形与与cd+1的四个正方形上下的四个正方形上下相对，界定相对，界定cd和和cd+1之间之间的一个正四棱柱。的一个正四棱柱。cd和和cd+1之间每一个这样的正之间每一个这样的正四棱柱，按图四棱柱，按图2-4的规则的规则剖分成剖分成14个四面体。个四面体。 cd+1 cd 图2-4 第第

12、2 2章代数方程的章代数方程的kuhnkuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性86 - 86 - 10102021-10-212021-10-2114个四面体个四面体 h 3 2 1 c b d e f i a g 4 1 b i a h 3 2 1 c b d e f i a g 4 h 1 i a h 3 2 1 c b d e f i g 4 h 1 i 4 4 h 3 2 1 c b d e f i g 4 h i g 4 4 3 2 1 c b d e f i g 4 f i g 4 4 3 2 1 c b d e f i 4

13、 2 c b i 3 2 1 c b d e f i 4 2 1 b i 3 2 1 c d e f i 4 2 1 i 4 4 3 2 c d e f i 4 2 c d i 3 2 d e f i 4 3 f i 4 4 3 2 d e f i 4 3 2 d i 3 2 d e f i 4 3 e f i 3 2 d e i 4 3 2 i 4 3 d e i 第第2 2章代数方程的章代数方程的kuhnkuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性86 - 86 - 11112021-10-212021-10-21半空间半空间c-1,+

14、的剖分的剖分t(,h) 这样一来，我们就得到半空间这样一来，我们就得到半空间c-1,)的一个的一个单纯剖分单纯剖分t(,h)，简，简记作记作t。 注意，从各层注意，从各层cd平面的剖分平面的剖分td(,h)到半空间的剖分到半空间的剖分t(,h)，并，并没有增加新的剖分格点。所有剖分没有增加新的剖分格点。所有剖分td(,h)，d=-1,0,1,2,.,的格点，的格点，组成剖分组成剖分t(,h)的所有格点。格点都是顶点：三角形的顶点和四面的所有格点。格点都是顶点：三角形的顶点和四面体的顶点。这样我们可以说：体的顶点。这样我们可以说：t(,h)的所有剖分格点组成的所有剖分格点组成t(,h)顶顶点集点

15、集v(t(,h)，简记作，简记作v(t)。 在下面叙述的算法里，主要牵涉到由剖分在下面叙述的算法里，主要牵涉到由剖分t中的四面体的界面中的四面体的界面三角形的顶点所组成的三角形的顶点所组成的三点组三点组(z1,d1),(z2,d2),(z3,d3)，或简记作，或简记作z1,z2,z3。今后所说的三点组，都是这样的三点组。今后所说的三点组，都是这样的三点组。 第第2 2章代数方程的章代数方程的kuhnkuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性86 - 86 - 12122021-10-212021-10-21引理引理2-1引理引理2-12-

16、1 设设(z(z1 1,d,d1 1),(z),(z2 2,d,d2 2),(z),(z3 3,d,d3 3) )是剖分是剖分t t中的一个三点中的一个三点组，记组，记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),(

17、z3,d3)是剖分是剖分t中的一个三点组。规定：中的一个三点组。规定：三点组的直径三点组的直径为为diam(z1,d1),(z2,d2),(z3,d3)=max|z1-z2|,|z2-z3|,|z3-z1|，也可简记作也可简记作diamz1,z2,z3。 第第2 2章代数方程的章代数方程的kuhnkuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性86 - 86 - 13132021-10-212021-10-21引理引理2-2引理引理2-22-2 设三点组设三点组zz1 1,z ,z2 2,z ,z3 3 位于位于c cd d和和c cd+1d+

18、1之间，则之间，则d3212h2z,z,diamz 证明：证明：从图从图2-3和图和图2-4容易看出，位于容易看出，位于cd和和cd+1之间的所有可能的三点组的直径不超过之间的所有可能的三点组的直径不超过 。d2h2 所以所以层数越高，三点组的直径越小。层数越高，三点组的直径越小。 第第2 2章代数方程的章代数方程的kuhnkuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性86 - 86 - 14142021-10-212021-10-212.1.2标号法标号法 第第2 2章代数方程的章代数方程的kuhnkuhn算法算法电子科技大学计算机学院电子

19、科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性86 - 86 - 15152021-10-212021-10-21标号标号的的定义定义定义定义2-12-1称按下式确定的对应称按下式确定的对应l：c1,2,3为由多项式为由多项式f确定确定的的z平面平面c的的标号法标号法： 。若若若若或或若若3/)z( farg, 3;)z( farg3/, 2; 0)z( f3/)z( farg3/, 1)z( l定义定义2-22-2记记f-1(z)=(z-)n；fd(z)=f(z)，d=0,1,2,.。称按下式确定。称按下式确定的对应的对应l：v(t(,h)1,2,3为由多项式为由多项式f导出的导出

20、的v(t(,h)的的标号标号法法： 。若若若若或或若若3/)z(farg, 3;)z(farg3/, 2; 0)z(f3/)z(farg3/, 1)z( ldddd第第2 2章代数方程的章代数方程的kuhnkuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性86 - 86 - 16162021-10-212021-10-21标号标号的图示的图示 图图2-5 2-5 标号区域标号区域 0 0 z z z= =x+iyx+iy 平面平面 f(z) w w= =u+ivu+iv 平面平面 i i iiiiii iiii 第第2 2章代数方程的章代数方程的

21、kuhnkuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性86 - 86 - 17172021-10-212021-10-21全标三点组全标三点组 定义定义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。 全标三点组的说法本身，并没有指明点的标号是由全标三点

22、组的说法本身，并没有指明点的标号是由(z-(z-) )n n还是由还是由f f确定的。事实上，今后我们遇到的全标三确定的。事实上，今后我们遇到的全标三点组，其点的标号可以都由点组，其点的标号可以都由(z-(z-) )n n确定，也可以都由确定，也可以都由f f确确定，还可以部分由定，还可以部分由(z-(z-) )n n确定，部分由确定，部分由f f确定。确定。 第第2 2章代数方程的章代数方程的kuhnkuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性86 - 86 - 18182021-10-212021-10-21引理引理2-3引理引理2-3

23、2-3设设zz1 1,z,z2 2,z,z3 3 是标号都由是标号都由f f确定的完全标号三点组，并确定的完全标号三点组，并且且|f(z|f(zk 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)必须落在图必须落在

24、图2-6的菱形阴影区域内，所以的菱形阴影区域内，所以 32| )z( f |k 0 1 2 3 图图 2 2- -6 6 32| )z( f |1 32| )z( f |2 32| )z( f |3 同理，同理， 。 32x)2x(x222第第2 2章代数方程的章代数方程的kuhnkuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性86 - 86 - 19192021-10-212021-10-21引理引理2-32-3的说明的说明 大家知道，多项式函数在平面的有限区域上是一致连续的，假大家知道，多项式函数在平面的有限区域上是一致连续的，假如我们能够

25、找到直径很小的标号都由如我们能够找到直径很小的标号都由f确定的完全标号三点组，那确定的完全标号三点组，那么，这三点的象在么，这三点的象在w平面上的相互距离也很小。再由引理平面上的相互距离也很小。再由引理2-3，每，每点的象与点的象与w平面的原点的距离也就很小了。当这个距离足够小时，平面的原点的距离也就很小了。当这个距离足够小时，三点组的每一个点都可以足够精确地作为三点组的每一个点都可以足够精确地作为f的一个数值零点。前面的一个数值零点。前面已经说明，按照我们的剖分，层数越高时，三点组的直径就越小。已经说明，按照我们的剖分，层数越高时，三点组的直径就越小。这就启发我们设计一种寻找完全标号三点组的

26、算法，使得一方面投这就启发我们设计一种寻找完全标号三点组的算法，使得一方面投影到平面上看，计算不超过平面的一个有限区域，另一方面，计算影到平面上看，计算不超过平面的一个有限区域，另一方面，计算要不断向上发展，达到越来越高的层次。找到这样的算法，计算零要不断向上发展，达到越来越高的层次。找到这样的算法，计算零点的问题也就解决了，即找到了多项式的根的近似值。点的问题也就解决了，即找到了多项式的根的近似值。 第第2 2章代数方程的章代数方程的kuhnkuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性86 - 86 - 20202021-10-21202

27、1-10-212.2互补轮回算法互补轮回算法 互补轮回算法互补轮回算法 进口出口分析进口出口分析 第第2 2章代数方程的章代数方程的kuhnkuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性86 - 86 - 21212021-10-212021-10-212.2.1互补轮回算法互补轮回算法 在剖分为在剖分为t-1(,h)的的c-1平面上，用平面上，用qm(,h)（简记作（简记作qm）表示顶点）表示顶点是是+mh(1i)的方块，这里的方块，这里m是一个正整数。也就是说，是一个正整数。也就是说，qm是以是以为中心的、半边长为为中心的、半边长为mh的

28、方块，它的两对对边分别与的方块，它的两对对边分别与z平面上的平面上的x轴和轴和y轴平行。三角形的一条边称为一条棱。方块的边界轴平行。三角形的一条边称为一条棱。方块的边界qm(,h)（简记作（简记作qm）取平面上的逆时针方向为正的方向。并且，当写）取平面上的逆时针方向为正的方向。并且，当写(z，z是是qm上的一条棱时，蕴涵按上的一条棱时，蕴涵按qm的正定向的正定向z是是z的下一个点的下一个点。t-1(,h)的每个三角形，按照其顶点面逆时针顺序定向，并且，若的每个三角形，按照其顶点面逆时针顺序定向，并且，若写写z,z,z是是t-1(,h)的一个三角形，蕴涵其顶点顺序给出三角形的一个三角形，蕴涵其顶

29、点顺序给出三角形的正向。的正向。 平面上两点平面上两点z,z对另一点对另一点z*的的张角张角，是指射线，是指射线z*z和和z*z之间的不之间的不超过超过的夹角。也可以把它叫做的夹角。也可以把它叫做平面上线段平面上线段zz对另一点对另一点z*的张角的张角.第第2 2章代数方程的章代数方程的kuhnkuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性86 - 86 - 22222021-10-212021-10-21引理引理2-4 引理引理2-4设设 ，则，则qm上按照正向次序，恰有上按照正向次序，恰有n条标号为条标号为(1,2)的棱（即始端标号为的棱

30、（即始端标号为1终端标号为终端标号为2的棱），而没有标号为的棱），而没有标号为(2,1)的棱。的棱。 2n3m mh z z h 图2-7 第第2 2章代数方程的章代数方程的kuhnkuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性86 - 86 - 23232021-10-212021-10-21引理引理2-4的证明的证明 证明证明：设：设z,z是是qm上的一条棱，上的一条棱，z和和z对对的张角记作的张角记作。由图易知：由图易知： n32m1mhharctg0 记记为为w=(z-)n和和w=(z-)n对原点对原点o的张角，则的张角，则 32mn

31、n0 按照按照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条棱，始端标号为条

32、棱，始端标号为1，终端标号为，终端标号为2。 同样，由于同样，由于02/3，若，若l(z)=2，则，则l(z)=2或或3，所以，所以qm上上没有标号为没有标号为(2,1)的棱。的棱。 第第2 2章代数方程的章代数方程的kuhnkuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性86 - 86 - 24242021-10-212021-10-21引理引理2-5 引理引理2-5设设 ，则在，则在qm(,h)外没有外没有t-1(,h)的标的标号由号由(z-)n确定的完全标号三角形。确定的完全标号三角形。 4n)21(3m z z= =+ +h h( (m

33、 m+ +( (k k+ +1 1) )i i) ) z z= =+ +h h( ( (m m+ +1 1) )+ +k ki i) ) 图图2-8 证明：首先证明，若证明：首先证明，若zz是是qm上或上或qm外外的一条棱，则的一条棱，则zz对对的张角小于的张角小于2/3n。事实上，若事实上，若zz是平行于是平行于x轴或平行于轴或平行于y轴轴的棱，这已由引理的棱，这已由引理2-4的证明及的证明及保证。现只须考虑保证。现只须考虑zz是是t-1的三角形的斜的三角形的斜边的情况。根据边的情况。根据qm的构造，不难证明张角的构造，不难证明张角最大的情况发生在靠近最大的情况发生在靠近qm的地方。由于的地

34、方。由于对称性，只要证明对称性，只要证明k是自然数，而是自然数，而z=+h(m+1+ki)，z=+h(m+(k+1)i)时，时，zz对对的张角的张角小于小于2/3n2/3n即可。即可。 2n34n)21(3第第2 2章代数方程的章代数方程的kuhnkuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性86 - 86 - 25252021-10-212021-10-21kkmm1kmtg,1mkarctgm1karctg22 m221)12(m211m2)1m(m221kkmm1km22 对于整数对于整数k，不等式当然成立。再注意，不等式当然成立。再注

35、意/2，就有，就有 n32m2)21(tg 现设现设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-) )n确定的完全标号三角形。确定的完全标号三角形。 n3/2 由图由图2-82-8，第第2 2章代数方程的章代数方程的kuhnkuhn算法算法电子科技大学计算机学院电子科技大学计算机学院

36、顾小丰顾小丰计算的复杂性计算的复杂性86 - 86 - 26262021-10-212021-10-21引理引理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不是一个完全标号三点组。不是一个完全标号三点组

37、。 证明证明：若：若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矛盾。同样，若矛盾。同样，若或或亦引出矛盾。最后剩下亦引出矛盾。最后剩下,均不超过均不超过的情况，这时的情况，这时,就是相应各就是相应各对点之间的张角，按题设均小

38、于对点之间的张角，按题设均小于2/3，与，与+=2矛盾。矛盾。 第第2 2章代数方程的章代数方程的kuhnkuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性86 - 86 - 27272021-10-212021-10-21 w w w 0 图图2-9第第2 2章代数方程的章代数方程的kuhnkuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性86 - 86 - 28282021-10-212021-10-21按照按照 4n)21(3m确定方块确定方块qm(,h),h)，这里符号，这里符号 r r 表

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

40、可按任何预先给定的精度要求把何预先给定的精度要求把f的零点算出来。的零点算出来。 第第2 2章代数方程的章代数方程的kuhnkuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性86 - 86 - 29292021-10-212021-10-21kuhn算法算法 算法算法2-1依次从依次从qm的第的第j个标号为个标号为(1,2)的棱的棱z1,z2出发，出发，j=1,2,n，这，这n条棱是容易找到的。条棱是容易找到的。 步步1（二维搜索二维搜索）若若z3空白，对于空白，对于(1,2)棱，存在棱，存在c-1平面上唯一的平面上唯一的顶点顶点z使得使得z1,

41、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)的一个四面体，且顶点顺序给出空间的右手螺旋

42、方向。计的一个四面体，且顶点顺序给出空间的右手螺旋方向。计算算ll(z)，令，令zl=z，转步，转步2。第第2 2章代数方程的章代数方程的kuhnkuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性86 - 86 - 30302021-10-212021-10-21kuhn算法说明算法说明 按照算法按照算法2-1，我们已经可以编制，我们已经可以编制kuhn算法的计算机程序了，算法的计算机程序了，而前面的知识，只有剖分法和标号法是这里要用的。在步而前面的知识，只有剖分法和标号法是这里要用的。在步1，按照，按照剖分法确定剖分法确定z，按照标号法通过计算

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

44、大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性86 - 86 - 31312021-10-212021-10-212.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，计算

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

46、机学院 顾小丰顾小丰计算的复杂性计算的复杂性86 - 86 - 32322021-10-212021-10-21进口出口分析进口出口分析(续续1)步步2则是降维的情况，一个负向全标三角形则是降维的情况，一个负向全标三角形z1,z3,z2是上一步的结是上一步的结果。现在，要取消果。现在，要取消z3，计算从剩余的，计算从剩余的(2,1)棱出去。所以应该把棱出去。所以应该把负向全标三角形负向全标三角形叫做它自己的叫做它自己的进口进口。综上所述，综上所述，(1,2)棱棱或或z1,z3,z2是该三角形的是该三角形的进口进口，(2,1)棱棱或或z1,z2,z3是该三角形的是该三角形的出口出口。第第2 2章

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

48、个面，则因都有标号相重而不到一个全标三角形的面，而另外两个面，则因都有标号相重而不是全标三角形。是全标三角形。从四面体的内部看来从四面体的内部看来，正向全标三角形正向全标三角形z1,z2,z3是是进口进口，负向全标三角形负向全标三角形z1,z3,z2是是出口出口。 把把进口进口和和出口出口统称为统称为门门 第第2 2章代数方程的章代数方程的kuhnkuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性86 - 86 - 34342021-10-212021-10-212.2.2进口出口分析图示进口出口分析图示 2 1 1 1 2 3 1 3 2 1

49、2 3 3 第第2 2章代数方程的章代数方程的kuhnkuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性86 - 86 - 35352021-10-212021-10-21引理引理2-7 引理引理2-7对于顶点在集合对于顶点在集合1,2,3中取标号的一个标中取标号的一个标号三角形或四面体，或者它没有门，或者它正好有一号三角形或四面体，或者它没有门，或者它正好有一对门，一个是进口，一个是出口。对门，一个是进口，一个是出口。第第2 2章代数方程的章代数方程的kuhnkuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性

50、计算的复杂性86 - 86 - 36362021-10-212021-10-21引理引理2-7的证明的证明证明：按照门的定义，对于标号的三角形，如果它缺少标号证明：按照门的定义，对于标号的三角形，如果它缺少标号1 1或或2 2，则它没有门。对于标号，则它没有门。对于标号1 1，2 2具备的情况，若没有标号具备的情况，若没有标号3 3，则，则(1,2)(1,2)棱是进口，棱是进口，(2,1)(2,1)棱是出口，另一棱是棱是出口，另一棱是(1,l)(1,l)或或(2,2)(2,2)不是门，所以正不是门，所以正好是一对门。若三角形全标，在负向的情况，好是一对门。若三角形全标，在负向的情况，zz1 1

51、,z,z3 3,z,z2 2 是进口，是进口，(2,1)(2,1)棱是出口；在正向的情况下，棱是出口；在正向的情况下，(1,2)(1,2)棱是进口，棱是进口，zz1 1,z,z2 2,z,z3 3 是出是出口。不论正向负向，另两棱均有标号口。不论正向负向，另两棱均有标号3 3，不是门。所以也正好是一对，不是门。所以也正好是一对门。门。 对于标号的四面体，如果它缺少任何一个标号，则它没有全标三对于标号的四面体，如果它缺少任何一个标号，则它没有全标三角形的面，是一个无门的四面体。若四个顶点取全了角形的面，是一个无门的四面体。若四个顶点取全了1,2,31,2,3标号，则标号，则正好有一对顶点标号相重

52、。这时，以同标号棱为棱的两个面三角形均正好有一对顶点标号相重。这时，以同标号棱为棱的两个面三角形均非全标。另两个面三角形都是全标三角形，是一对被同标号棱撑开的非全标。另两个面三角形都是全标三角形，是一对被同标号棱撑开的三角形。这时，站在四面体内部，若一个全标三角形在正面，则另一三角形。这时，站在四面体内部，若一个全标三角形在正面，则另一个在背后。若一个是正向全标三角形，则另一个是反向全标三角形；个在背后。若一个是正向全标三角形，则另一个是反向全标三角形；反之亦然。反之亦然。 第第2 2章代数方程的章代数方程的kuhnkuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算

53、的复杂性计算的复杂性86 - 86 - 37372021-10-212021-10-21引理引理2-8 引理引理2-8按照算法按照算法2-12-1，从，从q qm m的每个的每个(1,2)(1,2)棱开始的棱开始的计算，可以一直进行下去。计算，可以一直进行下去。 证明证明：因为不论计算走到三角形或四面体，有进口就有：因为不论计算走到三角形或四面体，有进口就有出口，所以，计算可以一直进行下去。出口，所以，计算可以一直进行下去。 对于三角形或四面体，计算若能进来，则一定能对于三角形或四面体，计算若能进来，则一定能够出去。所以，今后不说进入，而说计算通过一个三够出去。所以，今后不说进入，而说计算通过

54、一个三角形或一个四面体。角形或一个四面体。 把有门的三角形和四面体看作是把有门的三角形和四面体看作是“人人”，两个看，两个看作是一双手。这样，作是一双手。这样，kuhnkuhn算法的曲线都是由许多人手算法的曲线都是由许多人手拉手连起来的。有了这个比喻，就容易理解，如果曲拉手连起来的。有了这个比喻，就容易理解，如果曲线会分叉或打圈，就一定有一些三只手的线会分叉或打圈，就一定有一些三只手的“人人”，与，与前面证明的每前面证明的每“人人”正好有一双手矛盾。正好有一双手矛盾。第第2 2章代数方程的章代数方程的kuhnkuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性

55、计算的复杂性86 - 86 - 38382021-10-212021-10-212.32.3kuhnkuhn算法的收敛性（一）算法的收敛性（一） 这一节我们将证明，按照算法这一节我们将证明，按照算法2-1从从qm上每个标号上每个标号(1,2)棱开始计算，都收棱开始计算，都收敛到多项式敛到多项式f的的一个零点。的的一个零点。第第2 2章代数方程的章代数方程的kuhnkuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性86 - 86 - 39392021-10-212021-10-21计算的单纯形序列计算的单纯形序列定义定义2-4对于整数对于整数j，1

56、jn，顺次记从，顺次记从qm上第上第j条条(1,2)棱棱开始的计算所通过的三角形（二维搜索时）或四面休（三维搜索时）开始的计算所通过的三角形（二维搜索时）或四面休（三维搜索时）为为j1,j2,.,jk,.，称它为第，称它为第j个个计算的单纯形序列计算的单纯形序列。 按照这种记法，按照这种记法，jk可能是一个三角形，也可能是一个四面体。可能是一个三角形，也可能是一个四面体。我们知道，空间不共线的三个点的凸包是我们知道，空间不共线的三个点的凸包是2维单纯形，三角形就是维单纯形，三角形就是2维维单纯形；空间不共面的四个点的凸包是单纯形；空间不共面的四个点的凸包是3维单纯形，四面体就是维单纯形，四面体

57、就是3维单维单纯形。采用上述记法，在需要区别的时候，我们用纯形。采用上述记法，在需要区别的时候，我们用2jk表示它是一个表示它是一个2维单纯形，即三角形；或写作维单纯形，即三角形；或写作dim(jk)=2，即，即jk的维数为的维数为2，表明，表明jk是一个是一个2维单纯形，即三角形。同样，表示维单纯形，即三角形。同样，表示3jk维单纯形，即四面维单纯形，即四面体；体；dim(jk)=3表明表明jk是一个是一个3维单纯形，即四面体。维单纯形，即四面体。第第2 2章代数方程的章代数方程的kuhnkuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性86

58、- 86 - 40402021-10-212021-10-21计算的点序列计算的点序列定义定义2-5对于整数对于整数j，1jn，记，记(zj1,dj1)为为j1的的不在不在qm的顶点，对于的顶点，对于k2，当，当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平面的投影，平面

59、的投影，zjk也称为第也称为第j个计算的点序个计算的点序列。列。第第2 2章代数方程的章代数方程的kuhnkuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性86 - 86 - 41412021-10-212021-10-21定义的说明定义的说明 注意，计算的单纯形序列中的单纯形的维数注意，计算的单纯形序列中的单纯形的维数只可能是只可能是2或或3，所以，所以dim(jk)dim(j,k-1)的情的情况不可能连续发生。下面我们还将知道（见推况不可能连续发生。下面我们还将知道（见推论论2-1），），dim(jk)dim(j,k-1)的情况，只能发的情况

60、，只能发生有限次，即对于每个计算序列，步生有限次，即对于每个计算序列，步2只能执只能执行有限多次。行有限多次。 下面我们先讨论一下算法的性状。下面我们先讨论一下算法的性状。第第2 2章代数方程的章代数方程的kuhnkuhn算法算法电子科技大学计算机学院电子科技大学计算机学院 顾小丰顾小丰计算的复杂性计算的复杂性86 - 86 - 42422021-10-212021-10-21引理引理2-9 引理引理2-9若若dim(jk)=2，则，则jk qm。 这就是说，二维搜索不会跑到这就是说，二维搜索不会跑到qm外面去。外面去。 证明证明：若不然，存在若不然，存在j,k使使dim(jk)=2，但，但j