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

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

1、计算的 复杂性,计算机科学与工程学院,86-22,2023/8/1,第2章代数方程的Kuhn算法,剖分法与标号法 互补轮回算法 Kuhn算法的收敛性Kuhn算法的复杂性,86-23,2023/8/1,引 言,与各种传统的迭代方法（例如Newton方法）不同，Kuhn算法基于空间的一种单纯剖分，一种整数标号法和一种互补轮回的算法过程。如果说它的叙述不象Newton方法那么简单，却应当指出，一旦编成计算机程序以后，它的使用反而是极其简单的。为了用Kuhn算法解任何一个代数方程，只要把这个代数方程所对应的多项式的复系数组和计算的精度要求输入机器。然后，算法就会把该代数方程的全部解一起算出。对于Kuh

2、n算法，不存在初值选择以及其他一些使用方面的棘手问题。这是一种具有很强的大范围收敛性保证的算法。另一方面，虽然算法本身不象一个简单的迭代公式那么简单，但为了编制计算机程序，知道2.1和2.2的内容就足够了。,86-24,2023/8/1,2.1剖分法与标号法,设f(z)是复变量z的n阶复系数的首一多项式，即f(z)=zn+a1zn-1+.+an，这里n是自然数，a1,.,an是复常数。如果复数满足f()=0，就说是多项式f的一个零点或代数方程f(z)=0的一个解。我们的算法就是要把f的零点找出来。记复数zxiy平面为C，复数wuiv平面为C，则wf(z)确定复平面之间的一个多项式映射f：CC。

3、为了在下一节叙述算法，我们先叙述半空间C-1,+)的一种剖分及由f导出的一种标号法。在C-1,+中，记Cd=Cd，d-1,0,1,2,.。给定剖分中心及初始格距h。,86-25,2023/8/1,剖分法,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；+(r+a)+i(s+b)h；+(r-b)+i(s+a)h。称剖分T-1(,h)中三角形直径之上界为T-1(,h)的剖分网径。易知，T-1(

4、,h)的剖分网径为h。,图2-1,86-26,2023/8/1,Cd平面的剖分,剖分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-2,86-27,2023/8/1,半空间C-1,+的剖分T(,h)（简记作T）,按照平面的剖分，C-1的每一个正方形（由共

5、有一斜边的一对三角形组成），与C0的一个正方形（也由共有一斜边的一对三角形组成）上下相对，而斜边相错。C-1和C0之间每一个由上下相对的一对正方形所界定的正四棱柱，按图2-3规则剖分成5个四面体。,图2-3,86-28,2023/8/1,5个四面体,86-29,2023/8/1,半空间C-1,+的剖分T(,h)（简记作T）,按照平面的剖分，Cd（d0）的每一个正方形与Cd+1的四个正方形上下相对，界定Cd和Cd+1之间的一个正四棱柱。Cd和Cd+1之间每一个这样的正四棱柱，按图2-4的规则剖分成14个四面体。,图2-4,86-210,2023/8/1,14个四面体,86-211,2023/8/

6、1,半空间C-1,+的剖分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)顶点集V(T(,h)，简记作V(T)。在下面叙述的算法里，主要牵涉到由剖分T中的四面体的界面三角形的顶点所组成的三点组(z1,d1),(z2,d2),(z3,d3)，或简记作z1,z2,z3。今后所说的三点组，都是这样的

7、三点组。,86-212,2023/8/1,引理2-1,引理2-1 设(z1,d1),(z2,d2),(z3,d3)是剖分T中的一个三点组，记d=mind1,d2,d3，有ddkd+1，k=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-z2|,|z2-z3|,|z3-z1|，也可简记作diamz1,z2,z3。,

8、86-213,2023/8/1,引理2-2,引理2-2 设三点组z1,z2,z3位于Cd和Cd+1之间，则,证明：从图2-3和图2-4容易看出，位于Cd和Cd+1之间的所有可能的三点组的直径不超过。,所以层数越高，三点组的直径越小。,86-214,2023/8/1,标号法,86-215,2023/8/1,标号的定义,定义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导出的V(T(,h)的标号法：,86-216,2023/8/1

9、,标号的图示,图2-5 标号区域,86-217,2023/8/1,全标三点组,定义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-)n还是由f确定的。事实上，今后我们遇到的全标三点组，其点的标号可以都由(z-)n确定，也可以都由f确定，还可以部分由(z-)n确定，部分由f确定。,86-218,2023/8/1,引理2-3,引理2-3设z1,z2,z3是标号都由

10、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的距离均不起过。这样，f(z1)必须落在图2-6的菱形阴影区域内，所以,同理，,。,86-219,2023/8/1,引理2-3的说明,大家知道，多项式函数在平面的有限区域上是一致连续的，假如我们能够找到直径很小的标号都由f确定的完全标号三点组，那么，这三点的象在w平面上的相互距离也很小。再由引理2-3，每点的象与w平面的原点的距离也就很小了。当

11、这个距离足够小时，三点组的每一个点都可以足够精确地作为f的一个数值零点。前面已经说明，按照我们的剖分，层数越高时，三点组的直径就越小。这就启发我们设计一种寻找完全标号三点组的算法，使得一方面投影到平面上看，计算不超过平面的一个有限区域，另一方面，计算要不断向上发展，达到越来越高的层次。找到这样的算法，计算零点的问题也就解决了，即找到了多项式的根的近似值。,86-220,2023/8/1,2.2互补轮回算法,互补轮回算法 进口出口分析,86-221,2023/8/1,互补轮回算法,在剖分为T-1(,h)的C-1平面上，用Qm(,h)（简记作Qm）表示顶点是+mh(1i)的方块，这里m是一个正整数

12、。也就是说，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*的张角.,86-222,2023/8/1,引理2-4,引理2-4设，则Qm上按照正

13、向次序，恰有n条标号为(1,2)的棱（即始端标号为1终端标号为2的棱），而没有标号为(2,1)的棱。,图2-7,86-223,2023/8/1,引理2-4的证明,证明：设z,z是Qm上的一条棱，z和z对的张角记作。由图易知：,记为w=(z-)n和w=(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

14、上正好有n条棱，始端标号为1，终端标号为2。同样，由于02/3，若l(z)=2，则l(z)=2或3，所以Qm上没有标号为(2,1)的棱。,86-224,2023/8/1,引理2-5,引理2-5设，则在Qm(,h)外没有T-1(,h)的标号由(z-)n确定的完全标号三角形。,图2-8,证明：首先证明，若zz是Qm上或Qm外的一条棱，则zz对的张角小于2/3n。事实上，若zz是平行于x轴或平行于y轴的棱，这已由引理2-4的证明及保证。现只须考虑zz是T-1的三角形的斜边的情况。根据Qm的构造，不难证明张角最大的情况发生在靠近Qm的地方。由于对称性，只要证明k是自然数，而z=+h(m+1+ki)，z

15、=+h(m+(k+1)i)时，zz对的张角小于2/3n即可。,86-225,2023/8/1,对于整数k，不等式当然成立。再注意/2，就有,现设z,z,z是T-1(,h)的在Qm外的一个三角形，则它的每条棱对的张角均小于。记w=(z-)n，w=(z-)n，w=(z-)n，则w，w，w中每两点对原点的张角均小于2/3。所以，按下述引理2-6，z,z,z不是标号由(z-)n确定的完全标号三角形。,由图2-8，,86-226,2023/8/1,引理2-6,引理2-6设z,z,z是z平面上的一个三点组，它们在w平面上的映射象分别为w,w,w（这里所说的映射，对三点组的各点可以并不相同，可以是w=(z-

16、)n，也可以是w=f(z)。那么，若w,w,w均不为0，且其中任两点在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矛盾。同样，若或亦引出矛盾。最后剩下,均不超过的情况，这时,就是相应各对点之间的张角，按题设均小于2/3，与+=2矛盾。,86-227,2023/8/1,图2-9,86-22

17、8,2023/8/1,按照,确定方块Qm(,h)，这里符号r表示不小,实数r的最小整数。算法就是要从Qm上每个标号为(1,2)的棱出发，找寻完全标号三点组。如果全标三点组的标号不全是由f确定的，则它未能提供足够的关于f的零点位置的信息。但2.3将证明，按照下述算法，计算将在越来越高的层次上面进行，而在高层（事实上在除C-1外的各层），标号均由f确定。这样，按照引理2-3，我们可按任何预先给定的精度要求把f的零点算出来。,86-229,2023/8/1,Kuhn算法,算法2-1依次从Qm的第j个标号为(1,2)的棱z1,z2出发，j=1,2,n，这n条棱是容易找到的。步1（二维搜索）若z3空白，

18、对于(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)，令zl=z，转步2。,86-230,2023/8/1,Kuhn算法说明,按照算法2-1，我们已经可以编制Kuhn算法的计算机程序

19、了，而前面的知识，只有剖分法和标号法是这里要用的。在步1，按照剖分法确定z，按照标号法通过计算(z-)n得到l(z)。在步3，按照剖分法确定z，按照标号法通过幂函数计算(z-)n（当d=-1）或多项式计算f(z)（当d0）得到l(z)。算出l=l(z)以后，令zl=z的做法，是一个同标号替换的做法：用z（新的点）取代原有的与z标号相同的顶点（旧的点）。这种做法，叫做互补轮回算法。,86-231,2023/8/1,进口出口分析,我们分析一下算法2-1中的各步。步1从(1,2)棱出发找到z，这时我们说计算进入三角形z1,z2,z。步3从三角形z1,z2,z3出发找到z，我们说计算进入四面体z1,z

20、2,z3,z。在步1的情况，如果l(z)=1或2，得到的还是一个标号(1,2)的棱，下一次还是执行步1，计算将进入另一个三角形。从本三角形内部看来，三角形边界按逆时针定向，我们很自然地把正向(1,2)棱称作计算的进口，负向(2,1)棱则是计算的出口。如果l(z)=3，得到正向全标三角形z1,z2,z3，计算将离开三角形而进入四面体。这样，还应该把正向全标三角形叫做它自己的出口。,86-232,2023/8/1,进口出口分析(续1),步2则是降维的情况，一个负向全标三角形z1,z3,z2是上一步的结果。现在，要取消z3，计算从剩余的(2,1)棱出去。所以应该把负向全标三角形叫做它自己的进口。综上

21、所述，(1,2)棱或z1,z3,z2是该三角形的进口，(2,1)棱或z1,z2,z3是该三角形的出口。,86-233,2023/8/1,进口出口分析(续2),步3的情况，由于维数没有变动，所以简单得多。对于一个四面体，已经有一个面是全标三角形，那么不论第四个点的标号l(z)如何，都正好和某一个顶点标号相同。这样同标号替换以后，又得到一个全标三角形的面，而另外两个面，则因都有标号相重而不是全标三角形。从四面体的内部看来，正向全标三角形z1,z2,z3是进口，负向全标三角形z1,z3,z2是出口。把进口和出口统称为门,86-234,2023/8/1,进口出口分析图示,86-235,2023/8/1

22、,引理2-7,引理2-7对于顶点在集合1,2,3中取标号的一个标号三角形或四面体，或者它没有门，或者它正好有一对门，一个是进口，一个是出口。,86-236,2023/8/1,引理2-7的证明,证明：按照门的定义，对于标号的三角形，如果它缺少标号1或2，则它没有门。对于标号1，2具备的情况，若没有标号3，则(1,2)棱是进口，(2,1)棱是出口，另一棱是(1,l)或(2,2)不是门，所以正好是一对门。若三角形全标，在负向的情况，z1,z3,z2是进口，(2,1)棱是出口；在正向的情况下，(1,2)棱是进口，z1,z2,z3是出口。不论正向负向，另两棱均有标号3，不是门。所以也正好是一对门。对于标

23、号的四面体，如果它缺少任何一个标号，则它没有全标三角形的面，是一个无门的四面体。若四个顶点取全了1,2,3标号，则正好有一对顶点标号相重。这时，以同标号棱为棱的两个面三角形均非全标。另两个面三角形都是全标三角形，是一对被同标号棱撑开的三角形。这时，站在四面体内部，若一个全标三角形在正面，则另一个在背后。若一个是正向全标三角形，则另一个是反向全标三角形；反之亦然。,86-237,2023/8/1,引理2-8,引理2-8按照算法2-1，从Qm的每个(1,2)棱开始的计算，可以一直进行下去。,证明：因为不论计算走到三角形或四面体，有进口就有出口，所以，计算可以一直进行下去。对于三角形或四面体，计算若

24、能进来，则一定能够出去。所以，今后不说进入，而说计算通过一个三角形或一个四面体。把有门的三角形和四面体看作是“人”，两个看作是一双手。这样，Kuhn算法的曲线都是由许多人手拉手连起来的。有了这个比喻，就容易理解，如果曲线会分叉或打圈，就一定有一些三只手的“人”，与前面证明的每“人”正好有一双手矛盾。,86-238,2023/8/1,2.3Kuhn算法的收敛性（一）,这一节我们将证明，按照算法2-1从Qm上每个标号(1,2)棱开始计算，都收敛到多项式f的的一个零点。,86-239,2023/8/1,计算的单纯形序列,定义2-4对于整数j，1jn，顺次记从Qm上第j条(1,2)棱开始的计算所通过的

25、三角形（二维搜索时）或四面休（三维搜索时）为j1,j2,.,jk,.，称它为第j个计算的单纯形序列。按照这种记法，jk可能是一个三角形，也可能是一个四面体。我们知道，空间不共线的三个点的凸包是2维单纯形，三角形就是2维单纯形；空间不共面的四个点的凸包是3维单纯形，四面体就是3维单纯形。采用上述记法，在需要区别的时候，我们用2jk表示它是一个2维单纯形，即三角形；或写作dim(jk)=2，即jk的维数为2，表明jk是一个2维单纯形，即三角形。同样，表示3jk维单纯形，即四面体；dim(jk)=3表明jk是一个3维单纯形，即四面体。,86-240,2023/8/1,计算的点序列,定义2-5对于整数

26、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平面的投影，zjk也称为第j个计算的点序列。,86-241,2023/8/1,定义的说明,注意，计算的单纯形序列中的单纯形的维数只可能是2或3，所以dim(jk)dim(j,k-1)的情况不可能连续发生。下面我们还将知道（见推论2-1），dim(jk)

27、dim(j,k-1)的情况，只能发生有限次，即对于每个计算序列，步2只能执行有限多次。下面我们先讨论一下算法的性状。,86-242,2023/8/1,引理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，所以j,k-1和jk有一条公共棱在Qm上，具有标号1和2。若该棱是(1,2)棱，则它是内三角形j,k-1的进口，与由j,

28、k-1到jk的计算顺序矛盾；若该棱是(2,1)棱，则与引理2-1矛盾。若dim(j,k-1)=3，按照算法2-1（步2），j,k是Qm外一个z1,z3,z2全标三角形，与引理2-5矛盾。,86-243,2023/8/1,换一个角度分析进口出口,上节已证明，对于T-1中的三角形或T中的四面体，或者它没有门，或者它正好有一对门，一个是进口，一个是出口。但是，门之作为进口或作为出口，是相对于三角形或四面体而言的。例如图2-12（字母表示顶点，脚标表示该顶点的标号），B1C2是一个门，对于三角形BAC来说，它是出口，对于三角形BCD来说，它是进口。又如B1C2D3这个门，对于三角形BCD本身来说，它是

29、出口，从二维搜索转入三维搜索的出口；对于四面体BCDE来说，它是进口，从二维搜索进入三维搜索的进口。再如B1E2D3这个门，是BCDE的出口，又是BEDF的进口。如果一个门是某个三角形或四面体的出口，我们称该三角形或四面体为这个门的上方单纯形；如果一个门是某个三角形或四面体的进口，我们称该三角形或四面体为这个门的下方单纯形。,86-244,2023/8/1,图2-12,86-245,2023/8/1,引理2-10,引理2-10对于任何一个不在Qm上的门，它的上方单纯形和下方单纯形都是唯一存在的。,对于Qm上的门，它就是我们算法的起始棱，相应的结论是：它的下方单纯形是唯一存在的。,86-246,

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

31、z1,z3,z2时，它的上方单纯形是它本身，它的下方单纯形是T(,h)中以三角形z1z3z2为一个面的四面体，这样的四面体也是唯一的。当它不在T-1(,h)中时，由于任何一个不在T-1(,h)中三角形是且仅是两个四面体的一个公共面，因此这两个四面体一个是门的上方单纯形，另一个是该门的下方单纯形。,86-247,2023/8/1,引理2-11,引理2-11若(j,k)(i,l)，则jkil。,这就是说，在剖分并标号的半空间中，T-1的每个三角形和T的每个四面体，都顶多只允许计算通过一次。,86-248,2023/8/1,引理2-11的证明,证明：首先注意，jk=il，k1，l1蕴涵j,k-1=i

32、,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个(1,2)棱就是作为il进口的第i个(1,2)棱，所以i=

33、j。这与所设(j,k)(i,l)矛盾。,86-249,2023/8/1,推论2-1,推论2-1对于每个j，1jn，存在Kj使得kKj时，dim(jk)=3。,即：每个计算的单纯形序列除了开始的有限一段外，都由三维单纯形四面体组成。所以三维搜索是本质的。,证明：二维搜索只能在Qm内进行，Qm内三角形数目有限(8m2个)，每个三角形顶多允许计算通过一次。,注意，我们说每个三角形或每个四面休顶多允许计算通过一次，并不是说每个顶点顶多只允许计算一次。例如在图2-12中，若A2,B1,C2,D3依旧，但E的标号不是2而是3，那么下一次就应当计算A而不是F，A已被重复计算。所以，由(j,k)(i,l)不能

34、推出(zjk,djk)(zil,dil)。,86-250,2023/8/1,引理2-12,引理2-12存在（依赖于,h和多项式f的）R0，使得C(R)-1,+)外没有完全标号三角形，这里C(R)=z|z|R。,这就是说，三维搜索不会跑到C(R)-1,+)外面去。,86-251,2023/8/1,引理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,+)外，

35、所以,86-252,2023/8/1,。,注意，当z,z均由w=(z-)n标号时，不等式右端第二项和第三项均可去掉；当z,z之一由w=(z-)n标号，而另一个由w=f(z)标号时，不等式右端第二顶和第三项的系数2均可去掉。但是不论在任何情况，上述形式的不等式均成立。因此，,这样，据引理2-6，T(,h)位于C(R)-1,+外的所有三点组均非完全标号三点组。,86-253,2023/8/1,图2-13,86-254,2023/8/1,定理2-1,定理2-1投影到复平面上看，每个计算的点序列都有聚点。证明：对于每个整数j，1jn，zjk是一个序列。按照该序列的构造（定义2-5），注意QmC(R)，

36、二维搜索不超出Qm，三维搜索不超出C(R)-1,+)，可知zjkC(R)。但C(R)作为平面有界闭区域是紧致的，所以无穷序列zjk在C(R)中必有聚点。,86-255,2023/8/1,定理2-2,定理2-2设z*是计算的点序列zjk的一个聚点，则f(z*)=0。即：计算的点序列的聚点，都是多项式的零点。,86-256,2023/8/1,定理2-2的证明,证明：考虑计算的单纯形序列jk，这是一个没有重复的无穷的单纯形序列（引理2-11和引理2-8）。按照T(,h)的构造，QmC-1内的三角形数目有限，以C(R)为底的大圆柱内位于任何有限高度以下的四面体数目有限，但jk只能由不重复的Qm内的三角

37、形和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),d(k)，则有,86-257,2023/8/1,事实上，取,注意，为了这里证明叙述的方便，子序列的写法与定义2-5不同，号码j也省略了。现在，为了证明f(z*)=0，利用多项式

38、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以上的完全标号三点组，那么,86-258,2023/8/1,所以，据引理2-3，因z(k)是该三点组之一点，。,同理，,86-259,2023/8/1,代数基本定理,直到现在为止，我们没有预先假定多项式f的零点的存在。但是我们构造了算法，证明了这个算法所产生的每个计算的点序列在复平面上都有聚点，而这种聚点都是多项式的零点。这样，我们也就构造性地证明了以下定理。,

39、定理2-3设f(z)=zn+a1zn-1+.+an，其中n为自然数，z为复变量，a1，.，an为复常数，则f(z)必有零点。,至此，我们可以把多项式写成乘积的形式，并叙述零点的重数的概念。这就是下面的定义。,定义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-260,2023/8/1,2.4Kuhn算法的收敛性（二）,这一节我们将进一步证明，每个计算的点序列只收敛到多项式的一个零点；

40、从Qm上n个标号为(1,2)的棱开始的n个计算的点序列正好收敛到多项式的全部n个零点。,86-261,2023/8/1,定理2-4,定理2-4每个计算的点序列都收敛到多项式的一个零点。,86-262,2023/8/1,定理2-4的证明,86-263,2023/8/1,不妨设K足够大，使得当kK时，计算点序列的投影步长（在相应高度的三点组的投影直径）不超过r。再不妨设kk*，则序列Zjk从k=k*到k=k一段与C之交非空，因为它以不超过r的步长，不可能从距z*小于r的地方一步跨到距z小于r的地方。由于K的任意性，可知zjkC也是一个无穷序列，而C是平面有界闭集，由它的紧致性，存在zC是zjkC的

41、聚点，当然，z也是zjk的聚点，且zz，zz*。,再挖去分别以z,z,z*为中心的半径 的三个开圆重复上述讨论，又可得第4个聚点。这样做下去，zjk在C(R)有无穷多个聚点，于是据定理2-2，多项式f在C(R)有无穷多个零点。这样一来，必须f(z)0。这与所设f是阶数n大于0的首一多项式矛盾。,86-264,2023/8/1,组合的Stokes定理,下面，我们先对没有重零点的情况证明n个计算的点序列正好收敛到多项式的n个零点，然后再推广到一般情况。为此要作若干准备。定理2-5设Q是平面有界区域（连通或不连通），剖分成为有限个具有正的定向的三角形，各顶点的标号为1或2或3。称Q上的(1,2)标号

42、棱和Q内的标号为(1,3,2)的三角形为Q的进口（源）；Q上的(2,1)标号棱和Q内的标号为(1,2,3)的三角形为Q的出口（渊）。那么，对于Q，进口的数目和出口的数目相等。,86-265,2023/8/1,组合的Stokes定理的证明,证明：据所设，Q内三角形数目及Q上棱的数目都有限，所以进口的数目和出口的数目当然有限，对于每个进口，若它是Q上的(1,2)标号棱，则由它出发执行算法2-1中的步1；若它是Q内的标号(1,3,2)的三角形，则取消标号为3的顶点后，开始执行步1。这样做下去，或者找到Q内一个标号(1,2,3)三角形；或者互补轮迴过程将超出Q，在通过Q超出Q的地方将给出一个(2,1)

43、标号棱。所以，从每个进口出发的步1互补轮迴过程，都以找到一个出口结束。由于引理2-7及引理2-10，互补轮迴过程按进退两个方向都是唯一决定的。所以，对于每个出口，反方向执行步1（对(1,2,3)标号三角形要先取消标号为3的顶点），同样必终止于一个进口，这就完成了定理的证明。,86-266,2023/8/1,图2-15,86-267,2023/8/1,组合的Stokes定理的说明,注意，定理2-5中的Q比算法中的Qm一般得多，我们可以对任何剖分为三角形的平面有限区域进行观察，不管各顶点怎样随机地得到1或2或3的号码，总是进口等于出口。图2-15是一个例子，其中表示进口，表示出口。注意，对于组合的

44、Stokes定理，平面上的曲边三角形也是允许的。由定理2-1，定理2-2，以及定理2-3，已经可以将多项式改写为：,这里1,2,.,n是代数基本定理保证的多项式f的n个精确零点。,86-268,2023/8/1,引理2-13,引理2-13设j是多项式f(z)的一个单零点，1jn。则顶多只有一个计算的点序列收敛到j。,86-269,2023/8/1,附近，f近似于一个线性函数，近似于复平面的以z=j为中心的乘以常数因子,w=f(z)计算|argf(z)|所引起的误差小于/24；用,引理2-13的证明,证明：在z=j附近，,。即在z=j,的旋转。所以，存在以z=j为中心的半径足够,小的圆域，对这个

45、圆域内的任两点，用,代替,代替w=f(z)计算|argf(z)/f(z)|引起的误,差小于/12（下面第三章引理3-1将具体给出小圆域半径的一个估计）。,86-270,2023/8/1,在剖分为Td的Cd平面上，设z=j所在的一个三角形是，与有共同顶点的所有三角形的点集并的凸包为T()。当d足够大因而剖分足够细时，总可以使得T()整个位于上述小圆域内。我们要证明，小圆域内有且只有一个完全标号三角形，且其定向为正。记T()的边界为T，易知T的每一条棱对的每一点的张角都在,之间。所以T的,的象在w平面上按正向绕原点，每,一步(相当于T的一条棱)所转过的角在,之间。这样，T的w=f(z),象在w平面

46、上按正向绕原点，每一步所转过的角在,和,之间。所以，按照标号法，T上正好有一个标号(1,2)的,棱，没有标号(2,1)的棱。根据组合的Stokes定理，T()内正向全标形比负向全标形正好多一个。,86-271,2023/8/1,下面证明小圆域内没有负向全标形。考虑w平面上决定标号的三个顶角各为 的扇形在z平面上以z=j为中心的小圆域内关于 的逆象。我们有图2-17，其中(1)表示标号肯定为1的扇形区域，(1,2)表示标号可能是1或2的扇形区域，等等。显然，的顶角为，不包括边界；的顶角为。,86-272,2023/8/1,图2-16,图2-17,86-273,2023/8/1,设z1,z2,z3

47、是圆域内一个负向全标三角形。若至少有两点在中（图2-17中A,B,C三种情形），则必有一角大于，与剖分矛盾；在只有一点在的情形，若一点在相邻的，另一点在对面的（图2-17中的D），则必有一内角大于；若另两点分别在相邻的两个中（图2-17中的E），则必有一内角大于，都与剖分矛盾；在三点都不在的情形，如果三点在不同的，则它不是负向全标形。所以必有两点在同一。,综上所述，只剩下两点在同一，第三点在与此不相邻的区域的情形需要讨论。不妨设z2,z3(2,3)，z1(3,1)(1)(1,2)。,86-274,2023/8/1,若jz1z3z2，则z1，与剖分矛盾。所以jz1z3z2。由对称性，不妨设z2,

48、j在z1z3两侧。z1z3与(3,1)(1)(1,2)的边界的交点为z。考虑沿通过j的射线，令z3向j移动，z2背向j移动（图2-18），这是一个使z2zz3增大的过程，显然有上界。所以z1z2zz3。若z3=，则z2z3=z1z3jz3，所以jz2z3，zz3j-，这就引出 zjz3+jz3z的矛盾。若z2=，则z2z3=z1z2z2j，z2z3jz2jz3，引出jz2z3的矛盾。,86-275,2023/8/1,所以，圆域内没有负向全标等腰直角三角形。这样，据组合的Stokes定理，T()内有且只有一个全标三角形，其定向为正。再设zz”是圆域内T()外的任一棱，易知zz”对j（在内)的张角

49、不超过，所以f(z)，f(z”)对原点的张角不超过。因此，据引理2-6，圆域内T()外没有全标三角形。至此，我们证明了，当d足够大因而剖分足够细时，以z=j为中心的上述小圆域内总是有且只有一个全标三角形，并且它是正向全标三角形这样，按照算法，顶多只有一个计算的单纯形序列能无限接近j。所以，顶多只有一个计算的点序列收敛到j。,86-276,2023/8/1,引理2-13的说明,注意，引理的证明排除了小圆域内有任何负向完全标号的等腰直角三角形的可能性，即使该三角形不是剖分中的三角形。最后，还需要有关于多项式零点是多项式系数的连续函数的下述引理。,86-277,2023/8/1,引理2-14,引理2

50、-14首一多项式的零点，是多项式系数的连续函数。,86-278,2023/8/1,证明：回忆定义2-6，设f(z)=zn+a1zn-1+.+an=(z-1)k1.(z-j)kj，1,.,j互不相同，j及k1,.,kj均为正整数。当然，k1+.+kj=n。对于任何m，1mj，可取0，使得在z|z-m|内m是唯一的零点。根据复变函数论中的幅角原理，有,引理2-14的证明,注意上式左端是整数，而右端是系数a1,.,an的连续函数。所以当a1,.,an变化很小时，上述积分保持不变，也就是说当a1,.,an变化很小时，z|z-m|内多项式的零点数目（按重数计算）保持km不变。,最后，根据足够小的任意性，