（计算数学专业论文）一种加权的simpler+gmres算法.pdf

一种加权的s i m p l e rg m r e s 算法 摘要 g m r e s 方法足求解大规模非对称稀疏线陛方程组最常用的方法在实际应用 中，给出了许多对标准g m r e s 进行改进的算法，比如s i m p l e rg m r e s 和w e i g h t e d g m r e s s i m p l e rg m r e s 通过改进g m r e s 中基的生成过程，把求解最小二乘 问题转化成求解上三角矩阵的线性方程组，避免了求解最l b - - 乘问题，有效减小了 算法的计算量，同时使算法保持较好的收敛性w e i g h t e dg m r e s 则采用加权技术 来加快g m r e s 方法的收敛速度w e i g h t e dg m r e s 虽然有较快的收敛速度，但是 加权技术增加了算法的计算量。本文的主要贡献足提出一种新称为w e i g h t e ds i m p l e r g m r e s 的方法，它是在以s i m p l e rg m r e s 方法为基础，结合w e i g h t e dg m r e s 方 法得到的在控制计算量的前提下，通过加权技术来加快s i m p l e rg m r e s 的收敛速 度实验表明，对许多问题，w e i g h t e ds i m p l e rg m r e s 方法的收敛陛优于s i m p l e r g m r e s 、w e i g h t e dg m r e s 和g m r e s ，计算量小于w e i g h t e dg m r e s 本文分为以下四个部分第一章主要介绍相关的问题背景，并概述文章的主要 内容第二章简要地描述了g m r e s 、s i m p l e rg m r e s 以及w e i g h t e dg m r e s 算 法第三章具体给出w e i g h t e ds i m p l e rg m r e s 算法的主要思想，同时讨论该算法 一些主要的性质最后一章足数值实验，对于许多不同类型的问题进行测试，体现出 w e i g h t e ds i m p l e rg m r e s 算法跟原算法相比有很好的收敛效果 关键词：a r n o l d i ；g m r e s ；加权 一种加权的s i m p l e rg m r e s 算法 a b s t r a c t l v gm r e si st h em o s tp o p u l a rm e t h o df o rs o l v i n gl a r g es c a l en o n s y m m e t r i cs p a r s el i n e a rs y s t e m s t h e r ee x i s tal a r g ev a r i e t yo fm o d i f i c a t i o n st ot h e s t a n d a r dg m r e sa l g o r i t h m ，s u c ha ss i m p l e rg m r e sa n dw e i g h t e dg m r e s s i m p l e rg m r e sc o n v e r t sal e a s ts q u a r e sp r o b l e mi n t oat r i a n g u l a rm a t r i xl i n e a r s y s t e m ，s oi ti sl e s se x p e n s i v et h a ng m r e s w e i g h t e dg m r e s a d d saw e i g h t e d t e c h n i q u et os p e e du pt h ec o n v e r g e n c e ，b u tb e c o m e m o r ee x p e n s i v e i nt h i sp a - p e r ，w eg i v ean e wm e t h o dc a l l e dw e i g h t e ds i m p l e rg m r e s ，w h i c hi sb a s e do n s i m p l e rg m r e sa n di so b t a i n e db yc o m b i n i n gi tw i t hw e i g h t e dg m r e s t h e n u m e r i c a le x p e r i m e n t ss h o wt h a tf o rm a n yp r o b l e m s ，w e i g h t e ds i m p l e rg m r e s c o n v e r g e sf a s t e rt h a ns i m p l e rg m r e s ，w e i g h t e dg m r e sa n dg m r e s ，a n di s l e s se x p e n s i v et h a nw e i g h t e dg m r e s t h i sp a p e ri n c l u d e sf o u rp a r t s i nt h ef i r s tp a r t ，r e l a t e dp r o b l e m sa n db a e k - g r o u n di si n t r o d u e e da n dt h em a i nc o n t e n t so ft h i sp a p e ra r ea l s od e s c r i b e d i n t h es e c o n dp a r t ，w eb r i e f l yd e s c r i b et h eg m r e s ，s i m p l e rg m r e sa n dw e i g h t e d g m r e s i nt h et h i r dp a r t ，t h em a i ni d e ao fw e i g h t e ds i m p l e rg m r e si s i n t r o d u c e da n ds o m er e l a t e dp r o p e r t i e sa r ed i s c u s s e dt o o t h el a s tp a r ti st h e n u m e r i c a le x p e r i m e n t w et e s taw i d er a n g eo fp r o b l e m st os h o wt h a tw e i g h t e d s i m p l e rg m r e s h a sb e t t e rp e r f o r m a n c et h a ns o m eo r i g i n a la l g o r i t h m s k e yw o r d ：a r n o l d i ；g m r e s ；w e i g h t e d 厦门大学学位论文原创性声明 兹呈交的学位论文，是本人在导师指导下独立完成的研 究成果。本人在论文写作中参考的其它个人或集体的研究成 果，均在文中以明确方式标明。本人依法享有和承担由此论 文而产生的权利和责任。 责任人( 签名) ：朽影弗 矽og 年朔多de t 厦门大学学位论文著作权使用声明 本人完全了解厦门大学有关保留、使用学位论文的规定。 厦门大学有权保留并向国家主管部门或其指定机构送交论文 的纸质版和电子版，有权将学位论文用于非赢利目的的少量 复制并允许论文进入学校图书馆被查阅，有权将学位论文的 内容编入有关数据库进行检索，有权将学位论文的标题和摘 要汇编出版。保密的学位论文在解密后适用本规定。 本学位论文属于 1 、保密() ，在年解密后适用本授权书。 2 、不保密( 心 ( 请在以上相应括号内打”) 作者签名： 导师签名： 日期：w u 牌朔如日 日期：加谚年朔；口日 第一章引言 第一章引言 本文讨论如何求解一个大规模稀疏线性系统 a x = b ，( 1 1 ) 其中a r n 瑚是稀疏且非奇异。z ，b r n 为n 维向量。大型稀疏矩阵问 题主要来源于椭圆型和抛物型偏微分方程的离散化，也产生于电路设计与 计算机分析，动力系统网络等许多应用领域 目前已经出现了许多求解( 1 1 ) 的方法，近年来人们在求解大规模稀 疏线性方程组时倾向于运用迭代方法，这使得关于迭代方法的研究受到越 来越多的重视。在众多的迭代方法中，其中一大类就是k r y l o v 子空间方 法。而k r y l o v 方法中使用最广泛的是g m r e s 算法，g m r e s 方法是一种 求解大型非对称线性方程组的k r y l o v 子空间投影法，1 9 8 6 年由y s a a d 和 m h s c h l t z 提出【1 1 ，该法对于大型稀疏非对称矩阵特别有效，目前广泛应 用于机械、计算力学、计算数学等工程领域。g m r e s 主要是利用a r n o l d i 过程生成k r y l o v 子空间的一组基，当然还有许多方法是利用a r n o l d i 过程 来实现的，比如f o m 方法以及许多这些方法的变形和改进 6 另一种著 名的k r y l o v 方法就是q m r 算法【2 】q m r 方法与g m r e s 方法的主要区 别在于生成基的过程不同，它是利用l a n c z o s 过程来实现的。q m r 方法的 缺点在于会出现恶性中断，所以通常需要用l o o k - a h e a dl a n z o s 方法来避免 这种中断。利用l a n c z o s 过程来实现的算法还有很多，比如b c g 方法以及 许多它们的变形 6 】还有一种以k r y l o v 空间为基础的方法是h e s s e n b e r g 方法，这种方法的计算量和对存储量的要求都很少，也有着不错的收敛效 果，比如c m r h 方法( 7 】 1 9 9 4 年，h o m ef w a l k e r 在文【3 l 中对g m r e s 方法进行了变形，提 出了一种方法叫做s i m p l e rg m r e s ( 以下简称s g m r e s ) 的方法s g m r e s 方法的优点在于在每一次迭代的最后避免了求解个最b - 乘问题，这样 减少了计算量，但是它的收敛效果没有g m r e s 好( 可能会出现停滞的现 象) 1 9 9 8 年，a z e d d i n ee s s a i 在文 3 1 中对g m r e s 方法进行了改进，提 出了一种称为w e i g h t e dg m r e s ( 以下简称w g m r e s ) 的方法。w g m r e s 第一章引言2 利用加权技术不仅加快了收敛速度，而且对于有些问题，g m r e s 方法无 法收敛，w g m r e s 可以达到较好的收敛效果，但是加权技术会增大计算 量 本文的主要工作是：结合w g m r e s 的优点对s g m r e s 进行改进， 增强收敛效果，同时利用s g m r e s 自身计算量比较小的优点，控制计算 量，进而提出了一种新的，我们称为w e i g h t e ds i m p l e rg m r e s ( 以下简称 w s g m r e s ) 的方法。这种新方法的特点就是结合了w g m r e s 和s g m r e s 的优点，改进了计算量太大的缺陷，而且程序实现方面比较灵活，可以通 过改变d 矩阵的选取来改变收敛速度。这些优点得到了我们设计的一些 数值实验的结果证实。 第二章g m r e s ，s g m r e s 和w g m r e s 方法 第二章g m r e s ，s g m r e s 和w g l xr i r e s 方法 2 1g m r e s 方法 g m r e s 方法是利用a r n o l d i 过程生成一组正交基v 1 ，v 岛 令比= p l ，仇】，那么： s p a n v x ， 2 ，u k ) = k k ( a ，v 1 ) = s p a n v l ，a v l ，a 2 u 1 ，a 一1 u 1 ) 则a r n o l d i 过程满足以下等式： a v k = k 风+ h k + 1 k i j k + 1 e 舌， 其中风= ( ) 是一个k 阶的上h e s s e n b e r g 矩阵，e j 是k 维向量( o ，0 ， 3 0 ，1 ) t ， 它的第j 个元素为1 ，其他元素都为0 g m r e s 方法就是寻找( 1 _ 1 ) 的 近似解孤= z o + z k ，其中z k 凰( a ，n ) ，使得， r k = ( b a x k ) 上a 凤， 因此在最后，g m r e s 方法要解一个最b - - - 乘问题： r a i n 船i i p e l 一风+ 1 弧1 1 2 其中月k + - = ( 。，菇? 危。+ 。，。) 2 2s i m p l e rg m r e s 方法 s g m r e s 其实g m r e s 方法的一种变形，它生成基的过程与g m r e s 方法稍有不同，但同样都是利用k r y l o v 子空间k t ( a ， i t 。) 算法2 i ( s g m r e s 算法) 初始化：给定z ，t o l ，令r = 6 一a x ：p o = 1 2 ，令r = r p o ，并且p = 1 迭代开始： 第二章g m r e s ，s g m r e s 和w g m r e s 方法 4 6 r t = ( 三1 ji 三二) 2 3 加权的g m r e s 方法 w g m r e s 是对g m r e s 方法的一种改进 4 】。g m r e s 生成的是一组 k r y l o v 子空间的一组正交基，而w g m r e s 生成的是一组k r y l o v 子空间d 第二章g m r e s ，s g m r e s 和w g m r e s 方法 5 正交基。 算法2 2 ( w e i g h t e da r n o l d i 过程) 1 f o rk = 1 m ： 2 计算： w = a l k ， 3 f o ri = 1 k ： 4 玩= ( w ，l i ) o ， 5 叫= 伽一心2 i ， 6 e n d f o r 7 h k + 1 k = i i 叫d ，如果k + 1 k = 0 ，停止，否则，l k + 1 = w h k + 1 1 ， 8 e n d f o r 因此，w g m r e s 生成的c 1 ，f 2 ，f 南 令l k = 1 - ，1 2 ，i k 】，那么所求的解 就是d 正交( 看3 1 ) 的一组基。 z k = z o + z k ，其中z k l 七，使得， r k = ( b a x k ) - i - d a l k ， ( 上d 表示d 垂直，看3 1 ) 最后要解的仍然是一个最d 、- - u - 乘问题 其中风+ 。 m i n 甜k i ( 0 ，。) i p e l h k + l y k l1 2 ， 实际上w g m r e s 可以看成个预处理过程，由于w g m r e s 过程满 足关系： 4 l k = l k 凰+ h k + l , l k + l e ：， 其中l t d l k = ，饥= 【f 1 1 2 ，纠 如果令q k = 、伍l 奄，那么( 2 2 ) 就改写成， b q = q k h k + h k + l , k q k + 1e ：， ( 2 2 ) ( 2 3 ) 其中b ： 万a 万一，q ： 9 1 ，q 2 ，q k 】，q k + 1 = 万f k + 1 ，q ：q k = j 。 w g m r e s 方法可以看作对a 进行预处理，把a 转化成b ，然后对 b 应用g m r e s 算法，生成的第一个基i ，= - s r ll r ll d ，其中r 表示初始 第二章g m r e s ，s g m r e s 和w g m r e s 方法 6 残量，i | 表示加权范数( 看53 1 ) 。这种方法的优点在于收敛性优于 g m r e s ，但是由于最后仍要解一个最小二乘问题，并且添加了d 内积， 所以计算量比较大。 本文结合这两种方法的优点提出一种新的方法w s g m r e s ，这种方 法结合了以上两种方法的优点，对于许多问题，不但收敛性速度比g m r e s 、s g m r e s 和w g m r e s 要快，而且有效控制了计算量，在后面的 数值实验中可以得到验证。 第三章w s g m r e s 方法 第三章w s g m r e s 方法 3 1 加权的s i m p l e r 过程 7 先定义一下d 内积，如果d f o ( 1 i n ) ，d = d i a g d l ，d 2 ，d ，。) 是 一个对角阵，u 和v 是两个向量，u ，v r n ，那么它们的d 内积就是： ( u ，钞) d = v t d u = d i u i v t ， 如果( u ， ) d = 0 那么我们称仳和口关于d 相互正交，也可以表示成 u - i - dv 。 同样我们定义( 加权) 范数： i l u l l d = 俪= 佰瓦= 1e d i u ；，vu r “ vi = l 对于矩阵的情况，我们定义： i l g l l d = = 孤丽( 3 1 ) 其中入。( k t d k ) 表示k r d k 最大的特征值 令d = ( d ，d z ，d 。) t ，我们选取i i d l l = 何， d n = 1 时， ( i t ，v ) d = ( i t ， ) 接下来我们介绍一下w e i g h t e ds i m p l e r 方法。 算法3 1 ( w e i g h t e ds i m p l e r 算法) 初始化：选取，使得：i i r o l l d = 1 迭代： 1 f o rk = 1 m ： 2 计算：口知= a v 一l ，当七= 1 时，u 1 = a r o 。 3 当k 1 时，f o ri = 1 七一1 ： 这样当d l = d 2 = = ( 3 2 ) 第三章w s g m r e s 方法 a 胁七= ( y i ，v k ) n 。 b v k = y k p i 七v i 4 e n d f o r 5 p k k = 6 r k = 蔓) 8 7 e n d f o r 。 从w e i g h t e ds i m p l e r 算法我们可以推出，令圪= 【r 0 ，一l 】， w k = 【 0 1 ，u 2 ， 其中 ，饥】，那么就有 r k = a 坛= w k r k ， 帆= 【札，仇】是d 正交的一组基并且满足 s p a n w k )= s p a n a r o ，a 2 7 0 ，a 珈) ， s p a n 圪) = ( a ，r o )= s p a n r o ，a r o ，- 1 r o ) 求解方程就是寻找z k 纸( a ，r o ) ，= x o + 钆，使得： r k = b a x kl da k k ， 其中s p a n a k k 】= s p a n a y k ) = s p a n w k ) 令z k = v k y k ，玑= 【7 7 l ，r 1 2 ，叫丁，那么： 所以 a z k = a r o ，v l ，v k 一1 y k r 0 = r 女+ a k y k = r k + 名u 七= r k + w 么r k ， ( 3 3 ) ( 3 4 ) ( 3 5 ) ( 3 6 ) d 川m 0 ，、 、 七 七 m 风 m 0 第三章w s g m r e s 方法 令r k y k = k = 陈1 2 ，引丁，可以推出 k r o = + 矗仇， i = l 7 k = r k 一1 一黾u 根据( 3 4 ) ，( 3 8 ) 可得：i h 旧+ i 仇临= i i r k - 1 ， 所以， d = 订瓦珂霜； = 一- d 以= 劢而i 席 = l h 一1 i i ds i n ( a r c c o s ( k | i r k 一1 l i d ) ) 假设i l d = 1 ，那么这个过程可以写成 算法3 2 1 p = i i r o | i d = 1 2 o rk = 1 ，m ： 3 p = p s i n ( a r c c o s ( d ；) ) 4 e n d f o r 第3 步生成的p 就是仉 接下来我们推导如何求出毛( 1 i m ) 由于仇l d 帆，所以仉上dv 七，根据 f k v d v k = 0 ，所以 9 ( 3 7 ) ( 3 8 ) ( 3 8 ) 可得：v t d r k = v t d r k 一1 一 矗= v t d r 女一1 那么我们就有以下的迭代式子： = v d r k 一1 ， r k2r k 一1 一v k ， r k y k = 【l ，已，缸】丁，玑= 叼1 ，啦，讥】了1 ， z k = k y k ， x k = x o + z k ， 因为仇一l = r o 一等& 耽，令i l r o l l d = p ，r 0 = p ， ( 3 9 ) 第三章w s g m r e s 方法 我们得到： = v t d r k 一1 ， 1 k = r k 一1 一& 吼， r k y a = 1 = 2 ，纠丁，y k = 【r h 7 1 2 ，仉 1 1 ， i fk = 1 ，z l = q l r o ， i fk 1 ，钆= i l l 吼一l + t k - 1 1 ( 叩件l + 7 7 l 釉仇， x k2x o + p z k 3 2w s g m r e s 算法 接下来我们给出我们的w s g m r e s 的算法 算法3 3 ( w s g m r e s 算法) 1 0 初始化：给定z ，t o l ，令r = b a x ，p o = l d ，如果p o 1 时，f o ri = 1 k 一1 ： a p i k = ( 仇，v k ) z ) b k = 口七一p 娩v t 4 e n d f o r 。 5 p k k = i i d 如果p k k t o l ，令k = k 一1 ，跳到第1 0 步否则，令 咖七= 寸 8 r = r 一u k 9 e n d f o r 。 第三章w s g m r e s 方法 1 2 z = x + p o z 。 1 3 r = 6 一a x ，如果1 2 t o l ，z 就是我们要求的解；否则，令p o = i r l l d ， p = 1 重新进行迭代。 在实际的计算中， ( u ，v ) d = v t d u ， ( 让， ) d = 以u t v i ， i = 1 ( 3 1 0 ) ( 3 1 1 ) 数值实验表明，利用( 3 1 1 ) 进行计算会比( 3 1 0 ) 进行计算速度上快约9 0 ， 而误差会减小约4 0 5 所以在数值实验中我们采用( 3 11 ) 进行计算。根 据( 3 2 ) ，当d = ( 1 ，1 ，1 ) t 时，也就是d 是单位阵时，显然w s g m r e s 过程与s g m r e s 是一样的 根据( 3 3 ) ，( 3 4 ) 和( 3 5 ) w s g m r e s 最后就是要解这样一个方程： a v k y k2w k r k y k2r 0 ( 3 1 2 ) 现在考虑方程： 毗f = r o ( 3 1 3 ) 在g m r e s 方法中，( 3 1 3 ) 是有精确解的，l _ li r o ll 。e 。，但是这并不代表 g m r e s 有精确解，因为g m r e s 最后要求解一个最d 、- - - - 乘问题，而不是 ( 3 1 3 ) 而在w s g m r e s 方法中( 3 1 3 ) 不一定存在精确解，下面分两种情 况进行讨论： ( 1 ) 当 2 1 ，v 2 ，讥和r o 线性无关时，( 3 1 3 ) 不可能存在精确解，那么 问题就转化成求解： m i n l l w j 一7 o lk , 错w t d w k l = 昭d r o 错f - 略 纠 正 一 + 锄 m = 纨 + 中 旷 斯 孙孙 ， 幻 讯 一 七 七 h ， 巳 ：； 卜，1【 陈 = = z r 解求 c ； l 第三章w s g m r e s 方法1 2 那么方程就转化成r k y = v 曙d r 。 根据( 3 4 ) 和( 3 7 ) ，可以得到r k y k = k l ，z ，引7 ，e l i = v _ d r o ，这与 上面的结果是一致的。 ( 2 ) 当y 。，v k 和珈线性相关时，( 3 1 3 ) 显然一定存在精确解，那 么方程( 1 1 ) 就存在精确解，因此初值的选取是非常重要的。 考虑另一个方程： a k y k = r o ，( 3 1 4 ) 在g m r e s 方法中，k 是一组正交基，因此k 2 ( k ) 是比较好的在 w s g m r e 方法中，k 不是一组正交基，所以我们现在要讨论一下k 的 条件数。 根据( 3 1 ) 我们定义k o ( v k ) = i i u , l l d i l 盯1 i l d 为u 的条件数 引理1 1假设m r 舨电，并且m = 【口，e 2 ，e 】，其中o = ( q l ，q 2 ，o l k ) t ，o t l 0 ，男5 么k 2 ( m ) ( i i n i i ；+ 1 ) l a l l 证明： 仡2 ( m ) = | i m | | 2 1 1 m - 1i | 2 ， 若u = ( p l ，p 2 ：肌) 丁是一个单位向量，令u 7 = ( 1 一p ；) 一1 2 ( o ，p 2 ，肌) t ， 那么我们就有： i m u l l 2 = u ，口+ ( 1 一卢：) 1 2 乱2 i p t i l i a l i 2 + ( 1 一p ；) 1 2 i i u 川2 、i i n j i l + i l u 川1 因为w 旧= 1 ，所以l i m i z 卅同百玎 同样， m 1 = 【a 7 ，e 2 ，e k 】，其中a = ( 1 ( i l ，一a 2 a 1 一n 七q 1 ) t 同样可以得到： a i m 。1 1 1 2 、i i 口川；+ 1 = 、i i o 旧+ 1 1 q , 1 所以： a 2 ( m ) = l i l l i zj i m 。1 1 2 ( 1 i n l i ；+ 1 ) 1 a 1 1 定理1 1对于圪，我们有k d ( k ) 2 l i d 川仇一l 怯，其中k = r o 川r 0 1 i o ，y l ，仇一1 1 第三章w s g a 仍e s 方法 1 3 令肌= i r k - 1 川7 1 一1 l i d ，v l ，讥一j ，可以得到： y k = n k m k ， 证明：根据( 3 7 ) ， 其中： 0 1 。 1 0 因为i i y 岛l l d = v a , n a 。( v k t d v k ) = v z a m a 。( m n t d n k m k ) ， 并且n p y k = i ， 所以i i y 七l l d = 瓦= = = 面骊= i i i m l l 2 ，因此k d ( k ) = k z ( 慨) 。 根据引理1 1 我们可以得到： k , 2 ( 慨) ( il a l l ；+ 1 ) 1 1 其中： o = ( 1 1 r 七一1 1 1 d l i t o d ，1 l i r o d ， 一1 l l r 0 1 l d ) r ，q l = l f r 一* i i d i i r o i i d 令r 0 = l i d r j ，根据( 3 7 ) 可以得到：r j = m q 我们可以推出 1 1 4 l i d = i l a l l 2 = 1 。 因此h , 2 ( 缸) i i r o l l d ( | l r ；i i 刍+ 1 ) l l r 七一- l i d 故： g d ( k ) l h i i d ( 1 l r h l l 刍- i - 1 ) 1 1 1 r l , 一- i l d = 2 1 1 r o i i d l l r k 一- l i d ( 3 1 5 ) 推论1 1如果= 【r 0 ，v 讥一1 】，我们有k d ( ) ( i i t o i i d 十 1 ) 川r k x l l d 证明：同理根据( 3 7 ) ，令肌= 【r k - 1 l i t l i d m ，魄一l 】，可以得 到： k = 帆磁， 吲d 川训 h l q 鼠 h ，f-_-_il、 = 帆 第三章w s g m r e s 方法 蛭= 旧三 k 2 ( 峨) ( i l a l l ；+ 1 ) i o q 根据( 3 7 ) 可以得到：7 0 = n k a 我们可以推出l l r o 怯= l l a l l z 。 因此： k d ( ) ( i i r o ll 至, + 1 ) ll r k 一1 恼( 3 1 6 ) 由此可以看出，在算法3 3 中对于伯初始残量要进行单位化如果没 有进行单位化，根据( 3 1 6 ) ，随着迭代步数的增加，ii 一，怕会越来越小， 那么无论怖i f d 是多少，仡d ( w ) 就会越来越大，对于( 3 1 4 ) 这个线性方程 组的求解问题就会变得病态，这对于我们解方程是十分不利的因此我们 必须对初始残量进行单位化，因为在实际的计算中，k 般比较小，i i , - o l l d 和l h 一- d 相差不大，根据( 3 1 5 ) ，我们可以看出1 1 , - o l l d 1 1 , 七一- d 般不 会很大，所以n , d ( k ) 也不会很大，对于( 3 1 4 ) 这个线性方程组的求解问 题就是良态的。 d一七 r = q t 、， 一 矗一 d一七 r ，i、 = 0 中其 第四章数值实验 1 5 第四章数值实验 下面我们在p e n t i u mi v1 5 0 g h z ，内存2 5 6 m b 的计算机卜使用m a t l a b6 5 进行数值实验，来说明w s g m r e s 的收敛速度通常要比g m r e s 和s g m r e s 要快。在以下的数值实验中我们都取m = 2 0 ，初始向量z 。= ( 0 ，0 ，o ) t ，r = 6 a z 表示残量。在w s g m r e s 中的d = d i a g d 1 ，d 2 ，d 。) ， 其中d 产v 佤l r ( i ) l n o r m ( r ) ，t ( i ) 表示r 向量的第i 个元素。在计算( a ，6 ) d 的过程中我们是利用( 3 11 ) 进行计算，这样不仅大大减小了计算量，也大 大减小了存储量，我们不需要存储整个d 矩阵，只需要存储凡维向量d = ( d t ，d 2 ，d 。) 在求解玑的过程中，并不是采用算法3 3 中的方法，而 是利用( 3 1 2 ) 进行计算 在以下图中，点划线( ) 表示g m r e s 方法，点线( ) 表示s g m r e s 方法，而w s g m r e s 方法用虚线( 一) 表示横坐标表示迭代步数，纵坐标 表示残量( 佗d r m ( r ) ) 的大小。 图1 ：三种算法关于a d d 2 0 矩阵的收敛性 例子1 ：我们选取的矩阵是a d d 2 0 ，来自于矩阵市场，在半导体系统 设计技术中应用广泛。这是一个2 3 9 5 阶的方阵，这个矩阵有1 7 3 1 9 个非 第四章数值实验 1 6 零元素，它的条件数是1 7 6 e + 0 4 。我们把残量( 礼o r m o ) ) 控制在1 0 - 1 3 附 近。 从图1 中可以看到w s g m r e s 的收敛速度非常快。只需要5 1 步残量 就可以达到6 3 6 3 1 e - 0 1 4 ，而s g m r e s 和g m r e s 需要17 1 步残量才能达 到8 8 4 4 9 e 一0 1 4 和8 8 3 4 0 e - 0 1 4 ，s g m r e s 和g i v i r e s 这两条曲线基本上一 致。 图2 ：三种算法关于b f w 7 8 2 a 矩阵的收敛性 例子2 ：第二个例子，我们选取的是b f w 7 8 2 a 矩阵，也是来自矩阵市 场，应用于一般特征值问题。这是一个7 8 2 阶的方阵，有7 5 1 6 个非零元， 条件数是4 6 e + 0 3 。我们同样控制残量在1 0 川1 附近 从图2 中可以看出w s g m r e s 的收敛速度非常快。只需要1 5 0 步残 量就可以达到9 9 2 9 6 争0 1 4 ，而s g m r e s 和g m r e s 分别需要4 7 6 和5 1 0 步残量才能达到9 8 8 1 8 e _ 0 1 4 和9 8 3 6 1 e - 0 1 4 。 第四章数值实验 图3 ：三种算法关于c a n _ _ 4 4 5 矩阵的收敛性 例子3 ：我们选取的是c a n4 4 5 矩阵，同样来自于矩阵市场这是 一个4 4 5 阶的对称方阵，有3 8 0 9 个非零元，条件数是3 7 0 8 0 e + 0 1 7 ，在飞 行设计有限元结构问题中有广泛的应用。我们控制迭代步数在1 0 0 0 步以 内。 从图3 中可以看出w s g m r e s 的收敛速度比g m r e s 和s g m r e s 都 要快，g m r e s 和s g m r e s 这两条曲线基本重合，w s g m r e s 在1 0 0 0 步 时残量可以达到7 3 1 8 7 争0 6 ，s g m r e s 和g m r e s 只能达到1 1 8 5 4 e - 0 4 。 例子4 ：这个例子是f s _ 5 4 12 矩阵，来自矩阵市场这是一个5 4 1 阶的 方阵，有4 2 8 2 个非零元素，条件数是7 7 0 4 6 e + 0 1 1 ，我们控制残量在1 0 e - 8 附近，迭代步数在8 0 0 步以内 从图4 中可以看到g m r e s 和s g m r e s 不会收敛，而w s g m r e s 的 效果就非常好，在7 2 9 步的时候残量就达到了8 4 9 4 7 e 一0 0 9 ，这说明对于某 些问题，g m r e s 和s g m r e s 不会收敛，而w s g m r e s 方法有着非常好 的收敛效果。 第四章数值实验 图4 ：三种算法关于f s _ 5 4 1 2 矩阵的收敛性 1 8 下面我们把w s g m r e s 和w g m r e s 也进行一下比较，看看这两者相 对于以上这四个矩阵有什么样的收敛效果，我们还把它们的运算时间进行 了比较 在表1 中，每个格的第一行表示残量，第二行表示迭代次数，第三行 表示计算所用的时间( 单位是秒) ，因为实验所用的计算机较为落后，所 花时间较多，但是我们主要是对两种算法所花时间进行比较，所以这并不 影响我们的结论我们可以看到，w s g m r e s 相对于w g m r e s 也有着 非常好的收敛效果，时间上也占有优势，对于f s _ 5 4 1 _ 2 这个矩阵来说，效 果尤为明显，w s g m r e s 在7 2 9 步的时候残量就达到了8 4 9 4 7 争0 0 9 ，而 w g m r e s 在8 0 0 步的时候残量才达到1 6 1 8 4 e - 0 0 5 ，而且，w s g m r e s 只 用了3 4 4 2 9 0 s ，比w g m r e s 快了三秒多。可见w s g m r e s 不仅计算量比 w g m r e s 要少，而且收敛速度要比w g m r e s 快的多 第四章数值实验 表1 ：w s g m r e s 和w g m r e s 关于以上四个矩阵的收敛比较 a d d 2 0 b f w 7 8 2 ac a n4 4 5f s5 4 12 6 3 6 3 1 e 一0 1 49 9 2 9 6 争0 1 47 3 1 8 7 e - 0 0 68 4 9 4 7 e 一0 0 9 w s g m r e s5 11 5 01 0 0 07 2 9 1 6 1 0 3 0 s1 0 2 7 4 0 s3 8 8 9 8 0 83 4 4 2 9 0 s 8 2 1 4 4 e - 0 1 48 5 0 5 5 争0 1 41 1 1 2 2 e - 0 0 51 6 1 8 4 e - 0 0 5 w g m r e s4 91 6 31 0 0 08 0 0 1 5 6 0 3 0 s1 1 2 9 6 0 84 1 6 1 9 0 s3 7 9 4 4 0 8 1 9 本文研究了求解大型线性稀疏系统的一种新方法，从数值实验的结果 来看，这种方法的效果还是相当不错的，而且这种算法的移植性也很强， 关于s g m r e s 的所有改进算法都可以运用在w s g m r e s 上，比如对w 孓 g m r e s 进行预处理【1 2 h 1 3 】，还可以添加调和离子向量来加速收敛，具体 过程可以参考文献9 】【1 0 】【1 1 】，过程是十分类似的。根据( 3 2 ) 我们还可 以得到，取d 为单位阵时，w s m g r e s 算法就是s g m r e s 算法我们可 以通过改变d 矩阵的取值来改进算法的收敛速度，一般情况下选取的d 矩阵中所有元素都要大于等于0 ，否则在数值实验中会出现许多问题。 参考文献 参考文献 1 】y s a a d ，m h s c h u l t z g m r e s ：ag 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 mf o r s 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 j s i a mj s c i s t a t 谤t c o m p u t ，1 9 8 6 ， ( 7 7 ) ：8 5 6 8 6 9 f 2 】r f r e u n d ，n m n a c h t i g a l q m r ：aq u a s i m i n i m a lr e s i d u a lm e t h o df o rl i o n - h e r m i t i a nl i n e a rs y s t e m s j n u m e r m a t h ，1 9 9 1 ，( 6 0 ) ：3 1 5 3 3 9 【3 】h f w a l k e r ，l z h o u as i m p l e rg m r e s j n u m e r l i n a l g a p p l ，1 9 9 4 ，( 1 ) ： 5 7 1 5 8 1 【4 】a e s s a i w e i g h t e df o m a n dg m r e 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 r n s j n u m e r a l g o r i t h m ，1 9 9 8 ，( 1 8 ) ：2 7 7 2 9 2 【5 h s n a j a f i ，h g h a z v i n i w e i g h t e dr e s t a r t i n gm e t h o d i nt h ew e i g h t e da r n o l d i a l g o r i t h mf o rc o m p u t i n gt h ee i g e n v a l u e so fan o n s y