（计算数学专业论文）收缩和扩张krylov子空间方法.pdf

收缩和扩张k r y l o v 子空间方法 摘要 本文研究解大规模稀疏线性方程组的收缩和扩张k r y l o v 子空间方法在科学计 算中，尤其是在解大规模稀疏线性方程组时，k r y l o v 子空间方法显示出与众不同的 有效性当矩阵是对称正定时，常用的方法是具有短递推的共轭梯度方法( c g ) 但是 在许多情况下，系数矩阵不是对称的，这时常用的方法中有完全正交化方法( f o m ) 和广义最小残量方法( g m r e s ) 矩阵的非对称性导致这两种方法不具有短递推的 性质由于存储量和计算量的限制，这两种方法通常需要重开始研究表明，如果 系数矩阵具有模很小的特征值，那么k r y l o v 子空间方法一般会收敛得比较慢对 重开始方法来说，k r y l o v 子空间维数比较小，有时并不含有跟模很小的特征值对 应的特征向量，或者不含有相应的好的近似向量因此，重开始方法收敛得更慢， 甚至会停滞收缩和扩张的k r y l o v 子空间方法正是因为这个原因而被研究者提出 来其基本思想是用跟模最小的特征值对应的近似特征向量扩张k r y l o v 子空间， 以达到收缩小特征值，从而加快收敛速度的目的本文对收缩和扩张k r y l o v 子空间 方法作了全面的介绍，并研究了它们的收敛性本文根据前人的思想提出了解广义 s y l v e s t e r 方程的完全正交化方法和最小残量方法在此基础上把重点放在应用收缩 和扩张k r y l o v 子空间技术于s y l v e s t e r 方程和广义s y l v e s t e r 方程近年来，许多 人对如何快速求解这两个方程作了深入的研究，提出了不同的方法但是据作者所 知，本文提出的方法应该是解s y l v e s t e r 方程和广义s y l v e s t e r 方程的第一个加速方 法本文所使用的近似解空间是由两个扩张的k r y l o v 子空间作k r o n e c k e r 积得到 的子空间解空间的基表示为这两个扩张的k r y l o v 子空间的基的k r o n e c k e r 积， 称为k r o n e c k e r 乘积基这种方法在具有加速收敛的同时，也比应用于线性方程组 的通常的扩张k r y l o v 子空间方法需要少很多的存储量非常适合大规模s y l v e s t e r 方程和广义s y l v e s t e r 方程的求解 关键词：扩张k r y l o v 子空间；扩张a r n o l d i 过程；g m r e s 方法；f o m 方 法；r a y l e i g hr i t z 过程；调和r a y l e i g hr i t z 过程； r i t z 值；r i t z 向量；调和 r i t z 蓬；谖季雾r i t z 意萋；最小残量方法；完全歪交毙方法；s y l v e s t e r 方程；广义 s y l v e s t c r 方程 d e f l a t e da n da u g m e n t e dk r y l o vs u b s p a c em e t h o d s a b s t r a c t t h i sp a p e ri sc o n c e r n e dw i t hd e f l a t e da n da u g m e n t e dk r y l o vs u b s p a c em e t h - o d sf o rs o l v i n gt h el a r g es y s t e m so fl i n e a re q u a t i o n s i ti sw e l lk n o w nt h a tt h e c o n v e r g e n c eo fk r y l o vs u b s p a c em e t h o d sd e p e n d st oal a r g ed e g r e e0 nt h ed i s t r i * b u t i o no fe i g e n v a l u e so ft i l ec o e f f i c i e n tm a t r i x i ft h e r ea r es m a l le i g e n v a l u e s ，t h e n r e m o v i n go rd e f l a t i n gt h e mc a 2 1g r e a t l yi m p r o v et h ec o n v e r g e n c er a t e s l i k e w i s e i f o rt h ep r o b l e mo fc o m p u t i n ga ne i g e n v a l u e ，d e f l a t i n gn e a r b ye i g e n v m u e si sh e l p f u l + o n ew a yt h a te i g e n v a l u e sc a nb e e nd e f l a t e di sf o rt h ec o r r e s p o n d i n ge i g e n v e c t o r s t ob ei nt h es u b s p a c e o n c eak r y l o vs u b s p a c eg r o w sb i ge n o u g h s o m ed e f l a t i o n o c c u r sa u t o m a t i c a l l y h o w e v e r ，r e s t a r t e dm e t h o d sm a yn o td e v e l o pal a r g ee n o u g h k r y l o vs u b s p a c ef o rt h i sa u t o m a t i cd e f l a t i o n ，a n dc o n v e r g e n c et h e ns u f f e r sa c c o r d - i n g l ya l s o ，e v e ni fa p p r o x i m a t ee i g e n v e c t o r sd od e v e l o pt h a ta r ea c c u r a t ee n o u g h f o rd e f l a t i o n 。t h e yo n l yf o rt h a tc y c l ea n dm a yn e e dt ob ed e v e l o p e da f t e rar e s t a r t ，t h ea u g m e n t e dk r y l o vs u b s p a c em e t h o d si n c l u d et h ea p p r o x i m a t ee i g e n v e c t o r s d e t e r m i n e df r o mt h ep r c v i o u ss u b s p a c ei nt h en e ws u b s p a c e t h i sd e f l a t e st h es m a l l e i g e n v a l u e sa n dt h u si m p r o v et h ec o n v e r g e n c e i nt h i sp a p e r ，w ei n t r o d u c et h ea u g - m e n t e dk r y l o vs u b s p a c em e t h o d sa l g o r i t h m sa n dg i v et h er e s u l t so i lt h ec o n v e r g e n c e o ft h ea u g m e n t e dk r y l o vs u b s p a c em e t h o d s t h e s em e t h o d sa r ee q u i v m e n tt oe a c h o t h e r ，b u tt h e i ri m p l e m e n t sa r ed i f f i e r e n t w ea l s oc o m p a r et h e i ri m p l e m e n t s i n t h i sp a p e r ，w ef o c u so na p p l y i n gt h ed e f l a t e da n da 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 et os o l v i n gt h es y t v e s t e re q u a t i o na n dt h eg e n e r 畦i z e ds y l v e s t e re q u a t i o n ，b y o u rk n o w l e d g e ，t h e s em e t h o d si nt h i sp a p e rs h o u l db et h ef i r s tk i n do fa c c e l e r a t e d m e t h o d sf o rs o l v i n gt h e8 y l v e s t e re q u a t i o na n dt k eg e n e r a l i z e ds y l v e s t e re q u a t i o n 。 n u m e r i c a le x p e r i m e n t si nt h el a s tc h a p t e rs h o wt h a tt h ea u g m e n t e dk r y l o vs u b s p a c e m e t h o d sa r ev e r ye f f i c i e n t i n k e y w o r d s ：a u g m e n t e dk r y l o vs u b s p a c e ；a u g m e n t e da r n o l d ip r o c e s s ；g m r e s ；f o m ；r a y l e i g hr i t zp r o c e s s ；h a r m o n i cl h y l e i g hr i t zp r o c e s s ；r i t zv a l u e ； r i t zv e c t o r ；h a r m o n i cr i t zv a l u e ；h a r m o n i cr i t zv e c t o r ；m i n i m a lr e s i d u a lm e t h o d ； s y l v e s t e re q u a t i o n ；g e n e r a l i z e ds y l v e s t e re q u a t i o n 指导教燎： 曹志浩教授 指导小组成员 曹志浩教授 薛军工教授 魏鼗民一| l 教授 l l 繁一耄妻冬言 在现代科学计算中。我们经常需螫求解大型稀疏的线性方程组 矗嚣= 玉 ( 1 0 1 ) 其中a 船“是非奇异矩阵，b 桫， 是待求的未知向量这些线性方橼 组常常来自于用有限差分或有限元对偏微分方程的离散 4 l 此时矩阵a 一般是稀 藏戆，郅它的夫多数元素为零。女l 侮求勰这类阉题毫蔽鸯数篷线瞧代数疆壤戆磷巍 热点之一 由于瓶阵a 是稀疏的，我们一般使用迭代方法解这类方程组在这些迭代方法 中，k r y l o v 予空惩类方法嚣戈其往盎，越来越受到大家驰重视。遥几卡年寒，基予 k r y l o v 子空阐，研究者掇嬲了各种各样的方法，并对这些方法进行了深入的研究当 系数矩阵以是对称正定时，最常用的方法是共轭梯度方法【l ，2 ，3 ，1 8 ，1 9 ，2 1 ，2 3 ，3 9 】 但是在大多数情况下，矩阵a 不是对称正定的针对这种情况，人们糖如了b c g 2 4 ， c g s 4 5 ，b i c g s s t a b 4 9 ，f o m 4 1 ，g m r e s 3 7 等方法在这些方法孛，完全援 交化方法( f o m ) 和广义最小残量方法( g m r e s ) 非常重要，因为目前发展出来的 诸多方法都借鉴了它们的恩想 氍究表疆，在簿线羧方程缝时，k r y t o v 予空瓣穷浚懿皎敛睦穰夫程度上蒗赣予 特征值的分布当有小的特征值出现时，如果我们把小的特征值收缩摊，那么k r y l o v 子空间方法的收敛速度会有很大的提商同样在计算特征值时，收缩掉附近的特征 傻也能提窝收敛速度，当对应的持征向爨在子空闻里瓣对，小的特蔹馕也就牧鳙簿 了鳃果k r y l o v 子空阉静维数越来越夫，跟小将锺激稆对应的特徽向量很有可熊 就在k r y l o v 子空间中，因此这时候收缩就自动发生然而，对重开始的方法来说， k r y l o v 子擞间的维数是固定不变的，这熙特征向量并不会在k r y l o v 子空间中，城 者它】与k r y l o v 予空壤酶距离著甭会稷，j 、，嚣就救壤不会妻凌窭褒，踅对敦簸速 度可能会很慢，或者会出现停滞现象收某个循环中，跟小特征值相对应的特征向 量与k r y l o v 子空间的距离有可能比较小，因此在这个循环中，收缩会出现但摄 在下一个罐璎，势不一定会毒琵上垂戆揍援。 因此，为了加快k r y l o v 子空间方法的收敛速度，我们需要收缩系数矩阵的将 1 征值常用的技术有预条件 1 4 和扩张k r y l o v 子空间 9 ，2 2 ，2 9 ，3 1 ，3 2 ，3 8 这两 种技术的相同之处是都使用了近似特征向量但是不同之处在于前者用近似特征向 量构造预条件矩阵，而后者把近似特征向量加入到k r y l o v 子空间因此后者称为 扩张的k r y l o v 子空间方法本文主要研究后者研究表明，在k r y l o v 子空间中加 入特征向量或近似特征向量后，可以达到收缩矩阵的特征值，进而加快迭代方法收 敛速度的目的数值实验表明如果加入的是近似特征向量，在近似特征向量不是很 精确时，这些方法同样具有很快的收敛速度 现在我们给出本文常用到的一些记号鼢表示由所有n ，n 的矩阵构成 的空间；时表示n 维向量空间；( ，) 表示e u c l i d e a n 内积；”1 1 2 表示e u c l i d e a n 范数；厶表示nxn 的单位矩阵；k “。表示由n + 1 n + 1 的单位矩阵的前 n 列构成的矩阵；e 表示n 维向量空间的第m 个坐标向量；户k 表示次数不超 过m 的多项式全体；焉表示常数项为l 的，次数不超过r n 的多项式全体，即 焉= 扫：p p m 且p ( o ) = 1 文章的以下章节是这样安排的：第二章简要介绍a r n o l d i 过程及其相关的方 法，这些算法包括解线性方程组的f o m 算法和g m r e s 算法，求特征值和特征 向量的r a y l e i g h r i t z 方法和调和r a y l e i g h r i t z 方法具体细节请参阅文献f 5 ，1 2 ， 1 8 ，3 5 ，4 2 】；第三章详细介绍扩张的a r n o l d i 过程，以及扩张的k r y l o v 子空间方法 不同的实现方式；第四章主要介绍扩张的k r y l o v 子空间方法一些基本理论从这 些理论，我们可以知道扩张的k r y l o v 子空间方法有效的原因；在第五章，我们介 绍s y l v e s t e r 方程和广义s y l v e s t e r 方程，并应用扩张的k r y l o v 子空间方法来解这 两个方程；第六章包含一些数值实验这些数值实验表明扩张的k r y l o v 子空间方 法在解一些困难问题时是非常有效的 2 第二章a r n o l d i 过程及其相关的方法 在这一鬻我们给出a r n o l d i 过程5 ，3 9 ，4 0 ，4 2 ，弗讨论四个基于a r n o l d i 过稷 的迭代方法，其中两个遗代方法用来解线性方程组，另外两个迭代方法计算特征值 秘特征囱爨，这四个方法都尾k r y l o v 予空闻疋。( ) is p a n v ，a v ， ”- 1 ” 传 为近议子掇阕。 2 1a r n o l d i 过程( a r n o l d ip r o c e s s ) 给定k r y l o v 子空间j c 。( “) ，我们_ 町以用下面的a r n o l d i 过程生成k r y l o v 子空 间尼。( 口) 的一组规范正交耩，并且还可以得到一些有用的关系式 算法2 1 1 。a r n o l d i 避撩( a r n o l d ip r o c e s s ) j 定义t 7 l t ，翊口瞄 2 循环：j = 1 ，2 ，m 坩一a v j ； h i ，j v t w ，w 一钳一，毽，l 一1 ，2 ，- 一，j i h 5 + 1 j = 1 1 训f 2 ，如莱h j + 1 j = 0 ，那么a r n o l d i 过程停止； v i + i = + l 定义筑簿= 晦i 。v 2 ，】。癸多睫义一个( 钉；+ 1 ) m 懿上h e s s e n b e r g 缒 阵丢乙，它的非零元由上筒的算法给出，设珥。是由磊k 的前m 行构成的矩阵幽 上面的a r n o l d i 过程，我们可以有如下一魑结论f 3 9 ： l ，v 2 ，是k r y l o v 予空闻尼。( 口) 晦一组援范燕交基； a 一+ i 矗= 。十k 托m 十l e 荔； 嵋a 一日。 2 。2 完全正交方法f o m ) 和广义最、残量方法( g m r e s ) 给定初始向量z o ，我们可以得到( 1 , 0 1 ) 的残量方程组a z = r o ，其中r 0 一 b a x o 称为视始残向量。然后我们希望扶k r y l o v 子象闻中找到一个满足一定条件 静，使缳z 。= 。o + 爨更好熬近儆勰。 3 在【3 7 ，s a a d 等给出了完全正交方法( f o m ) 和广义最小残量方法( g m r e s ) 他 们所选的子空间是跟初始残量7 o 对应的k r y l o v 子空间 ，m ( t o ) ；s p a n r 0 ，a r o ， a m - - 1 r 0 ) 为了便于以后阐述，我们在这一节给出基于一般的k r y l o v 子空间。( ) 的完全正交方法( f o m ) 和广义最小残量方法( g m r e s ) ，即是说，u 不一定跟初始 残量共线由于存贮限制，我们使用重开始的完全正交方法( f o m ( m ) ) 和广义 最小残量方法( g m r e s ( m ) ) 算法2 2 1 重开始完全正交化方法( f o m ( m ) ) 给定初始近似解z o ，得到初始残向量o = b a x o ，定义残向量方程a z = r o 2 给定一个向量 ，应用a r n o l d i 过程得到k r y l o v 子空间厄，。( u ) 的一组规范正交 基v 1 j ”2 ，u m 3 求残向量方程a z = 7 b 的近似解z 。尼。( u ) ，使得它满足下面的正交条件： r 。= r 0 一a ：。上瓦。扣)( 2 2 1 ) 得到新的近似解o 。= o o + z r n 如果新的近似解不是足够精确，x o ：= z 。， t o ：= r m ，返回到2 i 否则，停止 因为厄。( ”) ，所以存在d 。瓞”，使得钿= d 。于是 y m = 1 0 一a z m = 7o a l ，m d m = o l ，m 日m d m h m + l , m v m + 1 e m t d m 由正交条件( 2 2 1 ) ，可得 d m = 蠕m 所以我们有如下的新的残向量表达式 r 。= 啊一蠕r 0 一k + l , r a 。+ 1 e 磊d m ( 222 ) ( 2 2 3 ) 如果r o 尼。( ) ，那么= v 5 , 0 此时新的残向量为= 一，h 扎。 。+ l e 三 由( 2 2 3 ) ，我们容易得到下面这个引理 引理2 2 2 如果r o k 。( 口) ，那么f o m 方法的残向量r 。= 一h m + l , m o m + l e 三，其 中d 。是线性方程组俾2 到的解于是t m 与 。+ l 共线，并且l | r 。1 1 2 = l h m + l , m e ：d 。i 当 = 7 0 时，得到跟 3 7 中的方法相同的重开始完全正交化方法 4 算法2 2 3 重开始广义最小残量方法( g m r e s ( m ) ) j 给定初始近似解。o ，得到初始残向量7 o = b a x o ，定义残量方程a z = 7 o 2 给定一个向量 ，应用a r n o l d i 过程得到k r y l o v 子空问j c 。( u ) 的一组规范正交 基 l ，y 2 ， m 3 求残量方程a z = r 0 的近似解丘。( 口) ，使得它满足下面的残量最小条件： 盯, d t p ：m c 。i n ( 。) l i f o a 。1 2 ( 2 2 4 ) 得到新的近似解z 。= x 0 + z 。如果新的近似解不是足够精确，x c ) ：2o m ， 7 0 ：= r 。，返回到2 i 否则，停止 同样令z 。= d m 于是 窿= ：职。) 怖一月2 腱 2 d r a 。p i n l i f o a v d i i ； 2 船怖一+ t h m 媚 = 躲憎一+ 蠕- ) r 。十+ ，( t + - r o 一如d ) 惦 = 忡一嘿) 圳+ 躲| | 唿l r 0 一? m d l l ； ( 2 删 由式( 2 2 5 ) ，我们容易得到下面这个引理 引理2 2 4 如果r 0 尼。+ 1 ) ，那么i i r 。1 1 2 = r a i n d e r 。1 | t + l r 0 一百。r i l l 2 然而不 论珊_ k = 。+ 】( v ) 是否成立，为了求得，我们都只需要解最小二乘问题 d r r a i n 。8 t + ，r 。一，d l l 2 只是当疋。+ l ( ) ，残量误差可以用| | 0 2 = | | 嘿l r o t _ _ i r n d m l l 2 求得当u = r o 时，得到跟f 3 7 中的方法相同的重开始广义最小残量方法 2 3 求近似特征值和近似特征向量的方法 大部分求大型稀疏矩阵a 的特征值和特征向量的方法都会生成一个子空间序 列k ，这个子空间序列包含的向量越来越近似于想要的特征向量在这些方法中， 核心问题是如何从子空间w b 求得想要的近似特征值和特征向量我们舍去子空间 序列的下标，设矩阵的列向量是子空间w 的一组规范正交基定义近似特征 5 值为0 ，近似特征向量为口= w g 常用的技术称为r a y l e i g h - r i t z 过程 3 5 ，4 2 ，它 满足g a l e r k i n 条件，即残向量f = a y o y 满足 i 上w 于是我们有 w 7 ( a w g o w g ) = 0 ， 即我们可以通过求特征值问题 w 7 a w g = 的 而得到a 的近似特征值和近似特征向量这些近似特征值和近似特征向量分别称 为r i t z 值和r i t z 向量下面的算法详细描述r a y l e i g h r i t z 过程 算法2 3 1 r a y l e i g h r i t z 过程 j 生成m 维子空间w j 2 计算子空间w 的一组规范正交基w i 3 计算矩阵h = w 7 a w ； 4 计算矩阵h 的特征对( o i ，讥) ，i = 1 ，2 ，m ，其中怕i 2 = 1 那么巩是矩阵a 的近似特征值，称为r i t z 值；吼= 吼是矩阵a 的近似特征向量，称为r i t z 向量如果r i t z 残向量范数| j a 执一0 , 瓠l l2 足够小，停止；否则，生成新的m 维 子空间w ，返回到2 另一种常用的从子空间w 得到近似特征值和近似特征向量的方法应用调和 r a y l e i g h - r i t z 过程，它满足p e t e r o v - g a l e r k i n 条件，即调和r i t z 残向量f = 锄一 满足 f 上a w 于是我们有 w 7 a 7 ( a w 口一目口) = 0 ， 即我们可以通过求广义特征值问题 w 7 a 7 a w j = 日7 a 7 w 而得到a 的近似特征值和近似特征向量这些近似特征值和近似特征向量分别称 为调和r i t z 值和调和r i t z 向量下面的算法详细描述调和r a y l e i g h - r i t z 过程 6 算法2 3 2 调和r a y l e i g h - r i t z 过程 j 生成m 维子空间w i 2 计算子空间w 的一组规范正交基w j 0 计算矩阵h = w t a t a w 和g = w 7 a 7 p y i 4 计算广义特征值问题何鱼= 以g 执的特征对( 巩，执) ，i = 1 ，2 ，m ，其中i | 雪1 1 2 = 1 那么吼是矩阵a 的近似特征值，称为调和r i t z 值；执= w 血是矩阵 的 近似特征向量，称为调和r i t z 向量，如果调和r i t z 残向量范数0 a 执一或 j fj 1 2 足 够小，停止；否则，生成新的7 n 维子空间w ，返回到2 在r a y l e i g h r i t z 过程和调和r a y l e i g h r i t z 过程中，我们常用的子空f 司是k r y l o v 子空间坛。( w ) 我们希望从这个子空间中找到矩阵a 的近似特征向量由上面的 a r n o l d i 过程，我们可以得到k r y l o v 子空间k 。( u ) 的一组规范正交基于是近 似特征向量可以表示为 y = 9 在基于a r n o l d i 过程的求近似特征值和近似特征向量的方法中5 ，4 0 ，4 2 ，相应地有 两种不同的方法第一种方法称为a r n o l d i 方法，它使用r a y l e i g h - i i i t z 过程于是 我们可以得到r i t z 对( 耿，矾) ，z = 1 ，2 ，m ，其中执= 或，( 0 ；，血) 是矩阵上n 的 特征对 对每个r i t z 对慨，m ) ，r i t z 残向量为 = a 1 0 执一以l 厶鱼= ( 月m + h m + l , m t h + 1 e ：) m 一吼a = h m + l , m e m t m - u m + l 定义犀= h m + l , m e 。t 吼，于是 = a y i 一日。玑= 厚“ 。+ l ，( 2 36 ) 并且 酬2 = i 届一 ( 2 3 7 ) 由引理2 2 2 和( 2 3 6 ) ，我们容易得到下面的引理 引理2 3 3 如果t o 天m ( ) ，对i = 1 ，2 ，m ，f o m 方法的残向量r 。和r i t z 残 向量 共线它们都可以表示为+ 1 的倍数 7 下面列出求a 的近似特征值和近似特征向量的a r n o l d i 方法 算法2 3 4 a r n o l d i 方法 j 开始：选择初始向量u ，对它进行规范化，得到 1 i 2 迭代；使用7 n 步a r n o l d i 过程，得到胁彬o v 子空问。( ) 的一组规范正交基； 3 求近似特征对：求矩阵h 。的特征对( 或，鱼) 0 i 为r i t z 值计算r i t z 向量 纨= v 赢虫 4 重开始：由偿3 刀计算r i t z 残向量的范数如果足够小，停止程序；否则，选 择一个新的范数为1 的初始向量，转到2 我们注意到，在上面算法的步骤4 中，新的初始向量难于选择一种选择方法 是，选择初始迭代向量为希望计算的某些特征值对应的r i t z 向量的线性组合然 而，如果组合方式不正确，所得到的初始迭代向量并不利于计算近似特征值和近似 特征向量 3 3 s o r e n s e n 的隐式重开始a r n o l d i 方法( i r a ) 4 6 】很好地解决了这个 选择新的初始迭代向量的问题它对且。使用q r 迭代，然后r i t z 向量的正确组 合得以形成【3 3 】 我们已经知道求近似特征值和近似特征向量的a r n o l d i 方法本质上是基于k r y l o v 子空间的r a y l e i g h r i t z 过程它不容易找到内部特征值，即不容易找到靠近原点的 特征值，主要是因为k r y l o v 子空间不一定包含能很好近似内部特征向量的向量， 还因为r a y l e i g h r i t z 过程本身的特性当矩阵对称时，r a y l e i g h - r i t z 过程能最优 地从k r y l o v 子空间抽出外部特征值3 5 】，但是对内部特征值却没有这种最优性质 3 4 当矩阵非对称时，r a y l c i g h - r i t z 过程一般也具有上面这种特性为了计算内 部特征值，在【3 0 ，m o r g a n 给出了调和a r n o l d i 方法，它基于调和r a y l e i g h - r i t z 过 程于是我们可以得到调和r i t z 对( 。执) ，i = 1 ，2 ，t r t ，其中执= 执，( 日。鱼) 是广义特征值问题 碟风蠡= ( 碟h m + 纛+ 。，。e 。e ：) 执= 瓯碟亟 的特征对 下面的几个引理刻画了g m r e s 残向量和调和r i t z 残向量吒ia 执一巩识的 一些性质 引理2 3 5 g m r e s 方法的残向量磊上s p a n a v k ) 8 证明因为z 。z o 十瓦。( ) ，所以z 。= + v 鲁d m ，d m r 由g m r e s 方法的 最小残量属性，g m r e s 方法的残向量 2 m 。r a i n ( 。) a 圳2 _ 蛐m i n 。一a d l l 2 于是w s p a n a y m 口 由调和r i t z 值和调和r i t z 向量的定义，我们有下面这个引理 引理2 3 6 调和r i t z 残向量f ；j _ s p a n a ) ，i = l ，2 ，- 一，m 当g m r e s 方法的初始残向量7 0 咒。( ) 时，下面的引理表明g m r e s 残向 量和调和r i t z 残向量共线 引理2 3 7 如果g m r e s 方法的初始残向量r oe 。( ) ，那么g m r e s 残向量 和调和r i t z 残向量噍，i = 1 ，2 ，- ，m 共线 证明因为吒ia i j ；一瓯执= a 执一鼠执，所以托厄。+ l ( ) 因为初始残向量 r o k 。( w ) ，所以可说明磊c m + l ( ) 由引理2 3 5 和引理2 3 6 ，和吃都垂直 于a e 。( u ) ，所以g m r e s 残向量和调和r i t z 残向量吒共线 口 下面列出求a 的近似特征值和近似特征向量的调和a r n o l d i 方法 算法2 3 8 调和a r n o l d i 方法 开始；选择初始向量 ，对它进行规范化，得到 l i 2 迭代：使用m 步a r n o l d i 过程，得到k r y l o v 子空间k 。( ) 的一组规范正交基； ，求近似特征对；求广义特征值问题( 醒目。+ h 象“。e 。e ：) 口= 5 h 釉的特征对 ( o i ，执) ，其中以为调和r i t z 值计算调和r i t z 向量执= 亟i 4 重开始：计算调和r i t z 残量f 。ja 执一反执的范数如果足够小，停止程序；否 则，选择一个新的范数为1 的初始向量，转到2 9 第三章扩张的a r n o l d i 过程及相关算法 3 1 扩张的a r n o l d i 过程 给定扩张的k r y l o v 子空间尼= 尼。( r o ) 十w ，其中 w = s p a n w ) = s p a n w 1 ，1 1 7 2 ， 女 我们知道扩张的k r y l o v 子空间瓦的一组基为r o ，a r o ，a m - - 1 t o ， 1 2 ，w 通过扩张的a r n o l d i 过程，我们可以得到扩张的k r y l o v 子空间尼的另一组基 u 1 ，”2 ， u m ，l ， t 0 2 ， k 和一个重要的关系式 算法3 1 1 扩张的a r n o l d i 过程( a u g m e n t e da r n o l d ip r o c e s s ) 1 定义 l = r o 川怯 2 循环：j = 1 2 ，一， ；+ 如果j m ，那么w a v j ，否则= a 1 q m i h i j = ( ，忱) ，= 一 k j v i ，i = 1 ，2 ，。，j i b + l ，j = 1 1 w 1 1 2 ，如果 什1 ，= 0 ，那么扩张的a r n o l d i 过程停止； u j + 1 = 畸+ l r 定义两个矩阵 z m + k ip 1 ，v 2 ，- - ，u 2 3 1 u 2 ，- 一，k j ， v r m + k + li u 1 ，u r n + + 1 】 另外定义一个( m + + 1 ) ( m + 女) 上h e s s c n b e r g 矩阵且。+ k ，它的非零元由上面 的算法给出 由扩张的a r n o l d i 过程，我们可以得到如下结论【3 8 】： u l ，v 2 ，1 h ， f l l l ， 2 ，t “是扩张的k r y l o v 子空间的一组基； ”l ，他，v r r t + k + 1 是一组规范正交的向量； a z 。+ k = 1 ，新k + 1 k + k 定义卢= l i t o 怯我们从仿射空间勒+ 。( r 0 ) + w 中找到最小残量解因为残 1 1 向量为 r = b a ( x o + z m + i , y ) = r 0 一a + k y =7 0 v 二+ k + l 且n + 删 = v m + k 十l ( p e l 一啊。+ ) 所以，对最小残量方法，我们有 恻”俩m i n 恤一+ k 啪 解这个最小二乘问题，可以得到y ) 进而可以求得近似解。= 2 ：0 + z 。+ k y 在f 3 8 1 中，s a a d 给出了下面这个定理 定理3 1 2 如果存在一个向量w w ，使得对某个1 曼t 冬m ，满足a w = 仇+ l 并 且h ；非奇异，那么，仿射空间。o + 。( 7o ) 十w 中包含线性方程组a x = b 的精 确解 注3 1 3 如果定理对i = 0 成立，此时j 4 = l ，即也可以说存在w 使得a w = r o ， 显然结论也成立，尽管这时风不存在 在上面定理的条件成立的情况下，扩张的g m r e s 方法可以得到精确解，这是 由于扩张的g m r e s 方法的最小化属性其它的投影方法，如正交投影也可以的得 到精确解，这是由于当残量为0 时，总满足残量正交性定理可以推广到条件：如 果存在一个向量t u oew ，使得对某个咖丘m + l ( r o ) 并且u o = a q o ( a ) r o ，其中q o ( t ) 是次数小于或等于n i 的多项式且q o ( o ) = 1 ，满足a w e = 咖假设 0 0 ，w o 为满足条 件的向量，我们知道残向量可以表示为r = r o a v a w = q ( a ) r o a w ，其中口 o ( r 0 ) ，w w ，q ( t ) 是次数小于或等于m 的多项式且q ( 0 ) = 1 我们取”= ；1 w o ， 则有r = q ( a ) r o a w = q ( a ) r o 一：珈= q ( a ) t o 一：a q o ( a ) r o = q ( a ) r o q o ( a ) r o 于是取 ，使得q ( t ) = q o ( t ) 就使得残向量为0 从上面的定理可知，选取w 1 ，u ，2 ，”使得它们是a w = q ，i 7 n + 1 的近 似解，可能会加速扩张的g m r e s 方法的收敛另一种选取w 的方法就是选取w 为跟小特征值相对应的近似不变子空间 3 2 往k r y l o v 子空间加r i t z 向量和调和r i t z 向量的方法 对于扩张的k r y l o v 子空间方法，往k r y l o v 子空间加r i t z 向量和调和r i t z 向 1 2 量是常用的选择，这些方法的基本思路如下： 1 给定子空间的维数m 十k 和要加的r i t z 向量( 或调和r i t z 向量) 的个数女；给定 初始向量z o ，计算初始残向量r o = b a x o 2 第一个循环使用标准的f o m ( m ) 方法( 或g m r e s ( m ) 方法) ，计算近似解x m + k 并得到相应的残向量r m + = b - a + k 如果没有收敛，令x o ：= z 。+ 女，r o ：= t m + k 计算出女个最小r i t z 值对应的r i t z 向量j l ，口2 ，“( 或计算出k 个最小调和 r i t z 值对应的调和r i t z 向量口1 ，口2 ，纨) 3 得到扩张的k r y l o v 子空间s p a n r o a r o ，a m - - 1 口l ，口2 ，扎) ( 或s p a n r o ， a r o ，a “_ 1 r o ，i 1 ，i 2 ，纨) ) 使用完全正交化方法求得近似解x m + k z o + s p a n r o ，a r o ， ，a ”- 1r 0 ，口l ，咖，讥) 并计算出新的残向量+ k = b a x 。+ k f 或使用最小残量方法求得近似解t m + k x o + s p a n r o ，a r o ，一，a 一1 r o 口l ，2 ， 呶) ) 如果收敛则停止；否则，令。o ：= x m + k ，r o ：= r 。拍 4 计算出七个新的最小r i t z 值对应的r i t z 向量i 1 ，9 2 ，讥( 或计算出k 个新的 最小调和r i t z 值对应的调和r i t z 向量i 1 ，口2 ，呶) ，返回到3 尽管往k r y l o v 子空间加r i t z 向量或调和r i t z 向量这一方法的基本思路很简 单，但是却有几种不同的实现方法下面我们详细描述这些不同的实现方法，并分 析它们的优缺点 3 2 1加人近似特征向量的扩张g m r e s 方法( g m r e s e ) 在f 2 9 1 ，m o r g a n 提出了基于扩张a r n o l d i 过程的实现方法给定k 个调和r i t z 向量口l ，i 2 ，纨( 或女个r i t z 向量9 l ，如，如) ，由扩张a r n o l d i 过程( 算法3 1 1 ) ， 我们可以得到 a z m t k = v + k + l 疗m + k ， 其中+ k = v 1 ，u 2 ，口l ，如，刻( 或者瓦+ = h v 2 ，虬j 2 ，鲥) v ，m + + 1 = p 1 ， 2 ， 。+ + l 】；且。+ k 是由扩张a m o l d i 过程得到的( m + k + 1 ) x ( m + k ) 的上h e s s e n b e r g 矩阵于是v l ， 2 ，吼，口2 ，讥是扩张的k r y l o v 子空间 瓦= 。( r o ) + s p a n y l ，口2 ，甄) 的一组基( 或者v l ，u 2 ，口l ，9 2 ，抓是扩 张的k r y l o v 子空间尼= 尼。( 7 0 ) + s p a n y 1 ，y 2 ，讥) 的一组基) ，7 ) 1 ，u