资源描述：
《《计算的复杂性》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、计算的复杂性计算机科学与工程学院第2章 代数方程的Kuhn算法剖分法与标号法互补轮回算法Kuhn算法的收敛性Kuhn算法的复杂性8/12/202186-引言与各种传统的迭代方法（例如Newton方法）不同，Kuhn算法基于空间的一种单纯剖分，一种整数标号法和一种互补轮回的算法过程。如果说它的叙述不象Newton方法那么简单，却应当指出，一旦编成计算机程序以后，它的使用反而是极其简单的。为了用Kuhn算法解任何一个代数方程，只要把这个代数方程所对应的多项式的复系数组和计算的精度要求输入机器。然后，算法就会把该代数方程的全部解一起算出。对于Kuhn算法，不存在初值选择以及其他一些
2、使用方面的棘手问题。这是一种具有很强的大范围收敛性保证的算法。另一方面，虽然算法本身不象一个简单的迭代公式那么简单，但为了编制计算机程序，知道2.1和2.2的内容就足够了。8/12/202186-2.1剖分法与标号法设f(z)是复变量z的n阶复系数的首一多项式，即f(z)=zn+a1zn-1+...+an，这里n是自然数，a1,...,an是复常数。如果复数ξ满足f(ξ)=0，就说ξ是多项式f的一个零点或代数方程f(z)=0的一个解。我们的算法就是要把f的零点找出来。记复数z＝x＋iy平面为C，复数w＝u＋iv平面为C'，则w＝f(z)确定复平面之间的一个多项式映射f：C→C
3、'。为了在下一节叙述算法，我们先叙述半空间C×[-1,+∞)的一种剖分及由f导出的一种标号法。在C×[-1,+∞]中，记Cd=C×{d}，d＝-1,0,1,2,...。给定剖分中心ž及初始格距h。8/12/202186-2.1.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
4、-1(ž,h)中三角形直径之上界为T-1(ž,h)的剖分网径。易知，T-1(ž,h)的剖分网径为h。图2-18/12/202186-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-28/12
5、/202186-半空间C×[-1,+∞]的剖分T(ž,h)（简记作T）按照平面的剖分，C-1的每一个正方形（由共有一斜边的一对三角形组成），与C0的一个正方形（也由共有一斜边的一对三角形组成）上下相对，而斜边相错。C-1和C0之间每一个由上下相对的一对正方形所界定的正四棱柱，按图2-3规则剖分成5个四面体。图2-38/12/202186-5个四面体8/12/202186-半空间C×[-1,+∞]的剖分T(ž,h)（简记作T）按照平面的剖分，Cd（d≥0）的每一个正方形与Cd+1的四个正方形上下相对，界定Cd和Cd+1之间的一个正四棱柱。Cd和Cd+1之间每一个这样的正四棱柱，
6、按图2-4的规则剖分成14个四面体。图2-48/12/202186-14个四面体8/12/202186-半空间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)。在下面叙述的算法里，主要牵涉
7、到由剖分T中的四面体的界面三角形的顶点所组成的三点组{(z1,d1),(z2,d2),(z3,d3)}，或简记作{z1,z2,z3}。今后所说的三点组，都是这样的三点组。8/12/202186-引理2-1引理2-1设{(z1,d1),(z2,d2),(z3,d3)}是剖分T中的一个三点组，记d=min{d1,d2,d3}，有d≤dk≤d+1，k=1,2,3。该引理由剖分法的定义直接得到。在引理2-1的情况，我们说三点组{z1,z2,z3}位于Cd和Cd+1之间。特别地，当d1=d2=d3=d时，我们说三
