（计算数学专业论文）非线性方程组奇异问题的数值解法.pdf

摘要 本文主要研究了求解非线性方程组奇异问题的l e v e n b e r g - m a r q u a r d t 方法。我们选 取l e v e n b e r g - m a r q u a r d t 参数为当前迭代点处函数值的模和梯度模的某种组合。利用 j a c o b i 矩阵的奇异值分解技巧，我们证明了在局部误差有界的条件下， l e v e n b e r g m a r q u a r d t 方法产生的迭代点列局部二阶收敛于方程组的某个解。并分别给出 了结合信赖域技巧的全局收敛的l e v e n b e r g m a r q u a r d t 方法和采用共轭梯度法求解线性 方程组的不精确的l e v e n b e r g m a r q u a r d t 方法。全文共分五章。 第一章，简单介绍了求解非线性方程组奇异问题的研究背景和意义。 第二章，在弱于非奇异性条件的局部误差有界下，利用奇异值分解证明了 l e v e n b e r g m a r q u a r d t 方法的局部二阶收敛性，给出了若干新的l e v e n b e r g - m a r q u a r d t 参 数以及相关的l e v e n b e r g m a r q u a r d t 算法，并进行了数值试验。 第三章，结合信赖域技巧，提出了具有全局收敛性的l e v e n b e r g m a r q u a r d t 方法， 证明了算法具有全局收敛性和局部二阶收敛性，并给出了相关的数值试验。 第四章，提出了不精确的l e v e n b e r g - m a r q u a r d t 方法，每一步采用共轭梯度法求解 线性方程组。给出了算法的局部超线性收敛性和局部二阶收敛性，并给出了相关的数值 试验。 一 最后，给出了论文的结论。 关键词：奇异非线性方程组，l e v e n b e r g - m a r q u a r d t 方法，信赖域技巧，不精确方 法，二阶收敛 n u m e r i c a ls o l u t i o n so ft h es y s t e mo fs i n g u l a r n o n l i n e a re q u a t i o n s z h a n gh u a r e n ( c o m p u t a t i o n a lm a t h e m a t i c s ) d i r e c t e db yp r o f l iw e i g u o a b s t r a c t t h i st h e s i sf o c u s e so nt h el e v e n b e r g - m a r q u a r d tm e t h o df o rs o l v i n gt h es i n g u l a r n o n l i n e a rs y s t e mo fe q u a t i o n s w ec o n s i d e rt h ec h o i c eo ft h el e v e n b e r g - m a r q u a r d tp a r a m e t e r a ss o m ec o m b i n a t i o no ft h en o r n lo ft h ef u n c t i o na n dt h en o r mo ft h eg r a d i e n t w ep r o v e u n d e rt h el o c a le r r o rb o u n dc o n d i t i o nt h a tt h el e v e n b e r g m a r q u a r d tm e t h o dw i t ht h i s p a r a m e t e rc o n v e r g e n c e sq u a d r a t i c a l l yt oas o l u t i o no ft h es y s t e mo ft h ee q u a t i o n sb yt h e t e c h n i q u eo ft h es i n g u l a rv a l u ed e c o m p o s i t i o no ft h ej a c o b im a t r i x a n dw ea l s op r e s e n tt h e g l o b a l l yc o n v e r g e n tl e v e n b e r g m a r q u a r d ta l g o r i t h mb yu s i n gt r u s tr e g i o na p p r o a c ha n dt h e i n e x a c tl e v e n b e r g m a r q u a r d ta l g o r i t h mw i t ht h ec o n j u g a t eg r a d i e n tm e t h o df o rl i n e a r e q u a t i o n s t h i sp a p e rc o n s i s t so ff i v ec h a p t e r s i nc h a p t e ro n e ，w eb r i e f l yi n t r o d u c et h eb a c k g r o u n da n dt h er e s e a r c hs i g n i f i c a n c eo ft h e s y s t e mo fs i n g u l a rn o n l i n e a re q u a t i o n s i nc h a p t e rt w o ，u n d e rt h ew e a k e rc o n d i t i o n st h a nt h en o n s i n g u l a r i t y , w ep r o v et h a tt h e l e v e n b e r g 。m a r q u a r d tm e t h o dh a sl o c a l l yq u a d r a t i cc o n v e r g e n c eb yt h et e c h n i q u eo ft h e s i n g u l a r v a l u ed e c o m p o s i t i o no ft h ej a c o b im a t r i x s o m en e wl e v e n b e r g m a r q u a r d t p a r a m e t e r s a n dt h ec o r r e s p o n d i n gl e v e n b e r g - m a r q u a r d ta l g o r i t h m sa r eg i v e na n dt h e n u m e r i c a le x p e r i m e n t sa r ec a r r i e do u t i nc h a p t e rt h r e e ，u s i n gt h et r u s t r e g i o nt e c h n i q u e s ，w ep r e s e n tt h eg l o b a l l yc o n v e r g e n t l e v e n b e r g m a r q u a r d tm e t h o d w ep r o v et h a tt h ea l g o r i t h mh a st h eg l o b a lc o n v e r g e n c ea n d t h el o c a l l yq u a d r a t i cc o n v e r g e n c ea n dg i v et h ec o r r e s p o n d i n gn u m e r i c a le x p e r i m e n t s i n c h a p t e rf o u r ，w ep r e s e n tt h ei n e x a c tl e v e n b e r g m a r q u a r d tm e t h o dw i t ht h e c o n j u g a t eg r a d i e n tm e t h o df o rl i n e a re q u a t i o n sp e ri t e r a t i o n w ep r o v et h a tt h ea l g o r i t h m h a st h el o c a l l ys u p l i n e a rc o n v e r g e n c ea n dt h el o c a l l yq u a d r a t i cc o n v e r g e n c ea n dg i v et h e c o r r e s p o n d i n gn u m e r i c a le x p e r i m e n t s a tl a s t ，s o m ec o n c l u s i o n sa r eg i v e n k e y w o r d ：s y s t e mo ft h es i n g u l a rn o n l i n e a re q u a t i o n s ，l e v e n b e r g m a r q u a r d tm e t h o d ， t r u s t - r e g i o nt e c h n i q u e ，i n e x a c tm e t h o d ，q u a d r a t i cc o n v e r g e n c e 关于学位论文的独创性声明 本人郑重声明：所呈交的论文是本人在指导教师指导下独立进行研究工作所取得的 成果，论文中有关资料和数据是实事求是的。尽我所知，除文中已经加以标注和致谢外， 本论文不包含其他人已经发表或撰写的研究成果，也不包含本人或他人为获得中国石油 大学( 华东) 或其它教育机构的学位或学历证书而使用过的材料。与我一同工作的同志 对研究所做的任何贡献均已在论文中作出了明确的说明。 若有不实之处，本人愿意承担相关法律责任。 学位论文作者签名：张坐型二 r 期：年月 e l 学位论文使用授权书 本人完全同意中国石油大学( 华东) 有权使用本学位论文( 包括但不限于其印 刷版和电子版) ，使用方式包括但不限于：保留学位论文，按规定向国家有关部f - j ( 机 构) 送交学位论文，以学术交流为目的赠送和交换学位论文，允许学位论文被查阅、 借阅和复印，将学位论文的全部或部分内容编入有关数据库进行检索，采用影印、 缩印或其他复制手段保存学位论文。 保密学位论文在解密后的使用授权同上。 学位论文作者签名：熬坐仨 指导教师签名： 同期：年月 日 慨卅年石月j - 日 中国石油人学( 华东) 硕上学位论文 1 1 研究问题的内容和意义 第一章绪论弟一早珀了匕 随着科学技术的高速发展和计算机的广泛应用，求解形如 f ( x ) = 0 ( 卜1 ) 非线性方程组问题越来越多的被提了出来，其中f 是r 疗_ r ”的连续可微函数。例如非 线性有限元问题，非线性断裂问题，弹塑性问题，电路问题，电子系统计算以及经济与 非线性规划问题等都可转化为非线性方程组的求解问题，只要包含有未知函数及其导函 数的非线性项的微分方程，无论是用差分方法或有限元方法，离散化后得到的方程组都 是非线性方程组。 但在实际问题中有许多非线性方程组，( x ) = 0 的求解问题是奇异问题，即其解x 点 处的导算子为一奇异算子。比如某种临界现象的物理问题，许多弹性力学和流体力学中 的问题，特别是弹性力学中的奇异现象、流体力学中具有不稳定解的湍流现象都可以归 结为非线性方程组奇异问题的求解。但是，长期以来，这类问题的求解一直难以得到圆 满解决。目前对于这类问题迭代算法的超线性收敛性问题的研究仍是国际上数值计算与 数值优化领域的热点问题之一，这是因为经典的求解非线性方程组的算法都很难直接推 广到相应的奇异问题中去。迄今为止，对这类问题提出的算法大都不具有超线性收敛性、 或在较为苛刻的条件下具有这种性质，但不具有实用性。如果这类问题的研究能在一定 程度上取得突破的话，对于非线性理论研究与发展具有极其重要的意义。 1 2 非线性方程组奇异问题的研究背景和现状 1 2 1 牛顿法研究的历史和现状 下面介绍用牛顿法求解非线性方程组奇异问题的历史。 众所周知，用于求解非线性方程组( 卜1 ) 的牛顿法采用迭代格式 x i + l = x i 一( f ( x i ) ) f ( x i )( 1 2 ) 并在j a c o b i 阵f7 ( x ) 是非奇异的时候，这种格式具有二阶收敛性。但当f ( x ) 奇异的 时候，利用上面的格式求解就很难保证收敛。为了克服这一现象，早期应用牛顿法思想 第一章绪论 求解非线性方程组奇异问题时，主要的想法是尽量避开f ( z ) 的奇异性。即采用下面两 ( a ) x 七+ l = x 七- ( f ( x 七) + 1 ) 一1 f ( z 七) ； ( b ) x 七十l = 一以( f7 ( x 七) ) 一1 f ( x 七) 若采用公式( a ) ，要找一个适当的正数，其目的是修ej a c o b i 矩阵( f ( ) + n ) 成为 非奇异。若采用公式( b ) ，每次迭代要确定一个4 ( o ) ，目的是为了保证舻( ) 0 单i 周- f 降，并且使不在奇异集合 xid e t ( f 7 ( x ) ) = 0 ) 之内。到了8 0 年代中期，一部分学者，如 d e k e r 巾- 和k e l l e y ，g r i e w o r k 2 1 ，a l l g o w e r 3 1 ，不再刻意回避奇异性，他们通过对n e w t o n 迭代序列的收敛性态研究，进一步发现牛顿序列收敛的性质与j a c o b i 矩阵f o ) 的零 瞄f y r y1 ， i ( x ) yj ， l j y a m a m o t o 5 1 所构造的扩张系统 暖f q r y 蝌1 l ( x ) y i ， l l 这些系统都有解z 。= ，0 ，v ) 对这类扩张系统比较实用的是9 0 年代a h o y 6 1 所设计 m ，= d e 篇， ( 1 3 ) 在对值空间r ( f ( x 。) ) 附加条件限制下，t o ) 是满秩的，d e t ( f ( x ) ) 和零空间的向量 密切相关。把d e t ( f ( ) f ) ) 在z 处展开，并利用g a u s s - n e w t o n 方法由( 卜3 ) 确定的丁( x ) 简 化，得到迭代公式： 2 中国石油人学( 华东) 硕士学位论文 工t “= x 七一d 七一! 二皇二老乏亏善兰挚v c ，一4 ， 其中d 七，v 七，u t 由方程组仇以= f ( x 七) ，b 女d 女= f ( x ) ，b ”七= q ，吼= f ( x | i ) + p q r 确定。同一时期，d a n ，f r a n k 和s c h n a b e l 7 l j l 入了t e n s o r 模型，其主要思想是在离 散化的线性模型后加上一个二阶项，即： m r ( x 。+ d ) = f ( x 。) + j c d + 去t 嬲 其中疋r 删雕一是在点x c 附近由，( ) 的二阶导数的信息给出，即， t = a r g m i n i l 乏k i 之= z 七，七= l ，2 ，pj 其中，z 七的定义可见p 1 。t e n s o r 模型的目标关键在于寻找一个d r n 使得d 是问题 m i n i m 丁( t + 酬： 的解。在j a c o b i 矩阵f ( x ) 是秩亏一并g u7 f + ) w 0 的条件下，基于理想的t e n s o r 模型所产生的迭代序列局部地、并且二步q 一超线性收敛于解，但是离散化的t e n s o r 模 型却是三步q 一超线性收敛于解。自1 9 8 4 年以来，该扩张方法被认为是求解非线性方程组 奇异问题的一个非常不错的方法。 近年来，非线性方程组奇异问题的求解有了新的发展。g er e n d o n g 8 1 在迭代公式( 1 4 ) 的基础上，采用修正的a b s 算法，避免了直接计算 。) 7 f ( h ) v 。，节省了计算量。0 5 年，g er e n d o n g s l 对于f ( x ) 的秩r a n k ( f ) ) = 疗一，1 ， 0 如果盯 0 ，使得对所有的 ( x ，占) ，由l e v e n b e r g m a r q u a r d t 方法( 公式( 卜8 ) 和公式( 卜9 ) ) 产生的迭代点列扛i 满足 i i x t + , - x l l 等i x k - - x * i i + 蒜o x t - x 1 2 及 i i x + , - x l l 等等产i x k - - x * o 0 ，使得护( x ) 忙c d i s t ( x ，x ) ，v x n ，则称f ( x ) 在 内局部误差有界。 注意到，如果j o c a b i 矩阵j ( x ) 在方程组( 卜1 ) 的解x 处是非奇异，则x 。为( 卜1 ) 的唯 一解。因此，f ( x ) 在x 的某邻域内有局部误差界；但反之未必正确。例如，对于函数 f ( x 。，x ：) = o 屯一l ，o ) r ，则f ( x 。，x ：) = o 的解集为x = 仁r 2ix ，- - o ，i 故d i s t ( x ，x ) = l x 。1 不难看出，如果选取= 扛r 2i 一口 0 ，使得l e v e n b e r g m a r q u a r d t 参数以满足 c l d i s t ( x i ，x ) 胁c 2 d i s t ( x i ，x ) ( 2 - 1 ) 我们证明了在弱于非奇异性条件的局部误差有界下，l e v e n b e r g - m a r q u a r d t 方法二阶收 敛于解集x ，给出了若干新的l e v e n b e r g - m a r q u a r d t 参数以及相关的 l e v e n b e r g m a r q u a r d t 算法，并进行了数值试验。 2 1引言 考虑非线性方程组 f ( x ) = 0 ( 2 2 ) 其中f ( x ) ：r ”一r ”是连续可微的函数。在文章中，我们总假设方程组( 2 2 ) 的解集非空， 记为x + ，在所有情况下，1 1 | | 表示欧式范数。 l e v e n b e r g m a r q u a r d t 方法用如下线性方程组的解d 女作为在点以处的一个搜索方 向： u：j+pki)d=一j：fk(2-3) 这里j k = j ( x ) ，以0 是迭代参数。l e v e n b e r g m a r q u a r d t 步( 卜8 ) 是牛顿步 d：=一j：f(2-4) 的一个改进，通过引入非负参数i ，l e v e n b e r g m a r q u a r d t 方法克服了j i 几乎奇异或坏 条件时牛顿步所带来的困难。选取恰当的参数肌可保证矩阵( 刀以+ 版，) 非奇异，而且 能够避免出现过大的0 以8 ，另外，当j k 奇异时，牛顿步( 2 4 ) 没有定义，而正参数段保 证了l e v e n b e r g m a r q u a r d t 步( 卜8 ) 是有意义的。 定理1 1 表明，若j ( x ) ( x + x ) 非奇异且初始点x 。离x 充分靠近时， l e v e n b e r g m a r q u a r d t 方法( 公式( 卜8 ) 和公式( 卜9 ) ) 产生的迭代点列二阶收敛于x 7 第二章局部收敛的l e v e n b e r g - m a r q u a r d t 方法 但在实际运用中，方程组解处的j a c o b i 矩阵j ( x ) 非奇异这一条件往往过强。最近， 众多作者【1 5 - 1 9 1 选取不同的l e v e n b e r g - m a r q u a r d t 参数，在弱于非奇异条件的局部误差有 界的条件下，证明了l e v e n b e r g - m a r q u a r d t 方法的二阶收敛性。在心满足条件( 2 1 ) r 目 标函数局部误差有界的条件下，我们证明了l e v e n b e r g m a r q u a r d t 方法的二阶收敛性， 并给出了若干新的l e v e n b e r g m a r q u a r d t 参数和相应的算法，数值试验表明新选取的 l e v e n b e r g - m a r q u a r d t 参数是非常有效的。 2 2 l e v e n b e r g m a r q u a r d t 算法及其局部收敛性分析 首先给出求解问题( 2 2 ) 的l e v e n b e r g m a r q u a r d t 方法。 算法2 1 ( l e v e n b e r g m a r q u a r d t 算法) 步骤1给定x o r 厅，占0 ，置k ：= 0 ； 步骤2 如果i i 刀疋| i 0 8 中国石油人学( 华东) 硕士学位论文 和0 b 1 使得 i j ( y ) 一，( z ) 1 1 l 。y x | i ，觇，y ( x ，6 ) = s 啦一x 。i l 0 ，0 c d i s t ( x , x ) ，觇( x ，6 ) = x x f i 0 ，c 4 0 和c 5 0 ，使得对任意 x i ，x t + 】( x ，b 2 ) 有： ( a ) i i d t 忙c 3 d i s t ( x ，x ) ； ( b )l k 畋+ e0sc 4 d i s t ( x , ，x + ) 3 住； ( c ) d i s t ( x , + l ，x ) c s d i s t ( x i ，x ) 3 坨 证明 由( 2 7 ) 等价于( 2 5 ) 可得 矿i ( d 女) 仇( 五一x i ) 又因为砘 ，b 2 ) ，所以可得 和 1 1 五- x , i i 0 x * - - x k 鸬 ( 2 1 3 ) ( 2 1 4 ) 五一x i i - ，b 2 ) 1 0 k，- ，仇 上段 2 中国石油大学( 华东) 硕十学位论文 证明 首先证明对任意k ，如果而( x ，b 2 ) ，= 0 , 1 ，k ，那么+ l ( z ，b 2 ) 然后，由x 。n ( x ，) sn ( x 。，b 2 ) 司得弓1 理成立。我们考虑k = 0 和k 1 两种情况。当 k = 0 ，由引理2 1 可得 忙一x h + 矾- - x * h x 。一x h + l l a 。1 1 - ，+ c ，d i s t ( x o , x ) ，+ c ，i k 。- - x * 0 ( 1 + c ，) ， 由( 1 + c 3 沙b 2 ，可得t ( x ，b 2 ) 下一步，我们考虑k 1 的情况。由 x f ( x ，b 2 ) ，= 0 , 1 ，k 和引理2 1 可得，对任意的，= l ，尼有 d i s t ( x ，x ) c s d i s t ( x l - l ，x ) 3 坨 c 9 ，一1 l l x 。一x 8 e ) r ，( 三) e 7 - l 其中由恢一x l 卜，和，上2 c s 可得最后一个不等式成立。因此由引理2 l 可得，对任意 ，= 0 ，1 ，k 有 甄咧碡叩( 扩1 因此可得 x k + l - - x * i x - - x * l l + 骞i i d ，i i - r + c ，r z i = t 0 ( 圭) 售7 。1，= 0二 叩科卜l ( + 南， ( 1 + 2 c 3 ) ，i b 其中由，i 三i 可得最后一个不等式成立。因此可得x 川o + ，6 2 ) 口 现在给出算法2 1 的收敛性定理。 定理2 1 若假定2 1 成立，r x 。充分靠近问题( 2 2 ) 的解集x ，那么由算法2 1 产 生的迭代序列 x 。 超线性收敛于问题( 2 2 ) 的某一解。 第二章局部收敛的l e v e n b e r g - m a r q u a r d t 方法 证明 如果d i s t ( x o ，x ) c ；2 ，由引理2 1 ( c ) 可得 d i s t ( x ，x ) d i s t ( x t ，x ) ，v k 0 因此，不妨设v 后，以( x ，6 ) 又由引理2 1 ( c ) 可得 上式蕴含着 d i s t ( x t ，x ) 0 ，r a n k ( ：) = ， 设以的奇异值分解为： 1 2 o 0 y ”= u i ：砰r 中国石油大学( 华东) 硕十学位论文 以= u 。曙 = 巩，吃+ 。：即吃 其中，” 0 ，r a n k ( ) = ，m k ( 托) = q 0 以下为了方便起见，省略 ，u 幻，圪，( 汪1 ，2 ，3 ) 中的下标后，因此以的奇异值分解为： 以= u 。 lk r + u 2：曙 引理2 3 设假定2 1 成立。若以( z ，b ) ，则有 ( a ) ( b ) ( c ) l p 。u - e0 d ( 忙。一瓦i i ) ； l i u ：畦刚d ( 恢一x | | 2 ) ； l i u 。u ；硎o ( 慨一训2 ) 证明 由( 2 1 1 ) n - q - 苣f 接得到结论( a ) 。e t t ( 2 8 ) 和矩阵扰动理论洲可得 从而可得 i d i a g ( z 。- z ；，：，o ) l l - l p , 一，0 三，l l x 。一x + 8 0 。一：0 三。l l x 。- x l 和1 2 ：1 1 _ l 。i i x 。一x + i l ( 2 1 8 ) ( 2 1 9 ) ( 2 2 0 ) 令= 一o f t ，其中以是以的p s e u d o 逆。也就是说，是问题m i n i i e + 以j 0 的最小二 乘解，因此由( 2 一l o ) 可得 l i u 。u ；p , i _ - r , + 3 k j 。i - i 丘+ 以( 瓦一x 。) 1 - - - o ( 1 1 x 。一瓦0 2 ) 令五= u 。k7 ，瓦= 一嚣e 由于瓦是问题m i n 0 r + z s 0 的最小二乘解，因此由( 2 1 0 ) 和( 2 2 0 ) 可得 1 3 、y00i0000卜l， 第二章局部收敛的l e v e n b e r g m a r q u a r d t 方法 i l p ：u ；+ u ，u ；) e0 = i i + z 瓦0 由于u ：与u 3 的正交性可得结论( b ) 。 + 工( 瓦- - x k ) l i i f , + 以( 五- - x k ) 忡l i ( z - j k ) ( x k - - x k ) 0 下面给出算法2 1 的二阶收敛性定理。 ：哆( 瓦一训 口 定理2 2 若假定2 1 成立，则算法2 1 产生的迭代序列 x 。，二阶收敛于问题( 2 2 ) 的解。 和 证明由。的奇异值分解可得 = 一k 区；+ 以i ) - 1 f k + jk dk = e u 。 u f 毋一睚2 一+ g 。i ) - 1 ：u ：t r 。医一2 + a 。，) _ 1l u f 疋一u 2 ( 2 2 1 ) ：侄；+ 。，) 1 ：u ；e = 。u 。篷；+ 。z ) - 1u f r + 。u ：区；+ 。i ) - 1u ；疋+ u ，u ；e ( 2 2 2 ) 由于 坼) 收敛于x + ，不失一般性，可假设 三。l l x 。一x i i 2 对所有足够大的k 成立。因此由( 2 2 0 ) 口- - f 得 和 ；+ 。，) - 10 l i i 20 陋；帆训瓴1 由引理2 3 可得 慨+ 以d , i | o ( 恢x 一 因此有 ( 盯：一三，l l x 。一x l i ) 2 玎) + d ( 恢一x + | 1 2 ) 1 4 4 万 盯， ( 2 2 3 ) ( 2 2 4 ) ( 2 2 5 ) u i i i i + ) 岭i 旷 坼 一 一 k 厶 d v | 0 ，使得 c 。d i s t ( x kx ) 段= m i n i 疋i i ，i l f 。i i - 0 ，使得 1 主1 ( 2 1 1 ) 可得 因此，可得 删万慨一训 p ；e l i p 圳f ( 以) 一f ( 瓦) 0 罡i l h 一墨l 万忙。一t0 p ；e0