（计算数学专业论文）按向量形式实现的隐式重启块arnoldi方法.pdf

按向量形式实现的隐式重启块a r n o l d i 方法 i i i 摘要 随着科学和技术的发展，越来越多的应用和计算问题需要求解形如舡= a z 的大型稀疏矩阵的特征值问题而且在实际的应用问题中，我们往往只需要其中 ! 螳女几个特征值众所周知，k r y l o v 方法非常适用于这样的计算问题，而其中的 a r n o l d i 方法是一个比较好的求解大型稀疏矩阵的少数n 个近似特征值的迭代方法 s o r e n s e n 在文献f 2 4 1 中给出著名的单向量的隐式重启a r n o l d i 方法后来，l e h o u c q 和m a s c h h o f f 把隐式重启技术推广用于块a r n o l d i 方法【1 0 该方法具有良好的收 敛性质，但必须特别注意h e s s e n b e r g 结构的保持在一篇关于模型降阶问题的文 章中mf r e u n d 介绍了一种按向量形式实现的块a r n o l d i 方法，它) k - x 地简化了判 断何时需要压缩线性相关向量的操作，同时也使压缩操作更容易进行因此，按 向量形式构造k r y l o v 子空间比按块形式的构造方式更可取 本文的主要工作是开发了按向量形式实现的隐式重启块a r n o l d i 算法来求解大 型特征值问题我们指出：隐式重启技术可以与按向量形式实现的块a r n o l d i 方法 结合( 定理3 2 2 ) ，而且按向量形式的实现方式比按块形式的实现方式收敛更快( 定 理3 , 24 ) 这是由于后者要保持h e s s e n b e r g 结构而前者的处理方式不再受这个限制 的缘故最后，我们的数值实验表明，该算法结合了块方法的优点和按向量方式 实现的优点，对实的重，稠密特征值的求解非常有效，收敛速度相当快 本文的结构和内容如下：在第一章，我们在第一节对特征值问题的背景及解法 探索历史给出了个比较详细的概述第- - - 节确r 绍了块a r n o l d i 过程及块方法较非 块方法的优缺点第三节讲述了将隐式重启技术用于块a r a o l d i 方法的原理第二 章对按向量方式实现的块a r n o l d i 过程作了详细的介绍，并在本章的最后举了个 具体的算例以方便理解本文在第三章中首先证明了隐式重启技术可以与按向量 形式实现的块a r n o l d i 方法结合，接着开发了按向量形式实现的隐式重启块a r n o l d i 算法来求解大型特征值问题的算法，最后，我们用理论和数值实验说明我们所开 发的按向量形式实现的隐式重启块a r n o l d i 算法所具有的优越性 关键词：隐式重启；块a r n o l d i 方法；特征值问题 按向量形式实现的隐式重启块a r n o l d i 方法 a b s t r a c t m a n ys c i e n t i f i ca p p l i c a t i o n sl e a dt ol a r g e - s c a l ee i g e n v a l u ep r o b l e m s ，w h e r e t y p i c a l l yo n l yaf e we i g e n v a l u e sa r eo fi n t e r e s t f o rs u c hp r o b l e m sk r y l o v m e t h o d s & r ew e l ls u i t e d o n eo ft h ek r y l o vm e t h o d sc a l l e da r n o l d im e t h o d i sag o o di t e r a t i v em e t h o df o ra p p r o x i m a t i n gaf e we i g e n v a l u e so fl a r g en l a - t r i c e s s o r e n s e nd e v i s e da na p p r o a c hf o rt h es i n g l e v e c t o ri m p l i c i t l yr e s t a r t e d a r n o l d in l e t h o d 2 4 l a t e r ，t h ei m p l i c i t l yr e s t a r t e dt e c h n i q u ew a s g e n e r a l i z e d t ob l o c ka r n o l d ib yl e h o u c qa n dm a s c h h o f f 1 0 t h er e s u l t i n gm e t h o dh a s g o o dc o n v e r g e n c ep r o p e r t i e s ，b u tl e h o u c qa n dm a s c h h o f fm n s tt a k es p e c i a l c a r en o tt od i s t u r bt h eh e s s e n b e r gs t r u c t u r e i np a p e r 6 】w h i c hi sa b o u tt h e m o d e r e d u c t i o np r o b l e m ，f r e u n di n t r o d u c e sa na l g o r i t h mw h i c hi m p l e m e n t s t h eb l o c ka r n o l d im e t h o di nav e c t o r w i s ef a s h i o n a so p p o s e dt ot h eb l o c k w i s e c o n s t r u c t i o n t h ev e c t o r w i s ec o n s t r u c t i o ni sp r e f e r a b l et ot h eb l o c k - w i s ec o n s t r u c t i o nb e c a u s ei tg r e a t l ys i m p l i f i e sb o t ht h ed e t e c t i o no fi l e c c s s a r 3 rd e f l a t i o n a n dt h ea c t n a ld e f l a t i o ni t s e l f o u rm a i nw o r ki st h ed e v e l o p m e n to fa ni m p l i c i t l yr e s t a r t e db l o c ka r n o l d i a l g o r i t h mi nav e c t o r - w i s ef a s h i o nt os o l v et h el a r g e - s c a l ed g e n p r o b l e m s w e p o i n to u tt h a tt h ei m p l i c i t l yr e s t a r t e dt e c h n i q n ec a nb ec o m b i n e dw i t ht h e v e c t o r w i s eb l o c ka r n o l d im e t h o d ( t h e o r e m3 2 2 ) ，a n dt h em e t h o di nv e c t o r w i s ef a s h i o nc o n v e r g e sm u c hf a s t e rt h a nt h em e t h o di nb l o c k - w i s ef a s h i o n ( t h e o r e m3 2 4 ) ，s i n c et h el a t e ro n em u s tp r e s e r v et h eh e s s e n b e r gs t r u c t u r e w h i l et h ef o r m e ro n ed o e s n th a v et h i sl i m i ta n ym o r e l a s t l eo d rn u m e r i c a l e x p e r i m e n t ss h o w st h a to u ra l g o r i t h mh a st h ea d v a n t a g e so fb o t ht h eb l o c k 按向量形式实现的隐式重启块a r n o l d i 方法 m e t h o da n dt h ev e c t o r - w i s ef a s h i o n ，i ti se f f i c i e n tf o rs o l v i n gt h em u l t i p l e a n d o rc l u s t e r e dr e a le i g e n v a l u e s ，a n di tc o n v e r g e sr a t h e rf a s t i nc h a p t e r1 w eg i v ea no v e r v i e wo ft h eb a c k g r o u n do fe i g e n v a h mp r o b - l e m sa a dt h er e s e a r c hh i s t o r yo fs o l v i n ge i g e n v a l u ep r o b l e m si ns e c t i o n1 1 1 1 s e c t i o n2 ，w ei n t r o d u c et h eb l o c ka r n o l d ip r o c e s sa n dt h ea d v a n t a g e sa n d d i s a d v a n t a g e sb e t w e e nb l o c ka n dn o n - b l o c ki i m t h o d s i ns e c t i o n3 ，w ee x - p l a i nt h ei m p l i c i t l yr e s t a r t e db l o c ka r n o l d im e t h o d i nc h a p t e r2 ，w eg i v e s o m en o t a t i o n sa n dt h ev e c t o r - w i s eb l o c ka r n o l d ip r o c e s sw h i c hi si n t r o d u c e d i n 6 ，w ea l s og i v ea ne x a m p l ef o rb e t t e ru n d e r s t a n d i n go ft h ep r o c e s s i n c h a p t e r3w ef i r s tp r o v et h a tt h ei m p l i c i t l yr e s t a r t e dt e c h n i q u ec a l lb ec o m - b i n e dw i t ht h ev e c t o r - w i s eb l o c ka r n o l d im e t h o d ，t h e nw ed e v e l o pa ni m - p l i c i t l yr e s t a r t e db l o c ka r n o t d ia l g o r i t h mi nav e c t o r w i s ef a s h i o nt os o l v et 】1 e l a r g e s c a l ee i g e n p r o b l e m s l a s t l y lw ep r e s e n tt h es u p e r i o r i t yo fo u rv e c t o r w i s e i m p l i c i t l yr e s t a r t e db l o c ka r n o l d im e t h o df o rt h ec o m p u t a t i o no fe i g e n v a l n e s t l s i n gb o t ht h et h e o r ya n dm l m e r i c a le x p e r i m e n t s k e yw o r d s ：i m p l i c i tr e s t a r t ；b l o c ka r n o l d i ；e i g e n p r o b l e m v 厦门大学学位论文原创性声明 兹呈交的学位论文，是本人在导师指导下独立完成的 研究成果。本人在论文写作中参考的其它个人或集体的研 究成果，均在文中以明确方式标明。本人依法享有和承担 由此论文而产生的权利和责任。 声明人( 签名) ：粳偏 锄i 年岁月z 日 厦门大学学位论文著作权使用声明 本人完全了解厦门大学有关保留、使用学位论文的规 定。厦门大学有权保留并向国家主管部门或其指定机构送 交论文的纸质版和电子版，有权将学位论文用于非赢利目 的的少量复制并允许论文进入学校图书馆被查阅，有权将 学位论文的内容编入有关数据库进行检索，有权将学位论 文的标题和摘要汇编出版。保密的学位论文在解密后适用 本规定。 本学位论文属于 1 、保密( ) ，在年解密后适用本授权书。 2 、不保密刚 ( 请在以上相应括号内打“ ”) 作者签名：殷编 导师签名： 日期：拗6 年岁月2 9 日 日期：年月日 按向量形式实现的隐式重启块a m o m i 方法 第一章引言 第一节特征值问题概述 形如a z = a z 的大型稀疏矩阵特征值问题产生于科学与工程计算的很多学科 中，如楼房、桥梁及涡轮机的防震设计，电路网与流体流动稳定性的分析，动力 系统中分支模式的研究等在大多数情况下a 是稀疏矩阵，即a 的绝大多数元 素为零有相当一部分矩阵是“结构化的”，也就是说，非零元素在矩阵中按一定 规律分布，如带状、分块带状等求解这类问题是近年来数值代数界研究的热点 之一，已经发展起来几十种有效算法但是在理论上，每个算法都不十分完善 如何有效地求解大型稀疏矩阵的特征值，是科学与工程计算中最重要也是最基本 的问题之一 矩阵特征值问题， a x = a z 、a r 、7 。v 即给定个n 阶方阵4 ，求它的部分或全部特征值 以及对应的特征向量x 对 于中小规模矩阵特征问题，人们在理论分析，算法设计，以及稳定性研究等方面 进行了广泛而深入的研究，已经提出了许多有效的算法，其中最为成功的就是q r 算法，该方法已经在软件包中得以实现因此，中小规模特征问题已经得到了较 好的解决对于大规模矩阵特征问题，当a 对称时，经过多年的研究，也已经有 非常成功的l a n c z o s 和s t r u m 等算法可以使用当a 为大规模非对称矩阵时，由 于计算量存储量等条件的限制，传统的数值求解方法往往不再适用实际问题中 产生的高阶矩阵，人们需要的往往是它的部分特征对对于不同的需要，目前， 还没有一种非常可靠的方法来处理所有问题【2 9 】_ 大型非对称矩阵a 的特征值计算有几种方法其中最常用的是a r n o l d i 方法， 非对称l a n c z o s 算法 1 7 ，2 6 和子空间迭代法【8 , 1 4 ，1 5 】_ 这些方法可直接用于a 或其 变形( a 一一，) 。【5 , 1 6 第二种情况需要对( a 一一d 进行矩阵分解，但它使得位于， 附近的特征值有很快的收敛速度。本文中我们集中于讨论只对矩阵4 的情况 按向量形式实现的隐式重启块a r a o l d i 方法 2 a r n o l d i 方法和非对称l a n c z o s 方法者瞩于k r y l o v 子空间法，它们一般比子空 间迭代法收敛快然而，没有一种方法是完美的非对称l a n c z o s 算龅含个只 有三项的递推但经常数值不稳定a r n o l d i 算法( 算法1 1 4 ) 数值比较稳定但计算 的每个基向量需要与前面计算出的所有基向量进行正交化操作于是随着算法的 进行，运算和存储成本都会增加a r n o d i 方法还要计算一个n 阶h e s s e n b e r g 矩 阵的特征值和特征向量，这操作的运算量为o ( n 3 ) ，当n 很大时，这个代价就变 得很赢因此，重启通常是必需的，如下面的a r n o l d i ( n ) 算法( 算法1 _ 1 5 ) 在给出a r n o l d i 算法和a r n o l d i ( n ) 算 去之前，我们先介绍a r n o l d i 过程( 这里采 用的是m g s 版本1 2 0 ，p 1 4 9 ，a l g o r i t h m6 2 j ) ： 算法1 1 1 ( a r n o l d i 过程) ( 1 ) 任选向量v - ，满足慨i vi | 。= 1 ( 2 ) f o rj = 1 ，2 ，一，n d o ： w d ：= a v j f o r i = l ，2 ，一，d o ： u ：= ( 札。，v i ) w j ：= w j h i j v i e n d d o h j + 1 j ：= 1 1 w j l l 2 i fh j + l d = = 0s t o p v j + i ：= “o j + 1 ， e n d d o 算法1 1 1 1 中，在第j 步首先用a 乘以前面的a n ，o l d i 向量v j 得到 ，然后利 用改进的g r a m - s c h m i d t 过程将w j 与前面所有的钆v 2 ，进行标准正交化，如 果得到的向量w j 满足1 1 w f l l 。= 0 ，则算法中断现在我们给出该算法的一些简单陆 质 命题1 1 2 2 0 ，p 1 4 7 ，p r o p o s i t i o n6 4 】假定算法1 1 1 在第n 步前没有发生中 按向量形式实现的隐式重启块a r n o l d i 方法 断，则得到的向量组：钆，”。构成k r y l o v 子空间 丘。( a ，”1 ) = s p a 1 l o i ，a v ：，a 一1 f i ) 的组标准正交基 命题1 1 3 【2 0 ，p1 4 8 ，p r o p o s i t i o n6 5 j 记k = u 1 也珥。】，算法1 1 1 中计算 出的系数h “记录在m + 1 ) n 矩阵玩中，其中，没有定义的元素h u 被置为o 巩表示删除凰中最后一行后的矩阵则下面的关系式成立； a = 且。+ h n + l , n + l e ：= k 十i 曰。 ( 1 ) 曙a = 髓。，( 2 ) ( 1 ) 式称为n 步a r n o l d i 分解，风为上h e s s e n b e r g 矩阵 利用算法i ，l t ( a m o l d i 过程) ，前面提到的两种算法可筒单地叙述如下： 算法1 1 4 ( a r n o l d i 算法) ( 1 ) 任选向量满足1 1 2 = 1 ( 2 ) 对于n = 1 ，2 ，直到收敛计算 ( 2 1 ) 完成”步a r n o l d i 过程得到n n 的上h e s s e n b e r g 矩阵h ， ( 2 2 ) 用任何种求特征值的算法求出h ，的特征值和相应的特征向量a 和：，i = 1 ，2 ，n ( 可能是复的! ) ( 2 3 ) 计算z ：“) = k 这时就得到a 的近似特征值和特征向量 妒和z ” ( 2 4 ) 如果用某种笋i 艉断定所求近似值已经足够好了，则停止，否则n - - n + 1 再回到( 2 ) 注1 算法1 1 4 中第( 2 3 ) 步得到的a 的近似特征渣和特征向量 和z 争 分别称为r i t z 值和r i t z 向量 算法1 1 5 ( a r n o l d i ( n ) 算法) ( 1 ) 任选向量钆满足慨j | 2 = 1 ( 2 ) 完成n 步a r n o l d i 过程得到n 的上h e s s e n b e r g 矩阵嚣。 3 按向量形式实现的隐式重启块a r n o l d i 方法 4 ( 3 ) 用任何一种求特征值的算法求出风的特征值和相应的特征向量 和越” 江l ，2 ， n ( 可能是复的! ) ( 4 ) 计算z ：“= w 。 如果得到满意结果则停止 否则 ( 5 ) 们= 。”再回到( 2 ) ，直到收敛 注2 与a r n o l d i 算法( 算法1 1 4 ) 比较算法1 1 5 最大的好处是避免n 不断增 加造成存储空间不足的困难然而，重启使得收敛变慢了 算法1 1 5 中将近似特征向量。5 叫作为初始向量重新启动( 步骤( 5 ) ) 这只是众 多重启方法中的最简单的一种，适合于只要求得到个特征值的情况般地，我 们要求解的特征值多于个，对于这种情况，f 面介绍几种重新启动方法第一种 重启方法是使用将近似特征向量按一定的权重相加得到的向量作为新的初始向量 s a a d 在【1 8 】中提出使用各近似特征向量相应的残差范数作为各特征向量的权重 然而，在实际应用中这个方法表现并不好于是s a a d 又提出另一种方法，选择一 个近似特征向量作为新的初始向量，每次只计算个特征值，例如，找到 。后压 缩掉 1 9 ，计算下个特征值a ：如此进行下去，直到求得所有的特征值这种方法 的缺点是每次只能计算得到一个特征值另外对复特征值的求解仍存在着问题 第三种是块方法的重启方式由于同时有几个初始向量，故使得同时找到n 个特 征值成为可能然而，对于相同大小的子空间，a 的幂与非块方法相比要低很多， 这导致了准确性的降低第四种重启方法由s o r e n s e n 在f 24 】中给出这就是著名 的隐式重启a r n o l d i 方法与第一种方法类似，他构造的新的初始向量也是近似特 征向量的组合，但他的组合方式是不同的首先对n 步a r n o l d i 分解( 1 ) 应用隐式 带位移的q r 算法，假设使用了p 个位移，则得到更新后的k 步a r n o l d i 分解，其 中k = n ps o r e n s e n 选取不需要的近似特征值作为位移实践证明，这种重启方 式非常有效，它优于前面介绍的方法 后来，l e h o u c q 和m a s c h h o f f 把隐式重启技术推广用于块a r n o l d i 方法【10 】该 方法具有良好的收敛性质，但必须特别注意h e s s e n b e r g 结构的保持本章的第二 按向量形式实现的隐式重启块a r n o l d i 方法 5 节介绍了块a r n o l d i 过程及块方法较非块方法的优缺点第三节讲述了将隐式重启 技术用于块a r n o l d i 方法的原理 在篇关于模型降阶问题的文章中 6 】f r e u n d 介绍了一种按向量形式实现的 块a r n o l d i 方法，相对于本章第二节介绍的按块形式实现的块a r n o l d i 方法而言， 它大大地简化了判断何时需要压缩线性相关向量的操作，同时也使压缩操作容易 进行因此，按向量形式比按块形式的构造方式更可取此外，在按向量形式实 现的情况下，初始块可以是任意的，而在按块形式实现时，它的各列必须是相互 正交的本文第二章对这一按向量方式实现的块a r n o l d i 过程作了详细的介绍，并 在第三节的最后举了个具体的算侧方便理解 由于压缩操作的存在，矩阵的结构会发生变化，本文在第三章中首先证明了隐 式重启技术可以与按向量形式实现的块a r n o l d i 方法结合，接着开发了按向量形式 实现的隐式重启块a r n o l d i 算法来求解大型特征值问题，定理3 2 。4 表明按向量形 式的实现方式比按块形式的实现方式收敛更快。我们主要利用数值实验来研究该 方法的性质好坏数值实验表明，该算法对实的重，稠密特征值的求解非常有效， 收敛速度相当快 第二节块a r n o l d i 过程 块虹n o l d i 方法是单向量a r n o l d i 方法的推广通过初始块 h = 【 l ，) ， v x r ”。 ( 3 ) 可以构造出块k r y l o v 子空间 k ( 4 ，v d = s p a n ，a ，a 2 h ，一，a 肘- 1 ) ( 4 ) 下面的算法描述的块a r n o l d i 过程是使用改进的g r a m - s c h m i d t 过程( 块m g s ) 进行正交化的版本 算法1 2 1 ( 块a r n o l d i 过程) ( 1 ) 任选n b 正交矩阵k ( 2 ) f o r ，= l ，2 ，m d o ： 按向量形式实现的隐式重启块a n i o l d i 方法 玛：= a 巧 f o r i = l 2 h i j ：= v , r 毋 k 1 = f ，一h t i e n d d o 计算q r 分解玛= k + 坞扎， e n d d o 由算法1 2 1 得到m 步块a r n o l d i 分解如下； a i 沁5 = l 知6 h m b + f m e a t m b m b 矩阵风f b 是个有b 条次对角线的带状上h e s s e n b e r g 矩阵， 乩。= 降 峨，为b 阶矩阵，q “为上三角矩阵 h 1m h i 、f _ h 【、? n ，1 r 。“伯 k 琏帅， i = 1 ( 5 ) 6 ) 的各列组成块k r y l e v 子空闯4 ) 的组标准正交基。倘若马扎，满秩，则h 。，u f 相互正交n ，= n m 矾川 f 为残量且满足嘿n f = o 抽b = 【e m b ，1 ，e m b ，2 ，e m b ，m l ，e m b ，m 为m b m b 单位矩阵，e m r ”b x b 由如6 的后b 列组成 如果在第步迭代时，0 秩亏( 不再满秩) ，可采用【3 】中提出的处理方式假 设乃的第女列与前面的k 一1 列线性相关，我们将坞扎，的第k 个对角元置为o ， 同时随机选取一个单位向量，并将它与u a 及k + ，的其它b 一1 列进行正交化， 用得到的向量取代玛的第k 列 6 按向量形式实现的隐式重启块a r n o l d 方法 7 以下是块方法较非块方法的几个优缺点： 块方法能够更好的求解重，稠密特征值，尽管单向量方法也能够通过压缩来处 理这样的问题 从高性能计算的角度来看，块方法用b l a s 3 矩阵一矩阵运算代替矩阵一向量运 算大大地提高了效率 对于维数固定的k r y l o v 子空间，例如，若空间是m b 维的，那么块方法将利用 m 一1 阶的多项式来求解不变子空间，而单向量的方法可以用m b 一1 阶的多项式 来求解对某些问题而言，高阶的多项式产生的近似效果可能会更好因此，对 于这类问题而言，块方法的收敛速度可能会没有单向量的方法好 块方法比单个向量方法复杂得多，且理论不完善 第三节隐式重启块a r n o l d i 方法 在【1 0 中，l e h o u c q 和m a s c h h o f f 把隐式重启技术推广用于块a r n o l d i 方法 算法1 2 1 运行 ，步后，我们得到( 5 ) 式对巩n 作一步带位移的q r 迭代 如下： 风，b j t l = q a t b r m b h 志b = r , _ l l b q m b + p ， ( 7 ) 由上面的( 7 ) 式容易推得下面的关系式： h i l i b q m b = q r , f b h + b ( 8 ) 把带位移的q r 算法类推应用于( 5 ) ，并利用( 8 ) 式，得 a m 。：胁 1 1 ) 。日南_ 1 ) m 1 + f a t e t 州( 9 ) 磁，”一。e 一。) 。，m 一，磁， 其中， i ( m t ) b = 【e ( m 一1 ) b ，l ，e ( m 一1 ) b ，2 ，一，e ( m 一1 ) 6 ，m 一2 ，e ( m t ) bm 一1 】 为( m 一1 ) b ( m 一1 ) b 单位矩阵，e ( * 】) 6 ， 一1 r ( m - 1 ) 由五 彳一1 冲的后b 列组 成由于h m b 为带状匕h e r s e n b e r g 阵，0 和h 5 也是带状匕h e s s e n b e r g 阵， 按向量形式实现的隐式重启块a r n o d i 方法 8 因此， 砌碥0 = f m o ，碍q m b e , l b ，m “磁q m b e m b ，m 】_ ( 1 0 ) 在( 9 ) 中等式两边都取前( m 一1 ) b 列得到m 一1 步块a r n o l d i 分解 a k 岛一，) 。= 陆一，) 6 日出一啪+ 磁一，e 西一，) “ 一， v 蔷- 1 1 6 = v m b q ( m 一1 ) b ， ( 1 1 ) f 志i = v m b q m h + ! m 一1 + f a , e r f bm q f 一1 ， 其中q m 6 = f q ( _ 1 ) q f 】i 如果应用p 个位移，其中1sp n o 时为，1 0 且当n ，1 0 时有，。( a ，r ) = 丘。( ，r ) 这样，c 。( a i r ) 为由a 和r 生 成的最大可能的k r y l o v 子空间，若n 我 f j 称k r y h 序列n a na 2 即，舻。r 已耗尽 当m 1 时。有m 个初始向量，这种情况更为复杂与m = l 的情况相比， 块k r y l o v 序列 兄，a r ，a 2 冗，一，a j 一1 r ，( 1 5 ) 中各列之间的线性无关性般会逐渐失去更确切地说，如果( 1 5 ) 中第j 个块 a j 一显中有列与它左边的各列向量线性相关，一般地，这并不意味着a j 。曰中 所有列向量都与它们左边的列向量线性相关因此，出现个线性相关的列并不 表示块k r y l o v 序列( 1 5 ) 已耗尽般而言，即使在( 1 5 ) 中发现了一个线性相关的 列，构造基向量的过程也要继续进行然而，我们需要合理地处理这些线性相关 按向量形式实现的隐式重启块a r n o l d i 方法l o 的列向量，这些列向量本身以及它们与一个或多个a 相乘得到的所有向量都应该 删除这一操作可按如下方式来实现：从左到右检查( 1 5 ) 中各矩阵的各列向量， 删掉与前面的列向量线性相关的列向量，于是得到了压缩后的块k r y l o v 序列 r i ，a r 2 ，a 2 r 3 ，一朋。r j ，( 1 6 ) 这个删除线陆相关向量的过程称为准确压缩在( 1 6 ) 中，对每个j = l ，2 ，一，j 。， 马是马一的子矩阵，且马r 一，当且仅当在( 1 5 ) 中的第j 个k r y l o v 块a j 。r 中发生了压缩这里规定r o = r ，m ，表示r ，的列向量个数，于是有 从上面的构造过程可以看到，( 1 6 ) 中矩阵的各列向量是线性无关的，对每个n ， 由这些列向量中的前n 个向量构成的子空间称为n 维块k r y l o v 子空闻( 由a 和 r 生成) 记该n 维块k r y l o v 子空间为瓦。( a 矗) 在这里，我们取 其中1sj ! j 。贝4 所得，a 维块k r y l o v 子空间为 t c 。( 4 曰) = c o l s p a n r 1 a r 2 a 2 月3 一1 日) ( 1 9 ) 需要强调的是，上面讨论的构造块k r y l o v 子空间的过程中，只采用了对线性相关 的列向量的准确压缩在实际的算法中，要在有限精度运算下构造予空间( a ，r ) 的基向量，那些。几乎”与它们前面的向量线性相关的向量也需要删除我们把 删掉这些几乎线性相关向量的操作称为不准确压缩在本章的第三节中，将描述 对于多重初始向量的情况，如何在a r n o l d i - t y p e 算法中方便地实现准确和不准确压 缩操作 第二节基向量 子空间k ( a ，冗) 的定义( 1 9 ) 用的是( 1 6 ) 中的列向量，然而，对中等大小的 这些向量就会趋向于线性相关，因此，它们不适合于数值计算，我们需要构造其 它合适的基向量 按向量形式实现的隐式重启块a r n o l d i 方法 1 1 下面，我们用 u l ，吨， 。碡“( 2 0 ) 表示配。( a ，r ) 的一组基向量，也就是说， s p m l v x ，v 2 ，一 n ) = k n ( a ，r ) n n 矩阵 k ：= ht j 2 - 。】 ( 2 1 ) 称为k ( a ，r ) 的个基矩阵 需要强调的是，本文讨论的算法是按向量形式来生成( 2 0 ) 中的基向量，而在 传统的块k r y l o v 子空间方法( 即第一章第二节介绍的算法1 2 1 ) 中采用的是按块 形式来构造的方式按向量形式的构造方式大大地简化了判断何时需要压缩的操 作，同时也使压缩操作容易进行因此，按向量形式比按块形式的构造方式更可 取这一点将在下一节作出说明 第三节a r n o l d i t y p e 算法 传统的a r n o l d i 过程产生k r y l o x 子空间( ，( ar ) n 1 ( 由 和单个初始向量r 生成) 的组标准正交基向量在本节中，我们介绍的a r n o l d i - t y p e 算法将传统的 算法推广到了块k r y l o v 子空间k ( a ，r ) ，n l 的情况 与传统的a r n o l d i 过程类似，该算法构造的基向量( 2 0 ) 为标准正交基，按照基 矩阵( 2 1 ) 的形式可表示如下： 嵋k = 除了基向量( 2 0 ) 以外，该算法还产生了向量， 作为接下来要生成的基向量+ 1 ，”。+ 2 ，+ 。的候选向量这里，m 。= m 。( n ) 表示( 1 3 ) 中到现在为止( 已产生n 个基向量的时候) 初始块r 的列向量个数m 堡鱼量型壅塞墨笪垡壅重星些生翌型查查盘1 2 经过准确压缩和不准确压缩后还剩的列向量个数候选向量f 2 2 ) 满足如下正交关 系； 曙+ 1o 。+ 2 + m j = 0 由于按照向量方式来构造( 2 0 ) 和( 2 2 ) ，使得判断压缩及实际的压缩操作都变得容 易可以证明；a r n o l d i t y p e 过程中在第n 步发生准确压缩当且仅当“= 0 事实 上，文献【1 中对l 8 n c z o s - t y p e 算法情况的证明跟本文中a r n o l d i - t y p e 算法情况本 质上是一样的。下面我们给出该结论的证明， 命题2 3 1a r n o l d i t y p e 过程中在第n 步发生准确压缩当且仅当日n = 0 证明：a r 。o l d i 时p e 过程在第n 步发生准确压缩# 。t l 与现，”。一t 线性 相关 即要证：o 错o 。与， 。一，线陛相关 1 若o 。：0 ，则显然瓯与b 2 ，。线性相关 2 若i 。与啦一一i 线性相关，则 一l 乩= 刚。c r i = 1 在a r n o l ( t i t y p e 过程中，构造的孙孙，- 卜o 。之间有如下关系： 昧一l o 。= 0 味l “一l = j ， 其中一1 = 【v l ”2 一l 】 由 o ，。= 0 = 寺” ( a l t h + o e 2 v 24 - + n 。一1 ”一1 ) = 02 = = o t l = 0 ， 同理可得n 2 = 。3 一“。一i = 0 ，于是o ，= 0 综上，命题得证 口 类似地，发生不准确压缩当且仅当慨【| 。0 但i ，。0 因此，在算法中我们检 查 慨| | 曼d t o l ( 2 3 ) 是否成立，其中d t 。1 0 是选定的合适的压缩容差如果满足条件( 2 3 ) ，则压缩 。( 即删除) ，并将所有剩下的候选向量的下标减去1 重置m c = m c 一1 若m c = 0 ， 塑墅暨翌塑堕堕查熏壁垫尘竺型查姿 1 3 则所 导块k 珂l o v 子空间已耗尽，算法终止。否则，重复压缩步骤直到找到一卟满 足慨f f d t 。l 的毗，然后正规化使其欧氏范数为1 ，得到 上面介绍的a r n o l d i t y p e 算法的完整陈述如下所示 算法2 3 2 f u n c t i o n i v , w , t ，r h o ，”a 。，礼】= v b a r n o l d i ( a ，n ，r ，m ，j m n z ) ( 0 ) o 。：= n ， = 1 ，2 m ， t = t ，f ( 1 ) f o r j = 1 ，2 ，- ，j m a x ( 11 ) 计算怖f f 并检查是否满足压缩准则( 2 3 1 如果 芮足，对奶执行下面的压缩步骤： t n c ：2h k 1 野t n c = = o ，酗j ：= j l 。n ：= j 拿 谴；滓止 魂：= 魂+ j ，i = j ，j + 1 ，j + m 。一l 返回到步骤( 11 ) ( 12 ) t j j 一= 怖叭v j = 奶0 。 ( 13 ) 计算吼。= a v ) ( 1 4 ) f o ? 、i = 1 2 t jd o f ：= 、弱! m q + 7 m ：= q + m ，一e ，n tj 肌d ( 1 5 ) f o r i = j ? n c + 1 j 一7 n 。+ 2 勺z ：= 哆o h 毋件m 。：= 啦+ ，n 。一q t k n d 使奶。与钆，正交 使与。j + l ，吗+ 2 ，。h d 正交 眈d ( 2 ) n = = = ，v ：= p 1 屹2 k i ，w ：= f + i 如+ ? t ：= 眉i = 1 丑, 2 , - - - ，, 。, ，r h 。：= 一。詹务品 注3 如果( 2 3 ) 中d t 。1 0 ，则算法2 3 2 只进行准确压缩 按向量形式实现的隐式重启块a r n o l d i 方法 1 4 注4 其它的块a r n o l d i 算法( 都不含压缩操作) 在【2 0 ，6 1 2 胡中有介绍 当主循环运行n 步后，算法2 3 2 构造出前面的n 个基向量( 2 0 ) ( 记录在v 中) 和接下来的m 。个基向量的候选向量( 2 2 ) ( 记录在中) 我们把前n 步循环过程 中计算出的系数分别记录在下面两个矩阵中： r h o ：= p 。，l - - mi = 1 , 2 , - - 三，t ：= c 】2 - i = 1 1 如2 - - - n ( 2 4 ) 此外，( 2 4 ) 中没有在算法2 32 中定义的元素t 州一。和t 引都被置为0 按照( 2 1 ) 中基矩阵k 的形式，这个循环过程可以简洁地用矩降形式表示对n 1 ，有 其中，分别为算法2 32 中的kr 在( 2 5 ) 中，我们假定只发生了准确 压缩如果同时进行了准确和不准确压缩，则在( 2 5 ) 中的右边要加上额外的一项 谢以印e f i 中的非零向量来自压缩检验( 2 3 ) 中的那些非零向量由于在算法2 3 2 的任何阶段最多有r n 一= ”t m 。( n ) 个向量被压缩，故该额外的矩阵 觅艮小， e ? 胡jjsd t o l 、伤= 面丽 下面我们对算法2 32 进行进一步的分析，为了方便表述，首先对类矩阵给 出如下定义 定义2 3 3 下带宽为m 1 的上h e s s e n b e r g 阵称为m l 一上h e s s e n b e r g 阵 例2 , 3 4 我们给出一个定义2 3 3 中定义的m 一上h e s s e n b e r g 阵的例子h 为个2 一上h e s s e n b e r g 矩阵，则它具有如下形式： 口 注5 算法2 , 3 2 得到的t 即n 为m 。一上h e s s e n b e r g 阵这甄m 。的定义 见( 1 7 ) 0 o x 0 0 o 按向量形式实现的隐式重启块a m o l d i 方法 例2 3 5 为了更好的理解算法2 3 2 ， 程取m = m 1 = 5 ，假定m 2 = 2 ，m 3 = 1