（计算数学专业论文）非线性多重分裂算法的收敛性研究.pdf

- 作线性方程组 摘要 f f z l = 0 在物理、力学，工程等问题中有广泛的应用背景。随着科学技术的进步以及汁算 工具的不断更新，它的算法研究获得进一步的深入发展。特别是并行计算技术的 出现和发展，使得求解非线性方程组的数值计算方法的研究获得新的进展，得到 r 一系列研究成果。 近些年来兴起的多重分裂算法，具有很好的并行结构，从而是易于进行并行 汁算的一类数值计算方法。在并行计算机发展的今天，此类算法更显现出发展的 夺吼对于线性微分方程边值问题的多重分裂赞：法，其收敛性理论以及收敛速度 的分析酃得到r 较为系统的研究。而对于非线性微分方程边值问题的多重分裂算 法，无论就算法的结构而言，还是就理论分析方面而言，都还存在着许多有待研 究的课题 本文首先介绍将多重分裂算法与科学及工程计算中广为应用的一种区域分解 技术一s c h w a r z 算法相结合，得到了一类多重分裂加性s c h w a r z 算法以及两水平 的多重分裂加性s c h w a r z 算法用于求解非线性方程组 f ( x ) = a x c ( x ) 一b = 0 其中。4 r “非奇异，b 咒 ，g 为一非线性映射。这类算法具有很好的并行 性能，因而特别适用干并行计算，其次，考虑到非线性多重分裂算法用于求解非线 性方程组( + + ) 的局部收敛性定理已有许多，这里我们着重考虑对于一类较为特殊 的非线性方程组的全局收敛性和单侧收敛性。并对算法做了改进，用 z 步n e w t o n 法来代替求得每个非线性多重分裂子问题的近似解，并给出相应的收敛性结论 最后，对文中所提到的算法均列出数值算例，证实了算法的有效性 关键词：数值计算；多重分裂； s c h w a r z 算法；非线性方程组；收敛 非线性多重分裂算法的收敛性研究 a b s t r a c t ( ) h a sb e e nw i d e l ya p p l i e di np h y s i c s ，m e c h a n i c sa , n de n g i n e e l i n g w i t ht h ed e v e l o p n l e n to fs c i e n c ea n dc o m p u t i n gt e c h n i q u e ，m a n ya l g o li t ，h n t sf o l s o l v i n gt h es y s t e m o fn o n l i n e a se q u a t i o n sh a v eb e e r sc o i s s t tu c t e da n d n n a l y z e d 。e s p e c i a l l yw i t ht h ed e 一 、c 1 0 1 ) m c n to fp a r a l i dc o m p u t i n gt e c h n i q u e ，c o r r e s p o n d i n gn u m e r i c a la n dt h e o s e r i c s e s e a i c h e sh a v em a d eg r e a tp r o g r e s s m u m s p l i t t i n gi n e t h o d s ，w h i c hh a v eb e e nw i d e l ys t u d i e di nr e c e n t l yy e a r s ，a r e ac l a s so fn u m e r i c a lc o m p u t i n gm e t h o d sh a v i n ga y e s yg o o dp n a l l e ls t r u c t u r e a s asc s u l l t h e ya r te a s i l yt ob eu s e dt oc a l c u l a t ei np a r a l m w i t ht h ed e v e l o p n m n t ( 什p a r a l l e lt e c h n i q u e 、t h es t u d yo f t h e s em e t h o d sh a sb e e ng r e a t l ys t i n m l a t e d a sf j rt h eb o u n d a r y v a l u ep r o b l e m so fl i n e a rd i f l b r c n t i a le q u a t i o n s m u l t i s p l i t t i n g m e t h o d sh a v eb e e r se x t e n s i o n a l l ys t u d i e d t h et h e o r i e sc o n c e r n e dw i t ht h ec o n v e r g e m ：ea sw e l la st h ec o n v e r g e n tr a t ea n a l y s i sh a v eb e e ne s t a b l i s h e ds y s t e m a t i c a l l y o nt h eo t h e rh a n d ，a sf o rt h eb o u n d a r y v a l u ep io b l e m sf o rn o n l i n e a rd i f l b xe l l t i a l “l u a t i o n s b o t h t h ea l g o r i t h m i cc o n s t r u c t i o na n dt h et h e o r e t i c a la n a l y s i so f n m l t i s p t i t t i n gm e t h o d s a r en e e d e dr e s e a r c h e si nt h ef i e l d sa r er e l a t i v e l yf e w i n t h i sp a p e r ，w c f i r s t l yp r e s e n tam u l t i s p l i t t i n ga d d i t i v es c h w a r za , i g o si t h m a n dat w o l e v e ln m l t i s p l i t t i n ga d d i t i v es c h w m za l g o r r h mf o rs o l v i n gas y s t e mo f n o n l i n e a re q u a t i o n s r ( x ) = a x g ( z ) 一b = 0 ，( t t ) w h e r ea 月“i san o n s i n g u l a rm a t r i x ，6 r 川i sag i v e nv e c t o ra n dg i sa g i x e n n o n l i n e a rm a p p i n g t h i sk i n do fa l g o r i t , h m s ，c o m b i n i n gm u l t i s p l i t r i n ga n d a d d i t i v es c h w a i za l g o r i t h m 、a r ee a s i l yt ob ea p p l i e dt oc o m p u t ei np a r a l l e l t h e ( , o u v e lg e n c ea n dc o n v e r g e n tr a t ei sa n a l y z e d s e c o n d l y ，c o n s i d e r i n gt h e r ea r em a n y l o c a lc o n v e r g e n c et l m o r i e so f n o n l i n e a s m u i t i s p l i t t i n gm e t h o d s ，w ee m p h a t i c a l l yp o i n t o u tt h eg l o b a lc o n v e r g e n c ea n d i m i l a t e ta lc o n v e r g e n c eo fs o l v i n gak i n do fr e l a t i v e l ys p e c i a ln o n l i n e a rs y s t e mo t ( a t i o n s 、，ea l s oc o n s i d e rt h ec o r t v e l 。g e n c eo fan o n l i n e a rm u t i s p l i t t i n gm e t h o d i l lw h i c l lt h es o l u t i o no ft h es u b p r o b l e m s a r ea p p r o x i m a t e db yt h ei t m a t i v es o l u t i o n s i i c l sa sm s t e p sn e w t o n si t e r a t i v es o l u t i o n i i 硕士学位论文 i nt h ee n d 、n u m e r i c a le x a m p l e sb a s e d0 1 1t h ea l g o r i t h m , sp l ( ；s e n t e d i l lt h i s p a p e ra ieg i v e na n dt h er e s u l t ss h o wt h e s ea l g o r i t h m sa l ee f f e c t i 7 e k e yw o r d s ：n u m e r i c a lc o m p u t i n g ；m u l t i s p l i t t i n g ；s e h w a r za l g o r i t h m ； n o n l i n e a re q u a t i o n s ；c o n v e r g e n c e 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其 他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个 人和集体，均已在文t p 以明确方式标明。本人完全意识到本声明的法律后果 由本人承担。 作者签名：l 虱蕊日期：) 口争年j 月o 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查 阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位 论文。 本学位论文属r 】二 1 、保密口，在年解密后适用本授权书。 2 、不保密圃。 ( 请在以上相应方框内打“”) 作者签名：l 墨後 铷锵斥气孕 日期：o 弘年，月矽口 日期拶u 埠月a j 日 第1 章绪论 1 1s c h w a r z 算法 1 8 7 0 年德国数学家has c h w a r z 首次用交替方法论证了两个相互重叠区域的 和集上l a p l a c e 方程d i r i c h l e t 问题解的存在性。稍后n e u r n a n n 注意刮这思想可 以用于求解两个柏互重叠区域的d i r i c h l e t 问题。1 8 9 0 年p i c a r d 进一步发展了 s c h w a l z 思想，用之于求解非线性椭圆型偏微分方程，并把算法定名为s c l m z 交 锛法( s a p ) 。经典的s c h w a r z 交替算法 2 1 给出了一类带有椭圆边值问题解的存 在性的构造性证明一个完整的区域被分解为可能互相重叠的子域，从一个初始 点开始迢近真解，每次迭代会交替的在每个子域上解一个较小的边值问题。由于 进行了区域分解，自然地在每个子域上引入了一些“人工”边界，而“人工”边界 j 二的值由其所在相邻子域上的迭代解交替着更新。s a p 算法已成为一种人们熟 知并被广泛采用的区域分解算法，可用于得到椭圆的、抛物的、双曲面以及偏微 分方程的连续或离散解1 2 “7 1 。 本世纪三十年代苏联数学家基于变分原理阐述s c h w a i z 算法，并推广到弹性 力学m 题上，其中尤以s o b o i e v ，m i k h l i n 的贡献最为卓越但直到6 u 年代以后， d 真正认识剖s c h w a r z 算法在数值分析方而的潜力，那时解矩形区域上的偏微分 方程出觋了一批新算法，如快速付氏变换，交替方向法及基于张量运算显式解， 这些算法对于非矩形区域均无用武之地。然而，s c h w a i z 算法可以把复杂区域分 解为若干相互覆盖的子区域，在予区域上可以用快速算法求解，这就增大了人们 研究的兴趣。此 l j 间，w e r n e r ，m i l l e r 和m i t c h e l l 等做了许多工作，m i l l e r 还给 m 了收敛性估汁。 但是，s c h w a r z 算法令人瞩目的发展还是近十年才开始的，其中并行汁算的 发展大大刺激研究者的兴趣。由前所述，经典的s c h w a r z 交替算法并不是并行算 法，康立山教授首先认识到s c h w a r z 算法在异步并行计算中的应用。把s c h w m z 算法与dc h a z g l l 等于1 9 6 9 年提出的混乱松弛法相结合，提出了解偏微分方程 的异步并行翁法1 8 “，异步并行算法的主要特征是它的过程在任何时候都不需要 等待数据输入，而是根据整体变量里最新信息来确定i t 一算是继续还是停止。异步 s c h w a i z 算法完全打乱经典s c h w a r z 算法的串行格局，充分考虑并行汁算机的特 点，假定每个子域q 对应一台处理机与一个解q 上边值问题的过程a ，| 4 ，的 运行依赖于a q ，上边值的最新信息。法国g l o w i n s k i 等应用s c h w a r z 算法加速共 轭梯度法，并在流体力学汁算上取得成功然而对s c h w a t z 方法作出全部解释当 归功于pl l i o n s ，他在首届国际区域分解算法会议的论文中，巧妙地把s c h w a r z 非线性多重分裂算法的收敛性研究 算法与投影方法联系起来。从而使那些看来复杂的收敛性证明，简化为对投影算 子的估计。对于多个重叠区域的情形，甚至非线性问题的s c i i w a i z 算法皆在统一 框架下得到处理。在第二屑国际区域分解算法会议上，l i o n s 又提出s d l w a i z 算 法的随机解释，把位势理论、布朗运动和s c t w a r z 交替方法联系起来，这种多学 科间渗透引起人们极大的兴趣 1 2 多重分裂算法 当今汁算机的发展已将计算方法的研究推向科学研究的前沿，科学计赞也已 经成为继伽利略与牛顿开创的实验与理论两大方法的第三种方法，并以前所未有 之势推动技术革命。在这场革命中，计算机与计算方法相互依存、相互配合，计 算能力的提高依赖于这两方面的发展。 在实践中提出的科学工程问题，如油、气藏的勘探与开发，大型结构工程、航 天器的设计，天气预报、反应堆的计算等，无不归结于求编大型偏微分方程，计算 区域往往足高维的、大范围的，其形态可能很不规则，给计算带来很大困难。为克 服这类问题，常将原问题的求解规划为在子域上求解，将大问题化为小问题，缩 i i , h 算规模，节省工作量，且算法可以是高度并行的，而多重分裂法正是具有此 类优点的一种偏微分方程数值解的新技术，f r o m m e r 及o i e m y ，w h i t e 等“q 对其已有一些研究成果。 假设给定一个线性方程组 这里a 矗“为非奇异矩阵，b r “为了通过迭代汁算得到( 1 1 ) 的解_ ， 0 l e a r y 和w h i t e i ”l 基于对系数矩阵a 进行一系列不同的分裂而得到一种多重 分裂算法。更确切地说，对a 的多重分裂定义为( m ，伊) ， = 1 ，一，l 。对 所有k 有m 。，n ，e “r n 。“，m “是非奇异的，a = 盯一n 。，而e 。是非负 的对角矩阵，且满足名。e = ，( n 阶的恒等矩阵) 。求解( 11 ) 相应的多 重分裂算法为 n = 0 1 ( 12 ) 其中扩。由下计算得到 m 。y “= 、，。“+ 6 、 = t t - ，l 。( 1 3 ) 这种多重分裂算法自然具有并行性，n 5 9 x 十s f 司n ，y “的计算是相互独立的， 当然可以以并行计算的方式分别得到。而且在并行的计算环境下，关于各个分裂 2 k 弘 胪 。m 硕士学位论文 分别进行计算，往往将这些结果的一部分组合起来构成整个多重分裂算法的达代 解，如扩。的第i 个分量不必计算若萨上相应的第i 个对角元为零元素。这样 就大大节省了计算的工作量，但其收敛理论远远不够明显和完整。n e u m a l l l l 和 p l e m m o n s z 7 j 则针对系数矩阵a 为 f 一矩阵或对称正定的特殊情形给出了收敛性 理论。 而对于求解非线性方程组 f ( z ) = 0 ， f j 一，( 14 ) 如果我们采用牛顿法来求解，则可以用多重分裂方法来求解在牛顿法中得到的线 性方程组，这种方法w h i t e i ”1 已采用。另一种方法就是将并行性直接引入问题 ( 14 ) ，即直接采用多重分裂法来求解此非线性方程组，相应地，提出了“非线性分 裂”这一概念，w h i t e “，“】，s h a o 和i ( a n g ”】均提到了由此概念所得到的非线性多 重分裂算法及其变形方法用于求解某些特定的非线性方程组。后来，f r o m m e r ”j 又 将加性s c h w a r z 方法和多重分裂法结合起来应用于求解一般的代数线性方程组， 同时给出了，一致的收敛性分析，该分析同样适用线性的二阶椭圆边值问题离散系 统的求解。而目前，对于多重分裂法的研究多局限于求解线性问题及其收敛性分 析，而实际遇到的问题可能是相当复杂的，因而对于非线性多重分裂及其收敛性 理论的分析是非常重要的。 3 非线性多重分裂算法的收敛性研究 第2 章一类多重分裂加性s c h w a r z 算法 2 1 引言 最初的s c h w a r z 算法可认为是一种乘性的s c h w a r z 算法的例子，而所谓的加 性s 。h i i i z 算法就是在每一迭代步中不再是交替地解子问题而是同步地解各个子 问题，整个削题的迭代解通过各个子问题的迭代解加权得到。加性的s c h w a l z 方 法已被证实在并行算法中是非常有效的，特别是可以作为一种预处理技巧。 加性s c h w a l z 方法的思想已经被用于一般线性方程组的求解1 2 0 “2 4 1 这些代 数加性s c h w a 】_ z 方法与区域分解有关但叉不尽相同，重叠子域的思想由重叠子系 统得到，提供了区域分解法与完全由代数背景得到的多重分裂方法的联系。多重 分裂方法在文献j 1 3 1 中已被采用，到目前为止，大量的论文都有所涉及 1 7 , 2 5 3 2 。 本章考虑非线性方程组 l - i - , ，4 圩m “为菲奇异矩阵，b 冗，c 为一非线性映射讨论求孵f 21 ) 的 一类多匠分裂加。h - s c h w a i z 算法和两水平多重分裂加性s c h w a r z 算法的收敛性和 收敛效率。 2 2 记号与算法 定义2 2 1 令a r “非奇异，称m ，e 。一，a = 1 ，l ，f = 1 ，l 为 的一个多重分裂，如果a = ，“一n ，k = 1 、，l ，且l 2 个非负对角矩阵 e lk r “x “清是 y e = 1 _ 1 ， ，l 。 一 = 1 据此，定义多重分裂加性s c h w a r z 算法的计算格式为： 上 “= fe y 一，n = 0 ：1 1 z 一 r 。u “。 = n z + g ( z 儿。) + 6 ， 七= 1 ， ( 2 2 ) ( 2 3 ) f 面0 f 入需用的一些基本记号和辅助结果1 3 3 ”t t 6 。 对于门”维向量z ，如果鼢 ( ) 矾，i = l 一，n ，则记z ( ) 或者 一 ( ) o 称向量。为正( 非负) 向量，如果 ( ) ( ) ；对于矩阵，可引入 4 类似记号。如果非奇异矩阵a 满足a1 0 ，则对n ”上的任一正向量，。，显然 有a 一17 1 0 。 如果| 4 = ，一满足m _ 1 0 且n o ( m 一1 n 0 ) ，则称4 ： i 一 为_ 的一个正则分裂( 弱正则分裂) 。显然正则分裂也是弱正则分裂。 引理2 2 1 【：1 没非奇异矩阵a 满足a 一1 0 ，且4 = m n 为一弱正则分裂 则p ( ，_ 1 _ ) 0 ，使得a u 0 ，同样可以得到a1 0 ( 可 见文献【3 3 ) 。 引理2 2 2 洲a 二二= ( o u ) ，b 二= ( b u ) r ”“，若a 为m 一矩阵，且当i 时，有6 。0 ，则当a 1 3 时，口也是a ，一矩阵，且0 b 一1 a。 对于给定的矩阵a = ( o u ) 冗“，它的伴随矩阵( a ) = ( o d ) r 。定 义为m ，= i r _ i ：刊ii ；则肖e a ，为n ，一矩阵，称a 为一矩阵。由引理 222 可导出一个关于h 一矩阵的类似结沦。 引理2 2 3 漫a b r “，且( a ) ( b ) ，若a 为日一矩阵，则b 也是h 赶! 阵。 对于矩阵a = ( o 。) r “”，其绝对值ia i 定义为la l = ( io 。1 ) r “ 荇为月一矩阵，则可以碍到关于a1 有界性的相关结论。 引理2 2 4 若a r “。为h 一矩阵，则有ia 一1 1 ( a ) 。 这里，我们还需定义冗“上的加权最大范数| | 忆，即 z ) 。 f z i n a xj 一 1 彰n h “ 其中u r “为某正向量 引理2 2 5 没a r ”。”，u r ”且“ 0 ，如果la u p n ，则】| a l l 。d 特别是对所有“r “，均有i ia ：c i 。e l i 圳。成立，其中 a 忆= s u p | | a 0 忆 ，i tl ，= 1 非线性多重分裂算法的收敛性研究 证明：v aer “，有( 以：咄= ，n ：c z ，q = 釜】f c ，( 等) ，贝 捺p n 剖t 。吲h 善n h 小沁外忆。 11 由”队定义，可得到l la r f 。刚z l l 。 2 3多重分裂加性s c h w a r z 算法及其收敛性 根据定义2 21 ，我们可以得到多重分裂加性s c h w a r z 算法中第扎步迭代的 解n 、 = 1l 。记 ：( ( t “) 7 ，( c m ) 7 ) 7 r “ l 乳i 晤e i , k ( m k 叫 fr j1 7 若气舻r 1 g 扛“) 又记y 1 = ( m 2 ) 一1 n “，= 1 ，一，l l、t 、。 瞎伊气m “6 ) j 邮“ l、丁r 谣伊气肼“g z ”勺) j 咖“口 则( 22 ) ( 23 ) 可改写为 x ”+ 1 = h x “4 - q g ( x 8 ) 4 - c 设映射f ：dcr 。一d ，其中d 为一闭集。若存在一非负矩阵p 月“一，使得对v x ，d 均成立 f ( z ) 一，( v ) i p i z 一耵 ( 2 4 ) ( p u ) 则称f 在d 上是p 有界的。若该非负矩阵p 的谱半径p ( p ) 1 ，则我们称? 在d 上是p 压缩的 6 、， l 咀 吁 l l e e 硕士学位论文 引理2 3 1 m 1 没映射g ：dcr 。一d ，是) 压缩的，其中d 是| ! j j 集，则对任 何、。t t d ，迭代序列一t 1 = g ( ) 收敛于g 在d 上的唯一不动点c ，并有误 差估汁武 j z “一z 1 ( 一p ) 1 1 “一m 1 1 = 12 、。 引理2 3 2 令a 躬“。“是非奇异的 里d 为一i 羽集。记i y + = ( ( t + ) 7 ， 且j 41 o g 在dc 冗”上p 有界，这 ( z 。) 7 ) 7 月“，则有 x + ：h x + 十国g ( x + ) + c ， ( 25 ) 若( “+ q p ) 1 ，则x 是x t l x + q g 瞵) + c 的唯。1 不挈穿，。+ 为( 2 1 ) 的解，? ：f ( 怎。e ，m ( m * ) 一t ) 7 ，( ；：，e i “( m 。) 。) 1 ) r 川。 证明：闪a _ ，一g ( 出) 一b = ：0 ，有c + = ( 彳。) 一。( j 。+ + g ( z + ) + b ) ，七= 1 ，一l a 故l l 烈m 寸1 盹_ 善州m 甲1 g q k = l w 厂6 一= i k i = e ( a i “) 。1 ( 。+ g + 6 ) ：、r ，“r 4 z j 即( 25 ) 式成立。 一由于g 是p 有界的，当然有h + q g 是h + q p 有界的。当非负矩阵 户：。h 十q j ) 的谱半径( 户) o t 且 1 u ， ( 26 ) 刚p ( 一i ) 1 。又若有p 【0 ，1 ) 使得 成立，则p ( a ) 目 1 。 证明：类似引理2 25 中的证明，知成立 ( 27 ) 定理2 3 1 设存在一个向量u r ” = 1 ，则有p ( h + q p ) 0 ，使银 l ( ，。) 一1 ( n _ tp ) 1u o ，+ q 尸f ，的第f 块为 f 。( a i ) “( + - p ) tz 。= _ g 强i ( ，6 ) 一2 ( + ，) ) f k = 1 即有i + q p i u u 。由引理2 3 3 ，知p ( h + q p ) l 。 推论2 ，3 - 1 假定a 非奇异且a 一0 ，j 。，。”为一非负矩阵。若p p ) l ，h 一 。州。一n “，k = 1 一，l 为一弱正则分裂，则p ( h + q p ) 1 。 证明：令e = ( i 。 ，1 ) 7 r “，q = ( a 一一一1 e = ( 一i 一1 p ) - _ 一。e ，因 ( l “p ) 0 。又a = m 。n 。，= 1 l 为弱正则分 裂，是非负矩阵，自然有a = 严一( 。+ p ) ，= 1 ，三为i 的弱正则分 裂。则有 f 严) 叫( 。斗j d ) iu = ( 妒厂1 ( 十户) z c = ( 一( 彳。) ( t p ) ) u = u 一( m “】1 e “ 推论2 3 、2 若( - 4 ) 一p 是且扛短阵， 一n 。，满足( a ) ( p ) 一l n i ， p 冗“。“为一非负矩阵假设a ；m 。 k = 1 ，l ，则有p ( h + q p l 0 ，贝 由定埋2 , 3l ，知其结论成立 一等 l 托 = 。 旺 珏 = p一4 t “ o 。i 习 ( f ) 1 0 ，( f “) 一1g “0 ，( f 2 ) 一( + p ) o ：有了：( 。，t ) + q 。( 。) j j ) 0 。且 由引理221 ，知p ( ( p ) 1 g ) o ，则o k 【o ，1 ) ，有 e ( ，k ) + 印巾。，) p ! “巩札， 、= 1 - ，上。 取一i ll i i x l k l 以，显然口【o ，lj ，最后有 i l ( m ) 4 - 0 ，( 。k ) p | 0 u 山定理241 知结论成立。 推论2 4 2 若l p 是h 一矩阵，且外分裂a = m 一n 满足( a p ) ( n ，。) 一i p = l ，- - ，l ，内分裂 ，“= f “一g 。，满足( 肘。) = ( ，“) 一 g “ ， o = j 一l ，则同样有由( 21 7 ) 式得到的迭代解收敛于方程组( 21 ) 的解义+ 。 证明：困a p 是h 一矩阵，且( a p ) ( m 。) ( f “) ，由引理2 23 可知 ( ”) ( f “) 是 ，一矩阵又因( f ) “) g l 0 ，可知( m ) = ( f ) 一 g 为 ( m “) 的弱正则分裂，且有p ( ( f 。) _ 1l g “1 ) 0 ，知j 巩 o ，1 ) ，使得 e ( 。，b ) + q 。( 。，k ) p i “o k 札 取= m a x l k l 如，易知0 0 ，1 ) ，且得到 由定理2 4 1 知结论成立。 瓦( 。) + q 。( 。k i p i “0 - t t 8 一 非线性多重分裂算法的收敛性研究 第3 章一类非线性多重分裂算法 3 1 引言 多重分裂法【；j 巳应用于线性方程组的迭代解法，它们都是基于对线性系统 的系数矩阵采取不同的分裂法而得到的然而，随着科学技术以及计算工具的快 速发展，非线性方程组的求解问题越来越多地被提出来了。因而，对于它的可解 性分折以及有效解法的研究，也引起了人们的重视。早在七十年代以前，无论在 理论方面或是在数值解法方面都已做了大量有意义的工作并且取得了相当丰硕的 成果阻3 6 “i 。但是，由于非线性的性质，给研究这些问题带来了一定程度的困 难，从已有的理论和解法的使用性看，还远不如解线性代数方程组那样成熟和有 效冈此，对于非线性方程组解的存在性以及有效算法都还有待于进步的研究 羽】改善。 本章采用非线性多重分裂方法来求解非线性方程组( 14 ) ，即 f ( z ) = 0 ，f ：r r 。 这类贸：法的局部收敛性已有许多 a 9 - - , n l ，本章则着重于对于下述一类较为特殊的 j i 线性方程纽 f ( 。) 二= a z g ( 。) 一6 = 0 ，a r 。n ， b 冗n ， ( 3 1 ) 其中a 为m 一矩阵，g ( z ) 一阶连续可微，为r 到几”的一个对角、逆保序的映 射，即其分量函数玑( z ) ，i = 1 ，只依赖于第i 分量：玑( 。) = g i ( z 。) ， 。 q ，( q ) 0 ，z = l ，一，。我们将针对求解( 3t ) 的非线性多重分裂算法，给 出其全局收敛性和单侧收敛性定理，同时还将讨论m 步非线性多重分裂n e , a r t o n 缓及其收敛性质。 3 2 非线性多重分裂算法的全局收敛性和单侧收敛性 定义3 2 1 令e 。r ”“为非负的对角矩阵，且满足量) e “= ，其中为 几”“! ：| 王位矩阵。对a 的组分裂a = ，一n “，a = 1 ，- ，l ，一个非线性 多匝分裂算法可定义为： r “川= = ”1 “ 9 u31 0 _ n 一4l 硕士学位论文 其中为求解1 i 式e 7 l ”s f 户( 。”“) = f 。”一c ( y “) 一。l l “一b = 0 、k ：l 一，l 。( 33 ) 为了讨论贷法的收敛性，下面引入本文需用的一些辅助引理。 引理3 2 1 若l 是n ，矩阵，a = 一m “一n ，= i ，l ，为a 的组正则分 裂，则 一( 末i 萨( 拼) r 1 舻) “，、k = 其中e 同前定义。 在 1 7 1i 1 已给h 了该引理的证明。另外，还有下而引理成立。 引理3 2 2 1 蚓( h a d a m a r d 定理) 假定f ：r 一咒”在咒“上是连续可微的，又 没对所有的_ 。r ”，| | f ( 。) _ 1i l + 。，那么f 是一个将r “映上r ”的同 胚。 首先讨论对于定义3 2 1 中所给的非线性多重分裂算法存在着全局收敛性 定理3 2 1 没_ 4 为m 一矩阵，a = m 一n a = 1 ：l 为a 的工组正则分 裂，g ：r “一几连续可微，且在r 上是对角的逆保序映射。则对任意z o r ，由定义3 21 所给的非线性多重分裂算法确定的迭代解序列 z “) 收敛到方 程组( 31 ) 的唯一一解z + 证明：南干g ( z ) 为咒”上对角的逆保序映射，知对任意z z ”，一g 7 ( z ) 为对角 的非负矩阵。 由于a = m 一n k = 1 ：，l 为正则分裂，可得a m 。m 。一g 7 ( 譬) ，南 引理2 22 知m ，m 一g 7 扛) 也为m 阵，且0 m 一g 7 ( ) 】“( 矿) 。 对任意。n “，有f ( z ) = a g ( z ) a ，由引理2 2 2 知p ( z ) 亦是m 一阵， 且0 ( f 7 ( 。) ) 。a ，则由引理3 2 2 知f ( x ) = 0 在r “上有唯一解，不妨设 为r 对任意z ”咒“由定义3 2l 可确定一组解序列 z ”) 。记e ”= z “一z + ，e “= n ，一z + ，则由a f 。“一g ( “) 一n 护b = 0 ，有 z + ) ) 出e ”一n 。c ”= 0 ( 34 ) 1 5 非线性多重分裂算法的收敛性研究 南于对任意的t 【0 ，1 一g7 ( z + t ( 旷。一) ) 为对角且非负的矩阵，容易得到 ，一岳( ? ( t pt ( y “r ) ) 出的逆存在，非负，且以( ) - 为上界，故有 叫争卜一z 、啪叭一a t “ e e k ( m 。) 一1 a ，“ie “l f 三 “1 l e k ( m 。) 。n 。i 1e 。i 。 l = lj j 1 i 引理3 , 21 知( ：1 e “( m 。) 一1 n “) 1 ，l ， 一l i m 。( e 。( 舻) “ = 1 即t i m 。f ”= r 。 下面，我们得到由定义3 2 ，1 给出的非线性多重分裂算法的单侧收敛性定理， 定理3 2 2 假设定理3 21 中各假定均成立对任意一r “，若七o 矿( w 0 r ) ，则以z “为初始点，由定义32j 中的非线性多重分裂算法确定的迭代解序 列 l j ”) ，均有护矿( z ”。+ ) ，n = 0 ，1 、，且收敛到，其中矿为f ( ) = f ) 在斤“上的唯一解。 证明：由定理3 2l ，只需证明迭代解序列具有单侧收敛性。记e 7 t = 。n 一矿， “= 旷，一矿，南( 3 5 ) ，知若矿0 ，则有矿0 ，k = i ，l ，而且， 一= 巴酽e o 。 mp 1 纳原理，没：c r 即e 1 0 时，对任意的n 都成立c n 0 即zr - 。c 。 同样，若：c o z ，可得到e “0 ，n = 0 ，1 ，即z 7 r 。 3 3 7 1 2 , 步非线性多重分裂n e w t o n 法及其收敛性 南干g ( j 1 ) 连续可微，则芦( 。，”) 的导数也存在。分别记。1 芦( z 。”) ，岛芦( z 、) 为户gj 关于第一个变量口和第二个变量的偏导，则有，7 ( z ) = 岛芦( 。、。) + 0 芦( z ，z ) = m 一g ( z ) 一n 。定义3 2 1 中的非线性多重分裂算法需求解非线 以驴 “ ，g ， 脾 坝 。： 肌 扩 _ l m 硕士学位论文 性方程组( 3 3 ) 。下面讨论对( 3 3 ) 式用m 步n e w t o l l 法近似求解时对应的多重 分裂算法，此时，称3 乍法为，。步非线性多重分裂n w t o i l 法，具体定义如f ： 定义3 3 1 定义32 1 中各假定成立，应用m 步n e w t o n 法求解( 33 ) 得到下述 ? 步非线性多重分裂n e w t o n 法： 1 = e k y “， n = 0 ，1 矮中“由下式计算得到 扩。，o 一护， = 1 - 扩。“1 = 犷。一一协户“( 。“，z ”) l ( 3 - 6 ) 1 p ( 扩，“”) ，u = 0 1 ，m 一1 ， ( 37 ) ( 38 ) 定义3 3 2 设，r ：dc 月一r ，若矿d 是_ = 7 1 ( t ) 的一个解且存在z + 的 一个邻域s d ，使得对任何初始近似点z o s ，由z ”1 = t ( x “) 确定的迭代 序列扛“) cd ，且收敛到z + ，则称是序列的吸引点。 定理3 3 1 设定理3 2 1 条件成立，则z 为由定义3 3l 定义的? 7z 步非线性多重 分裂n 一，