（计算数学专业论文）非对称系数矩阵方程组的对称化方法.pdf

上海大学硕士学位论文 摘要 本文在对g m r e s 方法分析的基础上，讨论了非对称系数矩阵方程组的两 种对称化方法，共扼斜量法和m r e s 方法。这两种方法有效地避免了非对称系 数矩阵方程组g m r e s 方法中的“长拖”问题 本文主要分析了m r e s 方法并对其进行改进，得到m r e s 方法求解近似解 的递推公式，非常好地避免了g m r e s 方法中了“长拖”，从而节省了计算量和 存储量。 最后本文还分析了这几种方法解方程组时相应的条件数及收敛速度估计式， 并给出了数值实例，比较了这几种方法的迭代步数和计算时间。从比较结果来看， 改进后的m r e s 方法虽然迭代步数较多，但由于每步计算量较少，从而整个c p u 时间最少。 关键词：非对称系数矩阵方程组，g m r e s 方法，长拖，共轭斜量法 m r e s 方法，计算量，存储量。 a b s t r a c t t h i sp a p e rd i s c u s s e st w os y m m e t r i z a t i o nm e t h o d sf o rs o l v i n gn o n s y m m e t r i c e q u a t i o n ss y s t e r h s t h e ya r ec o n j u g a t eg r a d i e n tm e t h o da n dm r e sm e t h o d t h e s e t w om e t h o d se f f e c t i v e l ya v o i dt h e 1 l o n gr e c u r r e n c e s ”i nt h eg m r e sm e t h o d i nt h i sp a p e r ，t h em r e sm e t h o di sm a i n l ya n a l y s e da n di m p r o v e di no r d e r t oa v o i dt h e ”l o n gr e c u r r e n c e s “，w h i c hr e d u c et h eo p e r a t i o n a lc o u n ta n dt h e s t o r a g e a l lt h ea b o v em e t h o d sh a v et h ec o n d i t i o nn n m b e r sa n d c o n v e r g e n c yr a t e s s o m e n u m e r i c a le x a m p l e sa r ea l s og i v e ni nt h ee n d b yt h e r e s u l t s ，a l t h o u g ht h ei t e r a t i v e s t e p so ft h em r e sm e t h o di st o om a n y ，b u tt h ec p ut i m ei st h el e a s t k e y w o r d s ： n o n s y m m e t r i cl i n e a rs y s t e m s ，g m r e sm e t h o d ，l o n g r e c n r r e n c e s ，t h ec o n j u g a t eg r a d i e n tm e t h o d ，m r e sm e t h o d ，o p e r a t i o n a l c o u n t ，s t o r a g e 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作除了文中特 别加以标注和致谢的地方外，论文中不包含其他人已发表或撰写过的研究成果 参与同一工作的其他同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示了谢意 签名： 华为一日期石矽 本论文使用授权说明 本人完全了解上海大学有关保留，使用学位论文的规定，即t 学校有权保留 论文及送交论文复印件，允许论文被蠢阅和借阅；学校可以公布论文的全部或部 分内容 ( 保密的论文在解密后应遵守此规定) 签名： 砌一备耘锥舻一6 似 砌导师签名：丽弓锣反侈期：t p ，石皿 上海大学硕士学位论文 第一章引言 大型线性代数方程组a x = b 的求解，是大规模科学计算与工程计算的核 心，是最常见也是研究最多的计算问题随着计算机的飞速发展，需求解的问题 的规模越来越大。一般而言，线性代数方程组根据系数矩阵a 的对称性可分为 系数矩阵对称方程组及系数矩阵非对称的方程组系数矩阵对称的方程组求解 相对而言是比较简单的，我们已经有了共轭斜量法，以及采用l a n c z o s 过程的 s y m m l q 方法和g m r e s 方法等等由于a 的对称性，这些算法并不复杂 而且在实际的计算过程中已证明这些方法对求解系数矩阵对称的方程组是非常 好的 再来看看系数矩阵非对称的方程组先看看它的重要性，现实生活中很多复 杂问题，他们的数学建模是非线性的微分方程组，一般很难得到他们的真解，所 以通常都转为求其数值近似解对所给的区间进行网格剖分后，在每一个网格点 进行离散化就能导出个线性的函数方程组正是由于非对称线性方程组在现实 生活中如此重要，且很多都涉及到国家的财产，必然要求有收敛速度快且稳定的 算法来求解非对称线性方程组。 随着对线性方程组的深入研究，目前已经提出了很多求解非对称线性方程组 非常有效的方法比较好的方法有：g m r e s 方法，建立在g m r e s 方法基础 上的重启动g m r e s 方法，不完全正交化法和双正交化方法，以及后来的c g s 方法和b i c g s t a b 方法等等，详细可参见f l o 。 本文将在对g m r e s 方法进行分析的基础上，针对g m r e s 方法中的“长 拖”问题和对称系数矩阵方程组求解时的优越性，讨论几种将非对称系数矩阵 方程组的系数矩阵对称化来求解原方程组近似解的算法，这几种算法都避免了 g m r e s 方法的各种“长拖”。 首先，我们来分析比较一下求解非对称系数矩阵方程组和对称系数矩阵的 g m r e s 方法 壹盘堂亟堂焦堡塞! 1 1 求解非对称系数矩阵方程组的g 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 ) ，即广义极小残 量法 7 。故名思义就是一种使的近似解误差最小的算法本节详细介绍了非对 称系数矩阵方程组的g m r e s 方法，指出该种方法中存在“长拖”的缺点。 求解线性方程组 a o = b 其中a 是非对称，将k r y l o v 子空间 r o ，a ”o ，a 女一1 ”o 正交化，运用a r n o l d i 过程t 取q 1 = r o l i f o h 2 1 q 2 一a q l h 3 2 q a a q 2 危k ，一l q k = a q k l h k 一1 ，一l q k 一1 一h k 一2 ，一l q k 一2 这里 k “一1 一( 4 吼1 ，吼1 )h l k 一1 = ( a q k l ，吼) ， k 一1 一堍卜, q i l l ，k = 2 ，3 ，j + 1 l = 1 假定h k ，k 一1 0 ，按a r n o l d i 过程计算到k j + 1 ，此时，令q j = q 2 ，一，划 有关系式 h 1 1 1 2 h 2 lh 2 2 九3 2 0 n 1 j h 2 ， h a j h 3 、r 1h j3 ( 1 1 2 ) 巧 “ 口 +b + 吗岛 = 岛 a 里这 土盘盔堂亟堂焦鲨塞! 是一个上h e s s e n b e r g 矩阵。同时易知 q 2 ，田j ： r o ，a r o ，- 1 托 马， ( 1 1 3 ) 马是一个j j 的上三角矩阵，它的对角元依次为 l11 丽隔丽丽 1 珂瓦j i i 而 现在考虑方程组( 1 1 1 ) 令近似解q = + q ，( ”，使r i ：b a x ，= a ( x + 一) 的范数达到最小。 b a x o a q f f 0 ) = 一q j h f f o 一b + l j q + l q j ( z o e l 一h j f ( g ) ) 一h i + 1 j 如+ 1 这里是，。) 的第j 个分量，卢0 = l l r oh 1 于是 q l | 2 = 0 肺e z 一马，。 2 + 碍扎，( ，j 力) 2 如果令 马产) = 风e 1 ( 11 4 ) 求出一个，可以得到一个近似解，但它不是极小残量法的解。但如果b 扎，= 0 ， 那么这个解使得r = 0 ，从而q 是方程组a z = b 的真解。只要d e t ( a ) 0 ，马 也一定有逆。实际上当h j + 1 , j = 0 时 a q = q h j 从而 q t a q3 = h 3 如果d e t ( 吗) = 0 ，那么马必有一个特征值为0 的特征向量，假定为f ，于是 a q3 = q j h | = 0 即q 是a 的对应特征值为0 的特征向量，这与d e t ( a ) 0 矛盾因此毋有 逆存在，这也说明在a r n o l d i 过程中发现h 一1 0 时，反而求到了真解。现在 将关系式( 11 2 ) 表示成 4 q j = 劬+ l 吗( 1 1 5 ) 连左堂亟圭堂坌量墨! 这里 秀= ( ，) 是一个+ 1 ) ，矩阵，它的最后一行为h j j 哆于是 r 3 = 一a o j f o ) = 强一q l 国i p = 劬+ 。( z o e 。一骂，) q + l 仍然是列标准正交阵因此 忱l 2 = l 号i = l l 岛e t 一葛，。8 2 这样极小残量法归结为求一个最小二乘问题，这个问题可以用旋转变换的方法求 解 令g l 是( 1 ，2 ) 的旋转变换，g 2 是( 2 ，3 ) 的旋转变换g j 是( ，j + 1 ) 的 旋转变换。它使 g j g 3 。g 2 g i h s 葛= ( 。 ? 。) 骘是一个j xj 的上三角阵。这样 i i q i | 2 = 1 1 g ，g ，一t g 。g - ( 风e - 一弱，) = i i z o g 3 9 g 2 g l e l 一冯，m 若记 8 | g c 2 g t e l = z o ( c 1 ，一5 1 c 2 ，s l s 2 c 3 ，- ，o ) 满足 碍产卜j ：o ( c i ，一8 1 c 2 ，( 一1 ) 。8 1 8 2 8 ，一l 勺) 7 0 8 = 协s ，嗡 从而 m + 10 = 慨m s 卅，j 上海大学硕士学位论文 5 也就是说它近似解的误差是递减的。该方法之所以称为广义极小残量法，是因为 采用的不是l a n c z o s 过程而是a r n o l d i 过程。该方法在实际问题中用的比较多。 g m r e s 方法是早期求解非对称系数矩阵方程近似解比较好的方法之一，因 为在设计该算法时我们是以使得近似解的误差是极小来进行的。但是在计算的过 程中我们会发现当j 过大时g m r e s 方法就变得不实际，因为随着j 的增大，存 储量和计算量都随之增大了。在a r n o l d i 过程中计算q + 1 有计算式 k 州，k 吼+ 1 = a q k 一h l k q i i ：1 右边所有系数 沌i = 1 ，2 ，3 ，k 都要计算，因此所有的q l ，q 2 ，吼都要保 存，从而时间复杂度和空间复杂度都很大同时就最后的近似解x j = z o + q j ，( j ) 而言，q 与f u ) 相乘也是不小的计算量。对于非对称的系数矩阵，设计避免这 一系列的“长拖”的算法就显得特别重要了。 解决g m r e s 方法长拖最初的算法应该是重启动的g m r e s 法。 重启动g m r e s 方法的思想很简单。即取定一个如，当在g m r e s 法中的 j = j o 时，求到，此时不再进行j = 如+ 1 计算，而是将z ，。作为新的初始向 量x o 重新进行计算。 具体算法如下： l ， r o = b a x o ， 卢= l l r o 舱，q l = 伊 2 ，用a r n o l d i 过程算得正交阵q j o + 1 与葛。 i l r j 。i i = 忙e - 一瓦， z j o = x 0 + q 如， 3 ，若满足循环停止条件，则停止。否则，令t 0 = x j o 重启动g m r e s 方法使得原来的g m r e s 方法的“长拖”得到很好的改善。 在运算过程中，我们可以任意取定j o 来控制要多少步来重新启动一次，增加了 运算的自由度。 上海大学硕士学位论文 6 1 2求解对称系数矩阵方程组的g m r e s 方法 对称系数矩阵方程组的g m r e s 方法的基本思想与非对称系数矩阵相似，区 别在于对称系数矩阵方程组g m r e s 方法中采用的正交过程不是冗长的a r n o l d i 过程，而是简洁的l a n c z o s 过程。 求解线性方程组 a x b ( 1 26 ) 其中a 是对称的矩阵，将k r y l o v 子空间 7 0 ，a r o ，a 一1 按l a n c z o s 过程正交化。取q i = r o 川m f l l q 2 = a q i o q q l 岛q 3 一a q 2 一o 。2 q 2 一风q l ， 这里o 一1 凤一l 风一l q k = a 玑一1 一a k l q k 一1 一风一2 q k 一2 ( a q k 一1 ，q k 一1 ) a 吼一1 一o m l q e 一1 一凤一2 q e 一2 吼= ( a q k l o t k l q k1 一凤一2 q k 一2 ) 凤一1 k 一2 ，3 。按l a n c z o s 过程计算到k = j + 1 ，令。j 这里 为对称三对角矩阵。 a q i = q j t ；8 m q m 毫 0 1 岛 p 1 叻岛 q l ，q 2 ，曰 ，有关系式 ( 1 2 7 ) 8 _ 2a _ 10 ，一1 0 i 。d | 上海大学硕士学位论文 7 再接下来的过程就与非对称系数矩阵方程组的求解差不多了，详细可参见 【1 0 。 通过对对称和非对称系数矩阵方程组g m r e s 方法的分析比较可以看出，如 果能在非对称系数矩阵方程组g m r e s 方法中采用l a n c z o s 过程而不用a r n o l d i 过程的话，整个算法的计算量和存储量都会大大减小。 1 3 本文的基本内容 第一章回顾复习了对称和非对称的g m r e s 方法，指出非对称g m r e s 方 法中存在“长拖”的缺陷， 第二章先复习了解对称系数矩阵方程组的共轭斜量法，并将共轭斜量法运用 到非对称系数矩阵方程组上，同时给出了收敛速度估计式 第三章介绍了另一种将系数矩阵对称化的极小残量法，这种方法是建立在 l a n c z o s 过程的基础上的，因此避免了g m r e s 方法的。长拖”，还进一步介绍 了这种极小残量法近似解的递推公式，及收敛速度估计式。 第四章中对文中所述几种解方程组方法的条件数和收敛速度进行分析，并给 出相应的数值例子 本文只是讨论了将非对称系数方程组的系数矩阵对称化后的几种算法，对 于非对称线性方程组，这些算法不一定是最好的，但是它们确实有效地避免了 g m r e s 方法计算过程的冗长，且很好的运用了对称系数矩阵方程组求解时的优 越性。 上海大学硕士学位论文 8 第二章解非对称系数矩阵的共轭斜量法 共轭斜量法是解系数矩阵对称的缌陛代数方程组的一种方法，它产生在五 十年代初期，参见参考文献f 1 5 ，现在公认它是一种好方法，可详见参考文献 f 1 6 1 ，1 7 ， 1 8 】。 本章第一节回顾了对称系数矩阵方程组的共轭斜量法，以及它的收敛速度估 计式第二节在第一节的基础上导出非对称系数矩阵方程组的系数矩阵对称化后 的共轭斜量法，并给出相应的收敛速度估计式 2 1 对称系数矩阵的共轭斜量法 本节复习了对称矩阵的共轭斜量法以及其收敛速度估计式，目的是为下一节 非对称矩阵方程组共轭斜量法的推导作铺垫。 对于线性方程组 其中a = ( ) 是n x n 实对称正定矩阵，给定初始解向量x o ，t - 0 = a x o b ， 可以得到序列 r o ，a r 0 ，一，a 一1 r o ，k 礼， 子空间m = r 0 ，a r o ，一，- 1 r o ) 为( 2 11 ) 的k r y l o v 子空间， 2 中将这 组向量按内积( a x ，y ) 正交( a 一正交) ，可得到a 一正交化的序列 咖，口l ，q k 进而得出( 2 1 1 ) 的k 次近似解。由于 2 】中已证明，对于序列，有一个 重要的关系式 ( “，r j ) = 0 ， j = 0 ，1 ，一，k 一1 从而m ，i = 0 ，1 ，2 ，k ，可由简单的公式得出，详细参见 2 。 这样有共轭斜量法常用算法为 土查盍堂亟堂垡堡塞! “ = 一( r k ，r k ) ( a 弧，吼) x k + l = z k 十o z k q + 1 = r k + a k a q k q k + 1 = r k + 1 + a ：q k k = ( r k + 1 ，r k + 1 ) ( r k ，r k ) 对于共轭斜量法的收敛速度估计， 2 中已提出，为 i l x k - i i - 缸i x o - 1 1 其中a 。为a 的最大特征值，a l 为a 的最小特征值，岳为方程组( 2 1 1 ) 的精 确解。 鼠= 1 ，t kf 、”a + a i l ) n ( z ) 为切贝谢夫多项式， 巩( 。) ：吐婴：些二塑e 共轭斜量法与其他求解系数矩阵对称方程组的方法比较起来，有几个重要的 优点， 1 ，每步迭代需要计算的量，用到系数矩阵a 的，只有a 与向量的乘法a 吼， 因此可以充分利用4 的稀疏性。 2 ，不要预先估计别的参数就可以计算，这一点不像切贝谢夫半迭代法，超 松驰法等方法。 3 ，每次迭代所需要计算的都是向量之间的运算，可以充分为第四代计算机 ( 向量运算计算机) 所利用。 4 ，正交序列q i 的求解过程很简短，不像m n o l d i 过程那样冗长。 占查盍堂亟堂笪监塞! ! 2 2 非对称矩阵方程组的共轭斜量法 由于共轭斜量法的种种优点，如果能将非对称矩阵组化为对称矩阵方程组， 然后再运用共轭斜量法的话，就能有效避免g m r e s 方法中的“长拖”， 对于线性方程组( 2 1 1 ) ，如果系数矩阵a 是不对称的，可以左乘一个a 7 得方程组 a 7 a x = a 7 b ，( 2 , 2 2 ) 这个方程组称为原方程组的法方程，它的系数矩阵a 7 a 是正定对称的( 如果a - 1 存在) 。于是可以用共轭斜量法求解。 取初始近似。o ， 0 = a 7 a x o a 7 b ，q o = 一r o ， k = 0 ，1 ，2 ， o l k = 一( 氛，氟) ( a 7 a 蟊，磊) ， 茁k + 1 = z k + o l k 鼐，氙+ l = 诧+ a k a t a 蟊 氨+ 1 = 氟+ l + a 蟊， k = ( 最+ - ，氏+ 1 ) ( 霞，氟) 上述算法中，a 7 a 的计算量是相当大的，更别说再加上其他一系列矩阵与 向量的乘法运算。因此在实际应用上上述算法的设计不是最理想的。由于毗的 计算式可以改写为o t k 一一( t k ，n ) ( a 吼，a q k ) ，且注意到r k + 1 中也有a 讯， 因此在每一步我们可以先将a 吼的计算值赋给一个值，然后再计算。 原先的算法可以修改如下： 取初始近似。o ，= a 7 a x o a 7 b ，4 0 一而， k = 0 ，1 ，2 ，- ， 凤= a 蟊 o t k = 一慨，住) ( 风，风) ， 。k + l = x + o k 氨，氕+ 1 = 堍+ 血a t 凤 靠+ 1 = 氏+ 1 + k 氨， h = ( 敢+ - ，氏+ 1 ) ( 住，氏) 我们可以将初始向量取为零向量，从而= a 7 a x o a 7 b = 一a 7 b ，这样 上海大学硕士学位论文 儿 在初始残向量中也没有a 7 a 了。 上述算法就存储来说，我们可以把每一步的凤放在同一个存储单元中，所 有的q k ，z 和k 也是各自只要一个存储单元，而所有的n 也只需两个存储 单元，这是非常好的。 现在来看看非对称线性方程组共轭斜量法的收敛速度估计式。 根据上一节已经给出的对称系数矩阵方程组解的收敛速度估计式，我们就得 到非对称阵系数方程组共轭斜量法的收敛速度估计式： 刮簧驯一刮 其中k 为a 7 a 的最大特征值，a i 为a t a 的最小特征值，i 为方程组( 2 2 2 ) 的精确解。 e k = i 肛( 麟) 在第五章中我们将会由a 7 a 的特征值与a 的奇异值之间的关系，进一步将 上述估计式化为a 的奇异值的形式，以方便与其他方法的收敛速度作比较 上海大学硕士学位论文1 2 第三章非对称系数矩阵方程的m r e s 方法及其改进 m r e s 方法( t h em i n i m a lr e s i d u a la l g o r i t h m ) ，即极小残量法，是由蒋尔雄 先生提出的【1 ，这种方法提出的初衷是为了避免g m r e s 方法中冗长的a r n o l d i 过程。本章第一节给出m r e s 方法详细的推导过程。第二节在第一节的基础上进 一步对m r e s 方法进行改进，得出m r e s 方法的递推公式。第三节给出m r e s 方法的收敛速度估计式。 3 1 非对称系数矩阵方程组m i r e s 。方法 对于非对称系数矩阵方程组 a z b ( 3 1 1 ) 的求解，考虑方程组 a 2 = b ，( 3 1 2 ) 其中 五= ( 0 三) ，s 一( ：) ，童一( ：) ， ( 3 1 2 ) 的系数矩阵是对称的，且( 31 2 ) 的第一个方程为 a x = b ， 即为( 3 1 1 ) ，它的第二个方程 a t y = c y ，c 可以取成y o ，c 满足 a 7 y o = c ， 这样求方程( 3 1 2 ) 的解，即为求方程( 3 1 1 ) 的解。因为a 是对称矩阵，我们就 可以用比a r n o l d i 过程简单的l a n c z o s 过程来求它的近似解取 南= ( x 珈0 ) ，娲= s 一赢。= ( 苫) 上海大学硕士学位论文 1 3 这里r o = b a x o ， 氨= 而川霸“= ( ：) ，a = r 0 “忆 2 风= 0 ， 岛西+ 1 = a 毋一o o 萄一岛一1 岛一1 ，j = 1 ，2 ，一，2 m 这里 = ( a 西，蠡) ，岛= 0 a 蟊一o o 毋一岛一t 西一- 叭 可以用归纳法证明 1 一岛2 啦k 一2 玑 ，屈 一1 o ，t h e n q 2 k = ( a 7 啦k 一1 一岛k 一2 蚴一2 ) 岛女l 岛k = i i a q 2 e 一岛k l q 2 k 一1 l i ，i ，风o ，t h e n q 2 k + 1 = ( a q 2 k 一岛 一l 口2 k 一1 ) 岛k 实际上由 胁翕= a 甄一a - 盈，a - = c a 蠡，蠡，= ( ( ? m ) ，( ：) ) = 。 岛= i | ( a ：吼) 0 = n a 7 m ， q 2 = a t q l 卢1 ， q 2 = 0 1 2 = o 他) = ( a 如，如) = 0 假定上述命题对k = j 一1 成立。考察k = j ，由 锄一l 勤= a 勃l o 卸一1 勤一1 一锄一2 勤一2 =啦、 惮。慨 = =， 一 o = 触 慨 、， o m 啦 ， ， = l 1 = 啦 七 上海大学硕士学位论文 1 4 囡 = ( 计瞬一。) 所以 嗡h 辄一，” 令 q 2 j 0 a t q 一1m ( 0 。 i i a 7 一1 一如一2 一2 | | ( a 7 一1 一口一2 q 2 j 一2 ) 屈卜1 证毕 上述l a n c z o s 过程也有基本关系式 这里 a 亩2 。= 囝2 。t 2 。+ 岛。翕m + l e 玉 亩。，。= 喻，函，一，翕。 0 ( 3 1 3 ) 划 、坩、p o 倔，( 驴 一i 0小 岛，a 、一吖“u 勤 勤 = 纠 、铲如 。啦奶嘘 硫一蚧一嗡嗡 勤 助 ； 吼 助 如、厂 旷啪o ，i = = + + 勤 上鲞盔堂亟芏笪堡塞 ! ! 玛。= 0 卢1 氐08 2 岛 岛。一1 岛。一1 0 若记 磊。+ - = ( 。? 弋风。) 则 a q 2 。= 0 2 。+ l + 1 如果记( 3 1 2 ) 的近似解为 耻( 卜尬m ，h 川7 础” 宙。的残量为 r m 酽 “ 1l - a 童m c 0 一a q 2 。， ( 苫) 一薹止，( a ) 一薹疡一，( a ，三一。) i i r o 一a j a q 2 j 1 2 + i i 扬一1 a 7 q 2 l | 2 考虑1 1 1 1 2 取极小，必须场一- = 0 若记达到极小的，为 ，+ = ( 矗，矗，一，岛；) 7 由此 即 z 。= ( ：) = 童。+ 国z 。，+ 一( 。+ 蓦y d 荡) m z 。= 。o + 坛q 2 j ，跏= y o j = l s 5 a 岛 m 埘 一 | l m r 土姿盘堂亟堂笪鲨塞 ! ! 现在来讨论，的求法。由 荒= = l l 瑟0 = l l 蠕i i = 因为，中的，2 ，一1 = 0 ，j = 1 ，2 ， 死。， 如果记( m 十1 ) x m 矩阵 得 这里 弼一a q 2 。， 罚一亩。+ 。磊。，+ 亩。+ 。( 怖慨一彳k ，+ ) r l l r o l l e 一磊。，+ | | 呼忡0 i i e l 一磊。州 ，m ，所以 卢1 ，2 0 8 2 f 2 + f 1 0 岛。，2 。 卢l 8 28 3 瓯8 岛。一l 也。 慌i i 。呼i l i i r o l i e 一l , n 9 1 1 - ( 3 l t 4 ) g 一( g l ，9 2 ，9 。) 7 = ( ，2 ，4 ， 。) 7 旧扬+ 助o + 扬勘 土连盍堂亟堂焦鱼塞 ! ! 利用旋转矩阵消去l 。中的危，风，一，岛。，将l 。化成上三角阵。令 f c 。s 。 nli 民2 r “，j p 1 2 ( 1 l r o l l e , 一l 。g ) = 1 1 r o l lp 1 2 e l p 1 2 工。9 p 1 2 l 。= q 8 l + 8 1 0 2s i8 3 0 一 一s 1 卢1 + c 1 岛c l 阮o u 8 l魄 0 取s 。= 屈( 所十熙) ，c 。一卢l ( 所+ 例2j 。i 尸1 2 l 。= c l s l o 0 1 1o l 0c 1 风0 8 4 8 5 其中7 ，= ( 所+ 鹾) ，6 t = s - 岛 岛。一1 岛。 岛r r 。- - i 岛。 土塑盔生亟堂笪堡塞 ! ! 得 再左乘p 2 3 令 尸2 3 p 1 2 l 。 s 2 他 尸2 3 岛3p 1 2 8 1 7 1 4 -s 2 风 5 2 风 一8 2 c i 卢3 十c 2 风0 2 傀 8 6画 0 历。l 岛。 凰( ( c 。岛) 2 + 鹾2 jz l ，c 2 = c 。岛( ( c 。风) 2 + 詹) ( ( c 1 岛) 2 + 例2 jz 1 ， 如= s 2 风 、 ， 比 如2 如 咭 吃 o q 嘞 驴 o 土塑盘堂亟堂焦监塞 ! ! 若记 民尸1 2 工。 若令c o = 1 ，以此类推，令 s t = m= m6 1 0 他如 0 c 2 尾0 8 68 t 岛t ( ( 臼一- 岛t 一，) 2 + ( 屈t ) 2 ) 5 ( ( 铀岛。) 。+ ( 艮) 。) 5 ， 对i = l ，2 ，m 有 p m m + l p 2 3 p 1 2 8 1 。篡， 岛。一1 岛。 g = q 一。岛；一。( ( 岛一。伪；一。) 2 + ( 国；) z ) 3 文= 8 i 岛e + 1 一s 1 c 2 8 1 $ 2 c 3 ( 一1 ) m - 2 8 1 8 2 ( 一1 ) m - 1 s 1 8 2 - ( 一1 ) m s l s 2 - s m 一2 c m 一1 8 m - 2 8 m - 1 s m - 2 8 m - l s m 土塑盔堂亟主堂焦堡塞 ! ! 有 p m 。+ 1 马3p 1 2 l 。 7 1d 1 0 y 2 如 0 y 3 如 0 d m 一1 0 d ( ”) = l l r o i p m ，。+ 1 最3 p 1 2 e 1 = ( d ( m ，d 妒，一，船，d 辨。) 7 令m 维向量 妒1 = ( 一1 ) 卜1j j r 0 s l 却- - o 一1 勺，j = 1 ，2 ，m ， d 辨，= ( 一1 ) “怖怕即8 m - i s 。 r n ? 7 2 上三角阵 = 厶= ( d p ，d ! m ，船) 7 1 1 乏如0 他以 0 那么最佳的= 鲩= r 二1 五。而此时 k 一1 嚅| | = l d 辨，i = 怖怕s 。8 。 因0 8 1 1 ，所以i l r 划是单调下降的近似解 。= z o + g ：, j q 2 j z o + 国麓9 二 ( 3 1 5 ) j = l 这里蠕是嘛的第j 个分量，o 麓= 【q 2 ，口4 ，q 2 m 。计算时可以设定1 1 1 1 足够小，再来计算z 。 上登塑型幽迭j 第三节中我们还会证明； ( i ) 当：o 且岛o ，j = 1 ，2 ，2 m 一1 时。m5 几+ ；1 当愚。一l ：o 且岛o ，j ；1 ，2 ，+ 一，2 一2 时。m 一1 2 。 此处为( 3 1 1 ) 的精确解- 这样设计m r e s 算法如下； 1 取正。，r 0 鲥一a 舶，q l = 删乩角= o ，c 0 = 1 s 。= 1 ，d 。= 一1 h ，k = 1 = a 1 。啦k 一1 一2 b 一2 q 2 k 一2 触：删lm ：k g o t 。4e k e 蚴刮i f0t h e n 1 岛一l = m = 七一 g o t o4 8 l s eq 2 “一山”州 = a q 2 k 一岛k l q 2 k 一1 0 云”! l鲫 3 ，q 。+ 。：。岛。0 t h e n t o e l s e i f 触= ， g o 。“2 + 1 。7 “ 口：c 一l 岛一1 ， b 。岛k ，y k ：胛，6 1 , 一1 = s 胁一1 c k = 。一k ，乳= b y k c ：一s 一1 c k 一1 ，也2d k 。咏 6 = - d k 一1 c 8 k ：r 一- ：，l 上海大学硕士学位论文 2 2 由嚅的最佳性可得 ( 焉，a 西) = o ，j = 1 ，2 ，2 m ， ( r 。，a q ) = 0 ，j = 1 ，2 ，一，m 由此可以知道上述方法最多n 步使r n = 0 m r e s 方法对求解非对称矩阵的方程组是非常有效的，它避免了g m r e s 方 法中a r n o l d i 过程的。长拖”。但是即便如此，还有两个问题需要考虑，第一个问题 是它没有避免近似解公式中乘法0 ；颤的长拖，第二个问题是第k 次近似解x k 与 第+ 1 次近似解x k + - 不像共轭斜量法那样有简单的表达式z t + ，= z k + o k 吼， 这是因为9 h 。的为首个元素与9 l 没有简单的关系。因此，当计算得z 女后， 还要重新计算z 女+ ，不能充分利用z k 提供得信息，这是很大的浪费。如何充分 利用算得的z k ，节省存储量和计算量，这是一个重要的问题 3 2 非对称矩阵m r e s 方法的改进 本节将在上一节的基础上，得到m r e s 方法求解非对称系数矩阵方程组近 似解递推公式，解决了m r e s 方法中没有解决的乘法上的“长拖”问题和浪费 问题，从而节省了存储量和计算量，提高了运算效率。 对于方程组( 31 1 ) 的m 次近似解z 。= z d + q 9 + ，其中的9 二是上三角 矩阵方程组r r 。鲕= a 。的解。此处 一r 1占1 加如 1 一1d m l 1 m d m = 慨 一l l r o i j s l 国 0 r o i i s l s 2 。3 ( - 1 ) m - 2 ij r o lj s l s 2 ( 一1 ) _ 1l i r o l l s l 8 2 s m l ( 一1 岛n 一1 c m 即有z 。一z o + 国未r ：a 。，从而m + 1 次近似解为z 。+ 1 = x o + 国轨1 p 4 1 1 i 。+ 1 ，要寻找z 。和z 。+ 。的关系就需要探讨国麓r 0 与0 篇+ 。r 未，以及a 。与氙+ ， 之间的关系，在这之前我们先看看风，与赢的形成过程。 土塑盔堂亟主堂笪堡塞垫 由上一节我们知道，尼。与矗是分别对( m + 1 ) x m 阶两对角阵l 。+ 。及向 量怖怕作一系列相同的g i v e n s 变换而得到的。我们再来回顾一下这个过程， 看看从中会有何发现 令 这样就有 p 1 2 l 。+ l = p 1 2 卢1 口2d 3 8 4 唣 b 3 p 1 2 l m + 1 = c ls i s 4q 岛。2 岛。一l 恳。 ，y 16 1 0m如 0 2 侥 风 1 16 l 0 c l 岛 8 t魄 岛。一2 岛。一1 。 显然左乘矩阵岛。并不影响p 1 2 l 。+ ，的第一列 岛。一2 岛。一1 岛。 土鲞态芏亟主堂焦堡塞丝 p 3 4 p 2 3 p 1 2 l m + l = 7 l g l 0 7 2d 2 讹如 c 3 所 风 岛。一1 岛。 此时左乘矩阵p 3 t 也不影响p 2 3 p 1 2 l 。+ - 的1 , 2 两列。依次下去就会发现左 乘矩阵p ( 。+ 1 ) 对已得到的最一1 h p ( 。一2 ) ( 。一1 ) p 1 2 l 。+ l 的前m 一1 列不产 生影响。由于兄l 是对l 。+ 2 作m + 1 个g i v e n s 变换得到的，而l m + 2 的前 m + 1 行m 列与l 。+ l 相同，对它所作的前m 个g i v e n s 变换就与l 。+ l 的相 同，这样对l 。+ 2 作m 次旋转变换，得到的矩阵的前m 行m 列与见。是相同 的，再继续作变换p ( 。+ 1 ) ( 2 ) ，所得的k + 1 的前竹；行m 列就与。是相同 的。同理，d m + - 与d 。都是对i f r o l l e - 作g i v e n s 变换而得到的，其中e - 的维数 膏 分别为m + l 和m ，它们的前m 个元素是相同的，即缸+ 。= l _ 、i 。 【u d m m + + l l 。j 现在再来分析0 二r 0 令国麓r 0 = 只。 其中只。= ( p t ，p 。 故有： p l 吖1 = 啦， p 1 5 1 + 船他= q 4 ， 阮如+ 珊加= ， p 。) ，即q 羔= 只。r m p l = q 2 1 1 p 2 = ( q 4 一p 1 6 1 ) 7 2 p 3 = ( 舶一p 面2 ) 7 3 p m 一1 d m l + p m l 知= 啦m ，p m = ( q 2 m p r o - 1 如一1 ) 1 h 若再令电+ ，1 1 - 。i + ，= p m + 。根据r r 。与r 。之间的关系我们可以发现 r l 与r ；的前m 列是完全相同的，r 。1 = ( 只。p m + 。) 。这样结合缸与 d m + 。的关系，就可以得到方程a z= b 的近似解z 。到z m + 的递推公式 z 。- - p m + l d 蜜毡1 占堡盔堂塑堂焦堡塞 ! i 其中p m + l 为r 。的最后一列，d 黯1 为矗+ ，的最后一个元素 现在我们就可以将上一节的算法修改如下： 算法： 已知非对称矩阵a j p “，b 尼1 “， l ，选取初始向量2 7 0 ，r o = b a 跏，卢= jj r o l i ，q l = r o z ，c o = 1 ，8 0 = 1 ，d o = 一j 臼，k = 1 2 ，w = a 7 q 2 k1 一阮k 一2 q 2 一2 岛e 一1 = l l u i i i f 岛k 一1 = 0 t h e nz k = x k 一1 g ot o5 e l s e q 2 k = 岛k 一1 w a q 2 k 一岛k l q 2 k l 岛一l l ”| | i f 岛= 0 ，t , h e ng o t o3e l s e q 2 k + 1 = 肫 3 ， a = c k l 岛k 一1 ， b = 阮 7 = 舻+ b 2 ，d = 8 k l 2 七一l i f k = 1 ，p k = q 2 k 7 ，e l s ep k = ( q 2 k p k - 1 6 ) h c k = n h ，s k = b h e = 一s k 一1 c k 一1 ，d k = d k 一1 c c k 4 ，x k x k 一1 + p k d k r = d k l c s k i f i rj t h e ng o t o5e l s ek=k+1g ot o2 5 ，p r i n t。k ，s t o p 我们发现，整个过程我们只需要两个空间来分别存储每步迭代的奇数下标的 一1 及偶数下标的口2 女由于每一步的7 和j 只要用一次，因此各自只要一个空 间来存储就可以了。还有每一步的d k 和z 也只用到了它们的前一个元素d k 一。 和x k t ，从而节省了存储量。最重要的是，这种算法还避免了正交过程的长拖 以及乘法上的长拖，且整个算法过程中不会出现“中断”现象。 占堡盔堂亟圭堂焦堡塞垄 3 3m r e s 方法的收敛性分析 引理1 对于上述产生的q j ，有常数d 寥和e 譬且掣。o ，e 望l 0 使得 q 2 j 一萎。u ) ( a a r ) k = o 证明 q 1 = r 0 川r 0 1 | = d 铲，d p = 1 1 1 r o l l 0 啦= a 7 q 1 卢1 = e 3 1 a 7 ，e 铲= 1 ( 1 i t o 懒) 0 因此命题对j = 1 成立。 现假定命题对j = 1 ，2 ，s 成立，考虑j = s + 1 的情况 类似的 况 q 2 1 = ( a q 2 s 一岛。一1 q 2 s 1 ) 岛。 一瓦1 卜蚤8 a 7 ( a a 7 ) k r o - - 助一- 三14 ( a a 7 ) j h s 一d 扩1 ( a a t ) 伯 d 妒1 ) = e 翌。助o q 2 。+ 2 = ( a t q 2 。+ 1 一历。q 2 。) 岛。+ 1 = - 鬲li a 7 d r u ( a 且7 ) y z s 十1l k = d = e r l a 7 ( a a 7 ) e p “) = 毋“勉+ 1 0 在分析收敛性之前我们先来分析算法中，当岛。一。= 0 或者倪。= 0 时的情 定理1 假如岛0 ，j 一1 ，2 ，一，2 m 一1 ，而阮。= 0 ，那么| 1 r 麓0 = 1 1 r 。| | = 0 即。= 矿假如岛0 ，j = 1 ，2 ，2 m 一2 ，而国。一1 = 0 ，那么z 。一l = 矿 0r r aa o d j j 一 蚴 相户 t aa t a 扣k e 8 岛 占查盔堂亟圭堂焦堡塞! ! 证明由岛0 ，j = 1 ，2 ，2 m 一2 ，2 m 1 ，屈。= 0 ，从l a n c z o s 过程的基 本关系式( 3 1 3 ) ， 因此 a 【蠡，岛，一，配m l = a ，函，一，蠡m 】 荒l i = i l e o a q 2 。in l = i | q 。( 1 | r