（基础数学专业论文）求解高维非线性方程组的沿场线微分延拓法.pdf

摘要 非线性方程组的求解是数值计算领域中的一个比较重要的问题 求解非线性方程组的方法包括n e w t o n 法、延拓法以及其它一些求 解方法它们在求解过程中具有较快的局部收敛性，但是它们对初 始点要求严格，这就导致这些算法对于非线性方程组的求解容易失 效 本文就n e w t o n 法、延拓法这两种算法进行了比较，并针对它们 的对初始点要求严格的缺点，提出了一种求解高维非线性方程组的 沿场线微分延拓法，该方法不依赖初始点，求解沿着场线前进我 们给出了理论证明，通过计算具体的数值列子，表明该计算方法是 可行的，也证实了理论证明的可靠性并给出了其解高维问题的一 般算法 关键词z 非线性方程组，n e w t 伽法，延拓法，微分延拓法 a b s t r a c t i nt h em a t l 蚰a t i c bf i e l d ，8 0 l v i n g 盯s t 咖o fi a n l i i l e 村e q l l a t i o n si s 锄i m p o r t a n tp r o b l e m i n l et r a d i t i o n a lm e t h o d si n c l u d en e w t o n sm e t h o d ，e 戚朗s j o n m e t h o d 锄ds o m eo t h e r s n e w t o n sm e t h o d i 饥s i o nm e t h o dh 暑ef 氆s to o n v e r g e n c ep r o p e 呶p u tt h e yo f t 朗t a i lt os o l 、，e i n ei l o n l i i l e 盯盯s t 咖e q l i a t i o 璐 b e c d u 眙t h e i rc o n v e r g e n c ei ss t r o n 酉yr e l a t e dt ot h ei l l i t 谢p o i n t b a 战j d t h e 咖p a r i 印咀o fn 朗渤sm e t h o d 柚dd c t 既s i o n 加【e t h o d ， ad i e 砌1 t i a t ec o n t i n u a t i 伽m e t b o da l o n gv e c t o rf i e l dl i 鹏f b f l v i n gh i g h e 卜 d i m e n s i o n a ji l o n l i n e 对s y 8 t e i ne q u a t i 0 咀si sp 掣s e d i ti 8n o tr e l a 舨，dt ot h e i n i t i a lp o i l i t ，i ti sf i l l i s h e d 出0 n gv e c t o r 舶l d 骶h 撇p r o v e di t t l l r 线岫p l e w e 陀g i 唧t od 册鲫b t r b l l et h ef e a s i b i l i 锣o ft h em 珊e r i c a l 加h e l l l o d ，觚d 砌0 d 8 t e do l l rth i 删i c a l 舫d i n g 芦a n da 咖8 la l 群) r i t h m 8w a sg i v 鼍m 蕾b r8 d l 讥i 堰 h i g h e r - d i i n e n s i o n a jn o n l i n e 对码僦锄e q u 8 t i o n 8 k e yw o r d 8 ：n o n l i l l e a re q u 8 t i o 璐，n e 毗o n sm e t h o d ，d is c i t i 肭咖e 静 t e 璐i o n 娥h o d d i 仃b r e n t i a t ec o n t i n u a t i o ni i 哦h o d 湖南师范大学学位论文原创性声明 本人郑重声明t 所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果除文中已经注明引用的内容外，本 论文不含任何其他个人或集体已经发表或撰写过的作品成果对本 文的研究做出重要贡献的个人和集体，均i ：三在文中以明确方式标明 本人完全意识到本声明的法律结果由本人承担 学位论文作者签名：杰疆b 加寥年，溯日 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅本人授权湖南师范大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存和汇编本学位论文 本学位论文属于 1 、保密口，在年解密后适用本授权书 2 、不保密口 ( 请在以上相应方框内打 ”) 3 9 jl 月 j 月 日 ，日 求解高维非线性方程组的沿场线微分延拓法 第一章引言 由于科学技术发展的需要以及计算技术的高速发展，使得非线 性问题成为实际领域中的一个重要问题，因而也是现代科学计算的 主要研究课题之一非线性方程组的求解则是解决这类问题的关键 所在 非线性方程组的求解广泛应用于数值天气预报、石油地质勘探、 计算生物化学、控制领域和轨道设计等方面，因此高效可靠的求解 计算方法，在科学计算中具有很重要的意义 通常非线性方程组是指几个变量n 个方程的方程组 f ( z ) = 0 ，z = ( z l ，z 2 ，z 。) r 兄“( 1 1 ) 这里f = ( ，五， ) 丁是从几维欧氏空间舻到彤的光滑映射如何 求方程组的解矿成为很重要的问题研究非线性方程组( 1 1 ) 的解的 存在性和有效解法虽然已有很多的成果( 见文献【1 1 3 】) ，但由于( 1 1 ) 的非线性性质，给研究工作带来很大的困难，”寻找大范围收敛的算 法可以说是几代人的梦想( 见文献【4 】 1 2 0 页) 大家知道，n 叭o n 迭 代法和它的变体是解非线性方程组的经典方法，至今都是基本的重 要的但是它的收敛半径一般很小，需要很好的初值m 因此? n e w t o n 法仅当初值很接近真解矿时才是收敛的但由于真解矿事先不知道， 实际上寻求一个较好的初值( 有时必须寻找所有的根) 本身就是相当 困难的因此，在上世纪7 0 年代，发展了一种延拓法( e m ) ( 也称同伦 ( h 咖o t o p y ) 算法) ，它有大范围的收敛性，取初值的容许范围被显著地 阔大了，于是，它成为解非线性方程组最有效的方法但将e m 解某 些复杂问题时，仍常常发散，因e m 仍严重地依赖于初值，使延拓曲线 严重地弯曲所致 我的导师领导的研究集体已经进一步作了许多研究如 一、多启动延拓法( m s e m ) ，其特点是找到一条从卸沿着矢量场 方向通往矿的路径，并使整个非奇异域都是吸引域，使初值的影响 变得越来越小，当快接近解时，才采用经典的n e 吼o n 法 高校教师在职硕士学位论文 二、搜索所有解的长方体算法，其将有界区域q 剖分为m n 个n 维长方体单元e ，判断有根的单元，在单元e 中求根，然后进行逻辑 判断其剖分结构简单，能搜索所有的解，当未知数不太多时很有效 应当指出的是，遗传算法是求解优化问题的有效算法，特别是武汉 大学康立山教授领导的研究小组创新的”郭涛算法”，能用于求解非 线性方程组的所有解( 见文献【1 】第五章) 求高维非线性方程组的 所有解的困难问题用这种算法有望解决 本文是在延拓法的基础上构造了一个新的算法：使解曲线z ( t ) 总是沿着理想的矢量场或在其附近连续地前进，到达根z ，并不受 初值一的影响，且通过了大量的数值实验，证明了其正确性当未 知数不太多时很有效，其保证能使计算求到根，或保证算到z + 的附 近，然后再采用n e w t o n 法、或改进的n e w t o n 法求解 本文的结构如下： 第二章主要介绍了已有的解非线性方程组的两种算法：n e 咖n 法及一般的延拓法，并对它们进行了分析，指出了它们各自的缺点 第三章提出了解非线性方程组的沿场线微分延拓法，给出了一个 新的微分延拓方程z 他) = y ( z ( ) ) = 一( d f ( z ) ) - 1 f ( z ) ，z ( o ) = 一给出了 证明 第四章及第五章给出了三个数值实例，验证了沿场线微分延拓法 解非线性方程组的正确性和可行性 第六章主要就以上研究内容提出需要进一步研究的问题 2 求解高维非线性方程组的沿场线微分延拓法 第二章已有的解非线性方程组的算法及分析 2 1n e w t o n 法算法及分析 在求解非线性方程的历史中，n e 毗o n 法是最经典的，至今也是非 常重要的计算方法设方程组f ( z ) = o 的根是矿，它的j a c o b i a i l 矩阵 d f ( z ) 在矿的某邻域g = ( 矿) cq 中非奇异已知f ( z ) = o 的一个 近似值z o g ，方向矢量， y ) = 一( d f ( z ) ) 一1 f ) 由于在邻域( 矿) 中每点z 都对应着一个方向y ( z ) ，因此他们在区域 ( 工) 中构成了一个向量场，这些向量曲线都向点矿汇集在点护， 用多元函数的t a y l o r 展开 f ( ，) 一f ( 扩) = d f o ) 0 一一) + 去 一一) d 2 f ( ) ( 矿一) t ， 因f ( 矿) = o ，于是可解出 z 一矿= y ( z o ) 一去d f 一1 ( z o ) ( z + 一z o ) d 2 f ) ( ，一z o ) t 若z 一一很小，可弃去上式右边第2 项，立即得到矿的近似值 z 1 = 扩+ y ( z o ) ( 2 - 1 ) 与前式相减，误差表示为 z 一z 1 = 一去d f 一1 ( z o ) ( z 一z o ) d 2 j f l ( ) ( z + 一z o ) r ) 因此有以下估计 i i z 一z l l i 岛7 i i z + 一z o l l 2 ， 其中扇= l i d f 一1 ( z 。) l i ，y2 搿i i d 2 f ( 可) i i 一般地，可将已求出的矿 作为初值，又用n e 毗o n 迭代公式 z 七+ 1 = z + y ( z ) ，七= 0 ，l ，2 ，( 2 2 ) 3 高校教师在职硕士学位论文 计算出下一步的新值矿，其误差有估计 l i z 一z 七+ 1 i i 反7 | i z 一z 七1 1 2 ，( 2 3 ) 其中凤= i i d f - 1 ( 一) 1 1 由此看到，在根z + 的附近，n 洲o n 法具有二次 收敛性在局部的范围下，它是沿着向量场y ( z ) = 一d f q ( z ) f ( z ) ，的 方向前进的，这是最佳的选择方向因此，n e w t o n 法至今都是解非线 性问题最基本的最重要的方法 n e w t o n 法的优点是收敛快，但计算量大，每次迭代，要计算d f ( 矿) 并求其逆，这是它的第一个缺点；另一个缺点是n 咖o n 法必须严格 限制初值护在矿的附近，才有好的效果，即须有一个以矿为中心， 以r 为半径的球，在这个球中的任意一点为初值，使用n e 毗o n 法才 会收敛到矿但要选择初值一很接近于零点矿一般是很困难的，因 为矿事先不知道在哪里一旦初值一选得不好，第一次迭代的结果 将会落到收敛球之外，以后的迭代将是到处乱跑，根本不会收敛第 一次迭代不好，可能导致了整个迭代的发散实际计算中也完全证 实了这种发散现象对于这些问题的研究有著名的局部收敛定理和 k 衄t o r 而c z 定理下面不加证明地给出这两个定理 局部收敛定理设f ：g c 兄n _ 俨，矿满足j f l ( 矿) = o ，f ( z ) 在矿的 开邻域g o c d 上可导，且d f ( z ) 连续，d f ( 矿) 非奇异，则存在闭球 = k ( 矿，r ) c g o ，使映射三( z ) = z d f ( z ) - 1 f ( z ) 对所有的z g 有意 义，且牛顿法矿“= 矿+ y ( z 七) 生成的序列超线性收敛于矿若还存 在常数m o ， i l d f ( z ) 一d f ( 矿) i i m i i z 一z i l ，( 二4 ) 则迭代序列至少平方收敛( 证明见文献【2 】) k a n t o r o v i c z 定理设f 是从gc 到的连续函数，在凸集 g ocg 上可导对任何z ，g o ，有常数，y o 使 i l d f ) 一d f ( 3 ) l i ，y i i z y 再设有卸g 0 使l i d f 一1 ( z o ) i | p ，i l d f 一1 ( z o ) f ( z o ) i i 叩，满足 = 2 p ，y 7 1 ，则用n e w t o n 迭代产生的序列 乳 收敛到唯一解矿 k ( 勋，r 1 ) ng o ，其中半径r l = 2 7 7 6 ，6 = 1 + 佣它们有误差估计、 l f z 七l | 击i i 矿 4 求解高维非线性方程组的沿场线微分延拓法 ( 此定理的证明见文献 3 】) 由此看到，要求 = 2 所，7 1 是一个非常严格的限制，因为对多 维问题，p ，7 可能很大，几乎要求，7 ( 因而l ij f l ( 正o ) 1 1 ) 很小很小，虽然以 后对n e w t o n 迭代的收敛性还有许多研究，但都不能改变此本质的缺 点，应当提到，我国王兴华教授早在1 9 8 0 年前后对牛顿法的收敛性 已作过一序列精深的研究，比较上述两个定理收敛范围的大小，对单 零点情形较准确估计了收敛半径，并得到某些改进结果 对于n e 毗o n 的收敛性及n e w t o n 方法的若干改进算法如b r 侧n 法、b r e n t 法、b 响法等，它们在( 文献【2 】【5 6 1 ) 及优化的书中有 专门的介绍 2 2 延拓法的算法及分析 n e w t o n 方法解非线性方程组( 1 1 ) 是局部收敛的。它只在初值z o 与方程组的解足够近时迭代序列才收敛延拓法可以作为扩大收敛 域的有效方法，可以从任意扩出发，通过延拓求得方程组( 1 1 ) 的 解为了解决由于初值选择不好常导致n e w t o n 迭代发散的问题， 延拓法在提供好的初值方面成了重要的不可少的角色延拓法原来 是研究算子方程的一种理论工具，l a h 妒( 1 9 肄1 9 4 8 ) 先后用它求解方 程与方程组经很多学者继续研兖延拓法目前已成为大范围解非线 性问题的最有效方法之一( 参见文献 1 ，2 ，5 6 ，1 4 ，1 5 ，1 6 1 ) 对于 任意给定的初值，用延拓法都可求得问题的解在 寻找大范围收敛 的算法”的历史追求中，延拓法部分地实现了”几代人的梦想” 设矿是非线性方程组f ( z ) = o 的一个根，已给初值工o 假如给定 了另一个函数g ( z ) ，且g ( 知) = o 我们能构造一个连接知和矿的延 拓( 或同伦，h o m o t o 阿) 日( t ，z ) = j f l ( z ) + ( 1 一) g p ) = o ，0 t 1 ( 二5 ) 它的解是一条同伦曲线z ( t ) 显然知= z ( o ) 是日( o ，z ) = o 的根当 t 从。连续地改变到l 时，我们能设想( 有些情形未必能如愿) ，此延 拓曲线z ( ) 的终点z ( 1 ) = 矿是月( 1 ，z ) = f ( z ) = o 的根为了数值 上求解( 2 1 ) ，作t 的一个剖分：幻= o l t 2 = 1 ，其步长 5 高校教师在职硕士学位论文 b = 如一如一- 一致地小，当仇适当大的话我们能逐个地求解以下子 问题， b ：日( z ，如) = 如f ( z ) + ( 1 一如) g ( z ) = o ，z ( 如一1 ) 已知，歹= 1 ，2 ，m ，( 禾6 ) 它取前一个问题弓一- 的解z ( 如一t ) 作为本子问题弓的初值，特别地 z ( o ) = 知因为从岛一l 到岛的改变很小，此初值z ( o ) 已是解z ( t ) 在 ( 2 ，“幻) 中一个很好的逼近，于是可用n e 叭o n 法求解初看起来延拓 法的计算量很大，其实不然，因为步长很小，又只要近似求解每个子 问题，每次只要迭代2 - 3 次即可在t = 1 时要得到很准确的解，要多 迭代几次 人们为延拓法的出现而高兴但用它解决一些困难问题时仍暴露 出某些缺点： 1 ) 如果初值知远离真解矿，d f ) 与d f ( 矿) 将有很大差异，此 同伦曲线z ( t ) 将有很大的弯曲如何保证z ( t ) 会逼近所希望的解矿， 而不是别的根呢? 因此初值的选择肯定也被限制了，即延拓算法收敛 到矿，仅当初值黝属于矿的某个吸引域d ( 矿) ( 当然，它包含矿) 才 可能显然，吸引域的大小依赖于同伦算法本身和g ( z ) 的构造 2 ) 当t 接近1 时，z ( t ) 将逼近目标矿虽然f ( z ) 与l t 都变得 很小，但可能g ( 矿) 很大，且d f ( 矿) 一- 很小，它使得求解日( t ，z ) = o 很 困难，即n e 毗0 n 迭代可能很坏，往往导致延拓求解失败如何选择合 适的g ( z ) 有很大影响 目前有两种简单而有用的方法选择延拓函数g ( z ) 如下： d 型：日( t ，z ) = t f ( z ) 十( 1 一t ) d f ( z o ) 扛一z o ) ，g ) = d f ( 卸) 一跏) ； f 一型：日( t ，z ) = f 0 ) 一( 1 一t ) f ( 知) ，g 扛) = f ( z ) 一f ( 黝1 ) 它们保证了对任何知有g ( 黝) = o 但实际计算时发现它们的适应能 力有很大的差别 假定f 在即是非奇异的，即行列式d 西( d f ( z o ) ) o 若f ( z 7 ) 在 某个中间值一= z ( r ) ，o r r 出现d ( z ，) 的奇性，上述算法终止了但这时d f ( 矿) 一般是非奇异的，人们能取 ，上的一，或者t ( r ，) 中的z ( t ) 作为新的初值，并再次使用延拓算 法由此看到，口型延拓具有穿过f ( z ) 的奇点( 线) 的能力，我们能重 新启动延拓法继续逼近目标，当然，穿过奇点( 线) 时，d 型延拓曲 线z ( ) 将有很大的弯曲，这是一个缺点不过这样越过奇点的幸运有 点随机性，我们不再讨论此类问题 对几型延拓，d 圩= d f ( z ) ，即h 和f 有相同的j a c o b i 矩阵在 延拓过程中，如果f ( z ( 亡，) ) 在有奇性，那么z ( ，) 也是日( z ，t ) 的奇点， 即几型延拓没有穿过奇点( 线) 的能力，于是计算在接近奇点t ，时将 终止但由于d 日= d f ，b 型延拓局部地有好的逼近方向 我们考察解曲线z ( t ) 方向的改变仿照d 州d e n k o ( 1 9 5 3 ) ，微分 日( z ，t ) = o 有 曰二( z ( t ) ，t ) 一( t ) + 凰( z l i c ) ，) = o ， 其方向导数满足d 嘶d e 】以的微分方程 一( ) = 一d 月( z ，t ) _ 1 风( z ，t ) ，z ( 0 ) = 知 因而延拓法也可转化为一个常微分方程组的初值问题求解下面讨 论它的斜率的变化情况 对d 型延拓，日= 伊( z ) + ( 1 一t ) d f ( 勋) 扛一知) r ，导数为 d 日= d f 扛) + ( 1 一) d f ( 粕) ，风= f 0 ) 一d f ( z o ) ( z 一勋) t 对p 型延拓，日= f ( z ) 一( 1 一) f ( z o ) ，导数为 d 日= d f 扛) ，风= f ( z o ) 我们比较这两种延拓如下在起点t = o ，它们的d 圩= d f ( 知) ，凰= f ( 跏) 是相同的，即两种解曲线有相同的初始方向一( o ) = 一d f 一1 ( 跏) f ( z o ) = y ( 知) 但在终点t = l ，虽然两者d 何= d f ( 矿) 仍相同，但风= f ( 跏) ( 对p 型) 与风= f ( z 木) 一d f ( 黝) 宰一知) r ( 对d 型) 是不同 的，它们都强烈地依赖于初值翔这使两种延拓曲线有着不同的方向 与路径，它们都可能严重地偏离了方向场y ( z ) 7 高校教师在职硕士学位论文 第三章描述场线的微分延拓方程及一般算法 前面我们知道，n e 毗o n 迭代，一“= + y ( 矿) ，七= o ，1 ，2 ，在接 近零点时有二次收敛性，其中y ( z ) = 一( d f ( z ) ) - - f ( z ) 是理想的方向 场，但只是由于初值不好它的第一次迭代就可能导致发散另一 方面，延拓法有较好的大范围收敛性，但仍有一个缺点，它强烈地 依赖于初值，可能使延拓曲线z ( ) 偏离了理想的方向场y ( 。) ，严重 地弯曲，以致绕道了无解区，或遇到奇点，或收敛到别的解等等，使 计算失败为克服它们的缺点，保持它们的优点，一种理想的方法 应该是：计算轨道总是沿着场线方向 y 扛) = 一( d f 扛) ) 1 f ) 为此我们提出一种沿着场线方向计算的微分延拓法 我们考虑小的正数t 令跏= y ，将 h ( t ，z ) = t f ( z ) 十( 1 一t ) j d f ( z o ) ( z z o ) = 0 ，0s ts1 改写为 d f ( y ) p 一可) + t ( f 扛) 一d f ( ! ，) 一y ) ) = 0 将第二式泰勒展开为 f ( z ) = f 扫) + d f ( ) 扛一暑，) + 去( z 一可) t d 2 f 代) ( z y ) ， 代入上式得 d f ( 箩) ( z 一掣) = 一( f ( z ) + 去( z 一3 f ) t d 2 f 媾) ( z 一3 ，) ) 现设如= z y ，出= t 是微分由上式可得微分关系 d z = 一( d f 0 ) ) _ 1 f ) d t 其实这里z = 可也是任意的因此，对任意给定的初值护，我们得到一 个新的微分延拓方程 ， ) = y 扛( t ) ) = 一( d f 扛) ) - 1 f ( z ) ，z ( 0 ) = z o ( 3 - 1 ) 8 求解高维非线性方程组的沿场线擞分延拓法 它准确地描述了场线的微分方程求解此方程，直到f ( z ) = o ，就 可得到了所需的根矿 前面我们说过如果设方程组f ( z ) = o 的根是矿，它的j a e o b i a n 矩 阵d f ( z ) 在矿的某邻域g = ( 矿) cq 中非奇异已知f ( z ) = o 的 一个近似值知g ，方向矢量 y 扛) = 一( d f ) ) _ 1 f ) 由于在邻域( 矿) 中每点z 都对应着一个方向y ( z ) ，因此他们在区 域( 矿) 中构成了一个向量场，这些向量曲线都向点矿汇集的如图 孓1 ( 其中矿= ( 1 3 3 3 3 ，o ) ) 图3 1z 向量场向根矿汇聚图 而一般地说，在计算过程中，在接近根的时候，f ( z ) 变小，方 向数y ( z ) 也变得很小，而z ( ) 的变化很小，可能当t _ o 。，才有可能 z ( t ) 一矿因此，适当大的t 后也可以采用较大步长当计算的根达到 一定的精度以后即可以终止计算，或者接近根以后改用牛顿迭代 由于方程组( 3 1 ) 是非线性常微分方程组，其可以有许多方法求 解( 见文献【1 7 - 2 2 1 ) ，为节省计算逆矩阵的次数，其中最好的可能是多 9 高校教师在职硕士学位论文 步法或显式龙格一库塔方法本文采用最简单的二阶显式龙格库塔 法求解 对于方程 一0 ) = y 0 ( t ) ) = 一( d f 扛) ) 1 f 0 ) ，z ( 0 ) = 护 其二阶显式龙格库塔公式为： 七l = 九y ( z n ) 如= y ( z 住+ 七1 ) 引入记号k ) = ( 七i + 如) 如+ l = z n + 0 5 ( 七1 + 乜) = + o 5 k 0 n ) 其中 为步长由于方程组( 3 1 ) 是一阶非线性常微分方程组，其准 确地描述了场的方向，为此我们有下面结论： 定理：假设在f ( z ) = o 的根矿附近的某个区域g 内，方向v ( x ) 形成一个场，所有的场线都朝向矿汇聚，f ( z ) 在矿的邻域g c d 上 可导，且d f ( z ) 非奇异，从这个场中的任何点一开始，求解方程( 3 。1 ) ，则有限步计算后得到的矿可进人矿的某6 邻域中 证明：限于考虑方程f ( z ) = o 的解是孤立的，且只有有限多个根 的情形 首先令，( z ) = 一( d f ( z ) ) 以f ( z ) ，设在矿的邻域g c d 内，以一为 起点的连接矿的场线z ( t ) 满足： 一( t ) = y ( z ( t ) ) = 一( d f 扛) ) 一1 f ( z ) ，z ( 0 ) = z o 其中z ( t ) 一z ( ) = 矿，用七阶显式龙格一库塔法求解，产生一个点列 知，z l ，晚，z 3 ，z n + i 如图冬2 在求解过程中点列跏，钆z 2 ，z n ，z n + 1 总落在以z o 为起点的 一条从点护开始到连接矿的场线z ( t ) 形成的带宽为笏的一个带 风( z o ，矿) = z ( z ( t ) 一正z ( ) + 6 ) ，o g _ o ) 则乃( z ) 0 一g 即 ，t m + n 哆佃= 芍+ 巧( z ) d t + ( g e ) m ，“ 所以 l i mz ? + m _ o o ， m + 。 这不可能，与有限矛盾 2 或巧( z ) 没有极限，则巧( z ) 在邻域岛( 矿) 中振动，这对于光 滑函数来说这不可能，也与有根矿矛盾 由此说明在根矿附近的某个区域g 内，方向y ( z ) 形成一个场 所有的场线都朝向矿汇聚的条件下，则从这个场中的任何点护开 始，通过求解方程组( 3 1 ) 都可以得到近似根扩落到矿的6 邻域中， 而且这样算得的根，其精度至少保证为二阶，因为我们所用的解微 分方程组的方法其精度至少为二阶，如三阶显式龙格库塔方法精 度可以为三阶等等，这里不再一一介绍 通过上面的理论分析及后面的数值实例的计算，我们得到对高维 的非线性方程组的求解算法 为了计算一个高维的非线性方程组的所有的根，我们不可能像我 们第五章分析的那样绘出其奇线，也不可能绘出其c o n t o 曲线，在前 述和后继的分析基础上我们可以得出如下的结沦：有界区域可以划 分为若干小区域，每块中都有方程组的一个根，在此小区域中，每一 点都有通往根的一条场线，这样我们在其中任何取一点，作沿场线的 微分延拓方程，即可求出此根 1 2 求解高维非线性方程组的沿场线饭分延拓法 高维的非线性方程组的多解问题的沿场线微分延拓法一般算法 如下： 1 在有限区域上均匀地或随机地布置适当多个点胁，i = 1 ，2 ， ， 2 以每个点n 为起点，作微分延拓计算，适当多步以后，例如l y ( z ) i = l o 4 ，可转入n e w t o n 迭代，则可得到一个根z 记在x 中；适当多 步以后，若l y ( z ) l 不减小，则方程组无相应的根，那么终止本次求根 计算 3 若以另一点乃为起点计算，得到一个根z ；与x 中的已有的根 比较，如果不相同，记入x 中若有一个相同则弃去z ；，这样x 中记 下高维问题的所有相异的根 在下面的章节里我们将举几个数值实例来分析和说明该方法的 可行性和正确性 1 3 高校教师在职硕士学位论文 第四章一维数值例子 考虑单元函数 ，= e 一矿， 其导数为，= 一矿，其n 佩0 n 方向为y = 一亭= e 1 王一1 考虑微分同 伦方程 一( t ) = y 扛) = e 1 一卫一1 ，z ( 0 ) = 0 ，( o ) = e 一1 我们可以观察到y ( z ) = o 的根为z = 1 下面我们用最简单的e 让f d r 公式 z n = z n l + l ，( z n 1 ) ， 来求解此方程取 = o 1 ，分别计算n = 2 0 ，n = 5 0 ，则r = 2 ，t = 5 我 们将计算得到的结果分别绘于下图1 4 中将n = 5 0 的计算结果分 别列于表l ，2 表1 ，l =【) 1 ，n = 5 0 步；，。= 5 o ，计舁巧，尔筮1 一z 加= o 0 0 3 1 0 0 1 7 1 80 3 0 0 70 4 0 2 00 4 8 3 80 5 5 1 40 6 0 8 00 6 5 6 00 6 9 7 10 您2 4 0 7 6 3 10 7 8 9 80 8 1 3 20 8 3 3 80 8 5 1 80 8 6 7 80 8 8 2 00 8 9 4 50 9 0 5 60 9 1 5 5 0 9 2 4 3o 9 3 2 20 9 3 9 2 0 9 4 5 50 9 5 1 10 9 5 6 1o 9 6 0 6o 9 6 4 6o 9 6 8 20 9 7 1 4 0 9 7 4 3 0 9 7 6 90 9 7 9 30 9 8 1 40 9 8 3 2 0 9 8 4 9 0 9 8 6 40 9 8 7 8o 9 8 9 00 9 9 0 1 0 9 9 1 1 0 9 9 2 00 9 9 2 8 0 9 9 3 5 0 9 9 4 2 0 9 9 4 80 9 9 5 30 9 9 5 80 9 9 6 20 9 9 6 6 0 9 9 6 9 表2 =叭，n = 5 0 步；r = 5 u ，丌异办，尔匿知= u u u 8 4 1 7 1 8 31 5 3 0 81 3 6 7 41 2 2 3 51 0 9 6 0o 9 8 2 60 8 8 1 50 7 9 1 2 0 7 1 0 50 6 3 8 1 0o 5 7 3 30 5 1 5 20 4 6 3 10 4 1 6 3o 3 7 4 3 0 3 3 6 6o 3 0 2 70 2 7 2 20 2 4 4 8o 2 2 0 2 0 1 9 8 10 1 7 8 20 1 6 0 3 0 1 4 4 30 1 2 9 8 0 1 1 6 80 1 0 5 10 0 9 4 50 0 8 5 10 0 7 6 6 0 0 6 8 90 0 6 2 00 0 5 5 80 0 5 0 20 0 4 5 2 0 0 4 0 7 0 0 3 6 60 0 3 2 90 0 2 9 60 0 2 6 7 0 0 2 4 00 0 2 1 60 0 1 9 40 0 1 7 5 0 0 1 5 70 0 1 4 2 0 0 1 2 80 0 1 1 5 0 0 1 0 3o 0 0 9 3 0 0 0 8 4 1 4 求解高维非线性方程组的沿场线微分延拓法 由上面的计算结果说明：用微分同伦方程组( 3 1 ) 来解非线性方 程是可行的而通过下面几个图的比较我们又发现，在固定步长九的 情况下，只有计算步数n 足够大的时候，计算得到的解才比较接近方 程的真解矿n 一2 0 步的解的余量为1 一z = o 0 7 5 7 而n = 5 0 步的 解的为余量1 一z 砷= o 0 0 3 1 ，后者的误差明显比前者要小得多 图4 1 ： = o 1 ，n = 2 0 步，( t ，z ) 图 1 5 高校教师在职硕士学位论文 图4 2 ：i l = o 1 ，n = 2 0 步( z ，) 图 图4 - 3 ： = o 1 ，n = 5 0 步( t ，z ) 图 1 6 求解高维非线性方程组的沿场线徽分延拓法 图4 - 4 t ，l = o 1 ，n = 5 0 步，( z ，) 图 通过上面4 个图的比较发现：在计算过程中，在接近根的时候，f ( z ) 变小，方向数y ( z ) 也变得很小，而这时z ( ) 的却变化很小，n = 5 0 时，解的余量l 一细= o 0 0 3 1 ，函数值的余量= o 舢8 4 通过进一步 计算，当n 一1 0 0 步时，解的余量1 一锄= o 0 0 0 1 ，1 一动l = o ，函数值的 余量知= o 0 0 0 1 ， = o ，从函数值的余量看，n = 5 0 时，知= o 0 0 8 4 ， 而n = 1 0 0 时，南= o 0 0 0 l ，多算了5 0 步它们的函数值才改变o 0 0 8 3 ， 这说明在接近根的时候，z ( t ) 的变化是很小的由于在零点附近，( z ) 已经很小用均匀剖分已不合适，效率很低这说明后面的计算要 适当改变步长，这样求得的根才接近真解上面4 个图，节点的取 值为白= 如一i + i l ，如果改变节点的取值，将其改为岛= o ，一l + j ，或 2 ，= 2 + j 2 之类的，而保持参数 = o 1 不变，计算表明其对计算 结果没有影响因为微分同伦方程组( 3 1 ) 与t 无关这样我们可以 选用适当的步长来提高计算的效率先取均匀剖分取l = o 1 ，计算5 步，再取较大的非均匀剖分取步长i l l = o 1 木i ，计算1 0 步，得到的结 果列于下表3 、4 1 7 高校教师在职硕士学位论文 表3 计算，余量1 一z 1 5 = o ， 0 f0 1 7 1 810 3 0 0 7io 4 0 2 010 4 8 3 810 5 5 1 4l0 6 0 8 0io 7 0 4 010 8 0 7 310 8 9 2 3 0 9 4 9 20 9 8 0 510 9 9 4 3 0 9 9 8 9l0 9 9 9 9l1 0 0 0 0 霰4 丌舁办，策笪r 1 5 = 。) ， i 1 7 1 8 31 5 3 0 81 3 6 7 41 2 2 3 51 0 9 6 00 9 8 2 60 8 8 1 5 0 6 9 6 50 4 7 6 30 2 7 7 5 io 1 3 4 7 0 0 5 2 60 0 1 5 50 0 0 3 10 0 0 0 30 0 0 0 0 l 图4 5 t 先求j l = o 1 ，n = 5 再求九= o 1 木i ，n = l o 步，t = 6 o ，( t ，z ) 图 求解高维非线性方程组的沿场线饭分延拓法 图4 _ 6 t 先求，l = o 1 ，n = 5 再求 = o 1 伽= 1 0 步，t = 6 o ，( z ，) 图 由表3 ，4 我们发现改用非均匀步长l i = o 1 幸i 来计算，只要计算 1 5 步就得到其真解矿= 1 ，使，= o ，这样可以节省计算的步数，大大 提高计算效率图垂5 和4 6 为相应的计算结果图当然，当直接计算 达到根矿附近的时候，我们可以改变计算的方法，用经典的n 嘲o n 迭代法或其它方法得到更准确的近似解本例不再介绍 1 9 高校教师在职硕士学位论文 第五章二维数值例子 5 1二维数值例子， 为了进一步验证第三章新方法的正确性，我们考虑两个未知数 x = ( z ，) 的二次方程组，( 本例的前部分来自文献【1 ，5 】) ，= 0 + o 5 ) 2 4 + y 2 4 1 = 0 ，夕= ( z 一0 5 ) 暑，一0 5 = 0 ( 5 - 1 ) f = ( ，9 ) 的j 8 c o b i 矩阵是 一r 掣40 甜 它的行列式j = o 5 0 2 一可2 一o 2 5 ) ，显然，它的奇线是一条双曲线 o 2 5 ( 户一可2 0 2 5 ) = 0 ( 5 - 2 ) 两个函数，9 有方向场为 咐卜蚪础c 耻击( 2 y 篇左芝貉言黑，4 ) 两条曲线，= 0 + o 5 ) 2 4 + ! ，2 4 一l = o ，9 = 扛一o 5 ) y c = o ，有4 个交点： p l = ( 1 4 2 5 7 ，0 5 4 0 1 ) ，舰= ( o 8 3 5 9 ，1 4 8 8 4 ) ， 尹b = ( 一2 4 9 3 0 ，一o 1 6 7 1 ) ，尹q = ( 0 2 3 1 4 ，一1 8 6 1 5 ) 此两曲线4 个交点p i ，仡，阳，m ，及相应的两条双曲线s i ，s 2 ，绘于图5 1 它们的奇线是两条对称双曲线 & ，& ：o 2 5 ( z 2 一! ，2 一o 2 5 ) = o ， 它们分全平面为4 个子域马，j = 1 ，2 ，3 ，4 ，但d ：和风并未被奇线分 开，它们组成了一个统一的区域现= d 2 + 仇+ 岛，这里q = 一g 求解高维非线性方程组的沿场线微分延拓法 z q ，箩= o 2 是一直线段我们将看到，它好象是被原来的两条直线 ( 奇线) 撕开了一样 图5 - l ，椭圆与抛物线有4 个交点，双曲线奇线 图5 2 t 矢量场y ( z ) = 一d f 一1 ( z ) f ( z ) 2 1 高校教师在职硕士学位论文 注意，现在原点( o ，o ) 不再是奇点，且直线岛也不是奇线但在此 直线岛附近，解此非线性方程组将遇到很大的麻烦 我们将它的矢量场y ( x ) 绘于图5 - 2 由图看到，在每个子域毋 中，大多数矢量y ( x ) 是朝向点弓汇集的，但例外的地方是接近直线 q 的邻域( 在这里矢量y ( x ) 平行于驴轴) 以及点( 口，o ) 附近( 在这里 矢量y 僻) 在d 。的一侧接近扩轴，在d 2 + 忱的一侧几乎平行弘轴) 在这些地方矢量y ( z ) 的方向改变很剧烈，几乎任何方法求解都难以 成功( 除非采用越过奇线的办法) 若取协中的任一内点作为起点，用牛顿迭代法计算，我们发现， 在矿的某邻域g = r ( 矿) cq 内，如果初值黝很接近矿，则通过计 算能得到其比较精确的解，如在点p t 的邻域中取勋= ( 1 。5 ，一o 。5 ) 只要 5 步，就能得到解z 5 = ( 1 4 2 5 6 8 ，o 5 4 0 1 4 3 ) ，很精确；但是在矿的某邻域 g = ( 矿) cq 内，如果初值勋远离矿，接近奇线，如在点胁的邻域 中取知= ( 一o 4 ，o ) ，通过计算，则其在第一步就一下子穿过奇线跳到 点( 1 9 5 5 ，一o 5 5 5 5 5 6 ) ，然后再慢慢收敛到另一个解p l ，而不是收敛到解 p 4 ，其解曲线扭动得很厉害，这种逼近路径的随机性表明：牛顿迭代 法的计算结果是无法预料的，是不可靠的，说明了其对初值的严重依 赖性 若取毋中的任一内点作为起点，用一般的延拓法计算，见图5 3 我们发现，每个零点b 的吸引域a ( b ) 都几乎接近整个子域d ，但 直线段岛，点( 口，o ) 及奇线& ，岛的某邻域例外注意，例如，虽然从 尸= ( o 5 6 ，o ) 出发的解曲线x ( t ) 能抵达尸i ，但它有很大的扭曲先越 过奇线s l ，然后再穿过s l 返回到只而从p = ( o 5 5 ，o ) 出发的x ( t ) 有 更大的扭曲其次从尸= ( o ，o 3 ) 到p 2 的x ( t ) 有相当大的扭曲，不同 的解曲线常在某些地方相交这种逼近路径的随机性表明，一般的延 拓法的计算结果在这些地方是无法预料的，也是不可靠的 求解高维非线性方程组的沿场线微分延拓法 图5 - 3 t 一般延拓法的解曲线图( 有些曲线相交) 现在再考察沿场线的微分延拓方程( 3 1 ) 一( t ) = y 扛( t ) ) = 一( d f 扛) ) _ 1 f ( z ) ，z ( o ) = z o 选起点来计算解曲线的路径的数值计算结果，