（计算机软件与理论专业论文）几类非线性问题的数值解法.pdf

几类非线性问题的数值解法 陈金海( 计算机软件与理论) 指导教师：李维国教授 摘要 本文讨论了处理具优势对称部分的非对称非线性问题的不精 确n e w t o n 方法。利用矩阵分裂技术，建立了求解此类问题的一 类不精确n e w t o n 分裂极小参量法、不精确n e w t o n 分裂对称l q 法( 简记：n e w t o n s m i n r e s ，n e w t o n - s s y m m l q ) ，并在合理的 假设下，证明了算法的收敛性。数值计算表明：n e 帆o n s m i n i 疆s ， n e w t o n - s s y m m l q 算法的收敛行为要好于一般求解非线性方程 组的n c w t o n - k r y l o v 子空间方法：n e w t o n - b i c g s t a b 、 n e w t o n g m r e s 和n e w t o n - m i n k e s 等算法。 建立了求解具有不定可对称化系数矩阵的线性代数方程组的 一类算法：预对称极小残量算法。该算法首先通过预对称技术， 将求解系数矩阵非对称的方程组的问题转化成求解系数矩阵对称 的方程组的问题，然后利用极小残量法求解所得对称方程组而得 原方程的一近似解。理论分析与数值实验表明，预对称极小残量 算法优于其它求解一般非对称方程组的k r y l o v 子空间方法，譬如： c g s ，g m r e s 等。同时获得了可对称化不定问题的不精确n e w t o n 方法，并针对问题的可对称化且不定的结构提出了不精确 n e w t o n - p s m i n i ：e s 算法。理论分析与数值试验表明， n e w t o n p s m i n r e s 算法优于其它处理可对称化不定问题的不精 确n e w t o n - k r y l o v 算法。 最后，本文讨论了一类处理正定可对称化线性方程组的算法， 基于系数矩阵可对称化的结构性质，提出了针对这种具有特殊结 构的非对称线性方程组求解的一类算法预对称正规共轭梯度 算法( p r e - s y m m e t r yr e g u l a r i z e dc o n j u g a t e dg r a d i e n t ( p r c g ) m e m o d ) ，理论分析和数值试验表明，对于正定可对称化线性代数 方程组的求解，新算法比文【l 】提出的求解正定可对称化线性代数 方程组的l r s c g 算法以及一般的处理非对称方程组的k r y l o v 方 法，譬如g m r e s ，c g s 等算法有更快的收敛速度，更高的误差 精度，以及更强的数值稳定性质。 关键词：具优势对称不定部分的非对称问题，k r y l o v 子空间方 法，可对称化问题，正规化，病态线性方程组 n n i n e r i c a ls o l u t i o n sf o rs e v e r a lc l a s s e so fn o n l i n e a r p r o b l e m s c h e nj i n - h a i ( c o m p u t e rs o f t w a r ea n dt h e o r y ) d i r e c t e db yp r o f e s s o rl iw e i - g u o a b s t r a c t i n e x a c tn e w t o n - k r y l o vs u b s p a c em e t h o d sf o rt h en o n - s y m m e t r i c p r o b l e m sw i l had o m i n a n ts y m m e t r i cp a r ta r es t u d i e di nt h i sp a p e r f o rt h en o n - s y m m e t r i cp r o b l e m sw i t had o m i n a n ts y m m e t r i cp a r t , a c l a s so f i n e x a c tn e w t o n - s p l i t t i n gm e t h o d s ：n e w t o n - s p l i t t i n gm i n i m a l r e s i d u a lm e t h o d , n e w t o n - s p l i t t i n gs y m m e t r i cl qm e t h o d ( d e n o t e d b r i e f l yb yn 钾n o n s m i n r e s ，n e w t o n s s y m m t o ) a l ep r e s e n t e d b ym a k i n gu s eo ft h em a t r i xs p l i t t i n gt e c l m i q u e u n d e rr e a s o n a b l e h y p o t h e s e s ，t h ec o n v e r g e n c eo ft h e s em e t h o d si sp r o v e d n u m e r i c a l c o m p u t a t i o n s s h o w t h a t n u m e r i c a lb e h a v i o r so ft h e n e w t o n - s m d 旧正sm e t h o d n e w t o n s s y 删l q m e t h o da r e s u p e r i o r t ot h o s eo fs o m es t a n d a r dn e w t o n - k r y l o vs u b s p a c e m e t h o d ss u c h a s n e w t o n b i c g s l ：a b n e w t o n - g m r e sa n d n e w t o n m 哝e se t e f o rl a r g es y s t e mo fl i n e a ra l g e b r a i ce q u a t i o n sw i t ht h ei n d e f i n i t e s y m m e t r i z a b l e c o e f f i c i e l l t m a r x ，w ep r e s e n t ac l a s so f p r e s y m m e t r y m i n i m a lr e s i d u a l m e t h o d ，b r i e f l y c a l l e da s p s a 倒d 昧e s - m e t h o d t h ep s m i l r e s m e t h o di se s t a b l i s h e db yf i r s t t r a n s f o r m i n gt h en o n - s y m m e t r i cs y s t e mo fe q u a t i o n si n t os y m m e t r i e j v s y s t e mo fe q u a t i o n sb yt h ep r e s y m m e t r yt e c h n i q u e ，a n dt h e n m i l i z i n gt h em i n i m a lr e s i d u a lo d 烈r e s ) m e t h o dt os o l v et h e s y m m e t r i cs y s t e mo fc q u a t i o l l sa n dg e tan e wa p p r o x i m a t i o nt ot h e o r i g i n a ls y s t e mo fl i n e a re q u a t i o n s t h e o r e t i c a la n a l y s i sa n d n u m e r i c a lc o m p u t a t i o n ss h o wt h a tt h ep r e s y m m e t r yt e c h n i q u ei s f e a s i b l ea n db e h a v i o r so f 也ep s m i n r e si ss u p e r i o rt ot h o s eo f s o m ek r y l o vs u b s p a c em e t h o d s ，w h i c ha r eu s u a la d o p t e df o rs o l v i n g g e n e r a ln o n - s y m m e t r i cl i n e a rs y s t e m s ，s u c h 舔c g s ；g m r e se r e ， a n dt h e ni n e x a c tn e w t o nm e t h o d sf o rs y m m e t r i z a b l ei n d e f m i t e p r o b l e m sa s t u d i e d i nt h i s p a p e r t h e o r e t i c a la n a l y s i sa n d n u m e r i c a lc o m p u t a t i o n ss h o wb e t t e rp e r f o r m a n c ec o u l db ea c h i e v e d i fa t t e n t i o n sa r ep a i do rt h es p e c i a ls t r u e t a r co fs u c hc l a s so f p r o b l e m s n e w t o n - p s m i n r e s m e t h o db c h a v 鼯w e l l a m o n g n e w t o n - k r y l o vm e t h o d sf o rs y r n m e t r i z a b l ei n d e f i n i t ep r o b l e m s f i n a l l y , ak i n do fp r e - s y m m e t r yr e g u l a r i z e dm e t h o df o rt h e n o n s y m m e t r i cl i n e a re q u a t i o n ss y s t e mi sd i s c u s s e d b a s e d0 1 1 c o m b i n a t i o np r e - s y m m e t r i ct e c h n i q u ea n dr e g u l a r i z e dc o n j u g a t e d g r a d i e n tm e t h o d t h en e wa l g o r i t h n v p r e - s y m m e t r yr e g u l a r i z e d c o n j u g a t e dg r a d i e n t ( p r c g ) m e t h o d ，i sp r e s e n t t h e o r e t i c a la n a l y s i s a n dn u m e r i c a lc o m p u t a t i o n ss h o wb e h a v i o r so ft h en e wm e t h o da l e m o r ee f f i c i e n ta n dr o b u s tt h a nl r s c gm e t h o dp r e s e n t e di np a p e r 【1 】 a n dt h o s eo fk r y l o vm e t h o d s ，w h i c ha l eu s u a la d o p t e df o rs o l v i n g g e n e r a ln o n s y m m m e t i cs y s t e m s ，s u c ha sg m r 卫s ，c g se r e k e y w o r d s ：n o n - s y m m e t r i cp r o b l e m sw i t had o m i n a n ts y m m e t r i c p a r t , k r y l o vs u b s p a c em e t h o d ，s y m m e t r i z a b l ep r o b l e m , r e g u l a r i z e d ， i l l - c o n d i t i o nl i n e a rs y s t e m 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得中国石油大学或其它教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示了谢意。 签名： 矽f 年夕月；日 关于论文使用授权的说明 本人完全了解中国石油大学有关保留、使用学位论文的规定， 即：学校有权保留送交论文的复印件及电子版，允许论文被查阅 和借阅；学校可以公布论文的全部或部分内容，可以采用影印、 缩印或其他复制手段保存论文。 ( 保密论文在解密后应遵守此规定) 学生签名： 导师签名： 细年岁月乡 日 5 年，月乡日 中国石油大学( 华东) 硕士论文第1 章引论 第1 章引论 非线性方程组 ，( 工) = 0( 1 1 ) 的数值求解，当j a c o b i a n 矩阵f ( x ) 为对称不定矩阵时，文 1 】讨 论了一类不精确n e w t o n 法n e w t o n k r y l o v 子空间方法。但当 ，( x ) 为非对称时，以往求解这类问题的算法，例如：不精确 n e w t o n g m r e s ，n e w t o n - b i c g s t a b 等，并不能保证其收敛性， 所以研究针对这类问题的特殊算法具有重要的意义。 本文首先研究j a c o b i a n 矩阵f ( x ) 几乎对称，或具有优势对称 部分时，非线性方程组( i 1 ) 的有效迭代法，在不精确求解方程组 f ( x k ) s k = 一，阮) 时，类似于文【3 0 】，通过对f ( x k ) 的对称分裂， 将方程等价地转化为一个不动点问题，然后在每步迭代时，采用 s m i n r e s 或s s y m m l q 求解方程的一个近似解。在一定的条件 下，我们证明了新算法的收敛性，并由二阶偏微分方程经有限差 分离散所得到的非线性方程组为例，进行了数值试验。计算结果 表明，对于j a c o b i 矩阵f ( 具有优势对称部分的非线性方程组， 新算法n e w t o n - s m i n r e s ，n e w t o n s s y m m l q 处理此类问题优 于一般的n e w t o n k _ , y l o v 子空间方法，譬如：n e w t o n - g m r e s ， n e w t o n b i c g s t a b 等【2 ，2 0 ，”1 ，具有较好的数值结果。 对于对称正定矩阵，共轭梯度法及其带预处理的共轭梯度法 i , 1 1 】( 简称为c g 方法) 是公认的有效算法；对于非对称矩阵，已有 g m r e s 类m j2 1 、b i c g 类【0 2 2 1 等多种比较成熟的算法。 介于两者之间的可对称化但不定非对称矩阵，它虽然不具备 中国石油大学( 华东) 硕士论文第1 章引论 对称正定矩阵那样良好的代数与分析性质。但也不象一般的非对 称矩阵那样结构上完全无规律可寻。离散偏微分方程得到的非线 性方程组，其d a c o b i a n 矩阵常常是大型稀疏的非对称但可对称化 不定矩阵，所以研究针对这类问题的特殊算法有重要意义本文 针对这类问题的可对称化结构【2 5 0 q 讨论完全针对这类问题的算 法。在这里我们称j a c o b i a n 矩阵非对称但可对称化不定的非线性 问题为可对称化不定问题。 对于求解大型稀疏线性代数方程组， a x = b ，a e r 非奇异，膏，b r ”，( 1 2 ) 当系数矩阵a 具优势对称部分时，文【3 0 】讨论了一类分裂极小残 量法( s p l i t t i n gm i n i m a lr e s i d u a lm e t h o d ( s m i n r e s ) ) ，这类算法的 实质是以矩阵分裂法为外迭代，以极小残量法为内迭代的内外迭 代算法，在实际计算中，这类算法取得了令人满意的效果。 本文研究了系数矩阵不定可对称化时，线性代数方程组( i 2 ) 的有效迭代算法。类似文 2 5 】，首先用预对称化技术将系数矩阵 对称化，然后再采用极小残量法0 v t r n r e s ) 求解( 1 2 ) 的近似解，这 也既是本文所建立的新算法预对称极小残量 法( p r e s y m m e t r i cm i n i m a lr e s i d u a lm e t h o d ( p s m i n r e s ) ) 的基本 思想，此类算法也可看作一种预处理迭代法【 8 ”】。以一类微分方 程经有限差分离散所得到的线性代数方程组为例。作了数值试验， 计算结果表明，对于不定可对称化线性方程组，新算法p s m i n r e s 较之一般的k r y l o v 子空间方法，譬如：g m r e s 或c g s 等，具有 更好的数值结果。 当系数矩阵是大型稀疏的正定可对称化矩阵，文 2 5 ，2 6 讨论 了一类预对称共轭梯度算法( l r s c g 算法是其中之一) ，这类算法 2 中国石油大学( 华东) 硕七论文第l 章引论 的实质是利用非对称的系数矩阵可对称化的性质，并结合共轭梯 度法而构造的一种预处理的共轭梯度法 1 5 , 1 6 , 1 7 】。但非对称的系数 矩阵对称化后，其条件数往往非常大，即非对称方程组( 1 1 ) 经预 对称化处理后将变成一病态的线性方程组。这必然给文 2 5 ，2 6 的 算法提出了挑战。 文献 1 】讨论了一类处理病态的正定对称线性方程组的算法 正规共轭梯度法( r e g u l a r i z e dc o n j u g a t e dg r a d i e n t ( r c g ) m e t h o d ) ，此类算法是以改善系数矩阵条件数为思想而提出的共轭 梯度法，我们可以把此算法看作一嵌套型【3 】的共轭梯度算法。 本文基于文 1 1 的正规共轭梯度法及文 2 5 ，2 6 1 的预对称化技 术，提出针对一类病态线性方程组( 系数矩阵对称化后) 的新算法 预对称正规共轭梯度算法( p r e - s y m m e t r yr e g u l a r i z e d c o n j u g a t e dg r a d i e n t ( p r c g ) m e t h o d ) ，我们在讨论了新算法收敛性 后，以一类非自共轭椭圆型微分方程经有限差分离散所得到的非 对称线性代数方程组为例，作了数值试验，计算结果表明，对于 病态的正定可对称化线性代数方程组，新算法较之一般的处理非 对称线住方程组的k r y l o v 子空间方法1 1 4 1 ，譬如：g m r e s t 7 1 或 c g s t l 0 】及文 2 5 】中的l r s c g 算法等，具有更好的数值结果。 中国石油大学( 华东) 硕士论文第2 章具优势对称部分的非线性问题 第2 章具优势对称部分的非对称非线性问题的不 精确n e w t o n 分裂算法 2 1 引言 非线性方程组 f ( x ) = 0( 1 1 ) 的数值求解，当j a c o b i a n 矩阵f ( x ) 为对称不定矩阵时，文 1 】讨 论了一类不精确n e w t o n 法- n e w t o n - k r y l o v 子空间方法。但当 f ( 力为非对称时，以往求解这类问题的算法，例如：不精确 n e w t o n - g m r e s ，n c w t o n - b i c g s t a b 等，并不能保证其收敛性脚l ， 所以研究针对这类问题的特殊算法具有重要的意义。 对于求解大型稀疏线性代数方程组， 出= b ，a r ”非奇异，善，b r ”，( 1 2 ) 当系数矩阵a 具优势对称部分时，文d o 讨论了一类分裂极小残 量法( s p l i t t i n gm i n i m a lr e s i d u a lm e t h o d ( s m i n r e s ) ) ，这类算法的 实质是以矩阵分裂法为外迭代，以极小残量法为内迭代的内外迭 代算法，在实际计算中，这类算法取得了令人满意的效果 本文研究j a c o b i a n 矩阵，( 对几乎对称，或具有优势对称部分 时，非线性方程组( 1 1 ) 的有效迭代法，在不精确求解方程组 f ( h ) 吼= 一，( 札) 时，类似于文 3 0 】，通过对f ( ) 的对称分裂， 将方程等价地转化为一个不动点问题，然后在每步迭代时，采用 s m i n r e s 或s s y m m l q 求解方程的一个近似解。在一定的条件 中国石油大学( 华东) 硕士论文第2 章具优势对称部分的非线性问题 下，我们证明了新算法的收敛性，并由二阶偏微分方程经有限差 分离散所得到的菲线性方程组为例，进行了数值试验。计算结果 表明，对于d a c o b i a n 矩阵，( z ) 具有优势对称部分的非线性方程 组，新算法n e w t o n - s m i n r e s ，n e w t o n - s s y m m l q 处理此类问 题优于一般的n e w t o n k r y l o v 子空间方法，譬如： n e w t o n g m r e s ，n e w t o n - b i c g s t a b ：, u l 等，具有较好的数值结 果。 2 2 n e w t o n - s m i n r e s ，n e w t o n - s s y m m l q 算法 求解线性方程组( 1 2 ) 的分裂极小残量法，算法描述如下： 算法2 1 1 3 0 1 。( s m i n r e s 算法) i 输入最大的外迭代步数屯。和停机标准占；最大的允许内 迭代步数女。 2 输入初始近似x ，计算r o ) = b a x ( ”，并置，= = 0 3 置净x 运行m i n r e s 算法七。次得到线性方程组 m y = k 。+ 6 的近似解y 7 k ) 4 置x ( 。# y 7 0 _ ) ，：，+ l ，并计算r ( f ) = 6 一出( “ 5 如果i ，i h s s l i ，o 0 2 或， k ，则输出x “，否则，转 步3 在算法2 1 中，若用s y m m l q 算法代替m i n r e s 算法，则 可得到s s y m m l q 算法。 算法2 2 ( s s y m m l q 算法) 1 输入最大的外迭代步数k 和停机标准占；最大的允许内 中国石油大学( 华东) 硕士论文 。 第2 章具优势对称部分的非线性问题 迭代步数t 一 2 输入初始近似工“。计算，( o ) = b 一舭( ”，并置，# 0 3 置j ，0 9 譬工m 运行s y m m l q 算法l j 。次得到线性方程 组岣，= n x + 6 的近似解j ，厶j 4 置工# y l , m ，则输出x “，否则，转 步3 在n e w t o n - k r y l o v 算法中，用s m i n r e s 或s s y m m l q 算法 取代k r y l o v 子空间方法，即得n e w t o n - s m i n r e s 或 n e w t o n - s s y m m l q 算法。 算法2 3 ( n e w t o n - s m i n r e s 算法) ( a ) 给定迭代初值， ( b ) 从k = 0 起，步长为1 ，直到满足收敛准则，执行： 选取适当的仉，以w 口为迭代初值做s m i n r e s 迭代，直 到第m 步，迭代值使得= f ( x d w + f ( x d 满足 0 0 2 仇8 f ( x i ) 8 2 ，令& = 令x | “= x k + s t 在算法2 3 中，若用s s y m m l q 算法代替s m i n r e s 算法， 则可得到n e w t o n - s s y m m l q 算法。 注2 1 从算法2 1 ，算法2 2 ，算法2 3 的定义可以看出： 1 如果分裂矩阵= 0 ( 零矩阵) ，则s m i n r e s 算法与 n e w t o n - s m i n r e s 算法分别退化为m i n r e s 算法与 n e w t o n - m i n r e s 3 0 l 算法。 2 n e w t o n - s m i n r e s 算法，一般不能直接构造无矩阵算法， 6 中国石油大学( 华东) 硕士论文第2 章具优势对称部分的非线性问题 只有当分裂矩阵n = 0 ( 零矩阵) 时，才可以直接构造无矩阵算法 【l t l o , n 。 3 对于n e 卅o n - s m i n r e s ，n e w t o n - s s y m m l q 算法，可以 与n e w t o n k r y l o v 算法一样，运用线搜索技术2 1 或信赖域方法【4 j 4 l 等技术构造全局收敛的算法。 4 实际计算中，选择何种技术构造的全局算法主要取决于所 解决的问题的结构与特性。 2 3 算法的收敛性分析及其实用的分裂策略 用a 7 表示矩阵a e r 的转置矩阵如果a 7 = a ，则称彳为 对称矩阵：若4 对称，且爿的特征值包含在区r 日q a ，b u c ，d 】中， 并且a b 0 c ( d ，则称a 为对称不定矩阵，对于矩阵a r ” 的分裂a = m n ，如果m 7 = m ，则称其为对称分裂；如果 p ( m 一) l ，则称其为收敛分裂：如果对某种范数有 吖“nl i l ；则称其为矩阵a 在这种范数意义下的一个收缩分 裂；对于矩阵a 置的对称分裂a = m n ，若7 = 一，则 称其为对称反对称分裂。 定义3 1 对于矩阵a r 的对称分裂a = m n ，若 0 2 吒( 一) ，则称彳具优势对称部分。( 其中，o r 。( 4 ) 为矩阵a 的最小奇异值) 离散偏微分方程得到的非线性方程组，有一类问题，其j a c o b i 矩阵是大型稀疏非对称的，但却具有优势对称部分，研究这类问 题具有重要意义。在这里我们称d a c o b i 矩阵具优势对称部分的非 对称非线性问题为具优势对称部分的非对称问题。 中国石油大学( 华东) 硕士论文第2 章具优势对称部分的非线性问题 2 3 1 算法的收敛性分析 对于一般矩阵，g a * y l o v 方法不能保证不精确n e w t o n 法的强制 序列一致小于1 ，从而迭代过程中可能出现停滞现象。其结果是 导致一般的n c w t o n - k r y l o v 方法m w t o n b i c g s t a b ， n e w t o n - g m r e s ，n e w t o n - m i n r e s 等) 发生中断但对于 n e w t o n s m i n r e s ，n e m o n s s y m m l q 算法，我们却可以保证 强制序列一致小于1 这一条件在解的附近总可以满足。 引理3 1 【1 7 1 设m 置是对称不定矩阵给定初始近似 歹o ) r “，设歹) e r ”m i n r e s 算法用于线性方程组晒i = 占而 得到的第后个近似记芦) = f 一 矽”如果矩阵m 的特征值均 包含在【日，明v c ，d 】中，并且a 6 0 c d ，b 一口= d c ，则 成立 咿虬髂一1 br = 器。 引理3 2 【3 0 1 设一r “”是非奇异矩阵，a = m n 是爿在 l ：范数意义下的一个收缩分裂，且肘r ”为对称不定矩阵给 定初始近似工o 矗”，设b ，) 是从x 柳出发，由s m i n r e s 算法产 生的迭代序列，如果每外迭代步所采用的m i n r e s 内迭代步数均 为m ，则成立 b - a x 。1 1 2 o - ( m ) 怕一出 辄( 肼) 0 矧臣1 ( 1 + 删肚) + l 眦：。 中国石油大学( 华东) 硕士论文第2 章具优势对称部分的非线性问题 定理3 1 假设非线性方程组f ( x ) = 0 满足如下性质：( 1 ) 存 在五使f 似) = 0 ；( 2 j f 在矗的邻域内连续可微；( 3 ) 矩阵，( 矗) 相 对于其一对称分裂f ( 矗) = m ( x ) 一似) ，具优势对称部分；且 该分裂为f 似) 在i ：范数意义下的一个收缩分裂， m ( x ) r 为对称不定矩阵在用n e w t o n - s m i n r e s 方法求解 过程中，如果每一步s m i n r e s 迭代的初值取0 ，在s m i n r e s 算法中每步外迭代所采用的m i n r e s 内迭代步数均为研。则存在 l 的一个开邻域d ，使v x k d ，相应于s m i n r e s 算法产生的 迭代序列冬：f ) 有 黪舻( 以) + 尸x k ) f k 峪玎扎) i i z 其中】7 为一不依赖于也，与s m i n r e s 外迭代次数有关的数。 证明因为f ( 矗) 具优势对称部分，即由 0 剑 r i h 吒( ，f 似) ) 知，f ( 矗) 非奇异由f 陬) 的连续性知： 孤。的一个开邻域d ，使w d ，f o ) 非奇异， f ( y ) = m ( y ) 一( y ) 是f ) 在l ：范数意义下的一个收缩分 裂，如同引理3 1 ，设 彳( y ) 的特征区间为【q ，气】u 【0 ，嘭】，且 卟 刊，b y - a y = 办铲剖， k = m , o a x o 肚i , ic , 型d , i j l ，p = m a x i n ( y ) m ( y ) - i h 。蚓理3 嬲a ， i i ，( 以) + f ( 也) s ? i h 盯( 埘) | | f ( ) + f ( 屯) s y 4 i i ：， 舯嘶脚( 藩卜州t “：， 中国石油大学( 华东) 硕士论文第2 章具优势对称部分的非线性问题 船( x d + ，( 毪) 仙马i ，( 黾) + f ( 黾) i i z s a c m ) ，( 磁) + ，( 吒) 妒1 0 2 s 盯( 珊) i f ，i 以) + f ( ) j ? 0 2 2 鲥】p ) + p 归。 协 矧曙1 0 + 叫谢肿一泐 。r1 一p 、 烈弋酉丽j + 1 ( 3 1 ) 时，由n e w t o n - s m i n r e s 方法产生的迭代序列k ) 收敛到非线性 方程组f ( x ) = 0 的解。 证明根据定理3 1 ，给定s m i n r e s 算法外迭代步数， n e w t o n - s m i n r e s 算法收敛的一个充分条件是蛎 l ，即 1 0 中国石油大学( 华东) 硕士论文 第2 章具优势对称部分的非线性问胚 2 ( 筹) 悖1 即， 算法产生的迭代序列g ， 有 囊n l f l f q k l f t ( x k ) s k1 1 2 r l l fc x , ) 1 1 2 帖捌“ 中国石油大学( 华东) 硕士论文第2 章具优势对称部分的非线性问题 2 3 2 实用的分裂策略 在用n e w t o n - s m i n r e s 或n e w t o n 2 s s y m m l q 算法求解中， 将j a c o b i a n 矩阵f 7 ( x d er ”做如下分裂： m ( x k ) ：塑出掣盟，n ( x k ) ；些掣( 3 2 ) 显然，m ( x d ，n c x , ) 分别为对称，反对称矩阵。且 f ( x a = 膨( ) 一( 黾) 为f ( 黾) 的对称- 反对称分裂。 对以上策略，我们给出了户( ( 也) 1 ( 以) ) 1 的一个充要条 件 定理3 4 在用n e w t o n - s m i n r e s 或n e w t o n s s y m m l q 算法 中，计算到第k 步时， 即在求吼使得 0 ，( 以) + f ( x k ) s ti h s 仇8f ( x k ) l h 成立时，设，( 机) 采用( 3 2 ) 式 定义的分裂，则当f ( x d 相对于此分裂，具优势对称部分时， p ( m ( x k ) - 1 n ( 黾) ) ix 瓴) x i 成立。 证明( 必要性) 设x 是m ( 以) 。n ( x a 的任意特征值五所对应 的任意特征向量。即m ( x 。) 一n ( x a x = 缸，也既是 ( 以弦= 2 m ( x , ) x 成立，且x 7 n ( x t 弦= 触7 m ( x d x ， 由 p ( m ( x i ) 。n ( x d ) 1 ，可知 i a i l ，易得 ix r n ( x , ) x1 = 4 缸7 m ( x k ) xl qx r m ( x k ) xl 成立。 ( 充分性) f ( x d 相对于( 3 2 ) 式定义的分裂，具优势对称部分， 即：0n ( x i ) i h 盯。( ，( x o ) ，由此知d e t ( ( h ) ) 0 ，即m ( x i ) 非 奇异。对m ( x k ) 。n ( x k ) 的任意特征值z ，x 是其所对应的任意特 中国石油大学( 华东) 硕士论文第2 章具优势对称部分的菲线性问题 征向量，即m ( x t ) 。n ( x k 弦= a x ，故( 孔h = 2 m ( x k 碡，且 x tn b t ) x = 缸l m ( x d x ， 由此易得：i x t n ( x i hj 刊缸7 m ( x k ) x 1 4x 7 m ( k h i ，即i 五l 1 ， 由五的任意性即知结论成立。 对于a 具优势对称部分的概念，我们可以进一步作如下探讨： 定义3 2 对于矩阵a r ，作对称分裂彳= 肘一，如果 l l 1 1 2 1 1 1 i n 吒( 一) ，吒( m ) ，则称a 具强优势对称部分。( 其中 仃。( a ) 和o - ( m ) 分别为矩阵a 和肘的最小奇异值) 。 注3 1 从定义可以看出：若矩阵a r 具强优势对称部分， 则可知a 具优势对称部分。 倒3 1 跫j ：- - 2 x 2 的矩阵彳= f 1 ：ll ： 5 ，其对称反对称 分裂为爿= 膨一，其中吖= ( ，：，1 ? 3 ) ，= ( 。乏一之。2 ) 。 容易算出：8 n 1 1 2 = 0 0 2 0 0 ，a 、m 的最小奇异值： 盯2 ( 爿) = o 0 2 9 8 ，2 ( ，) = o 0 3 0 0 。显然， 0 0 2 盯2 ( 爿) 盯2 ( m ) 即矩阵a 具强优势对称部分。 对于具强优势对称部分的矩阵彳，我们可以得出更进一步的 结论： 引理3 3 若矩阵a r “”相对于一对称分裂爿= m 一，具强 优势对称部分，则此分裂为收缩分裂。 证明a 具强优势对称部分，故对其相应的一对称分裂 a = m n 有 8n8 2 口。( 彳) s 仃( m ) = im 。虻， 中国石油大学(