（计算数学专业论文）求解线性方程组的总体（拟）极小向后扰动方法.pdf

摘要 本文研究了求解线性方程组的向后扰动方法对求解对称线性方程组的l a n c z o s 方法做出了向后扰动分析，给出了求解对称线性方程组的总体极小向后扰动 ( t m i n b a c k ) 方法为减少存储量，新算法采用重新开始的循环格式，并将总体向 后扰动范数作为判断算法终止的准则，克服了残量范数作为终止准则的不足，得到了 循环总体极小向后扰动( r t m i n b a c k ) 方法针对l a n c z o s 向量易失去正交性而引 起收敛速度下降的缺点，利用增广子空间技术向k r y l o v 子空间加入少量绝对值较小的 特征值所对应的特征向量进行收缩，给出了循环收缩总体极小向后扰动 ( d r t m i n b a c 酗方法 同样地，对求解非对称线性方程组的q m r 方法作出了向后扰动分析，结合总体向 后扰动范数拟极小化的技巧，绘出了求解非对称线性方程组的总体拟极小向后扰动 ( t q m b a c k ) 方法 数值实验表明，新算法在收敛速度、计算量等方面都有明显改善 关键词：线性方程组；k r y l o v 子空间：l a r l c z o s 方法；向后扰动 a b s t r a c t t h i sp a p e rm a i l l l ys t u d i e st h eb a c k w a r dp e r t u r b a t i o nm e t h o d si ns o l v i n gt h el i n e a r s y s t e m s ，a n dt o t a lm i n i m a lb a c k w a r dp e r t u r b a t i o n ( t m i n b a c k ) m e t h o df o rs y r n m e t r i c l i n e a rs y s t e m si s p r e s e n t e d 砸sn e wm e t h o di sc o m p o s e do fl a n c z o sm e t h o da n dt h e t e c h n i q u ew h i c hm i n i m i z e dt h en o r m w i s eo ft h et o t a lb a c k w a r dp e r t u r b a t i o n i no r d e rt o r e d u c et h ec o m p u t a t i o i l sa n dt h em e m o r i e s ，r e s t a r t e dv e r s i o ni su s e di n i t b yu s i n gt 1 1 e n o r mo ft h et o t a lb a c k w a r dp e r t u r b a t i o na st h et e r m i n a t i o no ft h e a l g o r i t h m 血en e w m e t h o dm a k e su pt h es h o r t c o m i n g so fu s i n gr e s i d u a ln o r l ，a n dt h e nt h er e s t a r t e dt o t a l m i n i m a lb a c k w a r d p e r t u r b a t i o n ( r t m i n b a c k ) m e t h o d i s p r o p o s e d 1 1 1 i sp a p e r e m p h a s i z e st h a tt h en e wm e t h o du s e st h ea u g m e n t e dk r y l o vs u b s p a c et e c h n i q u e t h e d e f l a t e dr e s t a r t e dt o t a lm i n i m i z a t i o nb a c k w a r dp e r t u r b a t i o nm e t h o d ( d r t m i n b a c k li s p r e s e n t e d w h e n s o l v i n gt h en o n s y m m e t r i cl m e a rs y s t e m s ，t h ep a p e rm a k e st h et o t a lb a c k w a r d p e r t u r b a t i o na n a l y s i s t o q m rm e t h o d ，a n du s e st h et o t a l q u a s i m i n i m a l b a c k w a r d p e r t u r b a t i o n ( t q m b a c k ) t e c h n i q u e ，s ot h er e s t a r t e dt o t a lq u a s i m i n i m a lb a c k w a r d p e r t u r b a t i o n ( r t q m b a c k ) m e t h o di sg i v e n t h en u m e r i c a l e x p e r i m e n t ss h o w t h en e wm e t h o d sa r eg r e a t l yi m p r o v e dn o to n l yi n t h ec o n v e r g e n c eb u tt h ec o m p u t a t i o n s k e yw o r d s ：l i n e a rs y s t e m s ；k r y l o vs u b s p a c e ；l a n c z o sm e t h o d ；b a c k w a r d p e r t u r b a t i o n 第一章绪论 在科学研究和工程应用中，经常需要求解大型稀疏线性方程组 血= b( 1 1 ) 其中a 是n n 的实矩阵，x ，6 r ” 目前，求解线性方程组的数值方法可分成两大类，一类是直接法，即通过有限次 的运算求出问题的精确解，例如g a u s s 消去法、列主元及全主元消去法、直接三角分 解法等但是由于直接法计算过程中存储量很大，当需要求解大型稀疏线性方程组时， 直接法就不适用了另一类求解线性方程组的数值方法是迭代法，即通过选取初值， 然后用同样的步骤重复计算，求得近似解在迭代法中，k r y l o v 子空间方法 3 1 是求解 大型线性方程组的一类重要方法，国际上有关k r y l o v 子空间方法的研究工作非常活 跃求解对称正定线性方程组的最有效方法是共轭梯度( c o ) 法【l 】及其预处理技术对 称l a n c z o s 方法【1 3 】【1 6 1 伫9 】是解对称不定线性方程组的有效方法之一在理论上，对称 l a n c z o s 方法产生的向量组是正交向量组，但是，在实际计算中，由于舍入误差的影响， l a n c z o s 向量易失去正交性为了减少存储量和运算量，人们采用重新开始的l a n c z o s 方法，即循环l a n c z o s 迭代法【1 1 i 另外p a i g c 和s a u n d e r s 基于对称l r i i c z o s 方法 2 提 出了求解对称不定方程组的s y n v j l q 方法【1 4 】和m i n i 陋s 方法【l ”，但是对病态线性 方程组s y m m l q 方法和m i n r e s 方法常常表现出不稳定性求解非对称线性方程组 的k r y l o v 子空间方法有许多特殊的方法，如a m o l d i 口 方法、广义极小残量法( g m r e s ) 、 双边l a n c z o s 方法、不完全正交化方法等y s a a d l 3 1 指出，a m o l d i 【2 1 过程实际上是建立 k r y l o v 子空间k ，( a ，t o ) = s p a n ( t o ，a r o ，a ”1 t o ) 一组标准正交基的过程将a m o l d i 回 过程用于求解线性方程组可得完全正交化方法( f o m ) r s s ，不完全正交化方法( i o m ) h 】【3 】【lo j 是完全正交化方法的一个变形，在理论上它是一种斜投影方法1 9 9 1 年f r e u n d 和n a c h f i g a l 基于非对称l a n c z o s 方法提出了求解非对称线性方程组的拟极小残量法 ( q m r 方法) 8 】在用非对称l a n c z o s 方法解非对称线性方程组时，也会发生算法中 断或数值不稳定k r y l o v 子空间方法通常用残量范数作为判断算法终止的条件若近 似解是精确的，残量范数是小的，但是反过来不一定为克服残量范数作为终止条件 的不足， k a s e n a l l y ”】在用g m r e s 方法1 5 删解非对称线性方程组时，考虑求满足扰动 方程( a 一。h = 6 的近似解使向后扰动范数忪。忆极小化，给出了求解大型非对称线性 方程组的广义极小向后扰动( g m b a c k i t s b 方法 二十世纪九十年代末，k a s e n a l l y 和s i m o n c i n i 以及曹志浩推广了广义极小向后扰 动( g m b a c k ) 方法他们在用a m o l d i 过程解大型非对称线性方程组时，考虑求满 求解线性方程组的总体( 拟) 极小向后避方遣 足扰动方程( 一一h = 6 + 占的近似解使总体向后扰动范数忪，硎，极小化，给出了求解 大型非对称线性方程组的总体g m b a c k 方法【1 7 】【1 8 】，并做出了理论分析1 9 9 9 年魏红 霞在用q m r 方法解非对称线性方程组时，结合向后扰动技术给出了广义拟极小向后扰 动方法( g q m b a c k ) 3 2 】 为了加快求解大型线性方程组迭代方法的收敛速度，人们不断地尝试改进已有算 法，一种有效的改进方法是将原算法结合收缩技术 2 2 2 6 】其中m o r g a n 的增广子空间技 术得到人们的重视他提出了用特征向量的重新开始g m r e s 算法，具体做法是向 k r y l o v 子空间加入少量模最小的特征值所对应的特征向量数值实验表明，效果很明 显 本文考虑应用l a n c z o s 方法求解对称线性方程组时，结合使总体向后扰动范数极 小化的技巧，加快l a n c z o s 方法的收敛速度，给出求解对称线性方法组的总体极小向 后扰动( t m i n b a c k ) 方法同时，为减少存储量和运算量，新算法采用重新开始的 循环格式，并将总体向后扰动范数作为判断算法终止的准则，克服了残量范数作为终 止准则的不足，得到了循环总体极小向后扰动( r 1 m n b a c k ) 方法本文在 t m i n b a c k 方法的执行中，针对l a n c z o s 向量易失去正交性而引起收敛速度下降的缺 点，利用增广子空间技术向k r y l o v 子空间加入少量绝对值较小的特征值所对应的特征 向量进行收缩，给出了求解对称线性方程组的循环收缩总体极小向后扰动 ( d r t m i n b a c k ) 方法 在利用q m r 方法解非对称线性方程组时，为加快q m r 方法的收敛速度，本文考 虑结合总体向后扰动范数拟极小化的技巧，给出求解非对称线性方程组的总体拟极小 向后扰动( t q m b a c k ) 方法同时，为减少存储量和运算量，新算法采用重新开始 的循环格式，并将总体向后扰动范数作为判断算法终止的准则，克服了残量范数作为 终止准则的不足，得到了循环总体拟极小( r t q m b a c k ) 方法 本文的结构安排如下：第二章对求解对称线性方程组的l a n c z o s 方法，进行向后 扰动分析，提出了用总体向后扰动范数作为判断算法终止的准则，给出了总体极小向 后扰动( n d 科b a c k ) 方法为减少存储量和运算量，新算法采用重新开始的循环格 式，得到了循环极小向后扰动( r t m i n b a c k ) 方法最后，分别将对称l a n c z o s 方法与 t m l n b a c k 方法、r t m i n b a c k 方法进行了数值比较第三章针对l a n c z o s 向量易 失去正交性而引起收敛速度下降的缺点，将收缩技术应用于r t m i n b a c k 方法，得到 循环收缩极小向后扰动方法( d r t m i n b a c k ) 最后进行了数值实验，将 d r t m i n b a c k 方法与r t m i n b a c k 方法进行了数值比较实验结果表明新算法具有 很大的优越性第四章对求解非对称线性方程组的q m r 方法进行了向后扰动分析，给 出了总体拟极小向后扰动( t q m b a c k ) 方法提出了用总体向后扰动范数作为算法 终止的准则，得到循环总体拟极小向后扰动( r t q m b a c k ) 方法最后将r t q m b a c k 方法与t q m b a c k 方法、q m r 方法、非对称l a n c z o s 方法进行了数值试验实验结 南京航空航天大学硕士学位论文 果表明新算法具有一定的优越性第五章对本文进行了总结 本文的数值实验均在实达计算机上实现，具体配置如下： c p u ：p e n 耵【m 主频：1 5 g h z 内存：1 2 8 m b 系统：w i n x p 软件：m a t l a b 6 1 求解线性方程组的总体( 拟) 极小向后扰动方法 第二章求解对称线性方程组的总体极小向后扰动 ( t m i n b a c k ) 方法 2 1 引言 考虑对称线性方程组 a x = b ， ( 2 1 ) 其中“是以月实对称矩阵z ，b r “设是方程组( 2 1 ) 的初始近似解，记 r o 3 6 一彳，卢= 忆v 2 鲁应用l a n c z 。s 过程m 1 可产生k r y i 。v 子空间 七。( 爿，t o ) = s p a n ( r o ，d r o ，a ”t o ) 的一组标准正交基v l ，v 2 ， ， 记 = ( v ；，v ：，v 。) ，则曙一是对称三对角阵，记为 h 。= 口l 8 1 0 ： 0 o 尼 ； 口，。0 。成 0 p m0 【。 又记瓦= 纛：) ，纠o ，。吡几n 则 彳= 。+ 以+ l v 。- = 吒+ l 瓦( 2 2 ) 求解对称线性方程组( 2 1 ) 的l a n e z o s 方法可描述如下 算法2 1l a n c z o s 算法 1 ) 选择( 2 1 ) 的初始估计m 令，o2 6 一出。，吲讣v 2 万r o ，记届v 。2 0 2 ) 对于- ，= 1 , 2 ，m ，计算： 岛v 22a v l 一口i v l ： 芦i “vj “= a v i a i p i v i _ l 4 南京航空航天大学硕士学位论文 d = v j 4 v j ； 卢，“= 0 爿1 ，j a j v j p v j 1 1 1 ： 3 ) 若d e t ( e 。) 0 ，解方程组巩y = 卢q ，其中q = ( 1 ，0 ，0 ) 7 是m 维列向量 4 ) 构成( 2 1 ) 的近似解= x o + q 在理论上l a n c z o s 过程产生的向量组是标准正交的，但是在实际执行中，由于舍 入误差的影响l a n c z o s 向量易失去正交性一个既简单又实用的办法是限制i ：, r y l o v 子 空间的维数m ，求得近似解靠，如果不满足精度要求，则用作为初始估计，重新 进行l a n c z o s 方法，则得求解对称线性方程组的重新开始的l a n c z o s 方法，即循环 l a n c z o s 方法 算法2 2 循环l a n e z o s 算法 1 ) 选择( 2 1 ) 的初始估计x o ，k r y l o v 子空间维数m 及精度要求占； 2 ) 计g ：r o2 6 一血。，卢= ，v 2 石r o ，记卢v o 2 0 ： 3 ) 对于j = 1 , 2 ，m ，计算 厦v 2 = a v l 一口i v l ； 岛“v j “= a v j 一口j v j 一岛v - l 2 口j = v j v j ； 岛。= i j v ，一口，v ，- f l j v ，一，| _ ； 4 ) 若d e t ( h = ) 0 ，解方程组以y = 肛f 帕； 5 ) 构成( 2 1 ) 的近似解靠= x o + h ：1 p e ，若忆0 s ，则结束；否则令x 。：= x 。并 转2 ) 在算法2 1 和算法2 2 中矩阵上0 可能奇异，为解决这个问题，p a i g e 和s a u n d e r s 考虑求y ，使得 峨心- ：e , i i ：= m i n 提出了求解对称不定线性方程组的m i n r e s 方法【1 4 】 耋堡垡丝查堡塑塑璺签! 型! 堡尘塑亘垡垫互鳖一 算法2 3m i n r e s 算法 1 ) 选择( 2 _ 1 ) 的初始估计，计算5 6 一一，夕= 蚓| ，v 2 詈，记届v 。2 o ； 2 ) 对于，= 1 , 2 ，m ，计算： 尾v 2 = a v i 一口l v l ； 卢“v j “= a v 一口j 一声v j l ； 口= v ：a v j ； 岛。= l i a r ，一a ，v ，- f l j v 川| | ： 3 ) 求解最小二乘问题l 玩- p e , l l ：= m i n ； 4 ) 构成( 2 1 ) 的近似解= x o + 比 在利用m i n r e s 方法解对称线性方程组时，利用残量范数作为终止条件，若近 似解是“精确”的，则残量范数很小，但是，反过来则不一定为克服残量范数作为 终止条件的不足，k a s e n a l l y 提出了求解非对称线性方程组的g m b a c k 方法1 5 1 ，曹 志浩等提出了求解非对称线性方程组的总体g m b a c k 方法【1 7 】【1 8 】下面给出一种求解 对称线性方程组的方法m i n b a c k 方法，该方法利用l a n c z o s 过程产生k r y l o v 子空间七。( 4 ，t o ) 的一组基，求近似解x 。托+ 七。( 一，0 ) 满足扰动方程( 一一。) x = b 并 使忪。忆极小化：另外，研究了求近似解靠，满足( 一一。k = 6 + j 使联合矩阵【彳，6 】 的向后扰动范数陋。，a 。1 1 1 ，极小化 2 2 向后扰动分析 首先讨论用l a n c z o s 方法和m i n r e s 方法求解对称线性方程组( 2 1 ) 的极小向后扰 动方法，将方程组( 2 1 ) 的近似解看作扰动方程 ( 爿一a ) x = 6( 2 3 ) 的精确解，r 称为扰动方程( 2 3 ) 的向后扰动，并称满足r n i n ，i ( a - a ) x = 6 的向后扰动为最小向后扰动，记为。下面的定理给出了如何求向后扰动的通式 南京航空航天大学硕士学位论文 和最小向后扰动。及其范数忪。忆 先引入一些基本概念和引理 矩阵的列拉直： 设= ( 口! ，) c ，记q = ( 口 a 2 f ，口。，) 7 ，( f _ 1 ，2 ， ) ，令 v e c ( a ) = 乱 口2 则称v p c ( 爿) 为矩阵一的列拉直( 列展开) 【4 2 1 弓i 理2 1 【1 6 】设爿c ，b c ”加，c c 9 瑚，则v e c ( a b c ) = ( c 7 。爿) v p c ( 占) 引理2 2 设彳c ，贝 j i i a i i ，= 1 1 v e c ( a ) l l ： 引理2 3 【4 习设4 c ，b c w q ， c c ”，矩阵方程允珊：c 有解的充分必 要条件为a a + c b + b = c ，在有解的情况下，a x b ：c 的通解为 2 a + c b + + 】，一a + a y b b + ( 2 4 ) 其中】，c ”9 是任意的，为矩阵爿的m o o r e p e n r o s e f s l 逆_ ；如果丘张：c 无解， 则a x b = c 的最小二乘解仍为( 2 4 ) ，并且a x b = c 的极小最小二乘解为z ：爿+ c b + 定理2 1 假设已执行了m 步的对称l 趾c z o s 过程，z 0 il a i l c z o s 向量v l ，v 2 ，v 。， 记为圪= v i ，v 2 以】，由l a n c z o s 方法或m i n r e s 方法得到方程组( 2 1 ) 的近似解， 可以表示为= x 0 + j ，。，则向后扰动a 的集合为 炙= 圪+ t ( 鼠一q 卢) i k 时c a r + k ( i 一) k r )( 2 5 ) 其中= x l l x 。并且 。2 匕+ - ( 鼠- e 。, a ) l l x 1 l ；1 = 一, - 1 l x i i ；1 i i a = ：i i ，= l l x 。酬匠j ，。- e , e l l ：= i m ：蚓f - l ( 2 6 ) ( 2 7 ) 求解线性方程组的总体( 拟) 极小向后扰动方法 证明类似于【1 5 】中的命题1 ，这里从略 下面研究用l a n c z o s 方法求解对称线性方程组( 2 1 ) 的总体极小向后扰动方法将 方程组( 2 1 ) 的近似解看作扰动方程 r a a ) x = b + j( 2 8 ) 的精确解将【，艿1 r 州”称为扰动方程( 2 8 ) 的总体向后扰动，并称满足 m i n l l t a ，司( 4 一弦= 6 + 以的总体向后扰动 ，司为最小总体向后扰动，记为 【，司“。下面的定理给出了用m i n r e s 方法求解对称线性方程组( 2 1 ) 时，总体向后 扰动 ，锄的表达式和最小总体向后扰动【，占l i i 。及其范数l i 【，6 k 忆 定理2 2 设靠是由m i n r e s 方法所得的对称线性方程组( 2 1 ) 的近似解， 【a ，翻r “”1 是满足扰动方程( 2 8 ) 的总体向后扰动，则 【，牛本务+ k ( 1 - ， ：k 瓯掣咽一) ( 1 + l l x a ：) “2 、”“ c ，占，。= ! j 生紫 肛蛳k 肚= 格= 务 其中足r “_ “) ，。2 a 一一靠和2 百可孝伊( 证明将工。代入方程( 2 8 ) 有 用矩阵乘法表示为 因为 a x m + 艿= 一，二 ( 6 n ：一 ll ( 2 9 ) ( 2 10 ) ( 2 1 1 ) ( 2 1 2 ) 南京航空航天大学硕士学位论文 ( 小矧= 南 由引理2 3 知，( 2 1 2 ) 的解为 m 2 本务+ k ( i - ， 其中k r 州”，并且 其中 ：掣鲁掣+ k ( i - c o , o j r ) ( 1 + 蚓伊2 。 h 巩。= 笔笋 脏蚶k 川，= 参 下面讨论求使i | 【，占】。忆达到最小 由( 2 1 3 ) ，有 肛郇k 川砷怒器 = n u n ( 2 1 3 ) ( 2 1 4 ) 蚪舰玩】r h 引修( 萼辩台 啪 显然p ，q 都是对称正定矩阵由c o u r a n t - f i s h e r 定理【1 】知， 幢，d 】。旺= 丸。( p ，q ) 其中九。( p ，q ) 是广义特征值问题a = z g 的最小特征值，因此得到如下定理 定理2 3 假设进行了m 步l a n c z o s 过程，x ，= + 心y 。是方程组( 2 1 ) 的近似解 一靠1 弋 r r 、，、i。， 。一。 血 = 口。生2 2 、i，三ij爿 ，虼一。卜h捌一卜一r 查堡垡壁查矍塑塑璺焦! 塑! 堡尘良星垫垫立垫 则恤，们。忆= 0 而，并且若p x = 旯q - x 对应于旯m ( p ，q ) 的特征向量为 = n ，：，吒+ 。r ，且q o ，则 y 。= 【也e ，也e ，吒。e r 证明类似于 1 7 中定理3 1 的证明，这里从略 2 3 总体极小向后扰动( t m i n b a c k ) 方法 由上节的理论分析，本节给出基于l a n c z o s 过程求解对称线性方程组( 2 1 ) 的总体 极小向后扰动( t m i n b a c k ) 方法 算法2 4 总体极小向后扰动( t m i n b a c k ) 算法 1 ) 选取初始估计确，计算5 6 一线，令= 蚓i v ，2 石r o ，记届v o 3 0 2 ) 对于j = 1 , 2 ，m ，执行l a n c z o s 过程 只“”，+ l 2 a v j 一口v ，一芦0 叶一i ： 其中q = 嵋一_ ，岛+ 。= i i a _ 一q _ 一岛_ 一。忆 3 ) 求九。( p ，q ) 及其对应的特征向量矿= 砭， 2 ，吒+ ，】7 ，则 y 。= 2 瓯，瓦砭，瓦。玩】7 ； 4 ) 构成( 2 1 ) 的近似解工，= + v y ， 为减少t m i n b a c k 方法的存储量，通常采用m 步循环t m i n b a c k 方法下 面给出求解对称线性方程组( 2 1 ) 的m 步循环t m i n b a c k 方法，即循环总体极小向后 扰动( r t m i n b a c k ) 方法( 肌) 算法2 5 循环总体极小向后扰动( r t m i n b a c k ) 算法( 埘) 1 ) 给出精度要求占，选取初始估计，计算，0 = b - a ，= a v o = 0 ， v ，2 舌 2 ) 对于，= 1 , 2 ，m ，执行l a n c z o s 过程 p i p i “= a v | 一a i v | 一p | vj i 、； 宣塞壁至堕垂丕兰堡主兰垡堡奎 其中口，= v ；4 v ，= i i a v 一口，v 一p i v j - , 0 3 ) 求丸，。( 尸，q ) 及其对应的特征向量为铲= 【砭， 2 ，吒+ 7 ，计算 y 。= 【 2 砭，吒 l ，吒。瓦1 7 ； 4 ) 若征，占】。忆= 0 露画 s ，构成近似解= + 圪，停止；否则 令x o ：= ，计算= 6 一瓴，令声= 1 1 , o l i ，v ，= 卢，转2 ) 2 4 数值实验 例2 1 设1 0 0 0 阶矩阵a 和1 0 0 0 维的向量b 分别为 a = 1 6 一1 5 6 0 1 一l06 0 6 1 6 2 2 1 6 1 0 6 一1 6 2 2 。= i ，取初始估计= ( ； ，应用算法2 t 和算法2 4 求解线性方程组c ：- ，结果如 表2 1 算法 m c p u 时间( 秒)： 算法2 1 1 51 4 4 3 04 1 6 1 1x1 0 5 2 01 5 1 2 01 0 0 3 3x1 0 。6 2 51 8 1 2 05 8 4 7 4 x1 0 _ 9 6 6o6“控“ 6 6 o oo挖乩o 6 o o 6砣6 o 6 6 。o。小6 o 。 。舶笼。 6 6 。也川。 6 6 。丝o。 5 2 6 o 艺0 6 o 垄坚垡壁查堡丝鲤璺堡! 垫! 堡尘塑星垫垫查鲨 算法2 4 1 5 1 0 8 2 03 8 8 6 4 1 0 5 2 01 3 8 2 0 9 3 9 4 3 1 0 “ 2 51 6 4 2 0 5 4 7 7 1 1 0 9 例2 2 设1 0 0 0 阶矩阵a 和1 0 0 0 维向量b 分别为 a = 一6l 一1 16ll 一1 1 6 l一1 1l611 1161 116 算法 ，挖 c p u 时间( 秒)： 精度 算法2 1 1 5 1 0 7 2 0 7 2 9 9 5 1 0 。 1 0 6 2 0 1 4 4 2 0 1 5 8 0 3x1 0 - 8 1 0 - 7 2 51 6 9 3 07 1 8 8 5 1 0 l l1 0 - 9 算法2 4 1 51 0 2 2 06 8 7 1 6 x1 0 “1 0 。6 2 01 3 8 2 01 4 8 9 5 1 0 - 8l o 7 2 51 8 4 3 02 1 5 6 1 1 0 。l l 1 0 。9 由表2 1 、表2 2 数值结果可见：在解对称线性方程组( 2 1 ) 时，算法2 4 比算法 2 1 的收敛速度更快，精度更高 下面考虑对称线性方程组( 2 1 ) 的系数矩阵为病态矩阵时，算法2 5 的有效性 h i l b e r t 矩阵是一个著名的病态矩阵，记为 2表 如 果 结q 程 方 性 线解求 4 2 2 互 鞑 表 和 法 算甩应 n _ i v = h 佶始初取 a = 1 以 1 n 1 - 1 l n - 1 - 1 三上l l , l n + 1n - i - 2 2 n l ( 2 1 6 ) c o n d ( a ) = 6 1 8 8 2 1 0 1 8 ；当，z = 5 0 时，c o n d ( a ) = 1 1 7 4 8 1 0 1 9 ；当n = 5 0 0 时， c o n d ( a ) = 6 3 2 4 2 1 0 2 0 可见h i l b c n 矩阵4 是一个严重病态的矩阵 例：s 设系数矩阵一如( 2 - a ，6 = ( i 取初始估计而= ( 0 ，精度要求为t 旷，根据矩阵爿中n 的不同取值，应用算法z s 求 表2 3 n 的取值 mc p u 时间( 秒) ： l ，占】删。i ， 3 070 0 4 0 00 0 0 6 24 8 3 9 4 x1 0 - 6 4 0 7 0 0 5 0 00 0 0 9 76 8 9 3 8 1 0 - 6 5 07 0 0 5 0 00 0 0 9 96 8 6 4 1 1 0 6 l o o1 00 2 6 0 0 0 0 0 8 42 3 0 5 2 x1 0 6 5 0 0 1 0 6 2 9 5 0 00 0 0 5 22 0 5 8 9 1 0 7 1 0 0 01 02 8 5 9 9 1 00 0 0 6 31 4 9 3 2 1 0 “ 从表2 3 可见，算法2 5 用于求解系数矩阵为病态的线性方程组( 2 1 ) 时，收敛效果 很好 求解线性方程组的总体( 拟) 极小向后扰动方法 例：4 设矩阵一如( 2 s ，a = 习 精度要求为1 0 一，应用算法2 2 和算法2 5 求解线性方程组( 2 1 ) 图2 1 其中n = 3 0 ，m = 7 ，算法2 为实线，算法5 为点划线 从图2 1 可见，算法2 5 的收敛效果很好，而算法2 2 出现了数值不稳定性 由表2 3 和图2 1 可以得出，算法2 5 特别适用于求解系数矩阵为病态矩阵的对称 线性方程组 、，lllllll，卜、 = 计 2 陆 图 始 如 初 果 取 结 南京航空航天大学硕士学位论文 第三章求解对称线性方程组的总体极小向后扰动方法 的收缩技巧 3 1 引言 近年来，人们为加快求解大型线性方程组迭代法的收敛速度，不断地尝试改进已 有算法，一种有效的改进方法是将原算法结合收缩技术【2 2 “ 1 9 9 5 年m o r g a n 提出 了带特征向量的重新开始g m r e s 算法【2 3 】具体做法是向k r y l o v 子空间加入少量模 最小的特征值所对应的特征向量，数值结果表明采用收缩技巧的重新开始g m r e s 算 法的收敛速度明显加快m j 1 9 9 7 年c h a p m a n 和s a n d 进一步发展了m o r g a n 提出的收 缩技术这一技巧越来越多地得到人们的重视 下面考虑循环总体极小向后扰动( i 玎m i n b a c k ) 方法的收缩技巧设v 1 ，v 2 ， 是l a n c z o s 过程产生的l a n c z o s 向量，m ，n ，n 是a 在k r y l o v 予空间七。( 一，t o ) 的k 个近似特征向量令f - m + k ，将y t ( f = l ，2 ，) 与v 。，v ：，v 。正交化得到向量组 v l ，v 2 ，l v 刖+ 2 ，v f ，记= 【v l ，v 2 ，m ，y 2 ，“】，矿= 【v 1 ，v 2 ，v 卅，l ，2 ，叶 ， q 是l x l 上h e s s e n b e r g 阵，其前m 阶顺序主子矩阵是l a n c z o s 过程产生的对称三对 角阵则有 a w = v i i t + 口，+ l v f + 1 衫( 3 1 ) 3 2 收缩l a n c z o s ( d l a n e z o s ) 过程 首先给出收缩l a n c z o s 过程( 记为d l a n c z o s ) 算法3 1 收缩l a n 娌o s ( d l a n 既o s ) 过程 1 ) 选取单位向量v l ； 2 ) 生成l a n c z o s 向量，对于_ ，= 1 , 2 ，聊，计算： a i = v r a v j ， 岛+ = i i 爿v ，一口，v - - f l j v j - 10 ； 查坚垡堡立堡塑箜篁堡! 塑! 壑尘旦亘垫塑互鲨一 p + 1 v j “= a v ，一a j v j 一卢j v 一l ； 3 、增加近似特征向量，对于，= m + l ，t 计算 a = v t a y m ( f = l 2 ，) ， = k 寺，匕6 ：， a ，+ i ，j v ，+ l = a l 一，一a 目v ， 为把收缩l a i i c z o s 过程应用于r t m i n b a c k 方法，可通过旷张成的子空间寻找 近似特征向量，【2 4 】给出求解如下特征问题 w 7 a 2 w g = t w 7 a w g ( 3 2 ) 取其k 个模较小的特征值所对应的特征向量蜀，9 2 ，凰，则m = w g , ( i = 1 2 ，t ) 为所 求的近似特征向量于是可给出求解线性方程组( 2 1 ) 的循环收缩总体极小向后扰动 ( d r v i i n b a c k ) 方法 3 3 循环收缩总体极小向后扰动( d r t m i n b a c k ) 方法 算法3 , 2 循环收缩总体极小向后扰动r t n b a c 岣算法 1 ) 给出精度要求占，选择初始向量，计算r 0 = b - a x 。，卢= l 1 1 ，v ，= r o 卢， 届v 0 = 0 ，并选择适当的正整数m ，k ，记f = m + k ； 2 ) 执行m 步l a n c z o s 过程得到标准正交向量组碟o 和对称三对角矩阵s 。( o ； 3 ) 求日的特征值和特征向量，选取k 个绝对值最小特征值所对应的特征向量 吐，破，畋，定义y = 嘤【匾，如，畋1 = 【儿，y 2 ，虬】； 4 ) 对，= l 2 ，执行算法3 1 ，得到向量组矿和矩阵日； 5 ) 求九。( j p ，q ) 及其对应的特征向量为i = 啊，也，e + 。r ，则 y l = 【吒e ，五日，曰+ 。e r ； 6 ) 若怄，占】。忆= = 聂而 占，计算x ，= + r y ，停止；否则，令：= x ， 转7 1 ； 7 ) 记矿= 【v 1 ，屿，以，y 】，解特征值问题7 a 2 矿g = 朋r 7 a w g ，取其k 个绝对值 最小特征值所对应的特征向量g 。，g ：，g 。，计算y ，= w g ，( f - 1 , 2 ，t ) ，令 y = 【y i ，y 2 ，y 】，转4 ) 3 4 数值实验 例3 , 1 已知条件同第二章例2 1 ，用循环总体极小向后扰动方法( 算法2 5 ) 和 循环收缩总体极小向后扰动方法( 算法3 2 ) 求解线性方程组( 2 1 ) ，结果如表3 1 表3 1 算法c p u 时间( 秒) ：雌，卅。忆 精度 算法2 ，5 4 5 0 6 01 9 5 1 6 l o 1 56 0 1 4 3 1 0 2 11 0 。2 0 ( m = 1 5 ) 3 3 8 5 03 9 1 4 2 1 0 1 55 2 3 3 3 1 0 1 61 0 2 5 算法3 2 3 9 1 5 02 4 0 2 5 1 0 1 65 8 9 1 6 x1 0 2 11 0 - 2 0 f m = l 5 k = 2 ) 5 9 0 9 08 7 3 3 0 1 0 1 61 4 9 5 4 1 0 - 2 7l o 2 5 由表3 1 可见，算法3 2 是求解对称线性方程组的有效方法之一 求解线性方程组的总体( 拟) 极小向后扰动方鎏 第四章求解非对称线性方程组的总体拟极小向后扰动 ( t q m b a c k ) 方法 4 1 引言 考虑非对称线性方程组问题 出= 6 ( 4 ，1 ) 其中4 足且为非奇异矩阵，x ，b r “ 求解非对称线性方程组( 4 1 ) 的k r y l o v 空间方法有许多特殊形式，如a m o l d i 方法、 i o m 方法、非对称l 翮c z 0 s 方法、g m r e s 方法、q m r ：s 法等k a s e n a u y 和s i i l l o n c i n i 、 曹志浩研究了基于a m o l d i 过程求满足扰动方程口一h = 6 + 占的近似解使总体向后 扰动范数0 【，8 1 1 ，极小化的方法本章研究基于非对称l a n c z o s 过程求解非对称线性方 程组( 4 1 ) 的总体拟极小扰动方法求解非对称线性方程组( 4 1 ) 的非对称l a n c z o $ 方法旧 可描述如下 算法4 1 非对称l a n c z o s 算法 1 ) 选取方程组( 4 1 ) 的初始估计，计算，0 = b - a x 。，= v l = 鲁， 令= v t ，届v 0 = ，1 w o = 0 2 ) 对坍= l 2 计算 屯“= 彳一口。一风一i ， 吮+ i = a 7 一一- 1 ， = ( 爿，) ， 选取+ 和风使+ 。风+ 。= ( 屯+ p 以+ 。) k + ，= 吒。r + l + 。；吃+ 。尾。 南京航空航天大学硕士学位论文 3 ) 记= i v , ，v 2 ，v m ，以= q 屈 ，2 0 _ ： 。 0 0 - t0 ： 。0 屁 0 y ma 。 4 ) 计算= x o + f l v e ；, 1 e 1 ，老：l l b - a x o l l ： 占，则停止：否则，继续 若非对称l a n c z o s 方法不发生中断，则l a n c z o s 向量组v 1 ，v 2 ，v ，构成k r y l o v 子空间以即，r o ) = s p a n ( r o ，a r o ，a 2 ，a “t o ) 的一组基 记或= ( 晨， 嵋玑删n 由算乩t 得 a 圪= + 。或 则残量为 _ = 6 一瓴= 屹。( f i e 。一也) 如果也奇异，则计算形成近似解f r e u n d 和n a e h t i g a l 8 1 考虑求使 i 也一q i i ：极小化，从而求得( 4 1 ) 的近似解靠：知+ 圪相应的方法称为拟极小 残量法记为q m r 方法 算法4 2 q m r 算法 1 选择方程组( 4 - 1 ) 的初始估计值，令2 6 4 ，记= 1 1 1 1 ， v l = 鲁；令 w i = v l ；取届v 0 = n w o = 0 ： 2 ) 执行m 步l