（应用数学专业论文）大型特征值问题的bjd方法研究.pdf

竹息t 程人学坝i 学位论立 摘要 对于求解重特征值和密集特征值问题，通常一步迭代求一个近似特征对的方法都会 因为问题的条件变“坏”而导致有效性下降。解决这个问题的手段很多，块方法是比较有 效的一类。 j a c o b i d a v i d s o n ( j d ) 方法是计算大型矩阵极端特征值问题的一种有效方法，但足当它 遇到上述问题时，它的修正方程的系数矩阵会变得很病念甚至奇异。基于这一事实，本文 研究了j d 方法的块形式，提出了块j d ( b j d ) 方法：选择一个块规模参数p ，每次迭代都计 算p 个r i t z 对而不是一个，对每个r i t z 向量修丁f 方程都做出校形，使得投影算子与所有的 r i t z 向量币交，从而避免了修证方程的系数矩阵条件变“坏”。 此外，结合精化策略和收缩技术，本文还提出了精化b j d ( r b j d ) 方法和收缩的 r b j d ( d r b j d ) 方法。精化理论的分析表明，r b j d 方法比b j d 方法更有效，它改善了近似 特征向量的收敛性态，提高了算法的收敛速度和可靠性：d r b j d 方法减少了可能存布的霪 复运算，进一步提高了算法的效率。 关键词：大规模矩阵特征值问题块j a e o b i d a v i d s o n 方法精化策略收缩技术 第1 贝 侪息t 程人学侦i 学位论文 a b s t r a c t w i t ht h ec o n v e n t i o n a lp r o j e c t i o na l g o r i t h mp r o b l e m sc a l la r i s e ，i ft h ed e s i r e de i g e n v a l u e s a r em u l t i p l eo ri f t h e ya l ev e r yc l o s et o g e t h e r ：t h ei l l - c o n d i t i o n e dm a yd e p r e s st h ee f f i c i e n c ya n d r e l i a b i l i t yo ft h em e t h o d t h e r ea r em a n ym e t h o d st os o l v ei ta n dt h e b l o c k m e t h o di sa e f f i c i e n to n e s j a c o b i - d a v i d s o nm e t h o di s v e r ye f f i c i e n tf o rc o m p u t i n gt h ee x t r e m ee i g e n p a i r so f l a r g e - s c a l em a t r i c e s ，b u t t h e s y s t e m m a t r i xo ft h e c o r r e c t i o n e q u a t i o nm a yb e c o m e i l l c o n d i t i o n e di fi te n c o u n t e r st h ea b o v es i t u a t i o n t h e r e f o r e ，t h eb l o c kv e r s i o no ft h ea l g o r i t h m p r e s e n t e di nt h i sp a p et r i e st of i xt h e s ei s s u e s t h ei d e a st h ef o l l o w i n g ：t h eb l o c ka l g o r i t h mi s p a r a m e t r i s e db ya na d d i t i o n a lp a r a m e t e r ：t h eb l o c ks i z ep n o wp r i t zp a i r sa r ec o m p u t e di n e a c hj di t e r a t i o n 。i n s t e a do fo n l yo n e f o re a c ho ft h e s epr i t zp a i r sas e a r c hd i r e c t i o ni s c o m p u t e df r o mt h ec o r r e c t i o ne q u a t i o n t h ep r o j e c t i o n si nt h e c o r r e c t i o ne q u a t i o na r ea d j u s t e di n s u c haw a y ，t h a tt h e yk e e pt h es o l u t i o n so r t h o g o n a lt oa l lr i t zv e c t o r s t h e s em o d i f i c a t i o n p r e v e n tt h es y s t e mm a t r i xf r o mb e c o m i n gi l l c o n d i t i o n e da n dn e a r l ys i n g u l a r b yu s i n gt h er e f i n i n gs t r a t e g ya n dd e f l a t i o nt e c h n i q u e ，f u r t h e r m o r e ，t h ep a p e ri m p r o v e st h e n e wm e t h o da n dp r o p o s e st h er e f i n e db l o c kj a e o b i - d a v i d s o nm e t h o da n dt h er e f i n e db l o e k j a c o b i d a v i d s o nm e t h o dw i md e f l a t i o n t h ef i r s to n ei m p r o v e st h ec o n v e r g e n c eq u a l i t i e so ft h e a p p r o x i m a t i o ne i g e n v e c t o r sa n dt h el a s ta v o i dt h ep o t e n t i a lr e p e t i t i o nw o r k b o t ht h en e w m e t h o d si m p r o v et h ee f f i c i e n c ya n dr e l i a b i l i t yo fb l o c kj a c o b i d a v i d s o nm e t h o dg r e a t l yi n t h e o r y k e yw o r d s ：l a r g e - s c a l em a t r i x ；e i g e n p r o b l e m ；b l o c kj a c o b i d a v i d s o nm e t h o d ( b j d ) ； r e f i n i n gs t r a t e g y ；d e f l a t i o nt e c h n i q u e 第艇 论文原创性声明和使用授权 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及 取得的研究成果。尽我所知，除了本文中特别加以标注和致谢中所罗列 的内容外，论文中不包含其它人已经发表或撰写过的研究成果；也不包 含为获得信息工程大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确 的说明并表示了谢意。 本人完全了解信息工程大学电子技术学院有关保留和使用学位论 文的规定，即：学院有权保留论文的复印件，允许查阅和借阅论文；可 以公布论文的全部或部分内容；可以采用影印、缩印或其它手段保存论 文。涉密论文按保密规定执行。本论文取得的研究成果归学院所有，学 院对该研究成果享有处置权。 挑各蓥融伟 日觌沙，鸯善月 导师签名：莒铂缸 呐：一沙j 印6 刃1 国 信息t 程人学坝i 学位论文 第一章前言 1 1 背景介绍 代数特征值问题是数值代数的一个重要研究领域，其研究具有重要的理论意义和应用 价值。在许多科学和工程问题如结构力学中的固有频率分析问题以及控制系统中的稳定性 等传统问题，以及在计算流体力学、量子化学、电子网络、化学工程和网络排队的马尔可 夫链模拟等现代的实际问题中，许多问题的解决最终都集中为矩阵的标准特征问题( r 。义 特征值问题和非线性特征值问题在这不讨论) a x = 2 x ( 1 i 1 ) 的求解，其中a 为玎阶实( 或复) 矩阵，( a ，j ) 为爿的特征对。 矩阵4 的特征值问题表面上看是一个很简单的求解非线性方程组血= 触的问题，其 中五为a 的特征值，x 为a 相应于名的特征向量。对于求解卫和x ，一个最直接的方法就是 先求解矩阵彳的特征方程d e t ( a 一五，) = 0 的根，再回代入上面的方程组中。实际应用中，除 了一些特殊的矩阵外，该方法对一般的矩阵是不可行的：其一，如果彳的阶数比较大，则 方程d e t ( a 一2 1 ) = 0 的计算量非常大；其二，d e t ( a 一九，) = 0 的求根是不稳定的。基于上述 原因，人们通过寻求其他的求解途径，提出了许多很好的思想方法和具体算法，促进了该 学科的不断发展。 目前，求解矩阵特钶：值问题的方法大体上可以分为两类：变换法和迭代向量法。变 换方法是利用矩阵特征值的相似不变性原理，通过一系列特殊的变换矩阵( 仞等f 三角知! 阵，h o u s e h o l d e r 矩阵，平面旋转矩阵等) ，对原矩阵逐次进行相似变换，将其化成个裙 易求解特征值的特殊形式( 对角形，三角形，拟三角形等) ，如j a c o b i 方法j ，g i v e n s 方 法【l l ，q r 方法 i 】等。变换方法收敛速度快。计算结果精确可靠，但它破坏原矩阵的元素分 柿( 如稀疏阵的零元分伟) ，并且由于需要存储矩阵元素，当矩阵的阶数很高时使得存储 量较大从而造成调用计算机外部设备的困难，因此，这种方法只适宜于求解阶数较低的稠 密矩薛的全部特征值问题。而迭代向量法是基于矩阵特征值，即特征多项式根的计算方法 本质上总是迭代法的事实，利用原矩阵进行运算，产生一些迭代向量的方法。由于迭代法 可采用压缩存储技术，因而它适用于求解高阶、稀疏矩阵的部分极大或极小特征值和相应 特征向量。目前常用的计算大型稀疏对称矩阵特征值问题的迭代法有子空问迭代法l l , z l 和 l a n c z o s 方法【1 ，2 1 等。子空间迭代法可同时求解几个极端特征值和相应的特征向量，但它有 收敛较慢，运算量较大，积累误差的缺点。l a n c z o s 方法是先将矩阵a 约化为三对角知阵 船i 虹 信息t 程人学硕i 学位论文 再求解特征值问题， 幺算法存储量不大，计算速度较快。但是l a n c z o s 方法只对部分类型 的特征值问题比较有效，对于其他类型的问题，由于l a n c z o s 向量之倒容易失去正交性， 使得方法容易停滞，因此对这些问题该方法的收敛效果并不是很好。通常两种方法结合使 用。 但在实际闽题中，矩阵阶数可能高达万阶甚至百万阶以上，而需要的却往往只是矩 阵依模最大或最小、依实部最大或最小、依虚部最大或最小的若干特征值或者在某区域中 的特征值及其相应的特征向量或不变子空日j 。人们发现用投影方法可将大舰模矩阵问题投 影到一个小的子空日j 上，从而转化成中、小型矩阵问题，进而利用已成熟的算法求得它的 近似解。所以关于各种投影方法及其变型的数值求解的理论研究、算法的丌发和软件的研 制都是当今计算数学和科学与工程计算研究领域中的重大课题，国际上的研究工作尤为活 跃，并且主导者学科的发展方向。 1 9 7 5 年，e r d a v i d s o n 在计算量子化学中的特征值问题时提出了计算大型列称矩阵 极端特征值问题的一种新方法- - d a v i d s o n 方法1 3 1 。大量的试验表明，d a v i d s o n 方法对于求 解对角占优矩阵的特征值问题是非常有效的。对角占优矩阵d a v i d s o n 方法能够使得不需要 的特征向量的分量从所求特征子空i 日j 的基中逐渐减小，从而大大提高收敛速度。但是， d a v i d s o n 方法在扩充投影子空间方面的存在天然缺陷。为了得到更加有效的新的扩充的向 量，s l e i j p e n 与v a nd e rv o r s t 对d a v i d s o n 方法的收敛性进行分析1 4 , s 1 ，将j a e o b i 处理特征问题 的思想与d a v i d s o n 方法结合起来提出了j a c o b i d a v i d s o n 方法1 6 1 ：在近似特征向量的币交补 空问上寻求对它的修正，然后通过修讵向量束扩展子空间，再在扩展予空f b j 中计算r i t z 列 作为特征对的近似。j a c o b i - - d a v i d s o n 方法具有较好的稳定性，对于非列角占优、4 1 一币规 矩阵也可能达到较快的收敛速度。 当要求计算的特征值是重特征值或密集特征值时，问题的性念会变得很坏，普通算 法的有效性会大大下降。从而人们提出块方法，用来在一次循环中同时计算多个特征对， 如果块的大小选的恰当，效果会很喜人的。再退一步，若还不行，人们又提出了收缩技术， 将已经收敛的特征对提取出来，不参加下一轮运算。这些方法和技术的运用大大改善了算 法的效率和可靠性。目前，几乎所有算法都有块形式，如块a m o l d i 方法0 3 , 1 s l ，块l 锄c z o n s 方法f 1 6 1 ，块d a v i d s o n 方法等。 在投影方法中，为了减少存储量，所选的投影子空问的维数m 通常较小，这样在经 过m 步迭代后，计算结果精度往往达不到要求，所以需要重新丌始过程，并用r i t z 向量作 为重新丌始过程的初始向量。但是对有些阅题，虽然r i t z 值收敛，但r i t z 向量可能收敛比 较慢甚至不收敛。鉴于此，为改善近似特征向量的收敛性，近年来，许多学者对重新丌始 初始向量的选取进行了很详尽的研究，提出了一些较好的方法，如动态稠密重新丌始过程 箱2 虹 信息t 程人学坝i 。学位论史 f s l ；用c g 递归进行重新丌始【6 l ；用动态稠密重新丌始和c g 递归的组合运用f 9 1 等等。另外， 在a r n o l d i 方法的研究过程中，为了改善近似特征向量的收敛性，【1 0 1 和【1 1 1 分别采用精化 簏略提出了选择重新丌始初始向量的精化a m o l d i 方法和精化块a m o l d i 方法，并证明了当 r i t z 值收敛后，精化近似向量也收敛。 总之，基于这一十分有意义的课题，本文研究大型稀疏矩阵的j a c o b i - d a v i d s o n ( j d ) 方法的“块”( m o c k ) 形式，提出了块j a c o b i d a v i d s o n ( b j d ) 方法；应用精化策略选取重新丌 始的初始矩阵，提出了精化块j a c o b i d a v i d s o n ( r b j d ) 方法。在此基础上，又结合收缩技术 提出了收缩的精化块j a c o b i d a v i d s o n ( d r b j d ) 方法。理论分析表明改进的算法提高了收敛 速度和可靠性。 1 2 投影方法及相关理论 求解中、小型矩阵的特征值问题，最常用且有效的方法是q r 方法| z 1 7 1 ，该方法在收 敛性分析、数值稳定性研究方面已经取得大量满意的结果，而且该方法已被成功地编制成 为使用可靠的软件，在m a t l a b 软件包中计算矩阵所有特征对的函数e i g 即以玖方法的原 理编制而成。还有一些如j a c o b i 方法和分而治之法1 2 l 也都是很有效的数值方法，在某些方 面也都有各自的优点。因此，对于中、小规模矩阵特征问题的求解基本上得到了完满解决。 但是对于大规模矩阵特征问题，运用这些方法柬解则面临着种种困难，主要表现在： ( 1 ) 常规方法通过对矩阵进行整体变换来计算出其所有的特征值，如果应用到人舰模问 题中去，一方面可能造成内存不足，而且计算时问冗长，另一方面对实际问题中广吨的人 舰模矩阵，人们关心的往往只是它的少量特征对，用标准方法进行求解，将造成极人浪费。 ( 2 ) 许多情况f 得到的大规模矩阵非常稀疏，或者具有比较特殊的元素分靠结构，则这 类矩阵本身进行变换将会引起非零元素的灾难性增加，进而会导致算法无法进行下去。 ( 3 ) 有些实际问题1 1 8 1 所能提供使用的只是一个用于形成矩阵向甓积的程序，矩阵元素的 信息难以显式的得到，此时根本无法使用常规的方法进行计算。 下是由于这些原因，寻找和研究求解大规模矩阵特征问题部分特征对的数值方法成 为一个非常重要的研究领域，它已成为国际学术界的研究热点之一。 现在解决大规模矩阵特征问题最常用的方法是投影类方法。其基本思想是将原矩阵 a 向适当低维子空剧进行特定的投影，将大规模问题转化为中、小规模矩阵特征问题，采 用常规方法计算其特征对用来作为大规模矩阵的特征对的近似。投影类方法的特点是不需 对大规模矩阵a 做任何改变，仅使用矩阵a 来形成矩阵- 向量乘积，从而可以减少内存需求， 节省计算丌支。投影类方法主要分成如下三类： 第3 负 1 2 1 正交投影方法 定义1 2 1 j 4 1 设对盯阶矩阵a ，给定脚维子空问占，在e 上的j f 交投影方法为寻找 ( 互，谚) ( 忪0 = 1 ) 满足g a l e r k i n 投影条件： 雠上e ( 1 2 1 ) i ( 彳一丑，) 谚上 并使用( 丑，谚) 作为a 的特征对( 五，竹) 的近似值。如果 v ，) 是子空问e 的一组标准证交基， 定义= 【v i ，屹，以】则上述关系式可以写成： 妻2 繁 ( 1 2 2 ) 【地= 丑只 、 此处h = 碟4 圪是彳在标准币交基 v ，) 二下对子空问e 的投影矩阵。若巴表示子空i j e 上 的市交投影算子，则上面的条件( 1 2 1 ) 可改写为 圪( 彳一互，) 磊= o( 1 2 3 ) 定义1 2 2 科对n 阶矩阵a ，是丹聊阶列t f 交规范矩阵，h = 蟛爿，假设h 的 某一特征对为( 互，只) ，则称互为a 在子空日j e = s p a n ( v ) 上的r i t z 值，简称r i t z 值；称 谚= 只为相应的r i t z 向量。用五和谚来逼近a 的特征值和特征向量，此逼近称之为 r a y l e i g h - r i t z 逼近。 事实上，j f 交投影方法就是r a y l e i g h r i t z 逼近。 设线性算子a m = 圪彳只，于是有如下定理。 定理1 2 1 3 9 1 予空间e 中的r i t z 值互和r i t z 向量痧是a m 的特征值和特征向量。 应用讵交投影方法求得的r i t z 值互和r i t z 向量谚是否收敛于特征值问题( 1 2 1 ) 的特征 值a 和特征向量昵? 实际上，当珊= n 时，r i t z 值互和r i t z 向量谚就是要求的特征值和特 征向量。如果m n ，且以的特征值互和特征向量谚接近a 的特征值 和特征向量识，则 残量( 4 一互，) 谚是小量。关于l i ( 以一丑，) 纪弘有如下估计式。 定理1 2 2 p 9 令= 0 只爿( ，一只) 9 ，则 i l ( 以一 ，) 识0 1 4 1 2 + 疋i i ( i 一只) 够0 ( 1 2 4 ) 由定理1 2 2 可见，特征向量识与子空间之问的距离忡一圪) 孵0 是一个非常重要的 量，通常一只) 仍0 不是小量，当且仅当聊m n 时，i i ( z - e ) 口, , l l = o 。当册 一时，t - p 捏：- 一 个正交投影算子，忖一只) 仍0 并不随m 的增大而必然减小。但是如果子空间e 比较特殊t 蝴l l ( z 一只) 仍0 随m 的增大而迅速减小。 假设子空i 日j e 是a 的一个脚维不变子空i 日j ，则必有历m 阶矩阵日，使得 信息t 程人学坝l 学位论史 r = a 一h = 0 ( 1 2 5 ) 显然，矩阵日是彳对e 的限制算子死的矩阵表示，并且日的特征值都是a 的特征值， 的特征值和特征向量都是a 的特征值和特征向量。 若子空间e 不是a 的不变子空问，则对于r ( h ) = 4 吒一圪h 中矩阵h 和a 的特征值之 问的关系，有下面的定理。 定理1 2 3 设由m 个n 维币交规范向量组成，h 为m m 阶矩阵，记 r ( h ) = a 圪一k h ，若a 的特征值为 ，屯，丸，h 的特征值为五，五，元，则可以找到 m 个不同的自然数，如，使得 l 九- 五i - 特征值及相应特征向 量的非常可靠和健壮的技术。 然而，当矩阵a 非对称时，在三列角化过程的每一步，都可能会发生严重中断【如。并 且严重中断的出现与舍入误差、问题的病态程度均无关。此时，问题变得非常复杂和困难。 关于如何处理和避免严重中断，目静己有了几个健壮的策略，t a y l o r 和p a r l e t t 提出了 l 锄c z o s 算法的“l o o k a h e a d ”版本，它利用2 x 2 选主元来改进l a i l c z o s 算法。后束c u l l u m 将不带再币交化的对称l a n c z o s 算法推广至非对称情况并提出了一种新的处理导出的三对 角矩阵的方法。同时，p a r l e t t l 2 3 1 和s a a d t l 8 1 等人从不同的角度研究了此方法。在没有严重中 断发生的日口提条件下，y e l 3 0 】分析了此方法的收敛性，结论表明：原矩阵的实部最大( 最小， 的特征值通常会在导出的三对角矩阵的特征值中出现。b a i l 2 4 1 的分析表明：在有限精度下， 如果r i t z 值的条件数合理并且没有严重中断发生，则r i t z 值的收敛性即意味着双讵交惟的 失去。 1 2 3 精化投影方法 对于非对称矩阵4 ，当我们用t f 交投影方法求解它的部分特征对时，可能收敛的非 常慢甚至发散，极不规则。为克服这一隐患，贾提出对于确定的近似特征值，摒弃现有的 使用经典投影方法求得的近似特征向量，而用另一个在求解子空日j 上满足最优条f ，f 的新的 向量作为近似特征向量，称之为精化向量，称这种方法为精化投影方法。理论分析表明这 种新的方法实际为两个萨交投影的复合【矧。 对任意求解子空f h je ，以及每一个近似特征值互( 可以是r i t z 值或者其它合理方法得 到的近似特征值) ，精化投影类方法【m ，捌为使用满足 卜互啦，4 = 。瓣，1 1 一互，弦8 ( 1 2 9 ) 的西，q 旧u - - 1 ) 作为与近似特征值互相对应的近似特征向量。称羁为a 在子空问e 上与互相对 应的精化向量，对指定的求解子空间e ，精化向量反，可通过计算一个小规模矩阵的特征 问题或小规模矩阵的奇异值分解( s v d ) 柬计算。特别地，当五为a 在子空f h 】e 上的r i t z 值 时，由关系式( 1 3 1 ) 和( 1 3 5 ) ，精化投影方法可以表述为 谚，置e ， ( 彳一五，) 谚上e ， f f ( 彳一互，) 蟊8 = 。m | i “n ：，0 ( 爿一互，) 甜0 第9 贝 ( 1 2 1 0 ) 信息t 程人学坝i ：学位论文 它用( 互，嗣) 作为( 磊，够) 的近似值。下面从精化投影类方法的收敛性理论和精化投影类算法 两个方面介绍这类问题的研究现状。 i 精化投影方法的收敛性理论 为揭示精化投影方法的本质，建立一整套平行于经典方法的严谨系统的理论，并与 经典难交投影方法比较，以说明新方法的优越性和发展潜力，最近几年，贾以及他和s t e w a r t 在这方面做了一系列工作。主要有 1 ) 精化向量羁的性态 在文献 2 2 ，2 6 ，2 9 q h ，对一般的投影空日j e ，建立了精化向量西。的先验估计式，并山此 说明了精化向量矗，收敛到相应的特征向量仍的充分条件与近似特征值五收敛到相应的特 征值丑的充分条件是相同的。因此精化投影方法彻底克服了传统的投影方法中可能出现的 在近似特征值收敛的情况下，相应的近似特征向量却可能收敛的非常慢甚至发散这一潜在 的隐患，从理论上可以保证在近似特征值收敛的情况下，相应的精化向量也必然收敛这人 大增强了精化投影方法的可靠性。 2 ) 精化向量巧与r i t z 向量谚的关系 文献【1 2 】从两个方面讨论了精化向量西，与r i t z 向量谚之间的关系其一给出了 s i n 0 ( 矗，谚) 的上下界，由此说明了只有在l l ( 彳一互，) 珥0 = 0 的情况下，a 会有谚= 羁。因此， 在一般情况下，精化向量羁与r i t z 向量囊是不同的；其二建立了近似特征对( 互，蟊) 的残量 l l ( 爿一互，) 谚l l 与近似特征对( 互，谚) 的残量l i ( 彳一互，) 谚0 之f h j 的关系，其结果表明前者怛不大了二 后者，并且在对称的情况下也可能比后者小的多，因此精化投影方法总足优于经典的投影 方法并可能远为优越。 3 ) 精化投影方法的一些其它性质的研究 在文献【7 】中给出了k r y l o v 子空间中精化向量的多项式表达式：在【2 9 】中。讨论了如何 理解精化投影方法等。 精化投影类算法 第1 0 贝 信息t 程人学侦l 学位论文 贾在提出精化思想，1 2 1 的同时，也指出这种思想对任意的投影方法都是适用的，将 精化思想应用到经典的投影方法即可得到相应的精化方法。如在a m o l d i 方法中应用精化 思想得到精化a m o l d i 方法、在子空间迭代法中应用精化思想得到精化子空i 、日j 迭代法。下 面介绍几种精化投影算法。 1 )隐式重新开始的精化a r n o l d i 方法( i r r a ) 7 1 与经典的a m o l d i 方法一样，实际计算中，为了能够收敛，精化a r n o l d i 方法一般必须 经过重新丌始。在文献 7 】中，贾研究了k r y l o v 予空日j 上精化向量的多项式表达式，利用 其结果提出了一种更加准确的位移，称之为“精化位移”( r e f i n e ds h i f t s ) 理论分析表明“精 化位移”对于所需的特征值的逼近程度要好于“准确位移”( e x a c ts h i f t s ) ，同时贾提供了计 算“精化位移”的廉价可靠方法。因此“精化位移”不仅在理论上优越于“准确位移”， 而且可以简便的计算得到。他将s o r e n s e n 的隐式重新丌始技术运用到精化a m o l d i 方法， 得到带“精化位移”的隐式重新丌始精化a m o l d i 方法( m r a ) 。大量的数值实验例子表明： 通常i r r a 会比i r a 有效，而对于一些困难问题和i r a 遭遇失败的问题，效果会更加明湿， 因此i r r a 是求解大规模矩阵特征问题更为有效的办法。 2 )隐式重新开始的精化调和a r n o l d i 方法( i r r h a ) 1 2 7 i 为了避免位移求逆的昂贵代价，贾提出了计算部分内部特征值和相应特征向量的精化 调和a m o l d i 方法，与i r r a 中的“精化位移，相似地引入“精化调和位移”，利用它将 s o r e n s e n 的隐式重新丌始技术应用到精化调和a r n o l d i 方法，得到隐式重新丌始精化调和 a m o l d i 方法( i r r h a ) 。数值算例将i r r h a 与m o r g a n 2 柳的隐式重新丌始的调和a m o l d i 方 法( i r h a ) ，i r a 以及i r r a 等方法的结果进行比较，表明对于内部特征值问题i r r h a 是 最优的方法。 3 ) 精化子空间迭代法1 2 2 i 贾从两方面对子空间迭代法做了改进。一是用精化向量代替原方法中的r i t z 向量，并 详细介绍了在算法中如何有效地计算；第二，改变原方法中的重新丌始矩阵，使之仅山所 求的特征向量的近似来组成。新方法收敛速度明显提高，与原方法相比最高能达到快数十 倍 第i i 贝 信息t 程人学颂i 学位论空 1 3 本文的结构 第一章，首先说明了本文的研究背景知识，其次介绍了解大规模矩阵特征值问题的 正交投影方法及相关理论知识。 第二章，介绍了本文的主要研究对象- j a c o b i d a v i d s o n 方法和理论，提出了块 j a e o b i - d a v i d s o n 方法，最后给出了理论分析。 第三章，结合精化策略改进了块j a e o b i - d a v i d , s o n 方法，并给出了收敛性分析。 第四章，利用收缩技术改进了精化块j a c o b i d a v i d s o n 方法。 第五章，指出了本文未完成的的工作和对本课题发展方向的展望。 1 4 符号约定 本文用r ”( c “) 表示n 维实( 复) 向量空间，r “( c ) 为所有的n x 肌阶实( 复) 知 阵的全体，用大写字母表示矩阵或者是线性算子，小写字母表示向量。 ，。表示 阶单位矩阵，若不产生混淆，用，表示。 彳是珂阶方阵， ，五， 为a 的特征值，五，屯，吒为相应的特征向量。a 的特征 对表示为( a ，x ) ，其中a 为特征值，x 为特征向量。 本文涉及的矩阵的特征向量均为币交规范特征向量，所给的范数若没有特别声明均 为2 范数。 x 7 0 “) 和x 7 ( x “) 分别表示向量x 和矩阵x 的转置( 共轭转冒) 。 列诈交规范矩阵v r “”( c ) 是指满足y 7 v = l ( 矿“v = l ) 的矩阵。 如果h ，以是珊个阼维向量，那么v = i v , ，以】表示甩研阶勉阵，其中v ，为v 的第 i 列。 如果v = ”以】，那么s p a n ( v i ，v 卅) 或者即日，l ( 矿) 表示由矿的列所张成的r 宅阀， s p a n ( v ) 1 表示子空问s p a n ( v ) 的话交补。 g 表示无穷小量。 o m 。( x ) 和。( x ) 分别表示矩阵x 的最大和最小奇异值。 u ( i ，：) 表示矩阵u 的第f 行。u ( ：，j ) 表示矩阵u 的第，列，u ( ：，i ：j ) 表示矩阵u 的第i 列到第，列构成的- i + i 列矩阵。 第1 2 贝 信息t 程人学坝l 学位论史 第二章块j a c o b i d a v i d s o n 方法及理论 2 1j a c o b i d a v i d s o n 方法 计算大规模矩阵部分特征值及相应特征向量的最常用方法是投影类方法。投影类方 法不对矩阵本身进行处理，在计算过程中只需要形成矩阵和向量乘积的子程序( 或者再加上 矩阵的转置与向量乘积的子程序) ，再利用其他一些处理技术，柬构造一个尽可能多的包 含待求的特征对信息的低维子空间，将矩阵往这个“适宜的”低维子空i 日j 中投影，从而在 这个低维子空b j 中计算出令人满意的近似解。所以在投影方法的计算过程中，最关键的是 获得高“质量”的求解子空间，通常的方法是对当前的子空间进行有效的扩充，从而完成 对近似特征向量的不多修正，使其逐渐逼近待求特征向量。在此过程中若能保持子空问的 最大维数m 小就能大大节省计算时问及存储空间。d a v i d s o n 方法和j a c o b i d a v i d s o n 方法1 6 ) 就是现在研究活跃的传统投影方法之一。 e r d a v i d s o n 于1 9 7 5 年提出了一种计算大型稀疏对称矩阵极端特征值的有效方法： d a v i d s o n 方法【3 l ，它。对于对角占优矩阵，d a v i d s o n 方法的收敛速度l ：k , l a n c z o s 方法要快。 随后它很快被推广到一般矩阵的情况，但它在扩充投影子空日j 方面存在着天然缺陷，于是 s l e i j p e n 和v a nd e rv o r s t 提出在近似特征向量的币交补空问中寻求特征向量新的信息的 j a c o b i d a v i d s o n 方法。他们通过解修正方程 ( ，一口妒“) ( 4 一互，) ( ，一币“) f = 一r ( 2 1 1 ) 获得对乒的一个修证向量f ，式中的( 互，) 为当静子空h j 圪上的近似特征对，r = 4 驴一互为 其残量。于是将投影子空间由圪扩充至圪在圪+ ，中将可能得到( a ，p ) 的一个更好的近似 对。 事实上，为尽可能实质地扩充予空日j ，注意到驴己在圪中，从s m n ( o ) 1 上找一个合 理的向量，将其加入k 。假设特征向量妒可分解为矿= 驴+ z ( z 上矿) ，代入一矽= a 妒中得到 彳( 驴+ z ) = a ( 驴+ z ) ( 2 1 2 ) 即 ( 爿一a 1 ) z = 一( 爿一a ，) 庐 注意到( ，一口妒“爿一旯，) = ，( ，一口眵“) z = z ，可得 ( ，一口妒”) ( 4 一t 1 ) ( 1 一i 妒”) z = 一r ( 2 1 3 ) 出于 是待求的，使用r i t z 值互代替a 就可得到 绝1 3 虹 信息t 程人学坝l 学位论文 ( ，一移“) ( 一互，x ，一口睁”) z = 一，( 2 1 4 ) 修币向量即通过解( 2 1 4 ) 式得到。文献 6 】讨沦了如此扩充投影子空间的优点，说明了 它可以比较有效的避免d a v i d s o n 方法可能出现的中断问题和停滞现象。 2 1 1j a c o b i d a v i d s o n 方法的算法描述 求矩阵a 的最大特征对的j a c o b i d a v i d s o n 方法可描述如下。 算法2 1j a c o b i d a v i d s o n 方法 1 输入矩阵a ，选择初始向量v o ，投影子空i 日j 的最大维数m ，计算v 1 = v o l l v o l i ， m = 彳h ，魄= 计；令k = 【v l 】，彤= 【w l 】，h j = 【 】，q = 啊，计算，= 一日v i 。 2 对k = 1 ，聊一1 执行循环 2 1 求解( ，一唯) ( 爿一岛顶一h 碟) f = 一，的近似解，且满足r 上唯； 2 2 对j = l ，2 ，k 执行循环 t ：= f 一( v 物v ， j = j + 1 2 1 3v k “= t ，+ 1 = a v t “，圪“= 【k ，吒“】，“= 【，w k + l 】； 2 4 对，= 1 ，2 , - - , k 执行循环 h j ，t + = v h ，+ l ， 吃山= 呓。_ ； ，= j + 1 2 5 计算珥+ 的最大特征对( 皖。y ) ； 2 6 y ；酾y ，”5 ，s = a u , 一钾； 2 7 测试是否收敛，若收敛则终止；否则，k = k + 1 ； 3 重新丌始：k = 【甜】，彬= 【s 】，h = 吼+ i 】，返回2 上述算法是计算矩阵a 的最大特征值及相应的特征向量。如果需要计算a 的按实部 ( 或按虚部或按模) 最大的特征值时，则在算法中作相应的调整。 为了减少运算的存储量和计算量，算法不允许投影子空问的最大维数m 很大，而算 法在m 的迭代中，一般满足不了收敛精度，所以几乎所有的投影算法都采用重新丌始技术。 随着人们对它的研究，重新丌始策略也丰富起来，较著名的有显式、隐式重新丌始和动态 稠密重新丌始技术【1 等。此外，在重新丌始过程中，保留多少、保留哪些r i t z 向量是j d 钨1 4 缸 信息t 程人学坝i 学位论文 方法中一个非常重要的环节。这些改进使得j d 方法变得更加灵活和更加有效。目前，j d 方法已成为计算大型对称和非对称稀疏矩阵极端特征值问题的最有效方法之一。 2 1 2 修正方程的求解与收敛性分析 对修正方程 ( 一唯v j ? ) ( 4 一哦，) ( ，一h 嵋) f = 一r 求解， v a l ，我们可以把它看作变换算子把( 4 一e d ) 限制到吱的正交补上。在珂论t 求 解时，有如下结果： t = 一( 爿一e d ) 一1 ，一f ( 彳一e d ) 一= 一唯一f ( 爿- o d ) - 1 吃 其中f = 一l v ? ( a o k i ) 1 吨的选择保证f ( ) 1 。但在实际的计算中，我们只需要得到它的 近似解即可，例如通过很少的几步g m r e s 迭代法来计算。 设 f ( a ，吃) = f ( a ，v , x a 一最，) = 【( ，一咋) ( 爿- o d ) l f 。】“( 爿一最，) ( 2 。1 5 ) 则t = f ( a ，吒) 吒足一个准确的解；由于在实际计算时只需要近似解就可以达到求的精度了， 所以通常求的是近似解：t = f ( a ，喙) = 一f ( 4 一统，) - 1 咋，其e e f = l ( 彳一最，) - 1 。 对预处理矩阵f ( a ，v k ) = 【( 卜唯) ( 爿一e d ) l 。，1 - l 我们有以下收敛性定理。 定理2 1 1 设在j a c o b i d a v i d s o n 方法的迭代中形成的投影子空剐构成的她孵序列 圪) ? ，矩阵a 在它上的证交投影序列为 玩) ? 。如果a 足h e r m i t i a n 矩阵，则 皖h 。足坼调 递增的且收敛。另外，如果预处理矩阵，( 爿，k ) = - ( ，一咋) ( 4 一皖驯r 是一致诈定的， 则序列 ( o k ，y ) ) 。收敛到j 4 的一个特征对。 证明：由算法2 1 的过程可知，峨+ ：l ：l ，即以是风+ 。的前七阶顺序主予阼， 当彳是h e r m i t i a n 矩阵时，可知风与峨+ 。也都是h e r m i t i a n 矩阵，从而根据极大、极小值 定理中的分隔定理知 b g s 岛g s 皖s 噬皖“ 其中岛，岛，o k ，皖+ 和研，g ，嚷分别是巩+ 。和蛾的特征值。在算法2 1 中计算的是矩阵的 最大特征值，由上面的陈述容易知道 吃) 。是单调递增的；又因为h 。= 皑_ kr 所以有 l i l = l 以 a v d = l l a l i ，从而只- 如也丸。设幺是目标向量p 和第k 步求得的近似特征向量吒之b j 的央角t 如果它满足t a r i 矢 0 ，使得对所有的z 上屹都有 o 0 ， 则 ( 皖，力h 。收敛到a 的一个特征对。 证明：从定理2 1 1 的证明和( 2 1 5 ) 可得 憋2 f i t 昏= o 而由条件e i g 1 , e 1 1 2 o 可知，l i m 唯= 0 。证毕。 定理2 1 3 只适合于不需要重新丌始的情况， 的定理显示这种情形可能出现停滞。 ( 2 i 7 ) 而实际计算中往往需要重新丌始。下酾 定理2 1 4 假设f = f ( a ，叱h 的计算值是 p ( a ，v k ) v k = f ( a ，v k ) v k + 矗= f ( a ，v k ) ( a 一0 , 1 ) v k + 毛 其中瓯是误差。如果爿是h e n n i t i a i l 矩阵，矩阵厂( 4 ，唯) 是一致证定的，则当! 鳃唧。0 时 ( 包，力 。收敛到a 的一个特征对。 证明：在j a e o b i d a v i d s o n 方法中，计算的唯+ = 户( 4 ，屹) 唯使得! 鳃户( 爿，唯) 咋= 0 ， 从而导出! 鳃( r , a f ( a ，咋) 噍+ 吒) = 0 。证毕。 当条件憋岛= 0 不满足时，j d 方法可能出现停滞