（计算数学专业论文）添加近似误差的重新启动的simpler+gmres算法.pdf

添加近似误差的重新启动的s i m p l e rg m r e s 算法 i i j 摘要 g m r e s 方法是求解大规模非对称稀疏线性方程组最常用的方法，实际应 用中存在着许多对标准g m r e s 进行改进的算法，加速技术是其中一类添 加方法( a u g m e n t e dm e t h o d s ) 是一类重要的加速技术该方法通过添加某些向 量到当前的近似空问，从而达到加快重新启动的g m r e s 方法的收敛速度的 晷的l g m r e s 是一种新的添加方法，它通过添加近似误差到当前的近似空 间，能有效防止g m r e s 方法求解问题时所出现的相间残向量交替方向的现 象，这种交替现象导致g m r e s 方法收敛很慢l g m r e s 方法仅需对标准 的g m r e s 算法做一些小的改动，因此算法实现比较容易，且该方法对很多类 型的问题都很有效本文利用s i m p l e ra r n o l d i 过程来实现l g m r e s 算法， 其出发点是，在用s i m p l e rg r m e s 求解问题时，仍然出现用g m r e s 求解 时所出现的问题：存在着相间残向量交替方向的现象本文所给出的s i m p l e r l g m r e s 方法能防止这种交替现象，加快s i m p l e rg r m e s 的收敛速度，且 其实现代价比l g m r e s 要小，数值实验结果也表明改进后的算法效果比原来 的要好 本文分为以下四个部分第一节主要介绍相关的问题背景，并概述文章的 主要内容在第二节里，简要地描述了g m r e s 算法和s i m p l e rg m r e s 算 法第三节具体给出l g m r e s 算法的主要思想，并用s i m p l e ra r n o l d i 过程来 实现l g m r e s ，得到一种较小代价的实现方式，同时讨论该算法一些主要的性 质最后一节是数值试验，对于许多不同类型的问题进行测试，体现本文所做 的修改对于原来算法的改进作用 关键词：s i m n e rg m r e s ；k r y l o v 子空间方法；l g m r e s 添加近似误差的重新启动的s i m p l e rg m r e s 算法 a b s t r a c t g m 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 c s 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 u st ot h es t a n d a r dg m r e sa l g o r i t h mm i da c c e l e r a t i n gt e c h n i q u ei so n eo ft h e m a u g m e n t e d m e t h o d sa r ea ni m p o r t a n tc l a s so fa c c e l e r a t i n gt e c h n i q u e s t h e ya p p e n dc e r t a i nv e c t o r st ot i mc u r r e n ta p p r o x i m a t i o ns p a c et os p e e dt h ec o n v e r g e n c eo f r e s t a r t e dg m r e s l g m r e si san e wk i n do fa u g m e n t e dm e t h o d i ta p p e n d s a 1 ) p r o x i n l a t cc r r o st ot h ec u r r e n ta p p r o x i m a t es p a c e ，e f f e c t i v e l yp r e v e n t i n gt h e a l t e r n a t i n gb e h a v i o rf o re v e r yo t h e rr e s i d u a l ，w h i c hr e s u l t si ns l o wc o n v e r - g e n e ef o rt h ee a s eo fg m r e s l g m r e s i se a s yt oi m p l e m e n t r e q n i r i n gs m a l l c h a n g e st ot h es t a n d a r dg m r e sa l g o r i t h ma n di ta p p l i e st oaw i d er a n g eo f p r o b l e m s i nt h i sp a p e rw ep r e s e n tas i m p l e rf o r mo fl g m r e sb ys i m p l e r a r n o l d ip r o c e s st h i si sb a s e do nt h ef a c tt h a tt h er e s i d u a lv e c t o r sa tt h ee n d o fe a c hr e s t a r tc y c l eo fr e s t a r t e ds i m p l e rg m r e sa l s oa l t e r n a t ed i r e c t i o ni na c y c l i cf a s h i o n ，s i m i l a rt ot h ec a s ef o rr e s t a r t e dg m r e s t h en e w v a r i a n tp r e s e n t e di nt h i sp a p e rc a np r e v m l tt h ea l t e r n a t i n gp h e n o m e n o na n da c c e l e r a t e t h ec o n v e r g e n c er a t ef o rt h ee a s eo fs i m p l e rg m r e s i tr e q u i r e sl e s sa m o u t o fw o r kt h a nr e s t a r t e dl g m r e sa n dt h en u m e r i c a le x p e r i m e n t ss h o wt h a ti t h a sb e t t e rp e r f o r m a n c e 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 d b a c k g r o u n di si n t r o d u c e da n dt h em a i nc o n t e n sa r ea l s od e s c r i b e d i nt h e s 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 sa n ds i m p l e rg m r e sm e t h o d i n t h et h i r dp a r t ，t h em a i ni d e ao fl g m r e si si n t r o d u c e dm i dt h en e wv a r i a n t ， r e f f e r e dt oa ss i m t ) l e rl g m r e s ，i sp r e s e n t e dt h el a s tp a r ti st h ei l n n l c ii c a l 添加近似误差的重新启动的s i m p l e rg m r e s 算法 e 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 sa n dt h er e s u l t ss h o wt h a tt h e n e wv a r i a n th a sb e t t e rp e r f o r m a n c et h a nt h eo r i g i n a la l g o r i t h m k e yw o r d s ：s i m p l e rg m r e s ，k r y l o vs u b s p a c em e t h o d s ，l g m r e s 厦门大学学位论文原创性声明 兹呈交的学位论文，是本人在导师指导下独立完成的 研究成果。本人在论文写作中参考的其它个人或集体的研 究成果，均在文中以明确方式标明。本人依法享有和承担 由此论文而产生的权利和责任。 责任人( 签名) ： 易仍多年9 月2 石日 巷弛 厦门大学学位论文著作权使用声明 本人完全了解厦门大学有关保留、使用学位论文的规 定。厦门大学有权保留并向国家主管部门或其指定机构送 交论文的纸质版和电子版，有权将学位论文用于非赢利目 的的少量复制并允许论文进入学校图书馆被查阅，有权将 学位论文的内容编入有关数据库进行检索，有权将学位论 文的标题和摘要汇编出版。保密的学位论文在解密后适用 本规定。 本学位论文属于 1 、保密( ) ，在年解密后适用本授权书。 2 、不保密 ( 请在以上相应括号内打“ ”) 作者签名：撕 导师签名： 日期：驴勿年f 月彤日 日期：年月 日 鲞塑堕堡堡重箜重堑壁垫塑! ! 竺望丝堡塑堕墨选 第一节引言 科学与工程计算中的许多问题都要求求解大型稀疏线性方程组 a z = b 这里的a 酽”是个非奇异矩阵，z ，b r “为n 维向量大型稀疏矩阵问 题主要来源于椭圆型和抛物型偏微分方程的离散化，也产生于电路设计与计算机 分析，动力系统网络，化学工程处理，经济模型等领域 近年来，人们在求解大规模稀疏线性方程组时倾向于运用迭代方法，迭代解法 因此越来越受欢迎，使得近二十年来关于迭代方法的研究受到越来越多的重视 在众多的迭代方法中，比较受欢迎的是类k r y l o v 子空间方法：如广义极小残 量方法( g m r e s ) 1 5 ，b i c g 方法 1 2 】与q m r 方法【5 对于系数矩阵a 是非 对称矩阵时问题( 1 ) 的求解，最普遍采用的是g m r e s 方法g m r e s 常被称 为“最优”的方法，因为它在k r y l o v 子空间里寻找使相应的残向量2 一范数( 见 2 1 】， 2 2 ) 达到最小的最优解 但是，g m r e s 方法有这样一个弊端：随着子空间维数的增大，每次迭代正 交化过程所需代价显著增长因此出现g m r e s 方法个众所周知的变形：当 k r y l o v 子空间维数达到某个固定的m 时，重新启动g m r e s 算法 1 5 ，记为 g m r e s ( m ) 一般来说，所选取的参数i l l 相对于n 来说很小，使得存储与计算 量要求都较合理。然而选择一个合适的重启参数i t l 是困难的，因为m 的大小会 显著影响收敛速度( 见 6 【3 ) 由于每次重启时新的近似空间与前面产生的子空间的正交性失去了，重启一 般会减慢收敛速度最糟糕的是可能发生停滞现象，即一个重启循环结束后残量 范数没有减小( 或几乎不变) 于是人们提出了许多对标准的g m r e s 算法进行 改进的算法改进的算法主要包括两类：复合迭代方法( 见概港陛文献 1 1 ) 和加 添加近似误差的重新启动的s j 皿p j e rg m r e s 算法 2 速技术这里主要讨论加速技术到目前为止，一般说来加速技术保留或复制在 g m r e s ( m ) 重启时所丢弃的某些信息对一般力i i 速技术的概述性的文献见 4 添加方法( a n g m e n t e dm e t h o d s ) 是一类重要的加速技术这些方法试图改善g m r e s 的收敛，其实现途径是，在每个重启循环里添加某些信息到标准的k r y l o v 近似空间里1 2 1 通常所添加的信息是与a 的最小的几个特征值对应的近似不变 子空间 在近似空间里包含谱信息的添加方法，最先是由m o r g a n 提出的( 7 ， s d ，且 文献 2 】， 1 a 做了进一步的讨论这些方法有时被称为压缩技术，因为它们的目 标是要有效地”压缩”掉a 的那些影响收敛速度的特征值在【7 里， m o r - g a n 提出了添加近似特征向量的g m r e s 方法( g m r e s - e ) 在每个重启循环 里，g m r e s e 首先利用标准的a r n o l d i 过程产生个m 维的k r y l o v 子空 间。然后将k 个近似特征向量( 由前个循环求得) 添加到该k r y l o v 子空间里， 也就是说该循环里的近似空间为由标准的a r n o l d i 向量和近似特征向量所张成的 m + k 维子空间，新的近似解从这个近似空间里求得最后，通过r a y l e i g h - r i t z 过程( f 1o ) 求得下个循环里要使用的近似特征向量m o r g a n 还指出，即使 所添加的特征向量不是很精确，g m r e s - e 仍然能有效地改善收敛状况在后来 的文献 8 】中，m o r g a n 提出了一种与g m r e s e 数学上等价的更有效的算法 g m r e s i r ，它利用的是隐式重启的a r n o l d i 过程 1 6 】在 9 】里m o r g a n 又提出 了另一种等价的算法g m r e s d r ，它具有隐式重启的高效性，但实现更简单，且 不存在隐式重启的数值稳定性问题此外，文献2 1 给出了与g m r e s e 类似的 压缩方法，该方法基于f g m r e s 1 4 ( f g m r e s 是g m r e s 的一种变形，它允 许每次迭代里的预条件矩阵不相同) 上述的压缩技术的有效性依赖于矩阵a 的 性质，因此这些方法对于某些类型的问题更适用，例如，它们对于那些由小特征 值造成的收敛慢的问题很有效，但对高度非正规的矩阵效果不大 2 这些方法由 于要在每个循环里解个特征值问题，实际应用中代价比较高，但是m o r g a n 提 添加近似误差的重新启动的s i m p l e rg m r e s 算法 3 出的这种添加向量到近似空间的想法很有用处 理想情况下近似空间应该包含准确误差c ，使得迭代解= z o + c 为原方 程组的准确解f 4 因此，另外的类加速技术基于近似空间里包含近似误差的思 想，主要有g m r e s r ( g m r e sr e c u r s i v e ) 方法f 1 9 与g c r o 方法f 1 7 g m r e s r 是一种内外迭代方法，即内循环和外循环可以使用不同的迭代方法在 g m r e s r 里，外循环使用的是g c r ( g e n e r a l i z e dc o n j u g a t er e s i d u a l ) 方法，内 循环里用另一种迭代方法( 如g m r e s ) 求得a c = n 的近似解( n 为第i 步迭代 的残向量) ，作为外循环的搜索方向与g m r e s r 紧密相关的是g c r o 方法， 它的提出是为了克服g m r e s r 里内循环肯可能遇到的停滞问题为使存储要求 合理，大多数情况下两种方法里外循环近似空间都需要截断( t r u n c a t i o n ) 1 8 文献f 1 1 结合上述两类加黻术的思想，提出了种称为l g m r e s 的新的加 速技术具体说来，该方法采用了m o r g a n 的添加向量到标准的k r y l o v 子空间的 做法，而选择近似误差作为添加到k r y l o v 近似空间的向量该方法添加近似误差 到当前的近似空间中，而所添加的近似误差是前面重启循环里所得到的，因此不 同于添加近似特征向量，这里所添加的近似误差不需要额外的计算l g m r e s 方法的实现比较简单，仅需对标准的g m r e s 算法做小的改动该方法的出发点 是，作者在实验中观测到，利用重新启动的g m r e s 方法求解问题时，导致收敛 很慢的原因主要在于：每隔一个循环所得的残向量是几乎平行的l g m r e s 方 法的提出就是为了防止这种相间残向量交替方向的现象数值试验表明这是一种 有效的方法，它能有效地防止上述的交替现象，且对很多类型的问题都适用，能 大大加快g m r e s ( m ) 的收敛速度 在文献2 0 中，w a l k e r 与z h o u 提出了s i m p l e rg m r e s 算法它利用所谓 的s i m p l e ra r n o l d i 过程产生k r y l o v 子空间的一组基，使得最后的求解问题简化 为求解个上三角方程组的问题，因此它的实现代价比g m r e s 的要小本文的 主要工作是利用s i m p l e ra r n o l d i 过程来实现l g m r e s 算法，给出l g m r e s 算 添加近似误差的重新启动的s i m p l e rg m r e s 算法 4 法的一种代价更小的实现方式，即s i m p l e rl g r e m s 算法，这是因为在用s i m p l e r g m r e s 求解问题的过程中，同样存在着相间残向量交替方向的现象，从而影响 了收敛速度本文所给出的s i m p l e rl g m r e s 方法能防止这种交替现象，加快 s i m p l e rg r m e s 的收敛速度，且其计算量比l g m r e s 要小，因而耗时更少， 数值实验结果也表明改进后的算法效果比原来的要好 本文的其它内容安排如下：在第二节，我们给出一些必要的预备知识，简要地 描述一下g m r e s 算法和s i m p l e rg m r e s 算法第三节具体给出l g m r e s 算 法的主要思想，并用s i m p l e ra r n o l d i 过程来实现l g m r e s ，得到一种较小代价 的实现方式，同时讨论该算法些主要的性质最后一节是数值试验，对于许多 不同类型的问题进行测试，比较s i m p l e rl g m r e s 与s i m p l e rg m r e s ，s i m p l e r l g m r e s 与l g m r e s 的数值效果，体现本文所做的修改对于原来算法的改进 作用 查垄堕堡堡差塑重堑壁垫塑塑型! 堡丝曼望墨盗 5 第二节g m r e s 与s i m p l e rg m r e s 算法 这一节简要地描述一下g m r e s 与s i m p l e rg m r e s 算法，为后文的叙述作 铺垫，g m r e s 是求解大型非对称矩阵问题最常用的方法，而s i m p l e rg m r e s 则是与g m r e s 数学等价，但实现代价更小的方法 2 0 2 1g m r e s 方法 g m r e s 方法实现的方式是：在k r y l o v 子空间里找使得残向量的2 一范数达 到最小的最优解 设z o 为迭代初始向量，r o = b a 。o 为初始残向量， g m r e s 方法利用 a r n o l d i 算法构造k r y l o v 子空间蜀。( a ，r o ) = s p a n r o ，a r o ，a ”- 1 r o ) 的一 组标准正交基v 篇= 【口。， 。 这个过程产生如下关系式a 一+ ，研n ， 这里鼠。矗( r e + 1 ) 。”是上h e s s e n b e r g 矩阵 g m r e s 方法在k 。( a r 。) 里寻找d 。，使得近似解z = x o + 对应的残 向量r = b a 。范数最小令p = 1 1 ”1 | | ，注意到”- = r 0 l l r 0 1 l 及上述分解 a v t = v + l 噩。，有 b a x = b a ( x o + d 。) = b a ( x o 十9 ) = r o a v 。口= l 卜o i l l a 、厶 = 乞+ 1 ( 声e l 一秀。爹) ( e l = ( 1 ，0 ，一，o ) 丁只”) 而v 知+ 1 为正交阵，故 1 1 6 一a x l l 2 一1 1 p c l 一f ，。1 1 2 则g m r e s 方法所求近似解为= z o + 、，k 骱，其中为最小二乘问题怕e 一 y ) h z 的解 般的重新启动的g m r e s 方法描述如下 添加近似误差的重新启动的s i m p l e rg m r e s 算法 6 1 初始：选择精度e 和初始向量。o ，计算r o = b a x o ，卢= l i r o l l z 以及 v 1 = 珊川r o 恬选择k v g l o v 子空间的维数m 2 迭代； 如rj = 1 ：md o ： u = a 哟i ，0 r i = 1 ：jd o ： 凡j = ( v ，饥) i v 2 v 一， z e n d h j 十1 ，j = i i v l l 2 ； v j + i = v h j + l , j ； e n a 3 计算近似解：求使1 i p e 。一豆。洲2 达到最小的g 。，计算。= 。o + k 渤。 4 重启：计算残向量r 。= b a x ，。和相对残量范数 醚如果 滞茎e 则停机，否则令x c ，= x 。，转步骤 上述算法的具体实现细节可参考文献 1 5 _ 2 2 s i m p l e rg m r e s 当a r n o l d i 过程中取u 1 = a r o l i a r o l l 2 时，得n tg m r e s 算法的一种简单 形式，即s g m r e s ( s i m p l e rg m r e s ) 在这种情形下，a r n o l d i 过程产生k r y l o v 子空间j ( a ，v 1 ) = s p a n v 1 ，a v l ，a m - 1 v 1 ) 的一组标准正交基 l ，v 2 ， 。) 每次迭代结束后，如果z 。一t 不是( 1 ) 的准确解，则子空间k 。( 4 ，”1 ) = a ( k 。( a ，伯) ) 鲞丛塑堡差塑里堑生垫箜! 垫! 旦丝鱼坚璺堕墨渣 7 的维数为m 2 0 s g m r e s 算法描述如下： 算法2 s i m p l e r j 初始化：给定 g m r e s x o 和精度e 计算r = b a x o 与p o = i r l l 2 若p o 1 ，则令p i k = 谚v k ，更新v k = 讥一p i k v i ，i = 1 ：k 一1 ( p 1 1 ) ) ( 氛p ) ) 若p 伽se 转步骤3 数 ( i i i ) 令x z + p o z 一叫若p p o e ，则z 达到精度，退出；否则，令r = ( r 一k v k ) p p n = p p o p = 1 ，转步骤2 口= 添加近似误差的重新启动的s i m p l e rg m r e s 算法 8 上述s g m r e s 算法的具体实现细节可参考文献f 2 0 】 在s g m r e s 算法中，产生了分解a r ow m 一1 = 兄。，这里的r 。为一 mx ， 的上三角矩阵( 注意到g m r e s 方法里相应的是上h e s s e n b e r g 阵) - 于 是最后要求解的问题由原来的上h e s s e n b e r g 阵的最小二乘问题简化为个上三 角方程组的求解，并且般说来所需代价变小了 添加近似误差的重新启动的s i m p l e rg m r e s 算法 9 第三节l g m r e s 与s i m p l e rl g m r e s 文献1 1 提出了一种称为l g m r e s 的新方法来加快重新启动的g m r e s 方 法的收敛速度文献 1 】的作者观察到，在重新启动的g m r e s 方法实现的过程 中，每隔个循环所得的残向量( 即相间残向量) 经常交替方向，因而减慢了收敛 速度s g m r e s 方法也出现同样的现象，在这一节里我们将用s i m p l e ra m o m i 过程来实现l g m r e s ，得到l g m r e s 的一种代价更小的实现方式 3 1出发点 考虑重新启动的s g m r e s 方法我们称相邻的两次重启之间的m 次迭代 为个循环重启次数用下标来表示：q 表示经i 个循环或m i 次迭代后所 得残向量第i + 1 个循环结束后所得残向量与前一个循环结束所得残向量满足 关系7 州一p 嚣1 ( a ) _ ，这里p 髯1 ( a ) 为关于a 的m 次多项式在每个i + 1 循 环里，s g m r e s ( m ) 寻找孔+ 1 z ；+ k 。( a n ) ，使得7 州上a k 。( a ，r 。) = k m ( a u 1 ) ( 1 j 1 = a n 川a n l | 2 ) 2 0 引言中已提到，g m r e s ( m ) ( s g m r e s ( m ) ) 不能保持连续重启产生的近似 空间之间的正交j 陛，导致收敛很慢以至发生停滞现象在收敛慢的情形下，与g m - r e s ( n ( ) 里一样，对于s g m r e s ( m ) 也存在着相间的残向量之间几乎平行的现 象换句话说，r 州与一1 之间夹角很小，n + - z “n1 ( n 为一标量) 我们 称相间残向量之闯的夹角为s k i pa n g l e s ，如么( 咒+ 1 ，一1 ) ；称相邻残向量间夹角 为s e q u e n t i a la n g l e s 对于许多问题，我们发现s k i pa n g l e s 相对较小，即使是当s e q u e n t i a la i l g l e s 为合理大小时( 亦即没有发生停滞) 对于s g m r e s ( m ) 我们测试了文献1 中 的相同的四个例子f 可从m a t r i xm a r k e tc o l l e c t i o n 获得) t a b l e1 列出了收敛 ( 忱1 1 2 l l r o i 。51 0 - 9 ) 时所需的外循环迭代次数( 重启次数) ，s e q u e n t i a la n g l e s 添加近似误差的重新启动的s i m p l e rg m r e s 算法 1 0 与s k i pa n g l e s 小的s k i pa n g l e s 启示着我们，如果与前面近似空间的正交性能 某种程度地保持下来，收敛速度应该会得到改善 t a b l eh 运行s g m r e s ( 3 0 ) 所得结果对每个问题列出了问题规模，迭代重启次 数( 忱| 1 2 川r o i l 2 茎1 0 _ 9 ) ，s k i pa n g l e 与s e q u e n t i a la n g l e p r o b l e m s i z e ( n ) c y c l e s l ( r i ，r i 一1 ) ( n + 1 ，n i ) a d d 2 02 3 9 52 84 9 9 711 6 o r s l r r l1 0 3 01 8 8 1 9 4 5 4 7 9 o r s r e g l 2 2 0 52 66 0 9 51 2 9 7 s h e r m a n l1 0 0 09 5 2 7 3 2 0 1 2 l g m r e s 方法的出发点是希望防止在g m r e s ( m ) 里出现的残向量交替方 向的现象，这种交替行为造成了连续重启循环里的重复信息假设圣为线性方程 组( 1 ) 的准确解g m r e s ( m ) 第i 个循环后的误差表示为e 。，即 如果当前近似空间里包含了准确误差e 。，即2 = 甄+ e 。，那么就解决了这个问 题定义磊= 一一1 为g m r e s ( m ) 里第i 个循环后的近似误差，且当j 1 时。，；0 选择近似误差作为添加到下一个近似空间k 。( a ，。) 的向量注意到 五五。( a ，r ) ，因此近似误差毛在某种意义下代表了前一个循环里产生并且 随后即被抛弃的近似空间k 。( a ，n 一。) ，自然选择讫作为添加到下个近似空 间正。( a ，n ) 的向量 般地，可以添加前k 个近似误差到下个近似空间里用l g m r e s ( m ，k ) 表示添加前k 个近似误差到标准的k r y l o v 子空间里因此，在第i + 1 个循环 查塑垫堡堡重箜重堑壁垫箜堕型竺堡丝曼堕墨墨 1 1 最后，l g m r e s ( m ，k ) 求得( 1 ) 的近似解可表示为： 0 x i + 1 = z 。+ 哑m + - 1 1 ( 4 ) n + c t i j ( 3 ) ，二z - k + l 这里多项式虢m + - 1 1 与。玎的选取应使得忆+ ，| | 。达到最小注意= 0 相应于标 准的g m r e s ( m ) 由于s i m p l e rg m r e s ( m ) 比g m r e s ( m ) 实现代价要小，且前面已经提到， 对于s i m p l e rg m r e s ( m ) 存在着类似的交替现象，我们给出l g m r e s 的一种 简单实现形式，称为s i m p l e rl g m r e s 为描述s i m p l e rl g m r e s 算法，首先 给出经添加的简单a r n o l d i 过程 3 2 算法与性质 近似空间维数设为m 假设第i + 1 个循环里，添加前k 个近似误差磊，z i 吨 ，z i k + l 到k r y l o v 子空间k 。( a ，n ) 里定义z k = b 商一h 一，魂一k + 1 】为 方便起见，经添加后的简单a r n o l d i 过程记为s - a r n o l d i ( m k ，k ) s - a r n o l d i ( m - k , k ) 算法描述如下： 算法3 经添加的简单a r n o l d i 算法( s - a r n o l d i ( m - k ，k ) ) j 初始；输入a 个近似误差z k ，m 与令磊= a 乙，计算 1 = a r 1 1z 怯v l = v l r 1 1 2 迭代： f o r j = 2 ：m 俐若j m 一，v j = a v j1 ；否则v j = z i - ( j 一。+ k 一1 ) 甜f o rk = 1 ：j 1 r k i = 吗v k ，u3 = v j r k j v k r d j = l i ”j l h ，= v j 而j 添加近似误差的重新启动的s i m p l e rg m r e s 算法 1 2 只输出：若女= 0 ，= h 一， ，否则k = r i 一k 一1 玩 上述算法产生如下分解 r鬟+1)=r。一”，”zr”。差三 r 铲1 + 凳1 白 ( ，岛：，) 丁那么就能得到递推关系式r 黔1 r 齄：一”。于是就能利用如下关系式递推计算残向量范数 r l 。：而瓣而戛：懈j ) | | 2 s 州c o s _ ( 6 。i i r 垃) ( 5 ) 根据最小残量准则 1 2 ，有 b a x i + 1j _ a j o ( a ，r i ) = k ( 4 ，v 1 )( 6 ) 令鼢+ 1 = 甄+ ，k 为修正量则v z ( b a ( x 。+ a m ) ) = 0 ，或进一步得到 = 嵋n = 蠕a s , ，；= 嵋a y m 9 = 9 令口= 崭u 。= ( 町1 1 q 2 ，) t 西巧；螺 ，。一 = h峨 里 则 这 添加近似误差的重新启动的s i m p l e rg ! v l r e s 算法 1 3 则修正量= y 口可表示为 西憾：二羔盈 i ff = l i f1 f 茎t i t k 一，z i 十m k f + 1 ) 巍i f 1 , 一k 2 ”l 啦j 一岛，修正量又可表示为 i ff = 1 i f1 l t r z k 口，r ：1 + 兰一1 ( 啦+ + 卵1 岛) + 十 二笛一k ( m y 5 + 协+ l 盈一( j 一。+ ) ) i f m 基于上述经添加的简单a r n o l d i 过程，现在我们可以给出 算法： ( 8 ) k 2 茎m s i m p l e rl g m r e s 假定已获得k 个近似误差z k = 【磊，孟一，z i 一女+ 1 和第i 个循环结束后所 得残向量第i + 1 个循环描述如下： 算法4 s i m p l e rl g m r e s 的第i + 1 个循环 1 将况，n 应用于经添加的简单a r n o l d i 过程，产生y 麓，v 。，；在简 单a r n o l d i 算法的正交化过程中求得o 。= 4 1 , 2 ，f 。 r 与r 鼢1 ) = r i - 。，即对每个j ，在第j 个正交化步骤里求白= 丐t ，( i 一+ ，1 与一州= t 冒一岛码，并执行更新p = p s i n ( c o s 一1 ( 岛) p ) 如果p p o 茎e ，转下一 步 2 形成近似解；求口= 麻1 0 。与x + 1 = x 。+ p o 0 = x i + p o ，这里 由( 8 ) 式给出 3 判断是否需要重启若p p o 墨e ，z 州达到精度，退出；否则令p o = p p 。 ，7 j 十l = r 弦1 p 0 更新玩= 眩+ 1 ，五，z ik + 2 】，这里筋+ 1 = 6 。令 p = 1 ，i = i + 1 转步骤j 丐白 口 十 w h 闸 卜 n 档 m m 添加近似误差的重新启动的s i m p l e rg m r e s 算法 1 4 注意当i 茎时，第i 个循环开始时仅有i 1 个近似误差，这是因为z j = o ( j 1 ) 因此当j 1 时，用a r n o l d i 向量代替刁，使得每个循环里近似空 间都为m 维换句话说，s i m p l e rl g m r e s ( m - k 、k ) 的第一个循环( i = 1 ) 与 s g m r e s ( m ) 的第个循环等价 前面提到过，( s i m p l e r ) l g m r e s 被设计着用来防止相间残向量交替方向 的现象现在就来比较s g i v i r e s ( m ) 与s i m p l e rl g m r e s ( m ，k ) 算法里的s k i p a n g l e s 与s e q u e n t i a l & n g l e 8 此时有与文献 1 】中相同的结论，k i i e 明过程是类 似的这里从s i m p l e rl g m r e s 的角度给出主要的结果 定理1 1 】( s e q u e n t i a la n g l e s ) 设s g m r e s 算法第i + 1 和第i 个循环所 得残向量分别为r 一与n 则残向量之间的夹角满足关系 c o s z ( f i + l ， f i ) 2 糕 ( 9 ) 注意匕述结论对g m r e s ( m ) 与( s i m p l e r ) l g m r e s ( m ，k ) 均成立该定理 表明收敛速度与相邻残向量之间夹角大小有关如果相邻残向量几乎正交，则收 敛就快如果能求得个残向量+ i 使得r 。上n ，那么就求出了准确解 下面的结论对g m r e s ( m ) 与s g m r e s ( m ) 均成立 定理2 1 1 1 ( s k i pa n g l e s ) 设s g m r e s 算法第i + 1 和第i 一1 个循环所得 残向量分别为r m 与，一则残向量之间的夹角满足关系 c o s 么( r i + i ，z i - 1 ) = 觥一畿( 1 0 ) 这里r 1 = n a 也+ 1 ，n = r 。一1 一a 6 。 上述结论对于分析收敛性没有直接的帮助下面在给出s i m p l e rl g m r e s 的 相应结论后，我们再来看它所给出的暗示作用 定理3 ( s k i pa n g l e s ) 设s i m p l e rl g m r e s ( m ，k ) 算法第i + 1 和第i 一1 墨垄丝! ! 堡耋塑重堕星垫塑! 塑里生鱼丝里望墨姿 1 5 个循环所得残向量分别为r 与r 一，则残向量之间的夹角满足关系 c o s 么( r i + l , r i - 1 ) = ( 1 1 ) 证明：证明过程与文献 1 】中t h e o r e m6 类似不同之处在于当前近似k r y l o v 空间为 s 2 = j ( a ，n ) us p 血几 勺) j = “一+ 1 ) 。 这里的匠。( a ，n ) 为s p a n r 。， 1 ， 2 ，一1 ) ，替代了原来的 墨。( 4 ，r ) = s p a n v 1 ，啦， 。 口 这个结论表明，对于s i m p l e rl g m r e s ，收敛也与s k i pa n g l e s 有关收 敛快意味着s k i pa n g l e s 大当用s g m r e s ( m ) 求解个问题时如果残向量发 生交替方向的现象，那么n 一。与n + 。之间的夹角就很小在这种情形下，因为 j 4 也+ 1 = r i - r l _ 1 ，| 4 文= n 一1 一n ，故定理2 中( a 瓯+ 1 1 a 瓯) 这一项是负的我们 在数值试验中验证了这一点由于在s i m p l e rl g m r e s 算法中第i + 1 个循环里 添加了前面若干个近似误差到当前的近似空间中，因此这样构造后( a 文，a 也一1 ) 项变为0 下面的数值试验部分表明，s i m p l e rl g m r e s 的这种添加机制所产生 的s k i pa n g l e s 往往比s g m r e s ( m ) 大，并且能有效防止在重新启动的s g m r e s 里出现的交替现象，从而船陕s g m r e s 的收敛速度 添加近似误差的重新启动的s i m p l e rg m r e s 算法 1 6 第四节数值实验 这一部分给出在m a t l a b7 0 里得到的数值实验结果所有的数值测试是在一 个操作系统为w i n d o w sx p ，c p u 为i n t e l ( r ) c e l e r o n ( r ) 2 6 6 g h z ，主存为 2 5 6 m b ，机器精度为e p s = 2 2 2 1 0 _ 1 6 的机器匕进行的我们将l g m r e s ( m k ，k ) 与s g m r e s ( m ) 进行比较来看加速效果，同时也将s i m p l e rl g m r e s 同 l g m r e s 进行比较来看改善效果 这一部分的1 0 个测试问题均来自于m a t r i xm a r k e tc o l l e c t i o n 这些问题 包含以如下名字命名的矩阵： a d d 2 0 ，o r s i r r l ，o r s r e g l ，s h e r m a a l l ，s h e r m a n 4 ， c a v i t y 0 5 ，c a v i t y l 0 ，c d d e l ，e 0 5 r 0 0 0 0a n dn o s 3 所有的例子中，通过设定准确解 为分量全是1 的向量来构造出右端项迭代初始向量为零向量所有的例子当中， 近似空间维数全设为m = 3 0 在所有的表格当中，s i z e ( n ) 代表所测试矩阵的阶 数，i t e r 代表重新启动次数，n l v 代表矩阵一向量乘法的次数，t i m e 代表求解问题 所耗的c p u 运行时间( 以秒为单位衡量) 停机准则设定为l e 。9 ( 1 l r 。1 1 2 l l o l l = 曼 1 0 - 9 ) 最大的外循环重启次数设定为3 0 0 ，符号一表示经3 0 0 次重启( 外层迭 代)