毕业论文（设计）同伦方法求解矩阵的特征值.pdf

哈尔滨工业大学理学硕士学位论文摘要本文主要研究的是川同伦算法求解矩阵的特征值问题。特征值问题在数学 和其他领域里有很多应川，如线性微分方程组稳定性和渐进估计的研究，球面 上二次函数稳定点求解及约束特征值问题等。同伦算法是19世纪70年代开始发展起来的求解非线性问题的一种有效的 方法。它克服了传统迭代法初值难选取以及局部收敛的弱点，同伦算法对初值 的选取没有严格限制，能够保证全局收敛，并且很容易实施并行计算。本文的主要工作：首先，阐述了特征值问题相关算法的发展历史、国内外 发展状况，研究领域，以及同伦算法的发展史等。其次，研究了三对角矩阵的性质、进行一些理论分析并通过公式计算对相 应的三对角矩阵的特征值和特征向量，利于与同伦算法求特征值比较。最后，着重介绍了同伦算法的发展及基本思想、阐述了同伦算法的基本理 论，给出了求解对称矩阵特征值的同伦映射的构造及其相关性质，跟踪同伦路 径进行求解，并根据具体算例进行误差分析。并把同伦算法和其它几种算法进 行比较分析。关键词：特征值；三对角矩阵；同伦映射；广义逆I哈尔滨工业大学理学硕士学位论文AbstractThis article studies the homotopy algorithm using matrix eigenvalue problem.Eigenvalue problem in mathematics and other fields,there are many applications,such as the stability of linear differential equations and asymptotic estimation of the sphere stability point of solving quadratic eigenvalue problems and constraints.Homotopy method is developed seventies began to solve nonlinear problems is an effective way.It is to overcome the initial difficulties of the traditional iterative method selected,and the weakness of local convergence,homotopy algorithm,the selection of the initial value is not strictly limited to ensure global convergence,and very easy to implement parallel computing.This article mainly:First,set the eigenvalue problem related to algorithm development history of its development,research,and the history of the development of homotopy algorithm,etc.Secondly,the study of three diagonal matrices,some theoretical analysis and through the corresponding formula tridiagonal matrix eigenvalues and eigenvectors,which will help with the homotopy algorithm to solve the eigenvalue comparison.Finally,focusing on the development of the homotopy algorithm and the basic idea,explained the basic theory of the homotopy algorithm is given Symmetric Matrix Eigenvalue homotopic mapping and related properties of the structure,the homotopy path tracking solution,and According to the error analysis of specific examples.And the homotopy method and the comparative analysis of other schemes.Keywords:Eigenvalues,Tridiagonal matrix,Homotopy map,Generalized inverseii哈尔滨工业大学理学硕士学位论文目录摘要.IAbstract.I I目 录.I I I第1章绪论.11.1 课题背景与来源.11.2 矩阵特征值算法概述及其研究现状.21.2.1 特征值问题算法.21.2.2 同伦算法在国内外的研究现状及分析.41.3 本论文研究的主要内容.1第2章三对角矩阵.22.1 特殊三对角矩阵的基本性质.22.1.1 Jacobi 矩阵.32.2 对称三角矩阵.42.2.1 对称三对角矩阵性质.42.2.2 非对称三对角矩阵化为对称三对角矩阵.52.3 本章小结.7第3章同伦算法.83.1 同伦算法的概述.83.2 同伦映射的构造.123.2.1 不动点同伦映射.133.2.2 凸同伦映射.143.2.3 牛顿同伦映射.153.2.4 修正的同伦映射.153.3 微分方程的初值问题跟踪曲线.163.3.1 参数微分法.163.3.2 弧长微分法.173.4 本章小结.19第4章同伦方法求解矩阵特征值.204.1 构造特征值同伦映射.204.2 数值试验.25ill哈尔滨工业大学理学硕士学位论文4.3 算法的比较.294.4 本章小结.33结论.34参考文献.35哈尔滨工业大学硕士学位论文原创性声明.38哈尔滨工业大学硕士学位论文使用授权书.38致谢.39IV哈尔滨工业大学理学硕士学位论文第1章绪论1.1 课题背景与来源特征值问题的解法长期以来对我们就有一种特殊的关注，因为它充分显示 出所谓经典数学与实川数值分析之间的差异。随着电子计算机的普及以及电子 技术的迅猛发展，矩阵特征值特征向量的计算越来越被从事计算数学的人们所 关注。因为无论是数学领域，还是其它领域，比如计算化学、计算物理、控制 论、信息论等领域，都离不开特征值问题的求解。可以说，特征值问题成了数 值分析的核心与出发点。矩阵计算是科学与工程计算的核心，可以毫不夸张的 讲，大部分科学与工程问题都要归结为矩阵的问题，其中具有挑战的问题是大 规模矩阵的计算问题。矩阵计算的基本问题有三个：其一，求解线性方程组问 题；其二，线性最小二乘问题；其三，矩阵特征值问题。在工程上，矩阵的特征值具有广泛的应川，如结构力学中的固有频率分析 问题以及控制系统中的稳定性，大型桥梁或建筑物的振动问题，机械和机件的 振动问题，飞机机翼的颤振问题，无线电电子学及光学系统的电磁振动问题，调节系统的自振动问题以及声学和超声学系统的振动问题，都与矩阵的特征值 密切相关；又如天文、地震、信息系统、经济学中的一些问题也关系到矩阵的 特征值。在科学上，计算流体力学、统计计算、量子力学、化学工程和网络排 队的马尔可夫链模拟等实际问题，最后也都要归结为矩阵的特征值问题。自Wilkinson于1965年发表著作代数特征值问题以来，在这方面已经 进行了大量的工作，并取得了重大的进展。在EISPACK程序包中，包含有许 多经典的方法，其广泛使用的效果在提高不同应用领域里的算法水平有着重要 意义。科学家和工程师们可以量体裁衣地按照他们各自特有的需要组装出更为 复杂的软件工具。这就激励着人们去写出结构优良、适川范围广、精确度高的 算法。这篇文章就是在这样的背景下产生的。传统的数值迭代法存在的最大问题是方法的有效性依赖于初值的选取初值 选取不当常导致迭代过程不收敛，而且一次只能求出问题的一个数值解。提出 的区间分析法虽能在较大范围内收敛，可判断在给定的区域内有无解，并对有 解区间求出其中的全部解，但它仍存在选择合适的初值区间的问题。同伦(homotopy)是代数拓扑学中的一个基本概念，在20世纪70年代开始川 于求解非线性问题的一种非常有效的方法。同伦法的基本思想是:借助同伦函数,-1-哈尔滨工业大学理学硕士学位论文从辅助映射的零点集出发，跟踪同伦映射的零点曲线，并逐步过渡到目标映射的 零点集。即：借助同伦”(借助同伦的零点集T(0)，从辅助映射g的零点 集出发跟踪同伦HQ,x)=O的解曲线，走到目标映射了的零点集。它克服了传 统数值迭代法容易陷入局部收敛的弱点，且对初值的选取没有严格限制，能够 全局收敛，因此它是一种大范围收敛的方法。因而被誉为20世纪数学研究中一 项带突破性的新成果。1.2 矩阵特征值算法概述及其研究现状1.2.1 特征值问题算法对一个阶实(复)矩阵4,它的特征值问题，即求方程4r=2x的非 平凡解，是数值代数的一个中心问题，这一问题的内在非线性给计算特征值带 来许多计算问题。为了求4r=2”中的2,一个简单的想法就是显式地求解特 征方程det(/d/)=0除非对于个别特殊矩阵，由于特征方程的系数不能够川稳 定的数值方法由行列式的计算来求得，既使能精确计算出特征方程的系数，在 有限精度下，其特征多项式/U)=det(N-X/)的根可能对多项式的系数非常敏 感因此，这个方法只能在理论上是有意义的，实际计算中对一般矩阵是不可行 的首先，若矩阵的阶数较大，则行列式det(4-X/)的计算量将非常大其次，根 据理论，对于次数大于四的多项式求根不存在一种通川的方法，基于上述原因，人们只能寻求其它途径因此，如何有效地、精确地求解矩阵特征值问题，成为 一门热点问题。计算矩阵特征值问题第一个且最简单的算法就是塞法山，它通过迭代逐渐 收敛到矩阵最大的特征值和特征向量，其中收敛速度依赖于第二个最大特征值 与最大特征值的比值小于1的程度，而且对于其他的特征值也不能保证收敛。针对塞法的这些缺点，人们将提出了逆迭代法，即将塞法应用于矩阵(力-。/尸，来求接近于。的特征值，其中。称为一个位移，逆迭代法根据。的不同可以求 任何要求的特征值。但是以上两种算法每次只能求一个单个的特征值，如果想 同时计算整个不变子空间，就要川QR迭代来计算，QR迭代在第，步迭代时，需要先选择一个接近于/的一个特征值的位移巧，其中i=L然后进行 QR分解，最后将得到收敛的特征值，算法收敛的快慢取决于,与力的某个特 征值的接近程度。对于非对称矩阵而言，利用QR算法可以求所有的特征值和所有可选的特-2-哈尔滨工业大学理学硕士学位论文征向量。对称矩阵作为一类具有特殊性质的矩阵，相对其它矩阵而言有其特有 的求解算法。目前，对称矩阵特征值问题已经有很多可以利用的算法，这些算 法提供给我们更多的灵活性和有效性。它们大体上可以分为两类：一类称为变 换法，另一类称为迭代法。变换方法是直接对原矩阵进行处理，利用矩阵特征值的相似不变性原理，通过一系列相似变换，如初等Hermite三角变换、Householder变换、平面旋转 等，对原矩阵逐次进行相似变换，使之变换成一个易于求解特征值的特殊形式,一般最后会化为三对角形式，随后应川求三对角形矩阵特征值的算法，三对角 QR迭代和逆迭代法，另外还有分而治之法、对分法等。三对角QR迭代目前是求解对称三对角矩阵所有特征值最快的实用算法，但它仅对=25左右的小矩阵是最快的。当25时，分而治之法是最快速的 算法。另外，当所求特征值可能成审时，上述两种算法是首选。对分法和逆迭 代法适于求特征值的一个子集，而且在所求的特征值“适当的分离”时代价比 较低。另外，变换法中比较经典的方法还有Rayleigh商迭代和Jacobi方法。Rayleigh商迭代是QR迭代的基础，但是因为它的特别迅速的立方收敛性，可 以独立的将它作为一个算法提出。Jacobi方法是计算特征值问题最古老的方法,始于1846年，它通常比任何方法都慢，但它有时比上面任何方法的计算结果都 要精确得多。一般而言，变换方法收敛速度快，计算结果精确可靠，但它破坏原矩阵的 元素分布（如稀疏阵的零元分布），并且由于要存储矩阵元素，当矩阵的阶数很 高时使得存储量较大从而造成调川计算机外部设备的困难，因此，这种方法只 适宜于求解阶数较低的稠密矩阵的全部特征值问题，适川于大型稀疏矩阵的算 法就是迭代法了。迭代法是基于矩阵特征值，即特征多项式根的计算方法本质上总是迭代法 的事实，利川原矩阵进行运算，产生一些迭代向量的方法。迭代方法是通过一 系列矩阵向量乘积而求得特征值和特征向量的。由于迭代方法可采川压缩存储 技术，因而它适合于求大规模矩阵的特征值问题，尤其是大型稀疏矩阵的部分 特征值和特征向量问题。这类的方法有Lanczos方法山、Arnoldi方法、Davidson 方法、子空间迭代法等。大型稀疏矩阵的特征值问题，在许多科学研究、工程 技术等实际问题中有着举足轻重的作用，因此这些迭代方法就显得尤为重要。随着科学研究和工程技术的不断发展中，人们需要对诸如飞机、航天飞机、空间站、海洋石油钻井平台等大型复杂结构进行动力分析和稳定性分析，而一-3-哈尔滨工业大学理学硕士学位论文个复杂结构的动力分析和稳定性分析可转化为大型稀疏矩阵的特征值问题。对于大型稀疏非对称矩阵，最常用的是Arnoldi方法。Arnoldi方法是克雷 洛夫子空间法最重要的一种，它的基本思想是先将矩阵化为海森伯格形式，再 求特征值。但Arnoldi方法构造的克雷洛夫子空间的标准正交基向量需要存储 在主存中，当基的维数女较大时，这一方法的存贮量很大以致无法实现算法，另一方面，为了保证收敛又需要左取值越大越好。针对这一矛盾，解决办法就 是：根据内存的能力取最大可能的左，这样Arnoldi方法得到的解未必能达到精 度方面的要求，随后，人们又提出了重新开始Arnoldi方法等一系列以Arnoldi 方法为基础进行修正之后得到的算法。目前，常用的计算大型稀疏对称矩阵特征值问题的迭代法主要有子空间迭 代法、Davidson方法和Lanczos方法。子空间迭代法可同时求解几个极端特征 值和相应的特征向量，但它有收敛较慢，运算量较大，积累误差的缺点；随后，人们对其作了进一步的研究，出现了预处理子空间迭代法，这种方法的运算量 较之子空间迭代法有所减小，但还是比较大。另外，当要求的特征值与不要求 的特征值之间的间隔较大时，预处理子空间迭代法收敛也比较慢。Davidson方法是E.R.Davidson于1975年提出的，大量的数值试验表明，Davidson方法对于计算量子化学中的特征值问题是非常有效的。继E.R.Davidson之后，许多学者发现，特征值分布密集使得Davidson方法的有效性下 降，并且Davidson方法存储量较大。同伦算法是一种范围的迭代方法，以求解域中任一点为初值，迭代序列都 可以收敛到方程的吸引点，对古典的迭代方法，一般是要求Jacobi矩阵非奇异，但是当参数在某一值时曲线为转折点，则计算就不能继续下去，尽管这一点为 正则点，也要终止计算。同伦算法则避免了这种情况的放生。并且同伦算法的 收敛性和稳定性依赖于原映射的性质，经过众学者多年的努力，连续同伦算法 已巳趋完善，在计算映射的多个零点、映射的不动点和求解互补问题、优化问 题、边值问题、矩阵特征值问题等方面取得了很大的成功。1.2.2 同伦算法在国内外的研究现状及分析同伦(homotopy)又称嵌入法，来源于延拓算法，本身是拓扑学中的一个概 念。而延拓算法作为研究算子方程的理论工具可追溯到20世纪，但作为数值工 具川于方程求根最早是Lahaye于1934提出的，1948年他又将延拓算法用于求 解方程组。1953年Davidenko将延拓算法与Cauchy问题联系起来研究了微分 法(Davidenko方法)，此后又有许多学者在这方面做了大量的工作。同伦算法-4-哈尔滨工业大学理学硕士学位论文是一种大范围求解非线性方程组的整体算法。路径跟踪算法最早由苏联学者 Davidenko和Gavurin提出，但是他们的工作都要求式阴(x/)非奇异的，这一 点限制了该方法的应川范围。1976年，Kellogg和Yorker利用微分拓扑工具解 决了同伦算法的全局收敛性间题，并川之给出了价不动点Brouwer定理的构造 性证明，使得方程求解的计算归结为某一微分方程初值问题解得计算。新的同 伦方法将H(x1)=0放在+1维空间的区域上加以研究，并借助于更 强有力的拓扑学工具进行研究，由于=0的解定义了几十 1维空间的一维 流行，即为一条曲线，所以如果能够证明此曲线通过(丁,1)。那么就可以根据 构造的同伦映射/(x*)=0从而x*是/(x*)=0的解，根据隐函数定理，如果H(xj)的Jacobi矩阵关于(x/)上行满秩，则曲线九存在,这样由Jacobi矩阵可逆降为矩阵行满秩。随后，于是引起了人们对同伦算法的重 新研究。接着Smale发表了全局Newton法的文章。Chow,MalletParet和Yorker 利川他们构造的同伦给出了一系列重要定理的构造性证明，同时给出了可川的 算法。此后同伦算法的研究蓬勃发展几十年来，人们从非线性方程组，不动点 间题，平衡间题，非线性规划，多目标规划，变分不等式，互补间题等多种数 学问题的角度对同伦算法进行了广泛的深入研究深入的研究，并成功地把它们 用于经济学，电子线路设计，自动控制，计算机辅助设计和制造等许多领域中，成为了引人注目的算法。1978年F.J.Drexler最早运用一种同伦方法求多项式方程组的所有解，但 这种同伦的起始点很难选取，且某条同伦曲线可能跑到无穷远。1979年，C.B.Garcia与W.I.Zangwill采川了典型的同伦，这种同伦起始点很容易求得，但起 始点的个数远远多于方程组解的个数，就有很多条同伦道路跑到无穷远，浪费 大量的计算时间。1984年A.P.Morgan对多项式方程组研究了两种同伦使起始 点容易得到又不会有很多同伦道路跑到无穷远。S.N.Chow,J.Mallet与J.A.Yorke构造了较好的同伦，但形式较复杂，1986年T.Y.Ii,A.P.Morgan简化了 这种同伦。1984年P.Brunovsky与P.Meravy在1985年A.H.Wright把尸 变 换到几维投影空间中，构造了齐次同伦，但仍难以克服多余的计算量，为此1987 年T.Y.Li,T Sauer与J.A.Yorke对一类退化多项式方程组构造了一种同伦，使同伦的道路数和退化多项式方程组的孤立解的个数相一致，这是一种很好的 同伦，因此针对不同的方程组应该构造相应的同伦。-5-哈尔滨工业大学理学硕士学位论文1.3 本论文研究的主要内容为求解非线性方程组，同伦方法通过构造一个新映射，新映射定义域的维 数与原映射的维数相同，而值域的维数降低一维，在利川Sard定理和正则值逆 象定理，得到若干互不相交的光滑曲线，这些光滑曲线的某些端点是映射的零 点，从这些曲线上的点出发，跟踪曲线直到原映射的零点。同伦方法求解矩阵 特征值问题，将特征值问题转化为非线性方程组的零点问题，由同伦路劲追踪 曲线。主要内容安排如下：第一章绪论中对特征值算法做了详细的阐述，了解其发展史及主要求解特 征值算法的优缺点。第二章，详细地介绍了三对角矩阵的理论基础、主要性质,分析对称三对角矩阵与非对称三对角矩阵，针对具体的矩阵求解特征值。第三章中，主要阐述同伦算法的基本理论、同伦方程组的构造和求解同伦 方程的几种方法。并根据由于构造的同伦映射并不能完全保证Jacobi矩阵的奇 异性，根据此问题的出现提出两种方法，（1）引入扰动参数函数，通过改变参 数来确定Jacobi矩阵的非奇异性，（2）利川广义逆矩阵，对任意的矩阵加号逆 总是存在并且唯一，川加法逆来代替Jacobi矩阵等等。接着介绍了几种微分方 程初值问题的跟踪曲线方法，最后利川龙格库塔方法求解转化后的微分方程。第四章，根据构造的连续同伦映射来求解具体的三对角矩阵的特征值和特 征向量，并通过算例比较分析方法的收敛性，并与经典的QR算法、Jacobi算 法进行了比较分析。-1-哈尔滨工业大学理学硕士学位论文第2章三对角矩阵2.1特殊三对角矩阵的基本性质三对角矩阵在线性代数、计算数学、组合数学以及应用数学中有广泛的应 川，所以三对角矩阵的研究一直受到人们的关注。定义2.1矩阵）=（q 称为三对角矩阵，如果当”力1时,有%j=0成立。考虑常系数热传导方程中的典型的实数域上的一类特殊三对角矩阵ba、c b a4=c b c0在文献网中得到三对角矩阵4的行列式的计算公式det（4）=yk 其中 x+y=b,xy=ack=0det（4）+b2-4ac n+i b b2-4ac n+1（9）一（9）2-/-,b2-4ac w 0b2-4acb5+1）（）/24“c=02/2det（4）=Z（-k=0利川以上行列式公式给出了三对角矩阵4的特征值计算公式。（1）三对角矩阵4的特征多项式卜/2/=Z（-1）1厂）a-与山攵=0（2）三对角矩阵4的特征值-2-哈尔滨工业大学理学硕士学位论文4=8+2yac cos（k兀）,k=1,2,nn+1例2.1给出下列5阶矩阵1000、32100A-032100032100032)的特征值通过求特征值的公式计算得到表2-1矩阵4的真实特征值Table2-1 The exact solution of matrix A444A4-1.00000.267952.00003.73215.0000利用三对角矩阵4的特征值，得到(1)Vcos()=0k=i 十 1n _ 卜万【”I(2)口 S+2而 cos()=Z(T)Y kk)bn2k(ac)k k=i n+k=o2.1.1 Jacobi 矩阵设2 、C，2 b2A-*.*.*.Zx Cn-2 an-l 2-1为三对角矩阵,如果知如q都是实数,且30,则称/为Jacobi矩阵。从矩阵力的形状可知，它的左阶顺序主子阵也是三对角阵，记为4。设4的特征多项式为外(从而有(Pk(=det(2/4)=(4 以)%.。)一也.例一2(-3-哈尔滨工业大学理学硕士学位论文令0o（X）=l,所以对=2,3,几，成立关系式9k（X）=U%M-xW-（，）其中Jacobi矩阵的特征多项式序列（Pn（,%（,01（4）,%（是任何区间a,b内的Sturm序列。Jacobi矩阵的特征多项式序列%（X）,%_i（X）,9i（X），Oo（X）中任意一个多项 式外（有1个实单根靖）,并且它们与明的1-1个实单根%尸）,%尸,.*1）,有如下隔离性质2.2对称三角矩阵2.2.1 对称三对角矩阵性质定义2.2设矩阵C1其中q=2,则称矩阵/为对称三对角矩阵。显然对称三对角矩阵是特殊的Jacobi阵，因此关于Jacobi矩阵的结论它都 具有，如果2。0为不可约的，否则可将可约问题转化为低级的不可约矩阵的问 题来讨论，首先指出，对于任意一个实对称矩阵，都可以经过Givens变换、Householder变换，Jacobi变换等一些正交相似变换变成对称三对角矩阵。推论2.1对实对称矩阵若即矩阵N是不可约的，Vzen-1,则力无重特征值，如果矩阵A中的兀素=4=a,匕=与=8时有推论2.2-4-哈尔滨工业大学理学硕士学位论文推论2.2实对称矩阵/在区间团-2%,+2切上有几个互不相同的实特征 值。推论2.3 令E=maxlql+I%l+I2l,ien i其中仇=2=0，则有即A的特征值都在区间-氏氏上。推论2.4令m=minQj I%I 1白 1 1 i e nM=max%+1 I+也 I、i其中d=2=。则对/的特征值2有：mAM推论2.5令s=maxlq 1,1白 I,，=1孔也=0,i则力的特征值2必满足冈口5从推论2.3-2.5我们可以很好的解决力的特征值界的问题。2.2.2非对称三对角矩阵化为对称三对角矩阵非对称三对角矩阵%4、C。2%A=.Cn-2 an-l by0,记P=diag（,72,小）2（纳也）Yk=I C1C2 Ck J则PT是一个对称三对角矩阵/*,且-5-哈尔滨工业大学理学硕士学位论文/1%d4*=4 一2 an-l dn_I0(攵=1,2,1)如果 P=diag(l,%”1)，2k=2n(n=1,2)h h ,b结2,也 cj Ck2,k=2n+l(n=0,1,2)则HP-=/*是一个对称三对角矩阵，且因而在对求解任意三对角矩阵的特征值问题都可以转化为求解对称三对角 矩阵的特征值问题，因为相似矩阵具有相同的特征值从而使原问题得到简化。在以后遇到求解矩阵特征值时我们给出的都是三对角矩阵。-6-哈尔滨工业大学理学硕士学位论文2.3本章小结本章首先介绍了工程上求解一些特殊三对角矩阵的特征值的问题，并给出 了相关的计算公式，性质等。接着给出了 Jacobi矩阵的定义性质，并在此基础 上定义了对称三对角矩阵的定义，介绍了一些重要的性质理论基础。最后对给 出了从一般的三对角矩阵变换到对称三对角矩阵的计算方法，便于以后的应用，本文中以后对求解三对角矩阵的问题都可以转化为求解对称三对角矩阵的特征 值特征向量的问题。-7-哈尔滨工业大学理学硕士学位论文第3章同伦算法3.1 同伦算法的概述同伦算法是从19世纪70年代开始，经过30年来的研究，现在已经发展成 为一种十分重要的计算方法，得到了广泛的应川，出现了不少有效地算法，其 中求解实对称特征值问题的同伦算法就是典型的一例。同伦算法可以分为两大类：一类是以微分拓扑学中的Sard定理、原像定理、一维流形定理和Euler折线法相结合而发展起来的连续同伦算法；另一类是以 代数拓扑学中单纯剖分和单纯逼近为基础发展起来的单纯通论算法。木文主要 川到的是连续同伦算法求解矩阵的特征值，因此只对连续同伦算法做一些介绍。计算非线性映射/：的零点问题，我们假设了是光滑映射。连续同伦方法是借助同伦(借助同伦的零点集T(0),从辅助映射g 的零点集出发跟踪同伦亿x)=0的解曲线，走到目标映射了的零点集。它克 服了传统数值迭代法容易陷入局部收敛的弱点，且对初值的选取没有严格限制,能够全局收敛，因此它是一种大范围收敛的方法。因而被誉为20世纪数学研究 中一项带突破性的新成果。先构造g：为一光滑映射，并将/与g用一个连续映射连接起来；然后再从平凡映射g的零点出发逐步过渡到目标映射f的零点。通常，连接/和 g的最简单而实川的线性同伦是：=Zf(x)+(l-0g(x)(x,0 e nx0,l(3-1)显然(x/)也是光滑的，且有H(x,0)=g(x),a(x)=/(x)当然,为了实现从 平凡映射g的零点过渡到目标映射了零点的目标,必须对g和有一定的要求o 引进一些记号和定义：”,()=(小)；re0,1T(y)=(*/)尺义0,1 1(。=X n:H(x,t)=y;ye 同伦映射”的零点集以记关于变元如/，XfS+i，%+i=?的x(+l)阶Jacobi矩 阵，记为“关于变元看,%，的Jacobi矩阵，即-8-哈尔滨工业大学理学硕士学位论文明西dxx dx28H=.dh dhYl Yldxr dx2dd ddxx&Z 因+idHx=Xjdhn._n_ 也dx.如敬L此.迎LH(x,t)=(似%/),hn利川上述记号，易知，H0=g,H1=f,并且丁加xl=J(y),了 特别地 30)n nxt=H；O)o我们的目标是希望从已知的，(0)=gT(0)出发，然后通过“T(0)中的道路曲线跟踪到达原问题的解集“(0)二尸(0)。定义3.1设H如(3-1)所定义，如果(x/)义0,1满足阴(*/)=，“在()的Jacobi矩阵行满秩,且当=0时,还有3叫 在(九)满秩,则称()为”的一个正则点。即映射在(X/)的Jacobi矩阵行降秩，则称(X/)是的 临界点。如果“使得”T(y)中的每个点都是的正则点，则称是“的一 个正则值，如果y不是的正则值，即存在。/)一1(丁)使得(x/)是的临 界点，则称y是映射的临界值。注：一般情况下我们希望已知的都是的正则值，如果其中的某个 y。0为的临界值，我们可利用扰动方法使/成为的正则值。如果/=0 呢？情况又如何，在此我们给出以下相关定理。定义3.2设x和y分别是欧式空间的子集，如果映射y是映 射，且与T都是光滑映射，则称h是x到y的一个微分同胚。如果这样的 微分同胚存在，则称x与y是微分同胚的。定义3.3设xx0,l是 向的一个子集，如果对任意的XX/0,1存在(XI)的一个邻域VeXxQI,使得V与 I的一个开集微分同胚，则称X是 k+1维光滑流形，若光滑流形X的子集丫也是光滑流行，就说丫是X的子流形。我们可以验证，(0,1)X 是+1维光滑流形，是几维光滑流行，中的单-9-哈尔滨工业大学理学硕士学位论文位开球以1)=*|刈1和单位球面S(l)=xg n|x|=l分别为n维和1维光滑流形。w中不包含端点的简单光滑曲线是一维光滑流形。本文中的流形都指光滑流形，并在维数明显或维数无关紧要时，可省略维 数不提，因为流形是欧式空间的子集，就可以讨论流形之间的光滑映射。定理3.1设x和y分别是左维和/维的光滑流形，左y是光滑映 射，如果，丫是映射”的正则值，则T(y)或者是空集，或者是X中左-1维 子流行。特别地，当左-/=1时，T(y)是一维光滑流形。由简单光滑 曲线组成。例 3.1 定义例：(0)x f 丁(%/)=d%2一3%+2)+(1)(x 1)可知。是”的正则值，”的零点集为“t(0)=,1),3-；)卜(0,1是图(3-1)的两条 简单光滑曲线，如果我们从“】()中点(1,1)出发，沿着”|(0)中的曲线走，可以 达到点(0,1),如果我们从(1,2)出发，沿着1(0)曲线走，则走向无穷远。从定理以及我们所举的例子可以说明，正则值的逆象有很好的几何结构，自然 会问，丫中究竟有多少点式光滑映射y的正则值？假如”的正则值在 y中很少，上述的定理将没有任何意义了，从而我们引出Sard定理。定理3.2设丫和。是光滑流形fU是光滑映射，即。是”的临界点 集，则”的临界值集)uU在。中的测度为零。推论3.1设0 是(3-1)所定义的”的正则值，则”的零点集t(0)由一 些互不相交的下列光滑道路组成，且每个连通分支或者微分同胚于单位圆，或 者微分同胚于区间0,1或(0,1或0,1)o同伦算法的的基本思想是:借助同伦函数，从辅助映射的零点集出发，跟踪同 伦映射的零点曲线,并逐步过渡到目标映射的零点集。即：从辅助平凡映射g在-10-哈尔滨工业大学理学硕士学位论文1X 的零点集lxg-i(O)出发，走到目标映射/在0 x 上的零点集 0 x/T(0)。所以，没有端点的连通分支和端点不在1X 上的连通分支对计 算映射了的零点没有任何帮助，另一方面，虽有一端点在1X 但却无界的 连通分支对计算零点同样没有任何帮助，反而会浪费计算时间和导致算法不收 敛，为了排除连通分支无界的可能性。“满足如下有界性条件：在中的一个有界开集。，光滑映射方满足 H-i(O)n(90 xO,l)=0,其边界为泗。在有界性条件成立的情况下，如果跟踪“7(0)中的某个端点在1义方的连 通分支，当连通分支的参数才从1变到。时,该连通分支将引导我们从平凡映射g 的一个零点走到目标映射了的一个零点。如果g在。的零点数目是奇数，即各 连通分支在lx 的端点的总数是奇数，则至少一个分支将引导我们从平凡映 射g的一个零点走到目标映射了的一个零点，连续同伦算法的基本思想就是沿 着这样的连通分支走，把零点计算问题化为微分方程初值问题。考虑同伦映射的零点集-1(0)=9*)。1义回/)=0,一般来说 集合“7(0)可能是非常复杂的，无法确定它的拓扑结构，但是如果0是“和明 的正则值，则由逆象定理知”7(0)是一维光滑流行，其边界点都在0 x 上,根据定理3.2,”t(0)是由光滑的简单曲线组成，每一条曲线或者微分同胚于 单位圆，或者微分同胚于单位区间，这正是同伦算法的所需要的。为了保证。同 时是“和明的正则值，接下来我们引入如下形式的广义Sard定理定理3.3设Vu,U u机是非空开集，r:VxX-，为光滑映象p(小，如果0，是P的正则值，则对几乎所有。丫，0为限制映象匕()=卜(见)的 正则值。通常在应用中经常取=与当成参数，令卜(%,)=”(,),如果 卜:。xOx0f 是光滑的，下关于空间变量了日趋尢吓和是可微 的，应川定理，此时。=Ox0,lu 向，V=D,故m=+1,p=n,立即得到 对所有的(看人)义，0是限制映射匕。()的正则，既是“54。的正则值。定理3.4设/:x T X是光滑映射，0 X为和明 的正则 值，且1(0)中从0,项pA/出发的曲线/与超平面;1相交，则存在x 中的领域N(项p4)及0,lx x中的曲线7(s)的管状领域7。)，使得对任意-11-哈尔滨工业大学理学硕士学位论文(x,2)g?/(x0,20)及任意t,x,2r g T(Z)矩阵-(x,2,0行满秩。其中H(x,A,t)=Zf(x,2)+(l-0D(g(x,2)-g(x,2)g(xo,2o)=O定理保证了预估计校正法的可行性，根据定理若。为H和阴正则值，只 要每一步的误差充分小，就不会出现因为Jacobi矩阵降秩而使算法无法执行的 情况，因为预估计校正法是自适应的，前面的误差不会影响后面的计算精度，可以使每一步的误差充分小。定理3.5设/,/(s),H,满足上述定理的条件，有如下的微分方程组HR(s)+82疝。)+H/G)=0 ho)(o)/(=K，4,oF其中i=心)H2=/)5f一axafal瓦agal+l(s)DH3=/(x(5),s)Og(x(s),s)g(x(0),2(0)记(s)=Gg(y,s)其中y=IXs),*(s),X(s)则存在曲线/(s)的管状邻域7。)以及(项p4)的邻域N(%，4),使对任意 yT(/),c gN),G(y,s)对了满足 Lipcshitz 条件。3.2 同伦映射的构造同伦方法通过构造一个新的映射，得到若干互不相交的光滑曲线，这些曲 线的某些端点是映射的零点，从这些曲线上的点出发，跟踪曲线知道原映射的 零点，同伦”的构造是多种多样的，下来讨论如何构造-12-哈尔滨工业大学理学硕士学位论文3.2.1 不动点同伦映射取初函数g(x,2)=1 xT x 2)构造定点同伦“(M X/)=/f(x,2)+(1-O(g(x,2)-g(x0,20)(3-2)根据广义Sard定理可知，若同伦：义xO,l 义 是光滑的，Oe 义 是了的正则值，作同伦方程式(3-2)则对几乎所有(苍 n x,0g H x同 时是映射“，明的正则值。H-1(0)=Z,x,2re0,lx 义 回色m=。有下列曲线组成：1)(0,1)x x中具有有限弧长的闭曲线；2)(0,1)x X中的曲线，且两端都在lx 义 中；3)(0,1)x x中一端点在lx x中的无界曲线；4)一条具有有限弧长的曲线分别以xl和x0中的点作为它的两个端 点，其中4v0-几=0；或者，一条以0,4?为它的无界曲线，这 两种情况必有一种发生，且只有一种发生；5)没有端点的(0)x n x中无界曲线。在上述条件中，假设了 在它的零点处Jacobi矩阵非奇异，此条件在证明 7(0)中的连通分支都是简单光滑曲线时起关键作川，但实际问题中，我们时 常碰到0 义 是映射”的临界值，当0不是同伦映射”的正则值，但仍有 类似上面的结论。定理3.10若：义x0,l 又 是光滑的，作为同伦方程(3-2)则对 几乎所有的(%,4)义，0是：X x0,l 义 在(0,lx 义 上的 正则值。H 一1(0)=上苍2/0,1 x 义 旧(人m=0由如下曲线组成：1)(0,1)x X中具有有限弧长的闭曲线；2)(0,1)x x 中的曲