（计算数学专业论文）多右端线性方程组的迭代法.pdf

y 慨幻 摘要 本论文主要讨论多右端大规模线性方程组a x = b 的数值迭代解法，其 中a 是n 非对称实矩阵，b 是由p 个右端向量构成的n p 矩阵目前常 见的有两大类迭代法用于求解这种多右端方程组，一类是块迭代法，另一 类是种子投影方法在方程组各右端比较接近或有某种联系时，使用后者 的效果一般比较好 r 7 本论文在块迭代法方面提出了两个算法，扩展的块c m r e s 方法( a b g m r e g ) 和块e n 方法我们分析了这两个方法的基本性质，并利用矩阵值多 项式对a b g m r e s 方法进行了残量估计，其显示了a b g m r e s 方法具有比一 般块g m r , e s 方法更好的收敛性态作为一个强健的块迭代法，必须要处理 发生在基本块迭代序列( 矩阵) 中的线性相关性问题对此，我们在块e n 方法中引进了一个收缩过程以处理这种相关性问题；重要的是该过程的引 入仍使算法保持着块运算的特点，这对于算法的平行计算是有益的 在第四章我们讨论了种子投影方法这类方法的一个重要问题是种子 系统的选择基于对方程组右端的变换，我们提出了一个种子系统的选择 策略，数值结果显示，该策略比起现有的两个策略更有效对于多右端线 性方程组的求解，同样也存在着预条件处理的问题针对模型问题，我们 分析并得到了松弛化不完全l u 分解的存在性条件以及预处理的稳定性条 件在一种行尺度意义下，这些条件显得简单有效，为得到一个有效的预条 件矩阵提供了某种基本保证在本文的最后我们讨论了块拟n e w t o n 算法， 建立了有记忆的块拟n e w t o 算法，从而放松了算法对存储量的过大要求 本文做了大量的数值实验，这些实验结果为我们的分析提供了帮助和 支持 千走蔫黧：豢嘉雾篓黧数：迭代法种子投影方法厅展q “l u 子空间方法，松弛化不完全分解 、 、 中图分类号：。0 2 4 1 6 ，0 2 4 1 7 u t h ei t e r a t i v em e t h o d sf o rs o l v i n g l i n e a rs y s t e m sw i t hs e v e r a lr i g h t h a n ds i d e s b yg u i d i n gf h i i i s ( 、a l el i a b s t r a c t o d sf ( j is o h 7 i n gt h el ar g ( 、 ，w h e , e 1j aa n7 l ，o n o n s y m m e t r i cr e a lm a t r i xa n db i sa nn pm a t ti xf o r m e db ypr i g h th a n ds i d e s 1 h e t ea r et w oc l a s s e so fi t e r a t i v em e t h o d st os 0 1 v ( 、t h es y s t e m s ：er i ei sb l o c k i t e , a t i v em e t h o d sa n dt h eo t h er i ss e e dp r o j e c t i o nm e t h o d sw h e ne a c h r i g h t h a n ds i d eo ft h es y s t e m sh a ss o m ec l o s e n e s so lh a ss o n l or e l a t i o n s ，t h el a t t e li s g ( 、t t e la l l y n l o r ee f f i c i e n t w e p r e s e n tt w ob l o c ki t e r a t i v ea l g o r i t h m si nt h i st h e s i s ：t h ea u g m e n t e db l o c k g m r e sm e t h o d ( a b g m r e s la n dt h eb l o c ke ni t l ( 、t h o dw es h o ws o m eb a s i c p r o p e r t i e so ft w om e t h o d sa n do b t a i nar e s i d u a ln o tn le s t i m a t eo fa b g m r e s b yu s i n gm a t r i x e d v a l u ep o l y n o m i a l l h ee s t i m a ! es h o w st h a tt h ea b g m r e s m e t h o ( 1h a sa ni m p r o v e d c o n v e r g e n c e 1 a t eo i lt h es t a n d a r ( 1 ) l o c kg m r e sm e t h o d a sar o b u s tb l o c ki t e r a t i v em e t h o d ，t h el i n e a r - l yd e p e n d e n c ei n t h eu n d e r l y i n g b l o c ks e q u e n c e s ( n l a t r i c e s ) m u s tb eh a n d l e d ad e f l a t i o np r o c e d u r ei s e m p l o y e d i nt h eb l o c ke nm e t h o dt oh a n d l et h el i n e a r l yd e p e n d e n c e 1 ti s i m p o r t a n ti s s l l e t h a tt h eb l o c ke nm e t h o dw i t ht h ed e f l a t i o n p r o c e d u r es t i l lk e e p sab l o c k w i s e c o m p u t a t i o t lw h i c hi ss t l j t a b l ef o rt h ep a r a l l e 】j s l l 】 i nc h a p t e r4 ，w ed i s c u s st h es e e dp r o j e c t i o nm e t h o d ，f o rw h i c ha k e yi s s u e i st h es e e ds e l e c t i o n w ep r e s e n taf l e ws e e ds e l e c t i o n s t r a t e g yb a s e d o i lt h e t la n s f o r m e d r i g h t h a n ds i d e so f t h es y s t e m c o m p a r e dw i t ht w o e x i s t i n gs e l e c t i o n s i t a t e g i e s ，o n rs h a t e g yi s n l o r ee f f i c i e n t a c c o r d i n gt ot h en u m e r i c a le x p e r i m e n t s r h e p l e c o n d i t i o n i n gt e c h n i q u ec a na l s o b ee n f l ) o l y 7 e df o r s o l v i n gt i l e l i n ( 、 s 3s t e i n sw i t hs e v e l a lr i g h t h a n ds i d e s p o l t h pn l o d e lp t 0 1 ) l e m s w es t u d y h i ( 1 e ti v elh ec o n d i t i o n sf o rt h ee x i s t e n c eo ft h er e l a x e di n c o m p l e t el uf a c t 0 1i z a t i ( ) 1 1 ( r i i u ) a n df o rt h es t a b i l i t yo ft h ec o m p u t a t i o n si n v o l v i n gt h er 1 i 。u p r e c o n d i t i o n i n go p e r a t i o n i nt h es e n s eo far o wm e t r i c s t h e s ec o n d i t i o n sa , 1 e 、，e r ys i r e p l e ( jf 、册( 1 e n t ，w h i c hs u p p l ys o n l eb a s i cg l l a i a n t e e s ) ro b t a i n i n ga 1 1 e f f i c i e n t 1 ) i p vt ，i a m 刚 。 旧 m“h s n 博 0 k 山一 剐 s w s n p i s 吖 懈 r c o n d i t i o n i n gm a t r i x f i n a l l y ，w ed i s c u s s t h eb l o c kq u a s i n e w t o nm e t h o da , n d p l e s e n t t i l el i m i t e dm e m o r yb l o c kq u a s i n e w t o nm e t h o d ，w h i c hr e l i e v e st h er e q u i r e m e n tf o l t h e a l n o u i l to ft h es t o r a g e t h en m n e r i c a le x p e r i m e n t si l lt h i st h e s i ss u p p l yt h eh e l pa n ds u p p o ltn ) r 0 1 1 ra n a l y s i s k e yw o r d s ：l i n e a ls 5 7 s t e i l l 8w i t hs e v e r a lr i g h th a n ds i d e s ，b l o c ki t e l a t i v e e t h o d ，s e e dp r o j e c t i o nm e t h o d ，a u g m e n t e dk r y l o vs u h s p a c em e t h o d ，r e l a x e d c o m p l e t ei uf a c t o r i z a y i o n a m s ( m o s ) ：6 5 f 1 0 ，6 5 y 2 0 致谢 本论文是在导师曹志浩教授直接指导下完成的从论文开题 之初直至论文的完稿，无一不蕴含着曹老师认真细致的指点和热 情的帮助，使我从中得到了很大的教益曹老师深厚的数学功底 以及讨论问题时的那种认真与严谨的作风，使我感到钦佩三年 来的学习，使我感到在专业修养和科研能力上都取得了不小的进 步在此向曹老师表示深深的敬意和忠心的感i 射 忠心感谢我的硕士导师一一上海大学数学系王德人教授多 年来，他一直给予我学业科研上的热情关怀和帮助，为我的研究 打下了良好的基础，并不断地给予我鼓励和支持 真诚感谢三年来指导、帮助过我的老师们：蒋尔雄教授、李立 康教授、於崇华教授、苏仰锋博士、魏益民博士、高卫国博士 同时我要感谢复旦大学数学所以及研究生院的许多老师所给予我 学习期间的帮助 感谢上海大学数学系的领导和老师们三年来给予我的支持， 以保障我顺利完成学业及毕业论文 我还要向我的同学和朋友们表达我的谢意：他们是刘仲云博 士、吴和兵博士、郭洪斌博士以及陈文斌、汪洋、张振宇、冯丽 红、石春超、孙令亮，在与他们共同学习和讨论中收益匪浅 最后我要感谢我妻子龚蔚春和儿子顾宜若三年来对我学习的 支持和帮助也感谢我岳母所给予的帮助，使我能顺利地完成学 、叱 i v 第一章绪论 i l 问题介绍 本论文主要讨论的问题是多右端大规模线性方程组 j 4 。= b i ，i = l ，- 一，p( 1 l 的数值求解，其中j 4 是n n 的非对称实矩阵，p ( c n ) 是一适中的数值 此问题的研究具有许多重要的实际应用背景，如在电磁场研究中1 9 2 ，需要 测试具有来自多个方向激发( 入射) 点的散射等，就涉及到这种多右端线 性方程组( 1 1 ) 的计算；其它还有诸如在化工领域、结构力学以及控制领域 等，都需要计算方程组( 1 1 ) 的解( 详见文 8 9 】中的参考文献) 由于实际问题中归结出来的方程组( 1 1 ) ，一般规模很大且呈稀疏结构， 因而使用迭代法是一种自然的选择，特别是使用k r y l o v 子空间迭代法因 此这种块迭代法( 1 ，1 u c ki r e r a f i r em e t h o d ) 的研究，近年来引起了人们的兴趣【3 5 块迭代法 所谓块迭代法，是指适合于同时求解( 1 i ) p 个方程组的迭代法为便于 区分，我们把适合于求解单个方程组 ( 1 2 ) 的迭代法称之为( 向量) 迭代法我们以c g 方法为例写出这两种形式的算 法 篡法! ! ；g g 左基堕 取初值g 、计算r = b a 一p ( o ) = t ( o f 0 r = 0 1 n 。= ( ，【“r 【) a p ( 、p ( ) ： z ( 1 ) = z ( 4 - f l ( 女】口( ) ： ，l o + 1j = “j n f 女) a 口”) ： ，。= ( 7 ( + 1j ，7 + 1 ) w ) ，r i ) ； f ) 【o + 1 l = ，f k + p k ) ) e n d f k l 上述c g 方法只适合于求解单个方程组( 1 2 ) 对于多右端线性方程组( 1 1 ) 的求解，必须对c g 方法进行推广令口= ，m ，x = 睁一一，z ， 咒一，则 【l1 1 可以写成下列等价的形式 其中p 称之为块尺寸于是求解( 1 3 ) 的块c g 方法( b l o c kc g 一、“t i ) 可以写 成下列形式 算法12 ：g g g 左法四 取初值x 冗一r ，计算州o l = b a x ( p oj = 几 f o r = 1 rr l k ) = f ，l 。、1a p i 。11 r i ) 1j 口o ： x k + 1 l = x k ) + j lo f k ： 凡( 。+ 1 1 = 月 一a p ( k ( c k 1 f “k ) = r ( ) 1r f 1 1 1 r ( 十1 ) 1r f + 1 1 ： f f k + 1 ) _ ：r + l + p f ) g ，l k ) ：i i t l k 1 当方法收敛时，就可以得到( 11 ) 的p 个解类似地还有块g m r e s 方法 8 9 1 ，块q m r 方法 3 5 】，块l a n c 一方法【8 2 】等 19 8 0 年，0 l e a x y 7 7 】首先开始研究这种块迭代法对于b c g 方法，0 1 l c a r y 证明了下列估计 忙一忆够( 矧一 ，一， ( 1 4 ) 其中z ；是a z = b 。的精确解，c 是常数，唧= a a ，0 j + 1 e = o ，纠冗p “， 则成立 u 。= ( u + ，l ，m + 1 宫。，( 1 8 ) 其帆= ( 日。皇。) 倒栅一 块g m r e s 方法 利用块a r n o l d i 过程可生成一个块k r y l o v 子空间芄。( a ，h ) = s p n n ， u ， 。1 u ) ，而h ，- ，k 。即可成为该空间的一组正交基具体的算法实旌可利用 修正的g r a m - s m i t h 正交化过程下面是求解多右端线性方程组的块g m r e s 方法( b l o c kg m r e s1 n e t h o d ) 算法l 尘b g m 鱼e s 左法婴 取初值x ( 0 1 r n 一，计算科o ) = b a x i ，q r 分解：冗( o l = h 见 f o r = l j 1 t ，t n ， dneh k o = r 蛭 = j h ， 巧i a 一 一 0陆 ( 2 r 分解：嵋= 巧+ 。h j + 1 j e n d ( j ) ： 计算n ) = i a 。，l i e l r 一“f i f 其中e 1 = 【o 7 刚”1 ) p 。p ) = x o j + u 。f y l 对于b g m r e s 方法，s i m m m i - i 等得到了下列残量估计 定理1l 【s 。】设 有谱分解a = z a z 其中a = 批( a a ，。) ，特征值满足 构造一个关于实轴对称的椭圆昂n “) ，其包含特征值a a ，但不包含原 ，一羔，其中实数r - 是中心，焦点为c “，长半轴为m 则由b g m r e s 方法产生的 残量，：h ，加满足 剐( 斋解磊) ”1 ，、m 圳 其中常数c 与m 无关 证明：见附录 比起一般g m r e s 方法的残量估计1 8 4 “r n “。s ”。c z ，( i i ；i 器) 1 “r 。，。= - ，- ，c - ， 其中一。( z ) = r l z l l ：i l z 一恢但这里的参数c ，e ，n 则属于包含a 。一，a 。的椭圆 e l ( q 叩) 很明显b g m r e s 方法改善了g m r e s 方法的收敛性态，即b g m r e s 方法也有类似于b c g 方法( 14 ) 的收敛性态又b g m r e s 方法也有n p 步的 有限终止性结论 另外，s i m o n c i n i 等还利用矩阵值多项式来分析b g m p 。e s 方法的残量估 计设圣。( a ) 是一个p 阶m 次的矩阵值多项式，其定义为壬。( a ) = 羔。a + 矗， 其中f ，冗 p 记 p ，= 巾，( a ) 币，( a ) ：a 己毛冗。”，中，( o ) 二，sm ) = f 】 特别，如果巾。( ) = ，一备1 m p 。p 是b g m r e s 的残量多项式，即 f 7 l 一1 1 = 中m ( ) 。咒三冗m 一j 4 r n ( 1 1 2 t = 0 是b g m r e s ( 。1 的残量则由b g m r e s 的残量极值性质，币。是下列问题的 解： m i u 1 1 0 ( a 1r 州”l f h 。e p n 、， ：是，瓢 j 【f 1 ，( z f n 方法 e n 方法是 l jf i m i 。- 和n w l i m a | 2 9 1 提出的用以求解方程组( 12 ) 的一种 迭代法，其本质一j ：属于矩阵修正算法，并有n 步有限终止性的性质 v u i k 和v 扎n 一1 rv c tf 9 s 对e n 方法进行了比较全面的讨论，并与g m r e s 方法和 br o y d m t 方法进行了比较对于某些问题，数值结果显示e n 方法比g m r e s 方法更有效，特别是重新启动形式近来，人们又用e n 方法来求解矩阵特 征值问题1 0 7 】 扩展g m r e s 方法 在我们的论文中，比较多的应用了m o r g m - 的扩展g m r e s 方法 7 3 1 所 谓扩展g m r e s 方法( a l l g l - m n t j e dg m r e sm e t h o d ) 是指在一般k r y l o v 子空间咒。i ( a ，r 0 ) = s p a n , - 。，a r o ，a m 一7 0 ) 中，添加一些向量，构成一扩展k r y l o v 子空间丘= 。+ y ，其中- g = s p a n f ， 之后在空间中利用g m r e s 过 程对方程组( 1 2 ) 进行求解这种方法的目的是改善原来g m i t e s 方法的收敛 性态( 实际上，块g m r e s 方法也可以看成是求解方程组( 1 2 ) 的扩展g m r e s 方法，即把n ，加。，a m 。“，一2 ，一m 看成是添加的向量，详见 2 3 ，8 5 1 ) 而 m o r g a l - 的扩展g m i i e s 方法，则是在丘。中添加的是对应于a 的一些很小特征 值的特征向量，饥以此形成一个扩展的k r y l o v 子空间= 7 c 。+ w ，其中 w = s p “n 钆，4 ) 这样一来，当a 有一些很小特征值时，m o r g a n 的a g m r e s 方法仍可保持比较好的收敛性态，而此时一般的g m r e s 方法的收敛性态不 是很好下面是m w t ，的结论 定理1 2 设a 有谱分解a = z a z 其特征值满足o p 类似于定理2 2 的证明，对任何z z ( o 1 + 成立 ” p z = z + 叩，+ o ( a ) r p 其中 q = z ，。( 三o ) z 。( i 序) 根据引理21 在? ：0 情形下的结果，并构造t j ( a ) ( j = i ，p 1 ) ，使其满足 p lp l t j ( a ) a 弓= 卢j q ( $ j ) g j ， 小， aa 0 叫闩 一z 。 一z qp 。 = a b 【| 是f 其中g ，= 勺+ 墨。n ，z 这样我们可以得到 n p l i 一1 r = ( 1 3 。q ( a ，) a gq ( a j 】 j ) z + ( 卢q ( a 。 l = c j2 】1 2 p 我f 门取o 。= 士( 卢q ( a ，) 2 ；_ - - ：脯+ ，q ( a ，+ ，) r 。，) ，则 t 一1 p l 一( 成q ( a 。) 一岛q ) r i 小。 利用i i 。! 1 1 l | ：及类似于( 11 0 ) 的估计( 详见附录) ，便可得到估计式( 2 1 0 显然，在实际计算时 空间只能取成= 庀。+ y v 口 我们只能得到特征向量。的近似弘，于是投影 s p a t t r f ”a r ， 1 r ( ，】，y 1 ) 定理24 设a 有谱分解a = z a z1 记n ! l ( v 一，) ，蚓i ：= 川i ：= 1 假设x ”z 是 x ， + 瓦中的最小残量解，则有估计式 咿叫：ss ( 斋黑磊) ”2 + i f a i i 萎警( j l - l 一岛+ j q ( ) ) i i ： 其中q ( a ) 由( 2 6 ) 给出 证明：在 。( 0 1 ) + 咒中的任何向量。可写成 ，p z = 一+ 刚。+ t j ( a ) r j o i = ij 2 1 其中蛳是垂直于的单位向量，于是 n， p t = b a z = 麒z t 一n 。( a ，t ，+ s i l 讥a u i ) a t ，( j 4 ) ，r i 2 11 1 1 j 。1 p l p l f ，( 4 ) d ， 0 l = 胁+ j q ( a f + j ) 叭j j = l j = 1 1 7 s + z s j | 成蚺解分p l= j 十 x 印， 巍最 “ 矿 q = ，m 一 舭 她 矾 取 “ 选， 矗 按 弘 | = 中其 + ，由引理2l 给出类似于( 27 ) ，我们可得到关系式 f p t 一( 。q ( a 。) 一 。m s 叽一m i q ( a f + j ) 6 ，小。 i = 1 j 3 1 ” p 1 十“q ( a ，) j 川n j h | i 肌。 ，_ ( 、，j + jq ( ) r 。小，j f 十j q ( a 州) n 。j ) 4 】：硅成立 二剑( 航q ( a ，) 一肋 ，q ( a ) ) z 。| | ? 删j 萎警一p 萎肌州机忆 i一 一 l 一1 类似地，对上述右端的第一项进行估计，可以得到( 2 9j 的估计，从而便证 明了( 21 1 ) 272 矩阵值多项式 在本小结中，我们利用矩阵值多项式对a b g m r e s 方法的残量进行估 汁，可以得到一个类似于( 1 1 3 ) 的估计式设2 印。 r ( m ，a r ( o ) ， 4 ”1 刷o 雪 是一个扩展的块k r y l o v 子空间，其中牙= ，却】_ 并设肖t ) 是 x “”】+ k 中关于l | r 【“峙= t ，( ( r ( ) 7 r t 】求极小得到的解，其中r ( ： b a x ( i 是x 的残量，于是我们有 定理2 , 6 设a 有谱分解a = z a z ，副o 】= 羔。毛p ，；z 3 ，其中t z ux l , , 是 的行向量，则成立 其中q 川( ) 满足 矗m l | f 曼k ( z ) ；_ = 1 l l q 。、 l i r o f q m ( a ) 。矗。| f = 。i i d p n 。i r o m ( ) 。几lj f f 。：f 。旧。队= s u p 十h ”q 。( 川f ，运算符。的定义见【l1 2 证明：任何xe x ( 1 ) + 足都可以写成 x = x ( o ) 4 - z “4 - p f a ) 。r ( o 1 8 其中，) ，fr ，f ，c 1 p 。，“冗。“一定义q ) = ，一a p ( a ) 三翌。 己并记a = 【l ! | jq 【 ) p 。，且 ，= ? l x = 打”一j l z ”? t ，( 4 ) o r ”= z a f l + q ( a ) o 几” z a f r + 1 t r ”：z a “十z a 成 令o j h 。1 7 z ： zz 其中兄一rj ：是 月= 孙n + ( z a + z a ，1 f 训0 ：f 勺( 1 7 f 1 7 ( , 。 2 1 ， z ，蜓 其tj f r ，是r t 的行向量- 现取q ( ) 满足( 21 3 j ，并取c 。= 寺鸬q ( ) ，j = l 下是 冗= q ( a ) o 冗= z q ( a ) 0 一 注意到n o ( a ) 。口怙i i q ( a ) i i f i i b i i ，( 参见文8 0 ，故 由一f ! ，i f 几i | fs1 1 2 1 1 f i i q ( a ) 。p psi l z l l f i i q ( a ) i i f i i ，i f sl t z l l r 、n 一( ? 例f ( 21 4 i l l rsl l p f = i i z1 咒 o l l f l i z1 1 w i i r ( o ) 1 1 f 、1 1 2 1 1 r 三i l z l l f 、并注意至u “冗f i i f 三 我们便可以得到估计式( 21 2 ) 注记2 2 事实上，估计式( 2 1 4 ) 是一个更好的估计式 对于近似特征向量，则有下列结论 定理2 7 设a 有谱分解a = z a z 一假设一一 是空间i 印一( h i o ) ，a r ( 4 一1 剐m ， 中的最小残量解，其中，= 】是z 的一个近似令y ： 彳1 ，z ，其仁| 7 冗1 7j 奇， 7 7 1 一x 。贝0 恤叫z ) 再砷m i i i i i n i i ，+ 舛j + 燃，。悱i i i i ，j l l f -( 2 15 其中( ) 满足( 2 】3 ) ，n 在下列证明中给出 证明：任何上 一j + 可写成 x = x + r ( t ，f a ) 。打 中f ，( ) 。cr 咒。“其残量 已一一r 而一是“的行向量按照定理2 6 的证叫过程，可以得毋 ，k ：，i ，j - ( 小1 ) ，d ”1 z 小 q ? 一q ( ，) ( 从而n = ，一n ) ，j ：碴 从而成立 ”r f ! l i q ( a ) 。i i i , 1 忪 i i a z i i f 忪忆 兰“( z ) 。7 “一川q 、j 凡“”f f ，+ 。7 “一7 f + y ! 燕。f - j f f f f f 厂j j 叩f f ， t 恬s k 便可以得到估计式( 2t 5 ) 23 算法的实施 笄法的基本实旃过程是：利用块a n l o l d i 过程，产生块k r y l t ，v 子空间丘。 的一组正交基，随后在。中获取一些近似特征向量并加入到。中而形成 扩展的块k r y l o v 子空间厄= 苊。+ w ，最后在苊中施行g m r , e s 过程以获得方 程的近似解x ( m ) 在我们的算法中采用了重新启动的策略 设x 是初始近似，r ( o i = b a x i o ) 是其残量作r ( o ) 的q r 分解 w ，h r 利用h 由块a r r o l d i 过程产生一组块正交序列，k 。作为 h 的基，并设一，3 n 是已知的近似特征向量令w = 【n ， 、v 。一州， ，( o = e 。“。，i f l ，啦】、其中吼是由a 叭关于q 的前列正交化得到于是成 市炎系式 j 中是( f 十p ) t 的块上h e ：s t , u m - g 矩阵，t = m p + ?由于丘= 一j w n w 中 n _ i i f i 阵y x ( o 可写成 限州r2 l6 ) ，成立 b a x = r 。一4 “= k r q 日“= q ( e l r 一f t 其中e ： x ”i = x 于是在 x ) + 丘中的极小残量解x 可通过 + w m - 获得，其中“满足 照然，p “， 1 丁湎过对其列向量“的残量取极小( 在2 一馍 匹义l ? ) 得至1 j ，即 t l 。f 。， 。址，维川 l 进步取， 阶正交阵，使得 其中t ( ，。是f 阶上三角阵于是 驯= 。+ wc t 可通过( 21o ) 而得到 下面我们来估计矩阵a 在厄中的近似特征向量下面的做法是由m o r g t m m 7 3 】提出的，我们只是做了一些简单的块推广 设咒是近似特征向量，其有形式= w ”冗t ；设p 是对应的近似特 征值根据投影条件( a 一日功正交于芄，成立 这是一个广义特征值问题w r a w z = o w 7 w z 为了更好地找一个接近于零特征值的特征向量，m o r g e u - 建议求解下列 m t y l 【l z l p r i t z 问题 7 a 7 a w z = o w 7 a 7 w z( 22 1 1 ) 这意味着使用基a w 作为正交条件令f = w 7 a 7 w ，g = ( 且) 7 a w ) ，则( 2 2 0 ) 是一个，的广义特征值问题 g z = d f z ( 2 2 1 ) 我们需要从中找j 个最小特征值p 对应的特征向垣一1 f 这样m = w z ， 便是对应于4 的近似特征向量。 为有效方便地得到矩阵g 和f ，我们也遵循m m g a t - 7 3 j 的做法，使用 ( 11 6 1 和( 21 8 ) ， g = i a y v f a w = h t ( 2 l ( 2 h = h t h = u j u l 记y = 【h“。】，y = 一，驰 于是 f = 7 r = v t a t v y v ，t a a ，t y y 显然f 的前m p 列与h t 的前t n p 列相同，而在f 的右下角块y t a 7 y ，则可 以通过 ，= j a 7 协= tv t d a t w o m ，= z j 码d ( t ，j = 1 、，f ) 得到，记号f o “表 示上一迭代步的f 因此只需很少的计算量便可得到矩阵g 和f 下面我们给出( 重新启动的) 扩展块g m r e s 算法，记作a b g m r e s ( m ，f ，p ) 为了描述的简单，不妨设f 可以被p 整除1 = s p 算法21 ：a b g m r e s ( m ，l ，p ) 算法 给出初值x ( o ，兄一y = 【y 1 ，l r 一，整数m 以及容许值t ，计算 几= 口a x f o r = 0 1 1 。q 咒分解：冗i ) = v i r ； f o ri ，j = 1 ， ，s ，i f ( 血= o ) t h e nj _ 。+ i m + j = ( a y e ) 7 y je l s ef m 十。，m + ，= z ，f z j e n d ( i j ) 2 o f o rj = 1 ，2 ，一，7 n ， = a 巧，f o r i = 1 ，一，s ，毋，m + t = 叼m e n d ( i ) ； f 日u = 曙啊， f o r i = 1 ，小马，= 弓， e n d ( i ) ； 【：= 一1 7 i l l i j q r 分解：= 巧+ 1 毋扎j ； i f l j ( ”1 1t h e nf ，1 十l = h j + l 。i e n d ( j ) 3 。f o r7 1 = 1 ，一，s 、j2 m + n w j = 4 蚱； fh i j = 妒w j ， f o ri = 1 ，a i 州m ) t h e n f j i = 孵， e n d ( i ) l：w j v i h o ； q r 分解：w j = 巧+ 1 日j “j e n d ( r ) 4 。根据( 2 1 9 ) ，计算o = a v g m i n r i l p o 。一u a 。f | 2 ( 注1 ，p ) ，并计算 x ( m ) = x l o ) + n ( m 1 5 。 计算几l 。l = 口一a x l t “，i f 【n n z l l ! p ，1 2 f ) t h e ns t 。pe l s ex ( o ) ：= x i ” 6 ”计算g = u f u 。，并形成f ；求广义特征值问题g z = o f z 的 个最小特征值 哦所对应的特征向量i = 1 ，z ：计算y = w z e n d f k ) 注记2 a 若j 不能被p 整除，则步骤3 一的计算只能按向量形式进行，而不 能用块形式 下面我们考虑a b g m r e s 0n f 川算法的计算量和存储量，并与b g m r e s ( m + s ，p ) 进行比较，注意到此时两个方法的投影空间维数是一致的，这便于比 较表2l 列出的是两个方法每一迭代步( 即关于足标t ) 的主要计算量， 表中a z 表示矩阵a 与向量z 的乘积运算：，d o t 表示向量内积运算由于 n m m 故a b g m r e s 方法的计算量比起b g m r e s 方法增加得很少 表21 _ 每一迭代步的主要计算量 i a b g m r e s ( 7 ，l ，sp ，p )b g m r e s ( mq - ，p ) ar t 十p l n v t t ( d o t i “j + f ，1 + t f + m p ) t p ；t f + p ) t v e ( l ( n 。d o t ( t + j l t 二p ( 2 rf a ( ：t o li z a t i o n ，j + n 一l，n + h + 1 l e & s t s q u a r e dp r o b l e m g e n e r a l i z e de i g c n v a l u ep r o b l e n l 注记24 若a 不是很稀疏，或7 , 很大，则在a b g m r e s 中的a y 计算可通过 a y = 0 h z 完成，此时f 个a z 的计算量变成小+ p ) 个n 维向量内积和m + p ) 个t 维向量内积的计算量，但同时还要增加，“+ ；( t + 1 ) 个内存 表2 2 列出的是两个方法的主要存储量( 不包括a ，x ，b 的存储量) 由 于t n ，两个方法的存储量基本相同 表2 2 一主要存储量 la b g m r e s ( m ，3 p ，p )b g m r e s ( m + s ，p )1 i 儿( + 2 p ) 十；t 2 + o ( ：)t ( t + 2 p ) + ；t 2 + o ( p t ) 2 4 数值结果 在本节中，我们选取数值例子p 3p 5 和p 1 ( 见1 3 节) 以考察a b g m r e s 方 法的收敛性态，并与b g m r , e s 方法进行比较当残量达到i l i a 2 ( ，。渤。 1 ，m11 4 、a b g m r e s 方法的收敛速度基本上是 b g m r e s 方法的两倍；甚至于a b g m r e s ( 1 4 p ，p ) 仍然比b g m r e s ( 2 5 ，p ) 收敛得 快( ，= 3 ) ，而此时前者的投影空间要比后者的小得多。 例2 2 取1 3 节的问题p 4 ，注意到此例的矩阵月有4 个很小的特征值，故 用g m r e s 方法计算，一般比较困难计算结果见表2 4 表24 算法得到例2 2 收敛解的迭代步数 a b g m r e sb g m r e s _ _ p m - 2 4n 1 = 1 91 1 1 二1 4m = 2 4 n l = 1 91 n = 1 4 l 21 53 7 31 82 71 1 8 1 8 5 44 696 9 8334 1 3 2 对于所有的p 和m ，b g m r e s 方法基本上不收敛；对于较小的p ( 3 ) ， a b g m r e s 方法的收敛性态也不太好( 相对于例2 1 ) ，但对于较大的p ( 4 ) ， 则a b g m r e s 方法的收敛性态基本上已同例2 1 的结果相同了，也就是说， 对于较大的p ，这4 个很小的特征值已基本上不影响a b g m i t e s 方法的收敛 性态了，这同理论分析的结果是相吻合的， 例2 3 考虑1 3 节的问题p 5 ，此时矩阵a 虽然没有很小特征值，但有些特 征值是很接近的此时用g m i l e s 方法计算，效果可能也不好；不仅如此， 即使使用m o r g a n 的扩展g m r e s 方法( 向量形式) ，计算效果也不好1 7 3 1 ，然 而使用a b g m r e s 方法计算，效果仍然良好，且比b g m r e s 方法具有更好的 收敛性态，见表2 5 的计算结果 表2 5 算法得到例2 3 收敛解的迭代步数 a b g m r e sb g m r e s p m = 2 4 m = 1 9m = 1 4 m = 2 4 m = 1 9m = 1 4 11 21 62 61 62 33 7 271 01 51 41 6 1 9 3781 31 41 72 l 4771 31 41 62 0 例2 4 考虑1 3 节的模型问题p 1 ，取矩阵阶数“= 9 6 1 ，并分别取参数 d 。= d 。= 0 和d 。= 6 4 ，d ：= 0 进行试算，此时导出的五对角矩阵且具有形式 a = ( 一l ，一1 ，4 ，一1 ，1 ) 和a = ( 一1 ，一3 ，4 ，1 ，一1 ) 表2 6 列出的是两个算法a b g m r e s 和b g m r e s 在得到收敛解时的迭代步数对于d 。= d ：= o ，a b g m r e s 方法 基本上有b g m i r e s 方法的两倍收敛速度；但对于d 。= 6 4 ，d 。= 0 ，则改善的效 果稍差一些 表2 6 一算法得到例2 4 收敛解的迭代步