（计算数学专业论文）斜对称占优系数矩阵的迭代法.pdf

中文摘要 二维对流扩散问题一p e 。a u + = 1 v 1 “，+ v 2 “，+ ( v l “) 。+ ( v 2 “) ， _ f 在单位区域上 的数值求解问题是数值线性代数的一个重要研究方面。不同的速度向量v = - v t ，u 1 的取法对应着不同的问题。通过五点中心差分可以得到该方程的线性近似 a x = ，。此时生成的系数阵当p e 取到1 0 3 一l o 。时a 具有强反对称占优，对称部 分正定的性质。本文中使用了两种迭代方法进行比较：第一种是三角迭代，它利 用a 的反对称部分构造r i c h a r d s o n 迭代的预条件矩阵，取得了较快的收敛速度。 第二种是k e y l o v 方法，具体讨论了四种k r y t o y 方法：f o m ，g m r e s ，b i c g 和q m r ， 在a 是奇异的或接近奇异情况下，它们第n 步残向量之间的关系。并且在第四章 中将三角迭代与g m r e s 方法的收敛速度和计算时间做了比较。 关键词：三角迭代，k r y l o v 方法，收敛加速， j辐1 车 a b s t r a c t t h en u m e r ic a lc o m pj t ac l o no na2 - dc o n v e c t io n d i f l u s i o nm o d e lp r o b l a m o hau n i ts q u a r ew i t has m a l lp a r a m e t e r ( p e c l e tn u m b e r ) a tt h eh i g h e r d e r iv a t iv e v a t l o u sw a yo fd e s i g n i n gt h ec o e f f i c e n t sf o rc o n v e c t iv et e r m w a sc o n s i d e r e d b yu s n gc e n t r a ld i f f e r e n c ea p p r o x i a m a t i o nw eg e tt h e 1 i n e a re q u a t i o l lo ft h ep r o b l e m s ：a x = f w h i c hi s d is s i p a t i v ea n d e s s e n t i a ll y n o n s y m m e t r i c w h e nw ec a l c u l a t et h ee q u a t i o nw i t h p eo f 10 一1 0 ，m a n ym e t h o dc o n v e r g e ss 1 0 w l yw eu s et w ot y p eo fm e t h o df o r c o m p a l a t o n o n ei st r i a n g l eit e r a t jv em e t h o d i tu s et h ee l e m e n to ft h e s k e wp a r to ft h em a t r i xat oc o n s t r u c tt h ei t e r a t i o nm a t r i xo fr i c h a r s o n it e r a ti o na n dc o n v e r g ef a s t a n o t h e rm e t h o di sk r y l o vm e t h o d s ： f o m ，g m r e s ，b i c g 和q m r c o n s i d e r i n gt h er e l a t i o nb e t w e e nt h e i rr e s i d u a l n o r ma tn t hi t e r a t i o nw h e nai ss i g u l a ro rn e a rt os i n g u l a r a n di nc h a p t e r 4 ，w ed on u m e r i c a le x p e r i m e n t ，c o m p a r i n gt h er e s i d u a l n o r mb e t w e e n t r i a nl a rm e t h o da n dg m r e sm e t h o d ，a n dt h er e s i d u a ln o r mc o m p a r a ti o no f t h eb l c ga n dg m r e s k e y w o r d ：t r i a n g u l a ri t e r a t i v em e t h o d s ，s k e w s y m m e t r i c ，k r y l o vm e t h o d 3 引言 单位区域上的两维对流扩散问题一心。1 幽+ 【v 1 虬+ v 2 “，+ ( v 1 “) 。十( v 2 “) ， ：f 的数值求解问题是近年来计算数学的研究热点之。在这一领域已经有了很丰富的 研究成果，并且还可以做许多更深入的研究工作。 通常的做法是将方程通过差分格式得到线性方程组a x = 厂。常用的差分格式 有标准五点差分，m a c 差分等，其中由五点差分得到的矩阵的对称部分是正定的。 本文采用的是五点差分格式。由于得到得矩阵一般是大型稀疏矩阵，通过直接法求 解是不可行的。而通过迭代法逐步逼近就可以得到预先设定精度的近似解。迭代法 的优点是计算过程简单，对大型稀疏阵存储量小，因此迭代法的基础理论工作得到 了深入的发展并有了许多迭代方法如j a c o b i 迭代，g - s 迭代，c g ，s o r ，k r y l o v 方法 等等。虽然不做预条件的迭代法能够保证收敛，但是对于某些问题收敛速度较慢， 随着网格的细分，矩阵阶数的增大，计算时间会迅速增加而变得不适用。如何根据 不同的问题采取合适的预条件就成为研究的重点之一。 本文第一章介绍对流扩散方程及其通过标准五点差分得到的线性方程组，第 二章介绍了三角迭代方法，并证明了它的收敛性以及讨论了参数的最优选取。第三 章讨论了四种k r y l o v 子空间方法的残向量比较，并给出了在a 是奇异和非奇异情 况下k r y l o v 子空间方法第n 步时残向量范数的关系。第四章给出数值试验的结 果。 考虑以下对流扩散问题 第一章问题的提出 一尸p 一1 a u 十i 1 v l “，+ v 2 “y 十( v 1 “) ；+ ( v 2 “) ，= f v ，= v ，( x ，y ) ，i = 1 , 2 ，“= u ( x ，y ) = f ( x ，y ) ( x ，y ) q = 0 , 1 x 【0 ，l 】， “a q = 0 其中速度向量p = 【v i ，v ：j 满足d i v ( v ) = o 表1 不同问题的速度向量 v e l o c i t yc o e f f i c e e t sf o rt e s tp r o b l e m 问题n v lv 2 1l2 21 2 x2 v l 3 x + yx y 4 8 ( x 2 一x ) ( 2 y 1 ) 8 ( 2 x 1 ) ( y l y ) 并由方程( 1 ) 用标准5 点差分格式得到线性矩阵方程 a u = f( 12 ) a 是( n 1 ) z 阶的矩阵，u 是( n 一1 ) 2 阶的解向量。 定义a = a 0 + a 。，其中a o = k ( a + a + ) = a 。+ 是a 的对称部分，代表( 1 ) 中l a p l a c e 算 子的中心差分近似，描述了方程中的扩散过程。a 。= ( a - a + ) = 一a + 是a 的反对称部 分。代表方程中的对流项的差分近似。在( 1 2 ) 中，如果满足 i i j i i a l 卜o d ) 则a 被称为反对称占优的。如果a 0 是正定的，则矩阵a 称为耗散的。在本文 的情况下，a 是耗散的。 根据差分格式，在方程左右各乘以p e 和h ：，我们可以得到a 有以下性质 | | 4 0 。= p e 4 hm ，a x ( i v l i , - + - v i j , ) _ if + i v l t , j + v i t , j + ii + v 2 t , j 。 v 2 t + i , j + f v ：。+ v ：。， 本文使用四个不同的问题，在表l 列出了这四个问题速度向量v 的取法。这 些问题部满足d i v ( v ) = v i 。+ 屹，= 0 。当p e 很大时，( 1 2 ) a 是反对称占优的。在 第四章的数值算例中取p e = 1 0 3 ，1 0 4 ，1 0 5 。 第二章基本三角迭代方法 1 定常迭代方法 为了解方程( 1 2 ) ，考虑使用定常迭代方法 ( 2 1 ) 其中b 是h 空间中的非奇异矩阵，h 指实h i l b e r t 空间。t 是一实参数。a 和 f 是( 12 ) 式中的系数矩阵和右端向量。 当( 11 ) 中的参数p e 非常大时，比如达到1 0 5 时，通过差分得到的方程( 1 2 ) 的系数矩阵a 就会是反对称占优的，此时许多迭代方法就会失效。 考虑两种1 3 的取法，分别称为t m 和p t m 第一种取法t m ： b = b c 十t ( ( 1 十i ) k 十( 1 一i ) k 。) i - i l ( 22 ) 第二种取法p t m b = ( b c + z k 。) g c 。( 1 3 c + tk l )( 2 3 ) 其中k l 和k 。是a l 的严格上三角部分和严格下三角部分，满足k u + k 。= a ， k ，= k ? ，b c 是一对角阵。 2 迭代收敛的充分条件 由变分迭代法的知识可以知道，迭代方法( 2i ) 收敛的充要条件是迭代矩 阵g = ，一b a = b 。( 口一r a ) 谱半径小于1 。 将b 分解为对称部分与反对称部分之和 b = 吼+ b 。，口。：；( 占+ b + ) ：联，b ，：三( b b ) = - b 根据( 2 2 ) ，( 2 ，3 ) 可以得到 对于t m b o5 b c + 订( k l k u ) ，i 2 l ，b 12r a l ( 24 ) 对于p t m 岛2 b c + r2 k ，邵l k ，e 2 r a l ( 2 5 ) 则由( 2 4 ) ( 2 。5 ) 得到 4 g = b “( b 一刮) = ( b 。d - 别1 ) “( b u r a o ) ( 2 6 ) 我们1 嵌足1 2 4 j ，l 2 5 j 式中取得的b 是耗散的，即8 n 是正定的。并且定义 昂= b o - j j 2 a o b o “= 巧 0鼻= b o 。”爿b o “”= 一鼻+ 则g 司表示为 g = b o 一佗( ，+ 明) 叫i l l - 战) b j 此 两边取范数，得到 i i g i i r = 忖+ 绵) 。( ，一琨) 忙炉+ 明) 。1 ”i k s - | z - p o ) l l ( 2 7 ) 由于p 是反对称矩阵，所以它的特征值都是纯虚数，即可表示为土c i ，c r 的 形式，而i + t p 的特征值就可表示为l 士c t i 。由此可得炉+ 媚) “1 ，和 矧。- o 证明：由( 28 ) 式可得 ”一哦) 忙1 铮p ( 馏i 4 8 0 17 2 ) 0 口 我们假设有下列估计式： ，一、 o y 4 ，sy _l 。= 啤。川22 7 ：， o f ，7 b _ c 2 i 2 9 根据( 2 4 ) ( 25 ) 式，有 对于t m ，我们有 ( o ) ( c 1 2 r y 3 ) - 兰b o 蔓( c 2 十2 r 7 3 ) i ( 2 1o ) 对于p t m 我们有 ( o ) ( 生兰监) ，风 c 2 ， ( 2 1 i ) c 1 由此我们得到b 是耗散的充分条件： 对于t m ： o r2 叭“景 对于p t m ： o 。! ：- 4 v y 3 ，o 。， 瓜丽 ( 7 1 以及三角迭代收敛的充分条件 对于t m ： 。，一2 矽，去矾 对于p t m ： 蔓二! 垒：= 三： 定理3 ： 方法t m 在h 。中收敛的充分条件是 f = 焘啦 方法p t m 在。中收敛的充分条件是 泳型乒成立 ( 2 ，1 2 ) ( 2 13 ) ( 2 1 4 ) ( 2 l 5 ) ( 2 1 6 ) ( 2 1 7 ) s 3 参数t 的最优取法 箍我们已经估计了( 2 9 ) 式参数y 。，y ：，y ，印c ：，考虑如何选取参数t 使蚓f 最小，由( 2 t 2 ) ，( 2 1 3 ) 得到 6 口1 ( r ) i r 口：( 0 1 对于t m ： 口( r ) ：l ，a ，( r ) ：j 尘一 。! + 2 r y3 。 c 【一2 z - y 3 y c l 。( 砷。芑皿z ( 卜赢扎。 l 0 1o，1 ( 21 8 ) ( 2 1 9 ) ( 2 2o ) 为了求得i ；一矾需要求解以下方程 风= 。m i 。n ，m a x ，p 1 ( ) | ，i p - , ( r ) 陆 p 肛) = 1 - - _ z a ；( r ) ，= 1 ，2 22 1 ) 对于t m 和p t m ，可以证明只要t 满足( 2 1 6 ) ( 2t t ) 则对于方程( 2 2 1 ) 有唯 一解，并且解t 。满足方程 , o l ( f ) = 一p 2 ( f ) ( 2 2 2 ) 这对于t m ，p t m 分别是二次和三次的多项式求根问题。 定理4 ：假设( 2 g ) 式成立并且t 满足( 2 1 6 ) 式，则方法( 2 4 ) 在岛中 收敛的充分条件： f = l 收敛速度： 4 胪卜i 再而i 而再百丽再丽而两i 耵 广 l + 2 7 7 3 + ( 7 7 1 + 2 叩3 ) ，7 i + 【( 1 一叩2 玎l + 2 ( 1 + 7 7 1 ) 7 7 3 ) 一十4 ，7 i ，7 2 ) 1 其中 q ：垒，7 ：丝，仉= c 。y ty l 口 7 一 业 一 定胖j 假殴( ? 9 ) 式成立并且t 满足1 2 1 7 ) 式，则方法( 2 5 ) 在。、中收敛的 允分条件是： 、是二次多项式方程 的解，1 i 收敛速度 p ：l 一丛r 口 t m 与p t m 有一些共i 司之处： 1 ：它们取得的预条件矩阵b 的反对称部分都是ta 。，这使得在收敛性证h j j 中由 4 ；对称部分的收敛估计变为考察b 与a 的对称部分之差的皤! | 二径。丽它们的对称部 分又都是正定的。这使得收敛性可以得到保证。 2 它们都采用t _ - 2 角迭代方法。作为预条件，以一个或几个二角矩阵的乘积 作为颅繁什矩阵的代价是可以接受的，因为求解b r 可以通过一系列求解：二角矩阵 方程而得，而每步二角方程求解又是非常快的。在实际的数值试验可以看出由于 p t m 每步迭代比t 要多做一次三角方程求逆( 当b c 取单位阵时，p 是两个三角 阵的乘积，而t m 是一个三角阵) 这使得每步迭代p t m 比t m 多消耗了2 0 的计算时 间。然i 面p r m 的迭代步数却只需t m 的1 2 到1 3 。从而从总体上，p t m 比t m 收敛 快。 扶第p q 章备种方法的试验结果比较来看：以p t m 为预条件矩阵的收敛速度最 快。f 酊不做顺条件的g m r e s 大体上与t m 相当。 4r c 的取法 趣以上的做法中，可以简单得取b c 为单位阵，即等价于取c ，= c ：= i 。 f u 是从数值算例中可以看出实际的效果并不理想。特别是对于t m ，当p e 较大 时收敛速度并不理想。可以在b c 的取法中作一些调整，利用a 1 的结构构造b e ， 仍然保持b c 的对角阵性质。 b c = ，+ o ) d d 是对角阵，是一实参数。 将a 】的上二角部分k 。利下二角部分k 。分解为一系列的三角矩阵之和。 矗。= k ，k ，= k 。 ，= 二j = 2 其中k 。是k ，的第i 条次对角线，k 。是k 。的第i 条次对角线。 由五点差分的格式知道k 和k 。只有第2 ，第n l 条次对角线才有非零元素。 并且由k 。，= 一k 。+ 可知矩阵乘积k ：，k 。= 一k ：，k 。，= - k u , k 。 是负半定对角 阵。 定义正# 定对角阵d l ，d 2 ，d ： d 1 = k l k l ，d 2 = k u k u j = 2t = 2 d = 去( d i + d 2 ) = 一( 也k l + + z k k u * ) 忙2卢2 虽然前面的收敛速度估计中并不能说明以这样的方法取d 和b 能够取得较快 的收敛速度，但是从实际的算例中可以看这个方法还是有效果的。 2 第三章k r y t o y 方法 i 阶y o v 方法介绍 k i v i 。，。方法是解线性方程组( 1 2 ) 的一种有效的迭代方法。当a 非奇异时，在 小趟过a 的最小多项式的迭代步数后就一定能够得到方程的解。当a 奇异时，如采 方程的解落在k r yl o v 空间中，就一定能够得到解。 关fk r y i o v 方法有以下结论： 6 令m 是矩阵。4 c 的最小多项式的阶数，i 足a 的指标。 0 有： i ) 方程a x = f 有k iy l o v 解的充要条件是，8 ( a ) 2 ) 如果k rv l 。v 解存征，它是唯一的，并且是d r a z i n 逆的解 x = a d f k ( a ，。) 3 ) 对于相容系统a x = f ，如果a 是可对角化的，则方程有k r y l o v 解。 叮e 髀蔗燃 d 是a 的不同特征值的个数 口 由k r yt o y 方法产 三第m 步迭代近似解 x 。= r 。 匕c “”，y 。c ” ( 3 1 ) 其巾p j ：【，_ ，v 。j 构成m 阶k i y l o v 空问k ( a ，i ) 2 s p a n ( t ，a f ，旷2 f ) 的基。 y 。足h 在吃中的系数向量。 找们考虑4 种k j y l o v 方法，缩写分别是f o m ，g m r e s ，b i c g 和0 m r a按照构成 吒的方法( a r n o l d i 和【& n c z o s 过程) 和确定系数向量的方法( g a l e r k i n 和 m in m iz a t ic ) n 方法) ，它们之间的关系可亩下表表不。 0 丧l6 - 种k 1 1 v l ( j 、r 方法比较丧 t a bjeo tk r v lo vm el h o d 下面分析各个方法的特点及性质。 先考虑求v 。的两种过程：m n 0 1 d i 过程千u1 a n c z o s 过程。它们部产生k ( a ，f ) 的基v 羊l i - - 个( m 十1 ) x m 的上h e s s e n b e r g 矩阵j 【，。，并满足 v 。：v 。，( ： 2 j 刈于a r n o l d j 过程，v 。满足正交性，敞有 v + 一a v 2h 。， 和v a v = 其中i i 。= i ，0 日。 ( ： ：3 ) l a n c z e s 过程在产牛k 的同时，还产牛矩阵虬构成k ( nw ) 的基，虬和v 满 足正交关系。即w 。v 是对角阵。为了避免l a n c z o s 过程的中断，q m r 算法采用 1 0 0 k a h e a d 【，a n c z o s 过程，它的v 。和毗满足块正交关系，即d - ：= w 。v 。是块对角阵。 所以l o o k a h e a dl a n c z o s 过程满足 虬+ + a v ：d 。 和w - a v 。：d h ( 3 4 ) 在实际计算中，可以将v 和w 的列向量部取作单位的，这样它们的范数部不大 r i 。在后而的估计式中会用到这一点。 当存l a n c z o s 过程中取w = v 利d 。= 1 ，这时l a n c z o s 过程和a r n o l d i 过程是等 价的。 再考虑求系数向量h 的两种方法：g a le i k i d 方法羊l | m j l 3 i m i z a t i o n 方法 ( ；c 【 “k ；n 方法要求残向量 = 爿j 。= 吃+ i ( p 。一- 。f v 。) 满足w ：r ，= o 。 即 儿y 。= e ，。当结束o o k a h e a dl a n c z o s 过程中一个块，且儿可逆时y 。= h 一e 。 m i n j m ；z a t i o d 方法要求残向量二范数极小。这等价于使e 一j 【，y 二范数最 小。刘 ，= ( 鼠) + e ，其中( 玩) 是或的m - p 广义逆。 ( 35 ) 档v ，由a l ，n o l d i ，彳法构造，! j ! | j 它等价于残量r 的二范数极小。 2 误差控制 在a 非奇异的条件下有如下结论( j ) ： 定理l ：如果a ，h m ，d m 是非奇异的，则b i c g 迭代_ 满足 i i a - i f - - 。删a - i f v m h 。一e ，t t 马l a 。卜i i 。r a i n ：l 慨( a ) f i i ( 3 6 ) 其中p - 【、一v 。疗。h 。d 。w 。，m 是不超过m 次并满足p _ ( o ) = l 的多项式。 对于f o m ，取w - = v 。，d 。= i 。即有类似结论。 定理2 ：如d 。对某一个k 妻1 是非奇异的，则对于q m rk 迭代满足 厂一f ( 2 y e , 1 1 - 1 1 a “乩m i n h l i p m ( 删 3 7 其中p = i 。一v 。 厅。( 雷。) + ，0 d 。+ t 。w + 一 对于g m r e s ，k = 1 ，w = v ，d = i ，p = i 。一v 。疗。青，+ v + “ 现将定理l ，定理2 推广到a 是奇异阵的情况。 当a 是奇异阵时，未必所有的线性方程组a x = f 都会有解。 在某些情况下，如果i n d e x a = l ，则要求r ( 爿) ，这样就可以将a 映射到r ( a ) 上，然后用k r y l o v 方法求解，从而可以避免坏条件数带来的计算误差。 定理3 如果h d 是非奇异的，则b i c g 迭代x m 满足 忙+ 厂一p r c a * x m | = 忙+ 一匕，。- i q 忙i i a + p 。i i 。r a i n ：。l i p 。( a ) i l ( 3 8 ) 其中厶汀，= a + a 是投影算子，p l = i “一v “曰。h - 。1 d - “w ：，p _ 是不超过m 次并满 足p 。( 0 ) = l 的多项式。 对于f o m ，取w _ = v 。，d 。= i 即有类似结论。 证明： 由( 3 2 ) ，( 3 4 ) 式知道 p 。a v = o ( 3 9 ) 并由e 。= d 1 w + 。f 和( 25 ) 式，得到 a + 卜a + ax 。= a + f a av h - le = a + p f = a + p 。( f a v 。z 。) z 是c 中的任意向量。 记d 是阶数不超过m 的多项式，并满足p 。( 0 ) = l 。 则对任意z f - a v _ z - 都代表 了一个p 反之，对任意一个p 。，雨r - - bz 。使f a v 。z 。2 “所以a p 一( f a v - z m ) 2 a p 。p ，( a ) f ，并且 a f a + av 。h - j , e ，= a p p 。( a ) f ( 3 1 0 ) 在( 3 1 0 ) 两边取范数即得到定理结论 定理4 ：如d 。+ 。对某一个k 三1 是非奇异的，则对于q m r 迭代x 。= v 。( j 孽。) + e 满 一，| | | | p r a 。卟i n 一) 硎 其中p 。= i 一v 。 对于g m r e s ，k 证明： 由( 24 ) d 。0 。w + 。a v 。 厅。( 厅。) + ，0 d 。w + 一 l ，w ，= v 。d m = i ，即p = i 一v 。豆。疗。+ v 。 玑阱例 又因为( h ，) + h 。= i 。 由此可知 只爿= 爿一_ j 疗。膏。+ 川 台 = 4 一+ 厅，= 。 现考察a + 卜a + ax afa ax = a f a + av ( 疗。) + e l = a + 厂一爿+ 【爿疗。，o w + 是阶数不超过m 的多项式，并满足p ( 0 ) = l 。 两边取范数即得定理结论。 3 贱向量比较 由二中知道k r y l o v 方法的残向量可以表示为 r = f av 。y = p 。f = p p ( a ) f ( 31 1 ) a p f = a + n p 。( a ) f 口 ( 3 1 2 ) 在( 31 2 ) 的“( a ) 用g m r e s 的第m 步的残向量多项式，得到 r 。= p r 6 = p 。q + s 6 ( 3 1 3 ) 其中q 。是i ( - + ( a ，f ) 的正交基，守是系数向量 类似地，在( 3 1 2 ) 中的p i ( a ) 用q m r 的第m 步的残向量多项式，有 r = p r 。= p v s 。 其中s 。可以求得 s “= e 。一疗。y = ( i 。一百。h 。) e ( 3 1 4 ) ( 3 1 5 ) 无沦a 是奇异或非奇异，都有如r 结论： 性质1 ：h 。，d ，非奇，则 一v m 1 9 m d 。- 1 w m r m ，g 和1f m 61 1 = 1 1g 。i i | | s 。，”i i ( 31 6 ) 其中g 。是h + g = h 。e 的解， 由3 1 2 可得到 i i bi i - l t w 。( d i n + ) 一g 。”i ir 。1 1 - 石m ) g 。f i i ir m ，。i i ( 3 1 7 ) 证明： 我们首先可以得到 巴绒+ ，= k “a 一+ 1 扎叠t h ：i 域1 吃级+ = + 月品一+ l 台0 。 r 品一+ 。 九扎。o 。： 。：1 吃q 一 = + l ( p ：+ 、7 0 。一g m d , 1 吮瓯+ ) 所以 匕盱城廿 = - - v m + l g 1 吃q 。 以及 = 搿鼍，= 匕q 。s ：一。= 一v m + l g ：域1 吃q 。s 。g - v m + l g ：域吃 呓= p ? k + s ：= p ? o _ m r 。s ：一= 一v 。+ g ：d ：1 吃q 。r 。s ：一，= 一v m i g 一 s o 。 由s ：一。的定义可知，膏：一s ：一，= 0 ，又有疗：一，g 。= ，。o l h ；g 。= 0 并且 疗：的零空间是一维的，故j ：一。与g 。相差一个倍数。所以 i ir m 。1 1 = 1 1g 。i ii is 。i i 性质2 ：设n + 。非奇，u 。是一单位向量，它张成 _ 的一维零空间，则 j jr m 。j j 兰( + 1 ) 1 1 ( d 。+ ) 。u 。j j | | r m ol l 证明：类似性质l 中b i c g 的做法，有 只q 。= ( ，一+ ； h 。日：，o 】d 。- + i t 阡0 t ) 绒+ ， = + ( ，1 。h ：，o d ：k 纬爿t + t ，。，o ) 月： = + ，( ，一。j ，：) 吒：， 口 ：彤，“：彤q 。+ 。s ：= q 。+ ，r 。+ i “。+ i “：+ t d ：i 畈+ t 呓 由于 - 和陟j 的列向量都取作单位的，他们的范数都不大于l 。 范数，可得： i lr 。lj - ( ，”+ 1 ) j | ( d 。+ ) 1 “i i i ir m 6 1 1 在上式两边取 9 阢 以如 艮艮 观锻似 第四章数值试验 在这一章我们对第一章表i 中的四个问题进于亍数值试验。 取p e 为1 e 3 ，1 e 4 ，l e 5 分别做迭代计算，在这情况下所得的a 是强反对称占 优的。计算结果分两个部分，第一部分使用三角迭代方法( 2 1 ) ，试验结果比较迭代 次数和计算时间，单元格内的数字代表迭代次数，括号内的数字代表计算时间。第 二部分使用r r y l o v 方法的g m r e s 和b ic g ，检验它们的残向量范数关系式( 3 1 7 ) 式。 第一部分：三角迭代数值试验 迭代初值取零向量，迭代收敛条件取p 1 l l r 。i t - 1 0 一，r ”是第m 次迭代残向 量，表不二范数。 表中g m r e s ( 1 0 ) 是l o 步重开始g m r e s 。p t m + g m r e s 为以p t m 为预条件的 g m r e s 。 t m + g m r e 8 的结果没有列出，因为实际的结果并不理想。 表格内的结果是迭代步数和迭代时间( 秒) 。 表1 问题l ，n = 6 4 ，矩阵3 9 6 9 * 3 9 6 9 p et mp t mp t m + g m r e s ( 1 0 )g m r e s ( 1 0 ) l 。3 1 8 5 ( 8 3 ) 7 0 “3 )5 7 f 4 1 ) 2 6 8 ( 1 1 1 ) 【l e 4 1 4 8 0 ( 7 5 6 )3 5 7 ( 2 2 6 ) 2 0 8 ( 1 7 6 4 )1 6 6 9 ( 7 3 1 ) 1 e 51 4 0 8 2 ( 7 1 7 )3 3 2 3 ( 2 0 5 )1 9 6 6 ( 1 7 2 )1 5 8 1 9 ( 6 9 7 ) 表2问题2 ，n = 6 4 ，矩阵3 9 6 9 * 3 9 6 9 p et mp t mp t m + g m r e sf i o ) g m r e s ( 1 0 ) 1 e 3 1 2 0 ( 4 8 8 )4 9 ( 3 1 3 ) 4 2 ( 2 6 9 )1 2 5 ( 5 1 6 ) l e 4 6 8 3 ( 3 4 )4 7 6 ( 2 9 9 4 )2 6 8 ( 1 9 8 3 )1 0 0 9 ( 4 3 1 7 ) l e 5 8 7 0 4 ( 4 5 4 + 7 ) 4 】6 f 2 5 3 7 ) 2 1 6 3 ( 1 9 0 3 )8 7 2 9 ( 3 7 7 ) 问题3 ，n = 6 4 ，矩阵3 9 6 9 * 3 9 6 9 p et mp t mp t m + g m r e s ( 1 0 )g m r e s ( 1 0 ) 1 e 3 2 2 6 ( i i 0 ) 7 9 ( 4i ) 9 6 ( 9 i )2 3 0 ( 1 23 ) 1e 41 5 4 3 ( 7 76 )5 5 5 ( 3 87 )3 1 0 ( 2 66 )1 6 3 7 ( 7 04 ) 1 e 5 9 5 6 6 ( 4 8 8 )3 9 8 9 ( 2 4 5 ) 2 1 0 5 ( 1 8 4 ) 1 0 4 9 6 ( 4 5 5 ) 问题4 ，n = 6 4 ，矩阵3 9 6 9 * 3 9 6 9 p et mp t m p t m + g m r e s ( 1 0 )g m r e s ( 1 0 ) i e 3 2 0 0 0 0 ( 1 0 6 9 )2 0 0 0 0 ( 1 3 8 6 )3 9 8 0 ( 3 4 6 )2 0 0 0 0 ( 8 5 2 ) l e 4 2 0 0 0 0 ( 1 0 7 2 )2 0 0 0 0 ( 1 3 8 6 )3 9 7 3 ( 3 6 3 )2 0 0 0 0 ( 8 9 9 ) l e 52 0 0 0 0 ( 1 0 7 5 )2 0 0 0 0 ( 1 3 0 0 )3 2 3 5 ( 3 4 8 )2 0 0 1 0 ( 8 4 8 ) 各个方法的收敛速度比较 后面每组图的按问题的次序依次列出各个方法收敛的情况。曲线符号的意义 是：”十”曲线代表t m ，0 曲线代表g m r e s ，”曲线代表p t m ，细实线代表 p t m + g m r e s p e = 1 0 3 孽 口胡x 哟h 。、j 、。3 ，釉j ? 矗，a “。，”嚣、；_ 口+? 姆慨，懈“ 。、； ；、t 奢。湃融。o 。“；，秘。：醣飘搿，i ；o 。譬鼙蕊蛰赫；。廊* 蠢y i ；二，。 c * j，htj 滁一。 鬻 a。、 豢 涎汰 ? 。弋j ； p e = 1 0 5 爹誉n 藜耧 - t 嚣 ，甜 罐| ，4 一t 孽誓+ j ，攀嚣黎一，7 黪沁，+ t ”i 糍i ，；x + 穆 、 _ 。五。r 一 、 念。 燃 过 ；。j ； 。* * “ 。 三 m * i 第二部分： kr 、， o v 方法残向量范数比较。( 不等式3 17 ) 记c l = 1 1 w 。( d m + ) g 。虬c 2 = i 【l ( d 。) 。g 。，1 1 分别代表不等式( 3 1 7 ) 的两个上界 图中虚线代表c l 曲线，点线代表c 2 曲线，实线代表第n 步时b i c g 残向量的范数 与第n l 步g m r e s 残向量的范数之比 参考文献 1 曹志浩，数值线性代数，复旦大学出版社，19 9 5 1 2 1l a 。f f r u k ie r ( b n v e r g e n c ea c c e j e r a t l o no ft r i a n g u i a rfc e r a t fv e m e t h o d s b a s e d0 1 7t h es k e w s y m m e t r i cp a r to ft h em a t r l x ，a p p l i e d n u m e r i c a 】m a t h e m a t i c s3 0 ( 1 9 9 9 ) 2 9 卜3 0 3 3 m ib o t c h e va n dlak r u k e r ，a b o u tj t e r a j v es o l u t i o no fs t r o n g i y o o d s y m m e ，cl i n e a r u a t l o ns y s t e m s ，z h v y c h i s l m a t im a t f i z 3 7 ( 1 i ) ( 1 9 9 7 ) 1 2 8 3 一1 2 9 3 4 i a k r u k i e r ，f m f j v em e t h o ds o u t f o no f m p l i c j td i f e z e n c e s c h e m e sa p p r o x j m a t e dt b ro n cc l a s so fq u a s i l n e a re q u a t o ns y s t 伽，i z v ， v y s s h u c h e b n 1 a v e d m a 7 ( 1 9 7 9 ) 4l 一5 2 1 5 、m a r l i sh o u c h b r u c k c h r i s t i a nl u b i c h m , e r r o ra n a j y s f se l ? k r y i c y m e t h o d si nan u t s h e l l ，s i a m j s e i c o m p u t1 9 ( 1 9 9 8 ) 6 9 5 7 0 l 6 【cfi p s e n ，c d m e y e r ，f i l el d e ab o b 2 n dk r y l o vm e t h o d s ，a m e rm a t h ， m e n t h l y1 0 5 ( 1 9 9 8 ) 8 8 9 8 9 9 订、pn ib r o w n h if w a l k e r ， g m r e so nn e a r l ys i n g u l a rs y s t e m s ，s i a m j m a t r i xa n a l a p p l1 8 1 1 9 9 7 ) 3 7 5 1 8 ys a a da n dm h s c h u l t z ，鳓臌sag n e r a i i z e dm i n i m a lr e s u d a l a g o t ：t h mf o rs o lv i n gn o n s y m m e t r l c n e a rs y s t e m s ， s i a m ，s c i ，s t a t c o m p u t 7 ( 1 9 8 6 ) 8 5 6 8 6 9 9 jc d m e y e r