（计算数学专业论文）多项式预处理cmrh方法.pdf

多项式预处理c m r i - i 方法 摘要 本文研究求解大型稀疏非对称线性方程组的c m r h 算法，主要的创新工作是提 出了多项式预处理的c m r h 算法，在本文中，我们把它称之为p c m r h 算法 求解大型稀疏非对称的线陛方程组有很多方法k r y l o v 子空间算法如g m r e s ， q m a ，c m r h 等，是求解此类问题其中的一类非常有效的方法c m r h 方法利用 h e s s e n b e r g 过程构造k r y l o v 子空间的组基，相对于g m r e s 方法而言，具有所需 的存储量较少等优点但和g m r e s 方法一样，c m r h 方法在解方程组时，可能 发生停滞为了克服c m r h 方法解线性系统a x = b 过程中可能出现的收敛缓慢或 不收敛，本文利用c m r h 本身构造出一种有效的多项式预处理因子m ( z ) 数值实 验表明；该多项式预处理因子非常简单且易于实现，p c m r h 算法可取得比c m r h 算法更有效的收敛 本文分为以下四章：第一章主要介绍相关的问题背景，并概述本文的主要内容 第二章简要地描述了g m r e s 算法和c m r h 算法在第三章，我们具体给出多项式 预处理c m r h 算法的主要思想，并给出具体的实现过程最后一章是数值试验，我们 对许多不同类型的问题进行测试，来体现本文所给出的p c m r h 算法对原来c m r h 算法的改进。 关键词：多项式预处理； c m r h 。 多项式预处理c m r h 方法 a b s t r a c t l v i nt h i sp a p e rt h ec m r hm e t h o df o rs o l v i n gl a r g ea n ds p a r s e ，n o n s y m m e t r i c l i n e a rs y s t e m si ss t u d i e d ，ap o l y n o m i a lp r e c o n d i t i o n e rf o rt h ec m r ha l g o r i t h m i sg i v e n ，a n dt h en e wm e t h o di sc a l l e dt h ep c m r hm e t h o di nt h i sp a p e r t h e r ee x i s tal o to fm e t h o d sf o rs o l v i n gt h en o n s y m m e t r i cl i n e a rs y s t e m s t h ek r y l o vt y p em e t h o ds u c ha sg m r e s ，q m r ，c m r hi so n eo ft h em o s t p o p u l a ra l g o r i t h m s c m r hu s e st h eh e s s e n b e r gp r o c e s st oc o n s t r u c tak r y l o v b a s i s c o m p a r et ot h eg m r e sm e t h o d s ，c m r hi sl e s se x p e n s i v ea n dr e q u i r e s s l i g h t l yl e s ss t o r a g e b u tl i k eg m r e s ，t h er e s t a r tc m r hm e t h o dm a yn o t c o n v e r g eo rb es t a t i o n a r y i no r d e rt or e m e d yt h i sd i f f i c u l t y , t h i sp a p e rg i v e sa p o l y n o m i a lp r e c o n d i t i o n e rf o rc m r hb a s e da l g o r i t h m t h er e s u l t so fn u m e r i c a l e x p e r i m e n t ss h o wt h a tt h ep o l y n o m i a lp r e c o n d i t i o n e ri sq u i t es i m p l ea n de a s yt o b ei m p l e m e n t e da n dp c m r hc a na c h i e v ec o n v e r g e n c em o r ee f f i c i e n t l yt h a nt h e c m r h 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 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 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 sa n dc m r hm e t h o d i nt h e t h i r dp a r t ，t h em a i ni d e ao fp c m r hi si n t r o d u c e d t h el a s tp a r ti st h en 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 tt h en e wa l g o r i t h m h 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 ：p o l y n o m i a lp r e c o n d i t i o n e r ，c m r h 厦门大学学位论文原创性声明 兹呈交的学位论文，是本人在导师指导下独立完成的研 究成果。本人在论文写作中参考的其它个人或集体的研究成 果，均在文中以明确方式标明。本人依法享有和承担由此论 文而产生的权利和责任。 责任人( 签名) 奇也叶 2 叩8 年等月孑d 日 厦门大学学位论文著作权使用声明 本人完全了解厦门大学有关保留、使用学位论文的规定。 厦门大学有权保留并向国家主管部门或其指定机构送交论文 的纸质版和电子版，有权将学位论文用于非赢利目的的少量 复制并允许论文进入学校图书馆被查阅，有权将学位论文的 内容编入有关数据库进行检索，有权将学位论文的标题和摘 要汇编出版。保密的学位论文在解密后适用本规定。 本学位论文属于 l 、保密() ，在年解密后适用本授权书。 2 、不保密( 也 ( 请在以上相应括号内打” ”) 作者签名：请伍计 日期：夕叩g 年乡月, 3 0e l 导师签名：7 舭吻嗍矽矽p 讣月乡秒日 j 第一章引言 第一章引言 在应用学科与工程领域中，如结构设计、油气资源探测、数值天气预 报、数值风洞等，常利用偏微分方程作为数学模型，再利用有限元或有限 差分等方法对偏微分方程进行离散化，得到如下形式的，大型稀疏的线性 方程组 a x = b ( 1 1 ) 这里的a 舻n 是个非奇异矩阵，z ，b 形为n 维向量。求解这类大型 稀疏的方程组通常可以运用迭代法。在众多的迭代方法中，比较受欢迎的 是一类k r y l o v 子空间方法( 也被称作多项式方法) 。如：g m r e s ( m ) ( 见 ( 2 】) ，q m r ( 见c 3 】) ，f o m ，c m r h ( m ) ( 见( 1 】) 等它们都是基于最小残 差法 z 。= x o + g n 一1 ( a ) r o( 1 2 ) 其中r 0 = b a x o 为初始残量， q n l ( z ) 为多项式且d e gq n 一1 几一1 使得 忆i l 最小，或 z 九x 0 + 虬t o ，a ) ，a r 。上( r o ，a )( 1 3 ) = b a z 。表示残差，( a ) = s p a n a 3 r o ) 哥是相关的k r y l o v 空间。 其中z 。满足一定的准则，不同的方法对应不同的准则，g m r e s 求得z 。 满足残量极小化的准则，q m r ，c m r h 满足拟残量极小化准则，f o m 方 法使残量满足g a j e r k i n 条件。令m ( z ) = 1 一z q n 一。z ) ，此即为残差多项式， 于是r 。= p n ( a ) r o g m r e s 方法是利用a r n o l d i 过程构造k r y l o v 子空间的一组基，q m r 则是利用l a n c z o s 算法去构造k r y l o v 子空间的一组基，而c m r h 方法则 利用h e s s e n b e r g 过程构造k r y l o v 子空间的一组基，然后在k r y l o v 子空间 上进行迭代的，但其存储量和正交化工作量会随着迭代次数的增加而变得 不可接受，所以要对其进行重启，即c m r h ( m ) 方法。可是c m r h ( m ) 方 法会失去超线性收敛性，产生停滞，这与g m r e s ( m ) 方法都相似，而对 于g m r e s ( m ) 方法，m b v a ng i j z e n 等在文( 见f 4 ，5 ，1 0 ，1 1 ，1 2 】) 等文章中，对其采用了多项式预处理的方法，主要问题就是找到有效的低 第一章引言 2 阶多项式p 。( z ) ，于是迭代解就能被应用到式( a ) a x = p n ( a ) 6 中，这会产 生一个k r y l o v 子空间 k ”( p 。( a ) a ，7 o ) = s p a n r o ，p 。( a ) a r o ，( p 。( a ) a ) m - i r o ) 它是k r y l o v 子空间k ( n + ) ( m - 1 ) + 1 ( a ，伯) 的子空间这种方法在处理内积计 算量很大时很有效。将这种思想用于g m r e s ( m ) 中，效果不错( 见【1 6 】) 。 因此本文将这种思想也运用到c m r h ( m ) 方法中，直接利用c m r h 本身 构造预处理多项式多项式预处理和混合迭代法( 见【6 ，9 ，1 0 ，1 3 ， 1 4 ，1 5 】) 极为相似，其主要思想是要减少迭代的次数。随着迭代次数的 降低，存储量就会减少，运算量也会降低 本文的其它内容安排如下：在第二章，我们给出一些必要的预备知识， 简要地描述一下g m r e s 算法和c m r h 算法；第三章具体给出p c m r h 算 法的主要思想以及预处理多项式的构造，并用过程来实现；最后一章是数 值试验，对于许多不同类型的问题进行测试，比较c m r h 算法与p c m r h 算法的数值效果，体现本文所做的修改对于原来算法的改进作用 第二章g m r e s 与c m r h 算法3 第二章g m r e s 与c m r h 算法 这一章简要地描述一下g m r e s 与c m r h 算法，为后文的叙述作铺 垫。g m r e s 算法是求解大型非对称矩阵问题最常用的方法，而c m r h 算法仅在构造k r y l o v 子空间的一组基所采用的方法与其有异，c m r h 算 法相对而言所需存储量更少，实现代价较低( 见【1 】) 。 2 1g m r e s 算法 g m r e s 方法实现的方式是在k r y l o v 子空间里找使得残向量的2 一范 数达到最小的最优解。 设x 。为迭代初始向量，7 ，o = b a x o 为初始残向量，g m r e s 方法 利用a r n o l d i 算法构造k r y l o v 子空间( a ，伯) = s p a n r o ，a r o ，a m l7 o ) 的一组标准正交基= ，v 。】。这个过程产生如下关系式a = 坛+ l 丢- m ，这里再r ( m + 1 ) m 是上h e s s e n b e r g 矩阵。 g m r e s 方法在( a ，咱) 里找寻h ，使得近似解z = x o + 5 m 对应的 残向量r = b a x 范数最小令卢= 忆注意到v t = r 0 l i r 。i i 及上述分 解a = + l 万。，有 b a x = b a ( x o + 5 m ) = b a ( x o + y ) = r o a v m y = i i r o l l u l 一a v r n y = + l ( z e l h 。y )( e l = ( 1 ，0 ，0 ，o ) 1 r , n ) 而+ 。为正交阵，故 | 6 一a z l t 2 = l j p e l h 。芗4 2 则g m r e s 方法所求近似解为z = z o + ，其中y m 为最小二乘问题 f 恤。一玩芗| | 的解。 现给出g m r e s ( m ) 算法 算法1 重新启动的g m r e s ( m ) 算法 1 初始：选择精度和初始向量黝，计算r o = b a x 。，p = 怖i l 。 以及v 1 = r 0 川r o i l 2 选择k r y l o v 子空间的维数m 。 第二章g a ，i r e s 与c m r h 算法4 2 迭代： ，d rj = 1 ：m d o ： v = a v j ； f o ri = 1 ：歹d o ： h o = ( v ，v d ； ”= 一h i j v i ； e n d h j + l ，j = i i v l l 2 ； v 3 + x = v h j + l ，j ； e n d 3 计算近似解：求使 j 肛，一z m j i ：达到最小的y m ，计算z 。= x 。+ 4 重启：计算残向量= b - a x 。和相对残量范数必i r o l l 如果必l ib o i l 则停机，否则令黝= 。，转步骤1 上述算法的具体实现细节可参考文献( 见 1 】) 2 2c m r h 算法 c m r h 方法的主要思想是利用h e s s e n b e r g 过程构造k r y l o v 子空间( a ) 的一组基l = ( f ”k ) ，在该过程中产生一上h e s s e n b e r g 矩阵，记为 z 瓦兄( + 1 ) 姚，其中a 玖= l k 瓦，( 见【1 j ) ；然后在k r y l o v 子空间上找一向 量，使其极小化 k r a 。i ( n a i r 0 ) ) t b - a ( z 。+ 磊) i = ：。k r a 。i ( n ，4 ，珈) 强一a z i t ( a ，r o ) 可以写为z n = l 。y n ，于是有 r a i ，n 、i i b a ( x o + ) i i = m ，i 。n | i 伯一a l 。i | z n e k 。( a ，r 0 ) 。 枷r r 。” “ = r a ，i 。n 怖一厶+ 1 玩u 1 i y n 心 = m i 婴i r o l l e i 一日。v - i l 如 ( 2 1 ) ( 2 2 ) 第二章g m r e s 与c m r h 算法 现给出c m r h ( m ) 算法 算法2 重新启动的c m r h ( m ) 算法 输入：k r y l o v 子空间维数m ，近似解精度 2 3 0 = 0 ，r o = b a z o ，令p ( i ) = i ，i = 1 ，扎 确定i o ，使得i ( r o ) l , 。= i i r o l l ；l t = 彘； p ( 1 ) 一p ( i o ) ( 表示互换p ( 1 ) 与p ( i o ) 的值) 迭代至近似解精度： 对k = 1 ，m 做 u = a i k 对j = 1 ，k 做 c = u p u ) ；h i 。k = c ；0 ) = 0 对f = j + 1 ，n 做 u p ( z ) = u p ( 1 ) 一c ( 1 j ) p ( f ) 如果k _ 佗 确定i o ，使得i ( 札o ) i i 。= i l u o 怯；p ( 忌+ 1 ) 一p ( i o ) h k + l ，南2 锃幻；l k + i2 赢 估计i i b a x k i ，如果其很小或者k = r t ，则求y 七 使得l i 万t y 一( r 。) i 。e ；+ 1i i 最小 巩= z o + l k y k ，停止迭代 z m = x 0 + l 。，y m 使得i i h , y 一( t o ) t 。e m + 1 i i 最小 2 7 。：= z 。重新迭代 5 第三章多项式预处理的c m r h 算法 6 第三章多项式预处理的c m r h 算法 迭代法有存储空间小，程序简单等特点，所以是解大型线性方程组( 特 别是稀疏矩阵情形) 的有效方法，它的收敛性和收敛速度是使用的关键问 题，不收敛的格式当然不能使用，收敛很慢的格式也使人力和机时浪费， 而且还不一定能算出结果。预处理的目的就在于改善收敛性。 3 1 出发点 所谓的多项式预处理，是指取m 满足 m 一1 = 4 a 、 其中s ( z ) 是个多项式( 一般是低次的) ，原方程组经预处理后成为 s ( a ) a x = s ( a ) b 然后用相应方法求解。 实际上也不必把s ( a ) 或a s ( a ) 计算出来，因为a s ( a ) u 可以由系列的 矩阵与向量乘积得到。 我们讨论某种意义下为最优的多项式s ( z ) 的选择，就是希望s ( a ) a 在 某种意义下尽可能接近单位阵，例如，使s ( a ) a 的谱尽可能接近单位阵的 谱，记a 的谱为仃( a ) ，次数不超过七的多项式空间为巩我们可以想 象在玩中寻找多项式s ( z ) ，使得m a xf 1 一a s ( 划最小但这要求知道a 的所有特征值，所以是不现实的通常我们提出这样的问题： 求 s ( x ) 风 使得 m 、一a x l l 一a s ( a ) i a e 、“ 达到最小。 e 可以取为个包含a 的特征值的区间【o t 纠，且有0 q p 第三章多项式预处理的c m r h 算法 7 其中g 是上三角矩阵g ：( 鼍1 ：三j ) 因为厶+ 。：+ ，g 仙 t 改f n + 1 = j + 1 ( c 1 ，n + 1 ，c 2 ，佗+ 1 ，c t l + 1 ，n + 1 ) t 厶h = 玩c n h 。 一册。，) 第三章多项式预处理的c m r h 算法 再由( 3 2 ) 得 而 a k = a 尺，n ( ) - - - - ( a r o a 2 r o 肿o ，c l n ，) 一0 二) k+=二。，。_+(妻一(噤“) l n + - = + ，g + t ，故z 。+ = 丘_ + - ( 二! 二。) 关，进行比较即得 ( 3 4 ) 因为珞+ 。的列线性无 (耋i蔓。)=。，。(妻)一九善，n(譬“) 再根据c m r h 方法解h e s s e n b e r g 矩阵最i j 、- - 乘问题，得 z n = x 0 + l n y ( 3 5 ) 8 第三章兰堕壅塑壁墨箜婴里簦盔 9 一一 一 一 一一 一一 因为l 。y ：k 。g 可，可得出向量g 可即为多项式q n 一( z ) 的系数 g 可= ( q o o l r 。- 1 ) t 一l ( z ) = c t o + ( 1 】z + - ，+ ( t n - 1 7 5 ”一1 ( 3 ，6 ) m ( 名) ：1 一z q n 一。( z ) 即为残差多项式，因此可得q n 一- ( 彳) = b 笋，令k = t t - - 1 ，此即得出鲰( a ) a 一1 ( 见【6 ) ，所以可用口七( a ) 作为预处理多项式。 3 3 算法 现给出c m r h ( m ) 算法 算法3 重新启动的p c m r h ( m ) 算法 输入：k r y l o v 子空间维数m ，近似解精度，预处理多项式黜次数 令幻= ( 三i ) ，q = ( 毫1i：茎：) 第三章多项式预处理的c m r h 算法 计算 (薹二。=再。，j(主：一二幻(髻 形成近似解x k = x o + l k y k ，其中y “ 算出预处理多项式叭( z ) c 最小化r ( y ) = i l 玩y 一( ) t 。e 1 c y k = ( q o o e k - 1 ) t q k 知) = q o + q l z + + o z k 一1 z 哥一1 2 对q k k ( a ) a x = q k k ( a ) 6 用循环c m r h ( m ) 算法 1 0 第四章数值实验 第四章数值实验 下面我们在a m da t h l o n ( t m ) 6 4x 2d u a lc o r ep r o c e s s o r2 2 0 g h z ，内存 1 5 g 的计算机上使用m a t l a b 6 5 进行数值实验。本章给出3 个数值例子来 比较c m r h ( m ) 和p c m r h ( m ) 的执行结果。以下的数值试验中我们取初 始向量x o = ( 0 ，0 ，o ) 丁，右端向量b = a ( 1 ，1 ，1 ) 丁，m = 2 0 。 在以下图中，实线( 一) 表示c m r h ( m ) 方法，点划线( - ) 表示p c m r h ( m ) 方法。由于k r y l o v 子空间的维数都取为2 0 ，则比较迭代步数与比较重 启次数没多大区别，因此在这里，横坐标表示重启次数，纵坐标表示残量 ( n 卯m ( r ) ) 的大小 例1 ：我们选取的这个矩阵来源于b r o w n 7 1 a = 1 、 i i - 1e1 l l 一1 e 在图1 我们取e = o 1 ，n = 4 0 ，预处理多项式次数七= 2 0 ；而图 2 我们取= o ，0 1 ，r t ：4 0 ，预处理多顼式次数抽= 2 0 ；表1 中我们取 = o 0 1 ，佗= 1 0 0 ，预处理多项式次数七七取从1 2 0 的值。把相对残量 n o r m ( r ) n o r m ( b ) 控制在1 0 - 1 0 附近。 从图1 、图2 中可以看到p c m r h ( m ) 的收敛速度非常快。当e = o 1 ， n = 4 0 时，c m r h ( 2 0 ) 需重启1 0 7 次才达到9 2 9 2 5 e - 0 11 ，而p c m r h ( 2 0 ) 只需重启3 次就达到1 1 1 4 3 e 一0 1 1 当= 0 0 1 ，n = 4 0 时，c m r h ( 2 0 ) 需重启8 4 0 次才达到9 0 0 7 5 e 0 1 1 ，而p c m r h ( 2 0 ) 只需重启6 次就达到 4 , 4 7 7 1 e - 0 11 可见做预处理的效果很明显。 表1 给出了预处理多项式的次数k k 取1 - 2 0 时，p c m r h ( 2 0 ) 方法所 需的重启次数，求解时间，相关残差范数以及收敛性的变化从表中可以 看出，除k k = 1 时，p c m r h ( 2 0 ) 方法不收敛外，取其余值时p c m r h ( 2 0 ) 都收敛。当岛后= 1 9 时重启次数和求解时间都达到最小值。 1 e 1 一 第四章数值实验 图17 = 0 1 ，n = 4 0 图2 7e = 0 0 1 ，佗= 4 0 1 2 第四章数值实验 1 3 预处理多项式次数后七重启次数求解时间( 秒)残差范数收敛性 1 1 0 0 02 7 5 0 00 0 0 1 1 不收敛 21 7 1 0 4 6 9 09 4 2 9 9 e 一1 l 收敛 32 8 9 0 7 8 1 09 4 5 9 6 e 一1 1 收敛 41 7 70 4 8 4 09 9 3 3 8 e 一1 1 收敛 52 3 60 6 5 6 09 6 9 6 0 伊1 1 收敛 65 00 1 2 5 09 6 9 8 8 e 一11 收敛 7 7 2 0 2 0 3 06 8 8 9 0 e 11收敛 8 6 00 ，1 7 2 08 5 5 7 9 e 1 1收敛 97 5 0 2 1 9 07 7 7 7 6 e 一1 1收敛 1 03 4 0 1 0 9 05 8 6 1 6 e 一1 1 收敛 1 14 00 1 2 5 0 5 5 3 0 9 e 一1 1收敛 1 2 3 20 1 0 9 06 1 7 6 4 e 一1 1 收敛 1 32 80 0 7 8 08 4 0 6 9 e 一11 收敛 1 42 3 0 0 7 8 03 6 5 7 0 e 11收敛 1 52 30 0 9 4 0 7 6 1 0 l e - ll收敛 1 61 7 0 0 7 8 04 8 0 5 7 e 一1 1 收敛 1 71 80 0 7 8 0 8 7 4 9 6 e 一1 2 收敛 1 81 10 0 6 2 0 7 8 9 3 0 e 一1 2 收敛 1 970 0 4 7 03 5 6 5 4 e 一1 2收敛 2 01 4 0 ，0 6 2 01 3 2 2 0 e 一1 1 收敛 例2 ：我们选取的这个矩阵来源于( 见 8 1 ) a = 1 11 a l 11 0 1a 2 1 0 l0 20 3 11 11 1l a n _ 1 1 第四章数值实验 1 4 其中a i = 1 + 话。 在这里，我们取= 1 0 ，凡= 1 0 0 ，预处理多项式次数后尾= 2 ，把 相对残量n d r m ( r ) 几d r m ( 6 ) 控制在1 0 1 0 附近。 从图3 我们可以看出：p c m r h ( 2 0 ) 明显比c m r h ( 2 0 ) 要来的好， p c m r h ( 2 0 ) 只需重启3 7 次就达到9 0 0 0 7 e - 0 11 ，而c m r h ( 2 0 ) 却需3 1 7 次才达到9 9 2 2 1 e 一0 1 1 。可见，经过预处理后，其收敛性能得到了大大地改 善。 图3 = 1 0 ，n = 1 0 0 例3 ：令a = s d s 一1 ，a ，s ，d r 1 0 0 0 1 0 0 0 ，s = ( 1 ，0 9 ) 是双对角矩阵， 1 是主对角元，0 9 是其上对角元，d = d i a 9 ( 一1 0 ，一9 ，一1 ，1 ，2 ，9 9 0 ) 。 在本例中，我们顺便把g m r e s ( m ) 也加进来比较一下，图4 中的点 线( ) 表示的是g m r e s ( m ) 方法。仍然把把相对残量n o r m ( r ) n o r m ( b ) 控 制在1 0 1 0 附近。 由图4 可以看出：由于a 的特征值有负特征值，g m r e s ( 2 0 ) 方法产 生了停滞，它重启了1 0 0 0 次，最终停在1 8 1 1 0 e 一0 0 6 ；c m r h ( 2 0 ) 方法有所 第四章数值实验1 5 好转，不过也重启了8 8 3 次才达到8 4 7 6 1 e 一0 11 ；而用p c m r h ( 2 0 ) 方法当 k k = 3 时则重启了4 8 1 次达到8 2 9 4 4 e 0 1 1 。可见预处理的效果很明显。 表2 给出了预处理多项式的次数惫后取1 2 0 时，p c m r h ( 2 0 ) 方法所 需的重启次数，求解时间，相关残差范数以及收敛性的变化。从表中可以 看出，七尼取1 2 0 时，p c m r h ( 2 0 ) 方法都收敛，但重启次数，求解时间 不随岛七的取值增加而增加或减少，当k k = 3 时重启次数和求解时间都达 到最小值。 表3 给出了上述三种方法的比较 图4 ：a = s d s 一1 第四章数值实验1 6 预处理多项式次数七忌 重启次数求解时间( 秒)残差范数收敛性 15 1 86 0 4 8 4 09 4 1 3 1 e l1 收敛 24 9 95 9 3 4 4 09 6 4 3 8 e 一11 收敛 34 8 15 7 2 6 5 08 2 9 4 4 e - 11收敛 4 6 2 57 5 1 7 2 09 7 8 5 1 e 一1 1 收敛 56 3 97 7 7 9 7 09 6 1 7 5 e 1 1收敛 69 3 411 3 6 7 1 09 7 3 1 9 e 一11 收敛 76 8 0 8 4 7 1 9 09 9 6 3 4 e 一1 1 收敛 86 4 98 2 ，4 8 4 09 8 6 3 7 e 一11收敛 97 4 79 4 9 2 2 09 3 9 7 2 e 一1 1 收敛 l o8 2 41 0 4 3 7 5 06 7 1 3 7 e - 1 1收敛 1 19 4 011 8 8 5 9 0 8 5 8 9 3 e _ 1l收敛 1 25 8 5 7 9 5 7 9 09 8 8 1 3 e 一11 收敛 1 36 9 0 9 3 1 4 0 08 4 2 7 1 e 一11 收敛 1 46 4 0 8 9 2 8 2 0 9 6 6 2 8 e 一11 收敛 1 55 9 98 4 9 5 3 09 8 6 4 1 e - 11收敛 1 67 5 51 0 4 5 4 7 09 8 9 7 2 e - 11 收敛 1 75 5 38 1 8 4 4 09 0 1 1 9 e - 1 l 收敛 1 8 7 3 01 0 4 3 9 1 09 3 9 3 2 e 一1 1收敛 1 96 1 1 9 0 2 9 7 08 6 0 7 3 e - 1 1收敛 2 06 6 0 9 7 0 4 6 09 8 1 9 6 c 一1 i收敛 表2 算法类型重启次数求解时间( 秒)残差范数收敛性 g m r e s ( 2 0 ) 1 0 0 03 6 8 0 3 1 01 8 11 0 e 6不收敛 c m r h ( 2 0 ) 8 8 31 0 0 ，2 5 0 08 ，4 7 6 1 争l1收敛 p c m r h ( 2 0 ) ( k k = 3 ) 4 8 15 7 2 6 5 08 2 9 4 4 e 。11收敛 表3 通过以上例子，我们对c m r h ( m ) 和p c m r h ( m ) 进行了一番比较。值 第四章数值实验1 7 得指出的是：使用p c m r h ( m ) 方法的主要目的在于减少迭代次数，缩短 求解时间。大量数值试验表明对于预处理多项式锨。( z ) 的次数七奄的选取 可以比较随意，大部分的七忌的取值得到的效果都还不错，当然也有不收 敛的。但胜的取值不能太大，否则会增加计算量，会使计算与处理多项 式的时间大大增加，破坏矩阵的稀疏性，并且舍入误差也随之增加，数值 实验表明后七并不是取得越大越好。 参考文献 参考文献 1 8 【1 】h s a d o k ，c m r h ：an e wm e t h o df 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 s b a s e do nt h eh e s s e n b e r gr e d u c t i o na l g o r i t h m ，n u m e r 。a l g o r i t h m s 2 0 ( 19 9 9 ) 3 0 3 3 2 1 f 2 】y 。s a m ，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 s ，s i a m j s c i s t a t i s t c o m p u t 7 ( 1 9 8 6 ) 8 5 6 8 6 9 【3 】f r e u n drw ，n a c h t i g a lnm 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 r n o n h e r m i t i a nl i n e a rs y s t e m s ，n u m e rm a t h ，1 9 9 1 ，6 0 ：3 1 53 3 9 4 】m b v a ng i j z e n ，ap o l y n o m i a lp r e c o n d i t i o n e rf o rt h eg m r e sa l g o r i t h m ，j c o m p u t a p p l m a t h 5 9 ( 1 9 9 5 ) ，9 1 1 0 7 5 】w j o u b e r t ，ar o b u s tg m r e s b a s e da d a p t i v ep o l y n o m i a lp r e c o n d i t i o n i n ga l - g o r i t h mf o rn o n s y m m e t r i cl i n e a rs y s t e m s ，s i a mj s c ic o m p u t ，1 5 ( 1 9 9 4 ) ，4 2 7 - 4 3 9 f 6 】p e s a y l o ra n dd c s m o l a r s k i ，i m p l e m e n t a t i o no fa na d a p t i v ea l g o r i t h mf o r r i c h a r d s o n sm e t h o d ，l i n e a ra l g e b r aa n di t sa p p l i c a t i o n s ，1 5 4 - 1 5 6 ( 1 9 9 1 ) ，6 1 5 6 4 6 7 】p n b r o w n ，at h e o r e t i c a lc o m p a r i s o no ft h ea r n o l d ia n dt h eg a i r e sa l g o r i t h m s ，s i a m j s c i s t a t i s t c o m p u t 1 2 ( 1 9 9 1 ) 5 8 - 7 8 【8 】r t g r e g o r y a n d d l k a r n e y , ac o l l e c t i o no fm a t r i c e sf o rt e s t i n gc o m p u t a - t i o n a la l g o r i t h m s ( w i l e y , n e w y o r k ，1 9 6 9 ) 9 1n m n a c h t i g a l ，l r e i c h e la n dl n t r e f e t h e n k ，ah y b r i dg m r e sa l g o r i t h mf o r n o n s y m m e t r i cl i n e a rs y s t e m s ，s i a mj m a t r i xa n da p p l ，1 3 ( 1 9 9 2 ) ，7 9 6 8 2 5 参考文献1 9 1 0 l r e i c h e l ，t h ea p p l i c a t i o no fl e j ap o i n t st or i c h a r d s o ni t e r a t i o na n dp o l y n o m i a lp r e c o n d i t i o n i n g ，l i n e a ra l g e b r aa n di t sa p p l i c a t i o n s ，1 5 4 1 5 6 ( 1 9 9 1 ) ，3 8 9 - 4 1 4 11 lo g j o h n s o n ，c a m i c c h e l l ia n dg p a u l ，p o l y n o m i a lp r e c o n d i t i o n e r sf o rc o n j u g a t eg r a d i e n tc a l c u l a t i o n s ，s i a mj n u m e r a n a l ，2 2 ( 1 9 8 3 ) ，3 6 2 3 7 6 【1 2 js f a s h b y ，m i n i m a xp o l y n o m i a lp r e c o n d i t i o n i n gf o rh e r m i t i a nl i n e a rs y s