（应用数学专业论文）线性方程组二级迭代解法与矩阵多分裂的收敛性理论分析.pdf

国防科学技术大学研究生院博士学位论文 摘要 自上世纪九十年代初以来，随着矩阵多分裂并行计算方法的提出，求解大型 稀疏线性方程组的二级迭代法受到了前所未有的关注。二级迭代法( 咖咖g e i t e r a t i v em e t h o d s ) 由内、外两个迭代过程嵌套而成，又称内外迭代法( i i l i l e r - o u t e r ) 或嵌套迭代法( n e s t e d ) 。内迭代可使整个迭代求解过程避免方程组的精确求解。在 迭代过程中反复精确求解方程组可能是一件开销很大的工作，采用某种( 内) 迭代 方法，通过计算和存储都相对简单的迭代过程获得方程组的近似解是解决问题的 有效途径。在多处理机系统，高效并行计算的前提是各处理机之间的工作负载平 衡。二级多分裂方法中内迭代次数选择的灵活性，为各处理机负载平衡提供了切 实可行的手段。本文主要针对单调矩阵和h 矩阵类，讨论大型稀疏非奇异线性方 程组的二级迭代解法，研究内容包括渐进收敛速度，最优内迭代次数，松弛型二 级多分裂方法的收敛性，以及矩阵多分裂序列和二级多分裂序列的收敛理论。论 文的主要工作和创新研究成果包含下述几个方面： 1 ) 在内外迭代方法都收敛的一般条件下，证明了定常二级迭代法的迭代序列关 于内迭代次数一致收敛于外迭代方法的迭代序列，其收敛速度决定于内迭代方法 的蜀一因子。用内外迭代方法的冠一因子和内迭代次数三个数量，给出了非定常 二级迭代法冠一因子的一个估计。对于单调矩阵，证明了非定常二级迭代法的收 敛速度不可能超过外迭代方法的收敛速度，但二者有可能相等。根据关于二级迭 代法收敛速度的分析，讨论了外迭代方法为s o r 迭代的块s o r 二级迭代法，给出 了数值计算结果，从理论上估计了收敛所需的最小内迭代次数。 2 ) 对于m 矩阵的定常块j a c o b i 二级迭代法，得到了其冠一因子的更精细的估 计给出了内迭代为点s o r 方法和点j a c o b i 方法时的比较定理，推导了优化内迭代 次数的目标函数，定义了内迭代次数的近似最优值。数值计算表明，所定义的近 似最优值非常接近实际最优值。 3 ) 二级迭代法与矩阵多分裂结合产生二级多分裂方法。对于在内迭代过程用外 推引入松弛因子的( 内) 松弛型二级多分裂方法，按照迭代矩阵的某个单调范数给出 了松弛型二级多分裂方法的一个比较定理。在相同或稍弱的条件下，把松弛因子 的收敛范围从熟知的( 0 ，1 】区间改进为( 0 ，) ， 1 ，并把这个结果推广到内分裂 为不完全l u 分解的松弛型二级多分裂方法。 4 ) 非定常二级多分裂方法可归结为更一般的基于矩阵多分裂序列的迭代方法。 本文给出了矩阵多分裂序列同步和异步迭代更为简洁的收敛条件，并证明了它们 关于迭代收敛的必要性。证明了同步迭代和异步迭代，以及不同的异步迭代模型 之间存在互不相同的收敛条件。应用这些结果，得到了基于矩阵二级多分裂序列 第v 页 国防科学技术大学研究生院博七学位论文 迭代法的一些新的收敛性质。 主题词：大型稀疏线性方程组二级迭代方法矩阵多分裂单调矩阵h 矩阵 并行计算 第v i 页 国防科学技术大学研究生院博士学位论文 a b s t r a c t t h et 、) v o s t a g ei t e r a t i v em e t h o d sf o rs 0 1 u t i o no f1 a 唱es p a r s el i n e a rs y s t e m so f e q u a t i o n sh a 【v eb e e na n e n t i o n - g e t t i n gn e v e rb e f o r ew i mt h ea d v e n to fp a r a l l e lm a t r i x m u l t i s p l i t t i n gm e t h o d s s i l l c ei l i n e t i e se a r l yl a s tc e n t u 巧t h et w o - s t a g ei t e r a t i v em e t h o d s a r ec o m p o s e do fi 皿e ra n do u t e ri t e r a t i o n s ， s ot h e ya r em s oc a l l e di i l i l e r 锄do u t e r i t e r a t i v em e t h o d so rn e s t e di t e r a t i v em e t l l o d s t h ei 衄e ri t e r a t i o n sm a k ei tp o s s i b l et 0 a v o i ds o l v i n gs y s t e m so fe q u a t i o n se x a c t l yi nw h o l ei t e m t i v ep r o c e s s t og e tt l l ee x a c t s o l u t i o n sr e p e a t e d l ym a yb ea b i g 、o r k ， i ti st l l e r e f o r ea 1 1e f f e c t i v e 印p r o a c ht og e tt h e a p p r o x i m a t i o ns o l u t i o n st h r o u 曲ac e n a i n ( i i l i l e r ) i t e r a t i o np r o c e s ss i m p l yi nc o m p u t i n g a i l ds t o r i n g i nm u l t i p r o c e s s o r s ，t h ep r e c o n d i t i o no fi m p l e m e n t i n ge f f e c t i v ep a r a j l e l c o m p u t i n gi sag o o do v e r a l l l o a db a l a n c ei i le a c hp r o c e s s o r 7 i kn e x i b l ec h o i c eo f t h e n l l l l l b e ro fi m l e ri t e r a t i o i l si nt 、v 0 - s t a g ei t e r a t i v em e t h o d sp r o v i d e saf e a s i b l ea p p r o a c h f o rag o o dl o a db a l a n c e t h i sp a p e rd i s c u s s e s 锕o - s 姆i t e r a t i v em e t h o d sf o rm e s o l u t i o no fl a r g es p a r s en o n s i n g u l a rl i i l e a rs y s t e m so fe q u a t i o n sw h i c hc o e 伍c i e n t m a t r i c e sa r em o s t l ym o n o t o n eo rh - m 撕x t h es t u d yi n v o l v e sa s y m p t o t i cr a t eo f c o n v e 唱e n c e ，o p t i m a l 伽m b e ro fi 衄e ri t e r a t i o i l s ， t l l e c o n v e r g e n c eo fr e l a x e d t 、o s t a g em u l t i s p l i t t i n gm e t h o d sa n dt h ec o n v e r g e n c et h e o r i e sf o rm a m xm u l t i s p l i t t i n g s e q u e n c eo rt w o g 魄em u l t i s p l i t t i n gs e q u e n c e t l l em a i na 1 1 di 肌o v a t i v ew o r ki i l t l l i s p a p e ri n c l u d e ss e v e r a la s p e c t sa sf o l l o w 1 ni ss h o w e dt h a tt h ei t e 谢o ns e q u e n c eo fs t a t i o i 坷叮t 、o s t a g ei t e r a t i v em e t h o d s c o n v e r g e su i l i f o n n l y t on l a to fo u t e ri t e i a t i v em e t h o d sa n di t sc o n v e r g e n c er a t ei s d e c i d e db yt l l e 置一f a c t o ro fi n n e ri t e r a t i o n s a ne s t i m a t i o no fr l f 如t o ro ft w o s t a g e i t e r a t i v em 甜l o d sa r eo b t a i n e du s i n gt h er l f 砬t o ro fi 衄e r 锄do u t e ri t e r a t i v em e m o d s ， a l o n g 晰t l lt h en u m b e ro fi m l e l ? i t e r a t i o i l s f o rm o n o t o n em 撕c e s ， i ti ss h o 、v e dt h a tm e c o l w e r g e n c er a t eo f1 1 0 n s t a t i o n a 巧t w o - s t a g ei t e r a t i v em e m o d si si l e v e rf 瓠t e rt h a i lt h a t o fo u t e ri t e r a t i v em e t l l o d sa n di ti sp o s s i b l ef o rb o n lt 0b e c o m ee q u a l a c c o r d i n gt om e a l l a l y s i sf o rc o n v e r g e n c er a t e ， w ed i s c u s st h eb l o c ks o r t 、) r o - g 吨ei t e r a t i v em e t h o d s o fw h i c ht 1 1 eo u t e ri t e r a t i v em e m o d sa r eb l o c ks o r “e r a t i o i l s 1 1 l en 啪e r i c a li n s t a l l c ei s p r e s e n t e da n dt 1 1 em i n i m a lm h n b e ro fi 衄e ri t e r a t i o i l sr e q u i r e dt oc o n v e r g ei se s t i m a t e d f o r b l o c ks o r t w o - s t a g ei t e r a t i v em e t h o d s 2 am o r ef i n ee s t i m a t i o n so fr l f a c t o ri sf o u r l do u tf o rs t a t i o n a 巧b l o c kj a c o b i t 、v o s t a g ei t e r a t i v em e t h o d sf o rm m a t r i x ac o m p 撕s o nt l l e o r e mi sp r e s e m e dw h e n l e i f u l e ri t e r a t i o n si sp o i n ts o ro rp o i n tj a c o b im e t h o d s 1 1 l eo b j e c t i v em n c t i o nt 0 o p t i m i z et h en 啪b e ro fi r u l e r i t e r a t i o i l si se s 诅b l i s h e da n d 印p r o x i m a t e l yo p t i m a l n 啪b e ro fi m l e ri t e r a t i o n si sd e f i n e df o rs t a _ t i o n a r yb l o c kj a c o b it w o - 虬唱ei t e r a t i v e m e t h o d s 第v i i 页 国防科学技术大学研究生院博十学位论文 3 au n i o no 士t w o s t a g em e t n o d sa n qm a 【n x i u u l s p 儿l l l i i 苎u l u l 芍3 u 1 _ u 。j “5 - m u l t i s p l i t t i n gm e t h o d s f o rt h er e l a x e dt 、) v d s t a g em u l t i s p l i t t i n gm e t h o d s o tw h l c ht h e r e l a x a t i o nf a c t o ri si n t r o d u c e db ye x t r a p o l a t i o ni ni n n e ri t e r a t l o n s ，a nc o m p a n s o n t h e o r e mi so b t a i n e d ， t h ec o n v e r g e n c ei n t e a lo fr e l a x a t i o nf a c t o rl sl m p r o v e dt r o m w e l lk n o w ni n t e r v a l ( 0 ，1 】t oan e wo n e ( 0 ，) ，1 1 ) 的定常二级迭代 法所产生的向量序列，那么，讧k _ o l 的子列扛“p k - 0 ，l 比扛盖圳更快的收敛。 从x ( 扣1 ) p 到x “p 经过p 次外迭代，而从舅扣1 到z 经过p 次内迭代，二者都计算产生 了p 个迭代向量，初一看内迭代次数恒等于l 似乎优于大于1 的情况。然而，不 能忽视的是内迭代次数不同所带来的计算工作量的差异。从( 1 2 1 ) 看出，每个x “p 的 第4 页 国防科学技术大学研究生院博十学何论文 产生都要比每个i 的产生多出p 1 个胍矩阵向量乘法以及由此带来的数据读写 开销。数值实验表明【6 6 1 8 崩，4 3 1 ，求解时间最少的最优内迭代次数一般总大于l ， 但也决非越大越好。 二级迭代解法自上世纪九十年代初开始受到格外重视，主要是由于并行计算 的推动。1 9 8 5 年o l e 哪，讹i t e 提出了求解并行求解( 1 1 1 ) 的矩阵多分裂方法【5 9 1 。 设有口台处理机，m 。，和e ( 江1 ，2 ，口) 是以刀矩阵，且 么= m ，一j ，d e t ( m 。) o ， f = 1 ，2 ，口， ( 1 2 5 ) 巨( f = l ，2 ，口) 是非负对角阵，满足e = ，( ，表单位矩阵) ，则( m ，j ，巨) 瑚如饵 l = l 称为矩阵彳的一个多分裂。对所有的扛1 ，2 ，口，并行求解方程组m x = z + 6 的解o ，然后通过权矩阵e 的加权组合得到新的迭代x “1 。 算法1 1 ( 矩阵多分裂方法) 【5 9 1 ：给定初值x o 如，后= 0 ，1 ，2 ，u n t i lc o n v e 玛e n c e 加，i = 1 ，2 ，口d os i m u l t a n e o u s l y m l x k 。= n t x + b ； x ：y e 。x ，r _ _ j 吉l 矩阵多分裂方法可以看作由经典的块j a c o b i 迭代法发展而来。块j a c o b i 方法有着 “天然 的分块并行计算格式，但变量块与块之间没有重叠，而矩阵多分裂允许 块间重叠。矩阵多分裂的应用总是把一个变量块与么的一个分裂彳= m 。一f 和 e 。( 或一台处理机) 相联系，而权矩阵e 。的玎个对角元中的非零元与对应块的大小接 近，而其它都等于零，从而处理机f 不必计算x 幻中对应零对角元的分量，由此矩 阵多分裂方法可望给出较高的并行加速比。自o l e a r y ，w l l i t e 开拓性的工作以来， 国内外学者对矩阵多分裂方法进行了大量深入的研究，例如，参见b a i 等 1 ，8 ， 1 0 】，w 1 l i t e 【7 5 - 7 8 ，】，n e u m a n n 等 5 7 】，b m 等【1 5 ，1 9 】，f r o i 姗e r 等【3 l ，3 5 ， 3 7 】。实际上，矩阵多分裂已经成为并行求解大型稀疏线性方程组的基本模型。 把矩阵多分裂和二级迭代结合起来是自然的。对于矩阵多分裂方法，每台处 理机的每一步迭代计算主要是求解形如( 1 2 2 ) 的方程组。1 9 9 2 年s z ) ，l d ，j o n e s 提 出了二级多分裂概念【硎，在多分裂( m 。，j ，巨) 汹，2 僖的基础上，令 m = 只一q ，d e t ( e ) o ， 汪l ，2 ，口，( 1 2 6 ) 由此形成矩阵么的二级多分裂( m ，e ，g j ，m ，置) 瑚2 。矩阵多分裂 ( m ，i ，e ) 酬，2 饵为二级迭代法提供外层并行计算框架。 第5 页 国防科学技术大学研究生院博士学位论文 算法1 2 ( 矩阵二级多分裂方法) 【6 6 】：给定初值x o 力， 七= 0 ，1 ，2 ，u n t i lc o n v e 唱e n c e 力，汪1 ，2 ，口d os i m u l t a i l e o u s l y y o = x ； 声r = 0 ，l ，仇f 一1 f y 7 + 1 = g ，y + x + 6 ； x m ：y e y m r 。 j _ j = l 由于各处理机并行工作，内迭代次数见。不仅与七有关，而且可以依处理机f 变化。 仇，兰p 时为定常二级多分裂方法。通过在不同的处理机使用不同的内迭代次数 仇f ，为处理机之间的负载平衡提供了有效的手段。虽然人们对如何确定最佳内迭 代次数仇，；所知甚少，但一个必要的原则是仇。的选择应尽可能使各处理机工作负 载平衡【6 6 18 1 。 口= 1 时二级多分裂方法退化为二级迭代法( 1 2 4 ) 。有意思的是，矩阵多分裂方 法本身也可以看作二级多分裂方法的特例，当m = o ( 江1 ，2 ，口) 时，二级多分裂 方法退化为b m ，e l s n e r ，n e u m a n n 的多分裂并行计算模型a 【1 5 】。若进一步有 仇，暑1 则得到矩阵多分裂方法( 算法1 1 ) 不难看出，算法1 1 也是 g f = 0 ( f _ 1 ，2 ，口) 和仇，量l 时算法1 2 的特例。 为了加快二级多分裂方法收敛，b m 等在内迭代过程进行外推，用下式 f y 。 + 1 = 缈( g y 。 7 + m ，+ 6 ) + ( 1 一彩) e y 。( 1 2 7 ) 取代算法1 2 的内迭代e j ， 。”= g ，y 。+ f x + 6 ，从而在二级多分裂方法中引入 松弛因子缈【1 8 】。这一类算法称为松弛型二级多分裂方法。缈：l 时退化为算法1 2 。 松弛型二级多分裂方法等价于内分裂m 。= f g i 由分裂m ，：土e 一( 上竺f + g ，) 御甜 取代后的二级多分裂算法。当4 为单调矩阵，外分裂彳= m 。一m ( 江l ，2 ，口) 为正 则分裂，内分裂m = 鼻一q ( f - 1 ，2 ，口) 为弱正则分裂，或者彳为h 矩阵，内外 分裂均为h 一相容分裂时，对任何整数序列仇。( f - 1 ，2 ，口，尼= 0 ，1 ，) ，b r u 等证明 了国( 0 ，1 】时松弛型二级多分裂方法的收敛性，并且还得到了如下的收敛结果：若 外分裂彳= m 。一m 满足0 m j _ 1 f 忆 1 ，内分裂m 。= e q 收敛，且舰p ”= 佃， 第6 页 国防科学技术大学研究生院博士学位论文 则当o 缈 1 时松弛型二级多分裂方法的收敛性，而 且最优的松弛因子总大于1 【1 8 】。第四章的主要工作是： 1 ) 首先给出一个( 内) 松弛型收敛性分析的基本定理，然后改进了b r u 等的结果， 在相同或稍为弱一点的条件下，证明了松弛型二级多分裂方法及其外异步算法的 收敛区间为( 0 ，) ，1 0 ) 。矩阵b 是非负的当且仅当算子b 将非负向量全 体映入自身。任何非负矩阵b 的谱半径p ( b ) 是b 的特征值，并且相应p ( b ) 存在非 第1 2 页 国防科学技术大学研究生院博十学位论文 负特征向量，我们把这个非负特征向量称为非负矩阵b 的f r o b e i l i u s 向量或p e r m n 向量。如果向量x 一) ，是非负( 正) 的，记做工j ， j ，) ，类似可定义矩阵比较式 b c ( b c ) 。给定矩阵b = ( 6 f ) 可定义矩阵俐= ( ) ，嘭= 。显然有，俐o ， 且关于矩阵乘积成立l b c l 俐l c i 。 单位矩阵，经有限次行( 列) 交换后所得矩阵尸称为置换矩阵，即r = ，。 定义1 4 1 ：设口r “”。如果存在置换矩阵尸，使得 御r ：降且：i ， 【- o岛z j 其中骂l ，岛2 分别是，x ，和刀一，刀一，方阵，1 ， k i ( 扛1 ，2 ，2 ) ，称为不可约 对角占优是指b 不可约，k l y k l ( f _ 1 ，2 ，玎) 且至少有一个严格不等号成立。 l ”i _ lvi 。 矩阵b 称为单调的是指b 可逆且召- 1 o 。b 是单调的当且仅当对任何向量x ， 只要觑0 就有x 0 。令z “”表示尺“”中所有非对角元非正的矩阵集合。z “”中 的单调矩阵称为m 一矩阵。对任何灭职疗中矩阵召= ( 岛，) ，定义召的比较矩阵 ( b ) = ( 6 f ) z 脚，其中 毛= m 歹i 多 矩阵称为h 矩阵是指它的比较矩阵是m 矩阵。因为m 矩阵b 的比较矩阵( b ) = b ， 所以m 矩阵必为h 矩阵。除此之外，严格对角占优矩阵，不可约对角占优矩阵， 或比较矩阵为对称正定的矩阵都是h 矩阵。 引理1 4 2 ：设b ，c r 脓”。 ( a ) 如果l 艿l c ，则p ( b ) p ( c ) 。 ( b ) 如果b 是m 矩阵，c z “”，且b c ，则c 是m 矩阵。 ( c ) 如果b 是h 矩阵，则b 可逆且l b 1 i ( b ) 1 惭1 。 定义1 4 1 唧，3 4 0 ：设b r ，m 可逆时b = m 一称为曰的一个分裂。分裂 b = m n 褓为 ( a ) 弱正则分裂是指m 1 0 ，m 一o 。 ( b ) 正则分裂是指m - 1 0 ，o 。 第1 3 页 国防科字技术大字研冗生阮博十字位论文 ( c ) m 分裂是指m 是指m 一矩阵且o 。 ( d ) h 一相容分裂是指( b ) = ( m ) 一i c i 。 ( e ) h 一分裂是指( m ) 一i c i 是m 一矩阵】。 矩阵的m 分裂必为正则分裂，正则分裂必为弱正则分裂。 引理1 4 2 1 3 4 0 ：设b = m 一是 ( a ) 弱正则分裂或正则分裂，则p ( m 1 ) l 当且仅当b 一o 。 ( b ) m 一分裂，则p ( m - 1 ) l 当且仅当b 是m 矩阵。 ( c ) h 一相容分裂且b 是h 矩阵，则b = m 一是h 分裂。 ( d ) h 一分裂，则b ，m 都是h - 矩阵，且p ( m _ 1 ) p ( ( m ) - 1 m ) ol 一所y 肛 = 噬茅掣= 阿y y 甜， ( 1 4 1 ) l 自nr 其中见= 以昭( _ i ) ，t ：) ，一，t 。) ) 。所定义的范数是单调的：如果酬h ( i j ，i 怫，则 。，( 。 。) 。设b r “”，i 。表示上述向量范数引入的算子( 矩阵) 范数， 咧眺2 l 刺姚中眺。因此， 。= 0 觑 b o ( 1 4 2 ) 从而，= ，= 1 。若b = 历昭( 目，垦，色) o ，x 相应分块为x = ( x j ，x ；，) 7 ， 则 ，= 0 出忆= 0 研1 ( 戤) k = 磷0 嚷1 e 一忆= 嘴怜一忆= 嚼慨k ( 1 4 3 ) 定义1 4 2 ：设序列& 。k 0 l 收敛于墨，数口t = l i 罢掣忙一e 俨称为序列 讧。k - o l ，收敛于x 的r 。一因子。如果甲是某个迭代过程产生的收敛于五的序列全 体，则 口= s u p 口p l 扛k _ o 1 一甲 称为该迭代法收敛于以的r 。一因子。显然口1 。若口 o ，当后充分大时，有 第1 4 页 国防科学技术大学研究生院博士学位论文 0 x 一x 0 ( 口p + s ) ( 口+ f ) ， 于是，迭代法产生的任意序列在霓充分大时都大致以等比数列口收敛于零的速度 收敛于x 。口也称为迭代法的渐进收敛速度。如果b ，分别为矩阵和向量，当 p ( 召) | # “，令4 ，= e g fo = l ，2 ，g ) ，即 d = f g ， ( 2 1 5 ) 其中f = 疣昭( e ，e ，) ，g = 砒g ( g l ，g 2 ，q ) a 算法2 1 ( 块g s 二级迭代法) ：给定初值妒 力，七= o ，1 ，姗t i lc o n v e 唱e i l c e y t o = ； 力，汪l ，2 ，g 弘，= o ，1 ，仇一1 只川= q + ( 厶“1 + 阮。+ 6 ) ，； x ? “= y t a l a i l z i n ，r o s e ， s z ) ，l d 以块g s 二级迭代法为实例，把块g s 二级迭代法的外分 裂( 2 1 2 ) 和内分裂( 2 1 5 ) 分别推广为 a = m nk n 2 ， 第1 7 页 国防科学技术大学研冗生院博十学位论文 和 m = f g 。 其中，m = 讲昭( m 。，m 2 ，m 。) ，f = 访昭( 互，e ，) ，g = 讲昭( g l ，g ：，瓯) p 9 1 。 非奇异对角块m 与彳。同阶但不必相等，i 和2 也不必是三角形矩阵。这里，内 分裂m = f g 与( 2 1 5 ) 使用了相同的记号f ，g ，但因矩阵m ，d 不一定相等，故 两式中f ，g 不一定表示同一个矩阵。外分裂么= m 一l 一2 称为4 的复合分裂， 它规定了一种求解( 1 1 1 ) 的迭代法 众“1 = 2 x + 1 + l x + 6 ，( 2 1 6 ) 即 m 。x ? 州= ( r 2 x “+ l x + 6 ) f ， f = 1 ，2 ，g ( 2 1 7 ) 算法2 2 ( 块二级迭代法) 1 4 9 1 ：给定初值p 。 如，- 七= o ，1 ，u n t i lc o n v e 略e n c e y 。o = ； 弦f = l ，2 ，g 弘，j = 0 ，1 ，仇一1 e y ：+ 1 = g f + ( 2 x “1 + i x + 6 ) ，； x ：q = y ， 若m = d ，l = u ，：= 三，算法2 2 退化为算法2 1 。若l = ，2 = 0 ，g = 1 ，算 法2 2 退化为二级迭代法( 1 2 2 ) 。设内分裂m = f g 为收敛分裂，p 为任一正整 数，令 m 口= m ( ，一r p ) 一2 ， n 。= m t i r p 丫1r p + n i ， r = f - 1 g = 坊昭( r l ，r 2 ，r 。) 置2 f - 1g i ， f = 1 ，2 ，g 若m p 可逆，彳的分裂彳= 一虬确定矩阵 t p = m ：np 块二级迭代法的整体迭代式为 m 矶x 州= x + 6 ， 七= o ，l ， 因此，如果所有的m 几( 七= 0 ，1 ，) 可逆，从任意给定的初值x o 出发， 法产生确定的迭代序列x ( 七= 0 ，1 ，) ，并且( 2 1 8 ) 可改写为 x “1 = 乙。x + m ：6 ， 七= o ，1 ， ( 2 1 8 ) 块二级迭代 ( 2 1 9 ) 第1 8 页 国防科学技术大学研冤生院博十学位论文 给定正整数p ，仇暮p 时( 2 1 9 ) 为定常块二级迭代法 工2 “= 乙x 。+ m ：1 6 ， 七= 0 ，1 ，( 2 1 1 0 ) 如果m 。= m 一2 和彳= m 。一l 均为正则分裂，称彳= m 一l 一2 为正则复合 分裂。 定理2 1 1 川：设彳一1 0 ，彳= 吖一l 一2 为正则复合分裂，时= ，一g 为弱正 则分裂，那么，对任何整数序列仇( 后= 0 ，l ，) ，矩阵m ，。( 七= 0 ，l ，) 可逆，块二级 迭代法收敛，即任意给定初值妒，由( 2 1 9 ) 产生的序列( 七= 0 ，1 ，) 收敛于( 1 1 1 ) 的解x 。 下面是关于块二级迭代法收敛速度的三个比较定理。 定理2 1 2 m ：设彳一1 0 ，彳= m 一1 一为正则复合分裂，m = f g 为弱正 则分裂且卯- 1 o ，则对任何p p 7 l ，有p ( 乙) p ( 乃，) l 。 当m = f g 为正则分裂时，必满足定理关于内分裂m = f g 的条件。这个 定理阐述了定常块二级迭代法的收敛速度关于内迭代次数p 单调增加的重要性 质。 如前所述，二级迭代法( 1 2 2 ) 是块二级迭代法( 2 1 9 ) 在l = ，2 = o ，g = 1 的 特例。从而，n 兰p 的定常二级迭代法( 1 2 2 ) 是块二级迭代法( 2 1 1 0 ) 的特例 定理2 1 3 1 6 6 1 ：设么一1 o ，彳= m 一为正则分裂，m = f g 为弱正则分裂且 g ，- 1 o ，瓦为定常二级迭代法( 1 2 2 ) 的迭代矩阵，则对任何p 1 ，有 p ( 五p ) p ( l ) 。 定理2 1 4 i 矧：设么= m 一和m = f g 均为收敛分裂，l i m 仇= + o o ，则二级 鼻 + 迭代法( 1 2 1 ) 收敛，其足一因子口p ( m 1 ) 。 本章通过分析内、外迭代方法的冠一因子和内迭代次数三者之间的关系，得 到了有关块二级迭代法收敛速度的某些新的结果。第二节在内外分裂都收敛的假 设下，证明了内迭代次数p 一佃时，定常块二级迭代法的迭代序列一致收敛于外 迭代方法( 2 1 6 ) 所产生的迭代序列，其收敛速度则由内迭代方法的蜀一因子p ( r ) 决定。第三节同样在内外分裂都收敛的假设下，对充分大的内迭代次数，综合内 外迭代方法的蜀一因子和内迭代次数，给出了( 非定常) 块二级迭代法足一因子的一 个估计。关于单调矩阵，证明了对任何内迭代次数仇( 忌= o ，l ，) ，二级迭代法的 收敛速度总不会超过其外迭代方法的收敛速度，并由此推得1 i m 以= + 时，块二 k 十 级迭代法与它的外迭代方法具有相同的收敛速度根据第二节和第三节的分析，当 内迭代次数充分大时，块二级迭代法的收敛速度取决于其外迭代方法的收敛速度。 第1 9 页 国防科学技术大学研究生院博十学位论文 因此，第四节我们讨论了外迭代方法为块s o r 迭代的定常块s o r 二级迭代法。数 值计算验证了我们的分析，对块s o r 迭代而言那些“好的松弛因子国，同样也 能显著地加快速块s o r 二级迭代法。当彳为h 矩阵时，用( 么) 的定常块j a c o b i 二 级迭代法的冠一因子，估计了使得块s o r 二级迭代法收敛所需的最小内迭代次数。 并由此得到对任何内迭代次数都收敛的松弛因子的取值范围。 下面列出要用到的引理。 弓l 理2 1 1 1 1 3 l ：设b r ”，b o 。那么 ( a ) p ( b ) 0 和数五使得戤厶，则p ( b ) 五；若戤 厶，则p ( b ) 五。 ( c ) 若存在向量x 0 和实数五使得戤触，则p ( b ) 旯。 引理2 1 2 矧：设彳一1 o ，么= m ，一l = m ，一2 均为弱j 下则分裂，则 p ( m f l i ) p ( m ；1 2 ) l ， 只要下列条件之一成立。 ( a ) l 2 。 ( b ) m i l m ；1 ，且l o 或2 o 。 2 2 定常情形 设p = 一x 为第七步迭代误差。因么= m p 一，易知对任何正整数p ，x 是算子乙x + m ；1 6 的不动点。因此，块二级迭代法( 2 1 9 ) 的迭代误差满足 p “1 = p 。= 毛毛- i l p o ， 七= o ，l ， ( 2 2 1 ) 为了与块二级迭代法的迭代序列x 区别开来，把外迭代方法( 2 1 6 ) 产生的迭代序列 重新记为z 。，即 胞m = 2 z m + 1 2 2 + 6 ， 七= o ，1 ， ( 2 2 2 ) 显然，外迭代方法( 2 2 2 ) 的迭代矩阵为 丁= ( m 一2 ) 。1 1 如果矩阵m 。= m 一2 可逆且p ( 丁) 1 ，我们称4 = m 一l 一2 为收敛复合分裂。 收敛复合分裂等价于对任何初值z o ，