（计算数学专业论文）非对称线性方程组的求解方法.pdf

上海大学硕士学位论文 = 1 1 1 = j i f i i i i i y 17 4 1 4 9 1 ” 2 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作除了文中特 别加以标注和致谢的地方外，论文中不包含其他人已发表或撰写过的研究成果 参与同一工作的其他同志对本研究所做的任何贡献均已在论文中作了明确的说 明并表示了谢意 签名：藓璇慨少肘彳 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即：学校有权保留 论文及送交论文复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容 ( 保密的论文在解密后应遵守此规定) 弛荡伎钟签名私而魄舻小矽 图书分类号：0 2 4 1 单位代号：1 1 9 0 3 ， 、，r。1 字号：0 7 7 2 0 0 2 5 上海大学理学硕士学位论文 非对称线性方程组的 求解方法 作者：苏英 导师：顾传青教授 专业：计算数学 上海大学理学院 2 0 1 0 年3 月 上海大学硕士学位论文4 ad i s s e r t a t i o ns u b m i t t e d t os h a n g h a iu n i v e r s i t yf o rt h ed e g r e eo fm a s t e ri ns c i e n c e a l g o r i t h m sf o rn o n s y m m e t r i c l l n e a rs v s te m s c a n d i d a t e ：s uy i n g s u p e r v i s o r ：p r o f g uc h u a n q i n g m a jo r ：c o m p u t a t i o n a lm a t h e m a t i c s c o l l e g eo fs c i e n c e s h a n g h a iu n i v e r s i t y m a r c h ，2 0 1 0 上海大学硕士学位论文5 摘要 本文分两个部分内容：第一部分通过将非对称系数矩阵化为对称矩阵，作者 在论文中给出了求解非对称多右端线性方程组的四种对称方法：m r e s f 范数算 法，m r e s q r 算法，p m r e s f 范数算法和p m r e s q r 算法。这四种方法都是将 初始残差矩阵投影到矩阵k r y l o v 子空间上，在全局、块a r n o l d i 算法和预处理方法 的基础上加以实现的。它们都有效地避免t b l o c kg m r e s 方法中的“长拖”问题 及重启b l o c kg m r e s 中的“b r e a k d o w n ”问题，从而节省了计算时间和存储量。数 值实例表明：对于非对称的多右端线性方程组，与块g m r e s 相比，对称的m r e 孓 f 范数方法和m r e s - q r 方法虽然迭代步数较多，但由于每步计算量较少，从而 大量地减少了计算时间，而带预条件的对称方法p m r e s f 范数和p m r e s q r 方 法不仅大大减少了计算时间，也大量地减少了迭代步数。 第二部分首先介绍系数矩阵为带位移的斜对称矩阵的特殊的非对称线性方 程组的m r e s 方法【3 1 1 ，在此基础上，作者在论文中给出了t h i c k r e s t a r tm r e s 方 法。t h i c k - r e s t a r tm r e s 方法从一定程度上解决了由于计算机本身浮点计算时存 在的舍入误差导致的算法实际运算时的有效性问题。数值实例表明：用m r e s 方 法求解效果不好的时候可以考虑用t h i c k - r e s t a r tm r e s 方法。与用m r e s 方法相 比，t h i c k - r e s t a r tm r e s 方法虽然每步迭代所花的c p u 时间增加了，但由于迭代 步数大大的减少了，使得t h i c k - r e s t a r tm r e s 方法在求解带位移的斜对称线性方 程组所用的总的c p u 时间大大的减少了。 关键词：全局a r n o l d i 算法，预处理，矩阵k r y l o v - 子空i f i ，非对称线性系统， 对称方法，多右端向量，g i v e n s 变化 a b s tr a c t t h i sp a p e rc o n s i s t so ft w op a r t s i nt h ef i r s tp a r t ，t h em l t h o r ，b yt r a n s - f o r m i n gn o n s y m m e t r i cl i n e a rs y s t e m st os y m m e t r i co n e s ，p r e s e n tf o u rs y m m e t r i c m e t h o d sf o rs o l v i n gn o n s y m m e t r i cl i n e a rs y s t e m sw i t hm u l t i p l er i g h t h a n ds i d e s ， n a m e l y , m r e s fm e t h o d ，m r e s q rm e t h o d ，p m r e s fm e t h o da n dp m r e s q rm e t h o d t h e s em e t h o d s ，b a s e do nt h eg l o b a l ，b l o c ka r n o l d ia l g o r i t h n r s a n dp r e c o n d i t i o n e di t e r a t i o n ，a r ei m p l e m e n t e db yp r o j e c t i n gt h ei n i t i a lr e s i d u a lm a t r i xo n t oam a t r i xk r y l o vs u b s p a c e a l lt h e s ea l g o r i t h m sa r ee f f i c i e n t i na v o i d i n gt e d i o u sl o n ga r n o l d ip r o c e s sa n dt h e b r e a kd o w n ”p r o b l e mo ft h e g m r e sm e t h o d a sf o rn o n s y m m e t r i cl i n e a rs y s t e m sw i t hm u l t i p l er i g h t h a n d s i d e s ，n u m e r i c a le x p e r i m e n t ss h o w ：c o m p a r e dw i t ht h eb l o c kg m r e sm e t h o d ， t h em r e s - fm e t h o da n dm r e s - q rm e t h o d ，a r em o r ee f f i c i e n tb yr e d u c i n gt h e c o m p u t a t i o n a lt i m ed u et oi t sl o w e rc o s ti ne a c hs t e pi ns p i t eo ft h e i rs e e m i n g l y m o r ei t e r a t i v es t e p s i tc a na l s ob ev e r i f i e dt h a tt h ep m r e s - fm e t h o da n d p m r e s q rm e t h o dc a nd r a m a t i c a l l yr e d u c e db o t ht h ec o m p u t a t i o n a lt i m ea n d i t e r a t i v es t e p s i nt h es e c o n dp a r t ，t h ea u t h o r ，b yi n t r o d u c i n gt h em r e s 3 1 】m e t h o df o rt h e s h i k e ds k e w - s y m m e t r i cl i n e a rs y s t e m s ，g i v e st h et h i c k - r e s t a r tm r e sm e t h o d ， w h i c h ，t os o m ee x t e n t ，h a ss o l v e dt h ep r o b l e mo fe f f e c t i v e n e s so fa na l g o r i t h m c a u s e db yt h er o u n d i n ge r r o ri nt h ef l o a t i n gp o i n ta r i t h m e t i c i ti sj u s t i f i e d i nt h en u m e r i c a le x p e r i m e n t st h a tt h et h i c k r e s t a r tm r e sa l g o r i t h mc a nb ea p r o p e rs u b s t i t u t ei fm r e sp e r f o r m su n s a t i s f a c t o r i l y f u r t h e r ，d e s p i t ei t sm o r e c p ut i m et h a nm r e sa l g o r i t h ma te a c hi t e r a t i v es t e p ，l e s si t e r a t i v es t e p sa st h e t h i c k - r e s t a r tm r e sa l g o r i t h mh a s ：i tc a nb em o r ee f f i c i e n tf o ri t so v e r a l ll o w e r c p ut i m e k e yw o r d s g l o b a la r n o l d ia l g o r i t h m ，k r y l o vs u b s p a c e ，p r e c o n d i t i o n e d i t e r a t i o n ，n o n s y m m e t r i cl i n e a rs y s t e m s ，s y m m e t r i cm e t h o d s ，m u l t i p l er i g h t h a n d s i d e s ，g i v e n sc h a n g e 上海大学硕士学位论文 摘要 a b s t r a c t 目录 第一章绪论 1 1 引言 1 2 矩阵相关知识引入 1 3g m r e s 方法 1 4 块k r y l o v 子空间的g m r e s 方法 1 5 预条件处理 1 6 本文所做的主要的工作 第二章求解系数矩阵为对称的多右端线性方程组的g m r e s 方法 2 1 g m r e s f 范数方法 2 2 g m r e s - q r 方法 2 3 p r e c o n d i t i o n e dg m r e s f 方法 2 4p r e c o n d i t i o n e dg m r e s - q r 方法 第三章求解系数矩阵为非对称的多右端线性方程组的m r e s 方法 3 1m r e s i f 范数方法 3 2 m r e s q r 方法 3 3p r e c o n d i t i o n e dm r e s f 方法 3 4p r e c o n d i t i o n e dm r e s - q r 方法 3 5 数值例子比较 第四章求解系数矩阵为带位移的斜对称的线性方程组的两种m r e s 方法 4 1 m r e s 方法 4 2t h i c k - r e s t a r tm r e s 方法 4 3 数值例子比较 5 6 1 1 2 3 0 4 6 8 8 o 3 6 9 9 4 7 1 4 7 7 1 6 1 1 1 l 1 2 2 2 雹 2 3 3 4 4 掣 4 5 同 上海大学硕士学位论文 参考文献 作者在攻读硕士学位期间已完成的论文 致谢 5 9 6 2 6 3 、 上海大学硕士学位论文 第一章绪论弗一早 珀。比 1 1 引言 数学的许多应用问题都要求解线性方程组 a x ( ) = 一i = 1 ，8 其中系数矩阵a 相同，右端项不同。把所有这样的方程组都组合在一起可以把它 写成： a x = b ( 1 1 ) 其中a c n 黼，b ，x c n 8 且它们的列分别为6 ( ，6 ( 扪，6 ( s ) 和z ( ，z ( 扪，z ( 。) ， 这里s n 。 大型线性方程组a x = 6 的求解是大规模科学计算与工程计算的核心问题，是 最常见也是研究最多的求解问题。随着需要求解的问题的系数矩阵规模的增大， 在有限资源内提高及优化算法性能就显得极为重要。线性方程组的系数矩阵a 可 分为对称和非对称两种情况：对于对称线性方程组，目前已经有很多有名的算法， 如l a n c o s 算法，共轭斜量法等等，这些算法相对比较简单，而且实际的计算过程 也证明这些方法对求解系数矩阵对称的方程组是非常好的；而对于非对称线性 方程组，情况要复杂的多，一般很难得到它的真解，我们通常是求它的数值近似 解。对于线性方程组： a x = b 我们可以通过著名的k r y l o v 子空间方法 ( a ，r o ) = s p a n ( r o ，a r o ，a 卅1 r o ) 来求解，其中伯= b a x o 。即把伯正交投影到子空间( a ，r o ) _ k ，然后可以通 过求解最小二乘问题的方法来求得线性方程组的逼近解。 大规模稀疏线性方程组的求解问题在现实生活中很多的复杂问题( p d e 问题， 线性控制论，电磁学等领域) 中都有重要的应用。由于非线性方程组在现实生活中 上海大学硕士学位论文 2 如此重要i 且很多都涉及到国家的财产，这样必然要求有收敛速度快且稳定的算 法来求解非对称线性方程组。到目前为止对求解非对称线性方程组已经提出了很 多非常有效的算法，如g m r e s 方法，重启g m r e s 方法，不完全正交化法，双正交 化法，c g s 方法和b i c g s t a b 方法，还包括著名的g l o b a lf o m 、g l o b a lg m r e s 算法【1 0 】，块共轭梯度法( b i b c g ) 3 0 ，块的残量极小化方法( b g m r e s ) 6 及块 的q u s i 最小残量法( b i q m r ) 算法9 ，2 s 等等。其中全局k r y l o v 子空间方法和块k r - y l o v 子空间方法是用来解大规模稀疏线性方程组的两种最主要的方法。 本文在第二章和第三章中对g m r e s 方法进行深入分析，针对g m r e s 方法 中出现的“长拖”和“b r e a kd o w n ”问题，在g m r e s 方法的基础上建立了几种 求解多右端线性方程组中的系数矩阵为对称的g m r e s 方法和系数矩阵为非对称 的m r e s 方法。第四章中对系数矩阵为带位移的斜对称的特殊的非对称线性方程 组，介绍了蒋尔雄先生在2 0 0 7 年提出的m r e s 方法【3 1 1 ，并在此基础上针对计算 机本身浮点计算时存在的舍入误差对算法在实际运算中有效性的不良影响，提 出了t h i c k - r e s t a r tm r e s 方法。数值例子表明：第三章中给出的四种算法都避免 了g m r e s 方法的“长拖”及“b r e a kd o w n ”现象，第四章中给出的t h i c k - r e s t a r t m r e s 方法改善了计算机本身浮点计算时存在的舍入误差对算法实际运算时有 效性的不良影响。 1 2 矩阵相关知识引入 假定e = i f 加表示维数为佗s 的向量空间。设x = ( ) ，y = ( ) e ，其 中i = 1 ，2 ，一n ，歹= 1 ，2 ，8 ，则定义向量空间e 中的内积： ( x ，y ) f = t r ( x t y ) = 其中汐为矩阵的转置，f 为f r o b e n i u s 范数，打( z ) 为矩阵z 的迹，a p n 礼矩 阵a 的对角元素之和。如果内积( ，) f = 0 ，就称两个向量在e - 上f 范数正交。 设k e ，i = 1 ，2 ，七，= 【m ，k 】 风表示一个k 后矩阵，其 q b h j 是矩阵风的第歹列向量。对于口= ( q l ，n 七) t r k ，定义宰运算【1 0 】： 七 埃木口= f q k 上海大学硕士学位论文3 ，i c 凰= 【术h ，1 ，况木h ，2 ，半日矗】 则很容易证明下列关系成立： v 木( a + p ) = ( v 宰q ) + ( v 木) ( v 木风) 木q = v ：l c ( 风口) 其中o t ，r _ | c 。 令v e ，则矩阵的块k r y l o v 子空间可以表示成： 咒m ( a ，y ) = s p a n ( v , a v , ，a 一1 y ) = s p a n v 1 ，v 2 ，a u l ，a 忱，a ，a m - 1 v l ，a m 一1 ) 下面分析求解非对称线性方程的g m r e s 方法。 1 3g m r e s 方法 g m r e s 方法( t h eg e n e r a l i z e dm i n i m a lr e s i d u a la l g o r i t h m ) ，即广义极小残 量法，是一种使近似解与真解的误差极小的算法。 设线性方程： a x = b 其中a 是非对称的实系数矩阵。系数矩阵为非对称的线性方程组一般采用k r y l o v 子 空间方法来求解迭代解。k 碍l o v 子空间方法是在k r y l o v 子空间做正交或斜投影的 过程，通过p e t r o v - g a l e r k i n ( b a z 。上l m ) 条件在线性空间( a ，y ) + x o 里找 至：l j a x = 6 的逼近解z 仇的方法，其中l 。是一个m 维空间。根据逼近理论，k r y l o v 子 空间方法就是用p ( a ) b 来逼近a b ，其中p ( a ) 是多项式，即 a 一1 b z m = z o + q m l ( a ) 咱 其中r o = b a x o , 。 在用k r ) ，l o v 子空间方法计算多项式p ( a ) 时我们要用到a r n o l d i 过程。接下来 介绍著名的a r n o l d i 过程： 给定r o = b a x o ，取u 1 = t o l i f o 其中 h 2 1 v 22a v l 一h i l 1 h 3 2 v 32a v 2 一h 2 2 v 2 一h 1 2 v l 詹，七一l v k2a r k 一1 一h k 一1 ，七一i r k 一1 一h k 一2 ，七一l u k 一2 一一 l ，七一l v l h k 一1 ，七一1 = ( a v k 一1 ，v k 一1 ) ， t 七一1= ( a v k 一1 ，v i ) 七一l 饥卜l = i i a v k l 一h 让一l 训， k = 2 州3 一，m + 1 i = 1 ，七一1 = o 表示s p a n ( q l ，( 1 2 ，q k 一1 ) 是a 的不变子空间，即珈，a r o ，a 七一2 r o 是 不变子空间。假定 七。七一l 0 ，按a r n o l d i 过程计算到七= m + 1 。此时令 v m = v l ，耽，】，有关系式 其中 彳= 手h m + l , m v m _ j t 一一 土渔盔堂塑圭堂垡迨塞 曼 _-_-_-_-_-_-_-_-_-一一一 2 f o rji 1 ，2 ，3 ，md o： ， 3 计算h i j = ( a v ：，仇) f o ri = l ，2 j 4 计算w j = a 一；：1h o v i 5 幻+ 1 ，j = 1 1 哟! 1 2 6 i fh j + l , j = 0s t o p 7 e l s ev j + x2 j h j h 、j 8 e n d d o 著名的g m r e s 方法是建立在k = a 上的正交投影方法。g m r e s 方法 描述如下： 令z m 是( a ，r o ) + z o 上的任意一个向量，则近似解可以表示为： x m = x 0 + v m y 其中y 是个m 维向量。 为使残量= b a x m = a ( x 一z 。) 的范数达到最小，定义 则 j ( y ) = l i b a z m 0 2 = l i b a ( x o + v 0 木v ) 1 1 2 ，竹i = b a x o a v m 木y = t 0 一v m 日_ 宰可一h m + l ，m t o n + 1 3 b n = v 。( 风e l 一日击木y ) 一危m + l ，m 乞m + l 其中是秒的第m 个分量，风= l i r o l l 2 ，于是 i i r m l l 2 = i i 屏o e 。一日纛引1 2 + 象+ 。，m y 未 若令 h m y = 阮e l 求出一个可可以得到线性方程组的一个近似解，但它不是极小残量法的解。但如 果 川1 ，m = 0 ，那么r m = 0 ，从而z m 就是方程组a z = 6 的真解。照d e t ( a ) 0 ， 那也一定有逆。实际上当 m + 1 ，m = 0 时 彳= 易 上海大学硕士学位论文6 从而 ： ， v t a v m = h m 如果d e t ( h m ) = 0 ，那么必有一个特征值为。的特征向量，假定为f ，于是 斛m = v m = 0 即v m 是a 的对应特征值为0 的特征向量，这与如( a ) o 矛盾。因此有逆存 在，这也说明在a r n o l d i 过程中发现k 肛l = 0 时，反而求到了真解。 如果 m + 1 ，m 0 ，则可将关系式表示成 a v m = v m + 1 日m 其中 焉一m = ( 。_ 九m + 。，m ) 是一个( m + 1 ) m 矩阵，它的最后一行为 刑- 1 。e 磊。于是 r m = r o a v 。幸y = r o v m + l 木秒 = v m + l ( 届o e l 一木y ) v m + 1 仍然是列标准正交矩阵。因此 0 2 = i 螺i = i l z o e 。一赢木训2 g t = ( j 二：j ，一，。 r m1 1 2 = l l g m g m 一1 g 2 g 1 ( 阮e l 一再m 可) 1 1 2 = l i z o g m g m 一1 g 2 g l e l r m y | 1 2 跟对称的情况一样。若记 d t 7 l + 1 = 风g m g m 一1 g 2 g l e l 则可满足 即 = z o ( c l ，- - 8 1 c 2 ，8 1 8 2 c 3 ，( - 1 ) m - 1 8 1 8 2 8 m - l o r e ，( 一1 ) 仇s l s 2 s m ) r 巧可= 卢0 ( c l ，一8 1 c 2 ，( - 1 ) m - - 1 8 1 8 2 8 m - l ) t r m i l 2 = 1 8 1 8 2 s 。l 风 + 10 2 = ij r m 0 2 l s m + l i 从而我们可以知道他的近似解的误差是递减的。 通过以上讨论a x = 6 的逼近解 z m = x o + v m 其中是函数j ( y ) = z o e l 一_ m 可最小值，也即 y m = a r g m i n 掣 i z o e l 一瓦可0 给出著名的g m r e s 算法如下： g m r e s 算法 1 计算r o = b a x o ，p = 8 i | 2 和u 1 = r o z 2 歹= 1 ，2 ，md o ： 3 计算屿= a v l 上海大学硕士学位论文8 4 i = 1 ，2 ，jd o ： 5 = ( 哟，v i ) 6 w j = w j h i j v i 7 e n d d o 8 吻+ 1 j = 1 1 w j l l 2 9 i fh j + i a = 0 t h e nm = j 1 0 j + l = 氆j ? h j + i o 1 1 e n d d o 1 2 计算i i & e 1 一_ m 训2 的最小值和z = x o + 秒 g m r e s 方法是早期求解非对称系数矩阵线性方程近似解比较好的方法之 一。因为在设计该算法时我们是以使近似解的误差最小来进行的。但是在计算的 过程中我们会发现负担比较重的“长拖”问题：当m 过大时，g m r e s 方法就变得不 实际，因为随着m 的增大，算法的存储量和计算量都随之增大了。即在a r n o l d i 过 程中计算吼+ l 有计算式 k h k + l , k q k + l2a 饥一f h i k v i i = 1 右边所有系数h 溉i = 1 ，2 ，3 ，后都要计算，因此所有的v l ，忱，讯都要保存， 使得时间复杂度和空间复杂度都很大。同时就最后的近似解z m = z o + v m y 而 言，v m 与y 相乘也是不小的计算量。对于非对称的线性方程组，设计避免的“长 拖”的算法就显得特别重要了。解决g m r e s 方法的“长拖”问题已经有几种思 想。 ( 1 ) 重启动的g m r e s 法 重启动g m r e s 方法的思想很简单。即取定一佰，当在g m r e s 法中的j = 如时，求n z j o ，此时不再进衍= j o + l 计算，而是将作为新的初始向量z o 重 新进行计算。具体算法如下： 重启g m r e s 算法 1 取初始解x 0 ，计算r o = b a x o ，p = i r o l l 2 ，口1 = r o z 2 用a r n o l d i 过程算得正交阵飞+ l 与可如 0 0 = 0 触t 一瓦f o o ) i 、 上海大学硕士学位论文 9 ix j o = x o + v j o y ( j o ) 3 若满足循环停止条件，则停止。否则，令x o = x j o 重启动g m r e s 方法使得原来的g m r e s 方法的“长拖”得到很好的改善。在 运算过程中，我们可以任意取定j o 来控制要多少步来重新启动一次，增加了运算 的自由度。 ( 2 ) 不完全正交化法 在计算中为了使v k + l 与 1 ，忱，讥都正交才使 中要计算h 诀，i = 1 ，2 ，k 。如果仅要求讥+ l 与最近的8 个，讥一1 ，u k - 8 + 1 正 交，那么 h k + l , a q k + 1 = a 纵一h i k v i i = k - s + 1 h i k = ( a v k ，仇) ( 饥，仇) 这样( 口l ，u 2 ，) 不是列正交矩阵。口1 正交于v 2 ，u s + 1 而与+ 2 不一定正 交。具体算法如下： 不完全正交化法 1 取初始解z o ，计算r o = b a z o ，p = i i r o f l 2 ，v l = r 0 p 2 用不完全正交过程算得列矩阵+ 1 与码 蚓l = i i 阮e t 一瓦，j j 巧= x 0 + v ) 3 计算| i 阮e l 一瓦训2 的最小值和z = 跏+ 可 从上面的讨论中可以知道：虽然不完全正交化法的计算量和存储量都大大减 少了，也使原来的g m r e s 方法的“长拖”得到很好的改善，但是收敛性分析没有 理论结果，实际上也没有保证。 移 k h 七：l 一 七g a = +口七 p 七 h 上海大学硕士学位论文 1 0 。 1 4 块k r y l o v 子空间的g m r e s 方法， 对1 3 节中提到的一般的k r y l o v 子空间方法我们可以将它推广到矩阵上得到 矩阵k r y l o v 子空间方法。矩阵k r y l o v 子空间方法是求解多右端矩阵方程组a x = b 的一种非常有效的方法。令y 是一个n s 的矩阵，则矩阵k r y l o v 子空间可以表 示成 ( a ，v ) = s p a n v , a v , ，a m - 1 y ) ( i ) g m r e s f 范数方法 g m r e s f 范数方法就是利用全局a r n o l d i 算法构造矩阵k r y l o v 子空间的f 范 数正交基的g m r e s 方法。用全局a r n o l d i 算法构造矩阵k r y l o v 子空间的f 范数的 正交基q l ，q 2 ，q m 即 t r ( q t q j ) = 0 ，t r ( 够q j ) = oi j ，i ，j = 1 2 ，m 全局a r n o l d i 算法可以表述如下： 全局a r n o l d i 算法 1 取几s g i 阵且满足f i q l 怯= 1 2 f o rj = 1 ，2 ，m 3 h i , j = t r ( q t a q i ) ，i = 1 ，j 4 = a 巧一名1h i ，j q i 5 吻+ l j = l i w j i | f ，i fh j + l , j = 0s t o p 6 q j + l = b + l j 引理1 2 如果第m 步前全局a r n o l d i 算法没停止，则块系统q l ，q 2 ，q m 是k m ( a ，) 矩阵k r y l o v 子空间f 范数的一组标准正交基。 引理1 3 由全局a r n o l d i 算法得出的= 旧1 ，q 2 ，q m 】，其中q ( i = 1 ，2 ，i n ) 是n s 的矩阵，成立下面的等式 其中o 是胛上的一个向量。 木q i i f = l i q i l 2 、 上海大学硕士学位论文 1 l 且 证明根据前面木的定义，有 木“= a i q i i = 1 木q 幅= m 啦q t ， l = 1 q ) f 又由矩阵q l ，i = 1 ，2 ，m 是f 范数上的正交基，故有 证毕。 定理1 4令 则下面关系成立： 半。瞻= 。2 = ； l = 1 z l = ( q 1 ，q 2 ，q m + 1 ) 磊= ( q 1 o0 ，q 2 ，q m ) m 一1 , r n - - 1 h m - 1 m h m , m - 1 危m m 0 。+ l ，m 叫。，k m a 磊= z k 木+ m + 1 ，仇【o n 。，0 n x 。，q m + 1 】， a 磊= z m + 1 木t m + 1 证明根据全局a r n o l d i 算法，有 j + l a q i = h t j q i ，j = 1 ) 2 2 ，m i - - - i m 汹 ，l 3 3 1 2 2 2 2 允 九 l l l 2 危 危 上海大学硕士学位论文 1 2 慕中j = t r ( q a q j ) ，则上面的等式又可以表示成 a = 木+ h m + l ，m 【0 啪，0 惝，q m + 1 】 在证第二个等式时，有 一川木 其中札m + 1 = ( 0 ，h m + l ，m ) ，从而可以得到 + l 木= 牛+ h m + 1 ，m 【o n 椭，0 啪，q m + l 】 故得证。口 综上所述g m r e s f 方法可以归纳如下： g m r e s f 方法 1 取，计算n o = b a x o _ j f l v l = r o l l 凰i i f 2 f o rj = 1 ，2 ，m 用全局a r n o l d i 算法构造f 范数正交基 q 1 ，q 2 ， 3 求解 舢m i n i i i ir ol i f e l 一+ 1 州2 4 计算= x o + 事广，其中广是上面最小二乘问题的最小解 ( 2 ) g m r e s q r 方法 块g m r e s 求解多右端线性方程组的另外一种更有效方法就是用块a r n o l d i - q r 算法构造矩阵k r y l o v 子空间的正交基的一种g m r e s 方法。用块a r n o l d i q r 算 法构造矩阵k r y l o v 子空间的正交基q 1 ，q 2 ，q m 即 讲q = 0 ，i j ，i ，j = 1 2 ，m ，讲q = 1 给定一个n s 的矩阵弱，则初始残量= b a x o ，计算它的q r 分解 = q 1 r 上海大学硕士学位论文1 3 其中q 1 e 彤8 是正交矩阵，r e r 8 x 8 是上三角矩阵。可以推导出求矩阵i 盯l o v 子空 间的正交基q - ，q 2 ，q m 的一般通项式 其中玩j = q t a q j 定义 j ( f ) = l l b a x i i f = i i b 一4 ( + 木f ) i i f 由定理1 4 有 b a x = b a ( x o + 玩木f ) = r o a 木f = r o 一+ 1 + 1 木f = + 1 ( r e l 一+ 1 木f ) 其中 = = 【q ，q 2 ，q 。】 h l l h 1 2 h 1 3 岛吼2i - 1 2 3 飓 。 j n l m 一1 上k 一1 m 0 0 又因z + 1 中的矩阵是正交的，故 如 0 。 + 1 j ( y ) = i i s a ( + z k ，i cf ) j i f = i i 凰一z m + 1 + l 木f i i f = i l + 1 ( j f c e l 一+ 1 宰f ) r l f = l i r e l 一+ 1 术f i i f 通过以上讨论可知：似= b 的逼近解可表示为 = + 磊木f +m r +mq + m玩q m 汹 = mq a 上海大学硕士学位论文1 4 其中f 是函数满足j ( f ) = 0 的矩阵解，即， f = a r g m i n fj i r e l 一+ 1 木fj f 则块g m r e s q r 算法如下： 块g m r e s q r 算法 l 取初始阵，计算凰= b a x o ，和q l r = r o ( q r 分解) 2 块a r n o l d i 算法构造矩阵块k r y l o v 子空间的正交基 3 求解 q 1 ，q 2 ， m i n ij r e l 一+ 1 宰fj f f e r 。x8 。 4 计算= x o + 木f 其中f 斤x s 是上面方程的矩阵解 考虑线性方程组 1 5 预条件处理 a x = b ( 1 2 ) 如果系数矩阵a 的规模很大，结构不好，会使方程组的求解变得困难。这时预条 件处理是解决用迭代解求解矩阵方程a x = 6 的一个可行的很好的方法。预条件 处理有左预条件，右预条件和双边预条件等处理方法，其中预条件矩阵可以由系 数矩阵a 的不完全分解取得。 ( 1 ) 左预条件处理 对线性方程组( 1 2 ) 进行左预条件处理可得新的系统 m 一1 a x = m 一1 b ( 1 3 ) 、 一土堡盔堂塑堂焦迨塞 ! 曼 _-_一一一 则我们可以得到线性方程组( 1 2 ) 的左预条件k r y l o v 子空间： s p a n r o ，m a r o ，( m 一1 a ) m 。1 r o 这里将m 一1 ( 6 一a x m ) 看成新系统( 1 3 ) 的残量。再结合g m r e s 方法可以得到( 1 2 ) 带 左预条件的g m r e s 算法： 带左预条件的g m r e s 算法 1 取初始解z o ，计算r o = m _ 1 ( 6 一a x o ) ，= i i r o l l 2 和v l = r o z 2 f o rj = 1 ，2 ，：m 3 计算w ：= m 一1 a b 4 f o ri = 1 ，2 ，歹计算j = ( w ，忱) 和w ：= 叫一h i ，j v i 5 计算+ 1 j = 1 1 叫1 1 2 和+ 1 = w h j + l a 6 令：