（计算数学专业论文）可重启的广义二阶krylov子空间方法.pdf

摘要 本文，我们如何研究求解二次特征值问题( q e p ) ： ( a 2 m + a d + k 净= 0 这里，m ，d ，k 都是阶矩阵，我们假定m 是非奇异的这个问题有许多的 应用，包括解相应的二次矩阵方程：m x 2 + d x + k = 0 首先，我们介绍基于一对方阵a ，b 及向量u 产生的二阶k r y l o v 子空间 靠( a jb ，“) 和构造在此空间上的一种有效的方法一一二阶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 子空间的重启方 法我们的方法应用了m o r g a n 的重启的思想，即算法中每一步都保留最接近 我们所求的特征值的若干个r i t z 对这样，新的子空间由两部分组成：一部分 是将最接近的那个r i t z 向量作为初始向量进行子空间的扩展而形成的向量， 另部分是上一步所保留的r i t z 向量中剩下的向量这样形成的子空间就会 含有更多的我们想要求得的r i t z 对的信息，继续下去就能达到我们的目的 数值实验说明，我们提出的方法是有效的 本文分为六章第一章是介绍二次特征值问题的背景，简单阐述求解该问 题的各种方法及优缺点第二章引入二阶k r y l o v 子空间，并在此基础上提出 广义二阶k r y l o v 子空间的定义及形成的方式，并结合q e p 找出两者之间的关 系第三章主要是列出广义二阶k r y l o v 子空间的基向量的形成的算法，并讨论 在此过程中出现的压缩和中断的现象，以及处理的方法而在第四章，我们直 接将该子空间方法应用到求解q e p 中在第五章，我们针对在第四章给出的 算法中可能出现的问题，提出一种可以重启的方法，该方法可加速收敛，节约 计算时间第六章，我们给出了四个数值例子，从不同的角度说明改进后的算 法是有其优势的本文的主要贡献是：将本文提出的广义二阶k r y l o v 子空间与 m o r g a n 重启的思想【1 3 】相结合，提出一种解q e p 的，有效的重启方法 关键词：二次特征值问题，线性化问题，二阶k r y l o v 子空间，广义二阶k r y l o v 子空间，r i t z 对 a b s t r a c t i nt h ep a p e r ，w es t u d yh o wt os o l v et h eq u a d r a t i ce i g e n v a l u ep r o b l e m ： ( a 2 m + 入d + n ) x = 0 ，m1d ! ka r es q u a r em a t r i c eo fn - o r d e r w ef 1 k s u m emi sn o n s i g u l a r t h i s p r o b l e mh a sm a n ya p p l i c a t i o n s ，i n c l u d i n gt h es o l u t i o no ft h ec o r r e s p o n d i n g q u a d r a t i cm a t r i xe q u a t i o n ： m x 2 + d x + k = 0 w ef i r s ti n t r o d u c eas e c o n d - o r d e rk r y l o vs u b s p a c e 鲰( a ，b ，u ) b a s e do i la p a i ro fs q u a r em a t r i c eaa n dba n dav e c t o ru a n dt h es e c o n d - o r d e ra r n o l d i m e t h o di sj u s tae f f e c t i v em e t h o db a s e do nt h i sk i n do fs u b s p a c e i ti su s u a l l y u s e df o rs o l v i n gt h eq u a d r a t i ce i g e n v a l u ep r o b l e m i tc a np r e s e r v et h eo r i g i n a l s t r u c t u r e so ft h eq e pa n da c h i e v et h eg l o b a lc o n v e r g e n c eb e h a v i o r s h o w e v e r t h es e c o n d - o r d e ra r n o l d im e t h o di sd i 伍c u l tt or e s t a r t i nt h e p a p e r ，w em o d i f yt h eg e n e r a t i o nw a yo fas e c o n d o r d e rk r y l o vs u b s p a c ea n d t h em o d i f i e ds u b s p a c ei sc a u e dt h eg e n e r a l i z e ds e c o n d o r d e rk r y l o vs u b s p a c e t h e nw ed e r i v ear e s t a r tm e t h o db a s e do nt h en e ws u b s p a c e w ea p p l ym o r g a n sr e s t a r tt h i n k i n gf o ro u rp r o b l e m ，i e ，w ep r e s e r v et h e n u m b e ro fr i t zv e c t o r st h a ti sm o s tc l o s e s tt ow h a tw ew a n t e di ne a c hs t e po f t h ea l g o r i t h m ，t h e nt h en e ws u b s p a c ei sc o m p o s e do ft w op a r t s ，o n ep a r ti s t h eb a s ev e c t o r sw h i c hi sp r o d u c e db yt h em o s tc l o s e s tr i t zv e c t o ra st h ei n i t i a l v e c t o rf o rt h ee x p a n s i o no ft h es u b s p a c e t h eo t h e rp a r ti st h er e m a i n i n gr i t z v e c t e r so fth el a s ts t e p a n dt h en e ws u b s p a c ew i l lc o n t a i nm o r ei n f o r m a t i o n o fo u rm o s tw a n t e dr i t zp a i r w ew i l la c h i e v eo u rp u r p o s ei fw ec o n t i n u ei n t h es a m ew a y n u m e r i c a le x a m p l e sd e m o n s t r a t et h a tt h em e t h o di se f f e c t i v e t h ep a p e ri n c l u d e ss i xp a r t s i nt h ef i r s tp a r t ，t h er e l a t e db a c k g r o u n da n d t h ec o u r s eo fd e v e l o p m e n ti si n t r o d u c e d t h eb a s i cm e t h o d st os o l v et h el a r g e s c a l eq e pp r o b l e mi sa l s oi n c l u d e d i nt h es e c o n dp a r t ，as e c o n d o r d e rk r y l o vs u b s p a c ei si n t r o d u c e da n dt h e g e n e r a l i z e ds u b s p a c ei sd e f i n e d t h e nt h er e l a t i o n s h i po ft h eb o t hi sf o u n d i nt h et h i r dp a r t ，w eb r i e f l yd e s c r i b et h eg e n e r a t i o no fb a s i sf o rg e n e r a l i z e d s u b s p a c e a n dw ed i s c u s st h ep h e n o m e n o no fd e f l a t i o na n dt h eb r e a k d o w na n d g i v et h ec o r r e s p o n d i n gm e t h o d st oc o p ew i t h i nt h ef o u r t hp a r t ，w ed i r e c t l ya p p l yt h en e ws u b s p a c et os o l v et h eq e p i nt h ef i f t hp a r t ，w ed e r i v eam e t h o df o rr e s t a r t i n g t h em e t h o dc a ns a v e t h ec o m p u i n gt i m eg r e a t l y i nt h el a s tp a r t ，w et e s tf o u re x a m p l e sa n dt h er e s u l t ss h o wt h a tt h e m o d i f i e da l g o r i t h mh a sb e t t e rp e r f o r m a c et h a nt h eo r i g i n a l k e yw o r d s ：t h eq u a d r a t i ce i g e n v a l u ep r o b l e m ；l i n e a r a l i z e dp r o b l e m ；s e c o n d o r d e rk r y l o vs u b s p a c e ；g e n e r a l i z e ds e c o n d - o r d e rk r y l o vs u b s p a c e ；r i t zp a i r s m 厦门大学学位论文原创性声明 本人呈交的学位论文是本人在导师指导下，独立完成的研究成 果。本人在论文写作中参考其他个人或集体己经发表的研究成果，均 在文中以适当方式明确标明，并符合法律规范和厦门大学研究生学 术活动规范( 试行) 。 另外，该学位论文为() 课题( 组) 的研究成果，获得() 课题( 组) 经费或实验室的 资助，在() 实验室完成。( 请在以上括号内填写课 题或课题组负责人或实验室名称，未有此项声明内容的，可以不作特 别声明。) 声明人( 签名) ：斗8 期专 年多月r 日 厦门大学学位论文著作权使用声明 本人同意厦门大学根据中华人民共和国学位条例暂行实施办 法等规定保留和使用此学位论文，并向主管部门或其指定机构送交 学位论文( 包括纸质版和电子版) ，允许学位论文进入厦门大学图书 馆及其数据库被查阅、借阅。本人同意厦门大学将学位论文加入全国 博士、硕士学位论文共建单位数据库进行检索，将学位论文的标题和 摘要汇编出版，采用影印、缩印或者其它方式合理复制学位论文。 本学位论文属于： () 1 经厦门大学保密委员会审查核定的保密学位论文， 于年月日解密，解密后适用上述授权。 () 2 不保密，适用上述授权。 ( 请在以上相应括号内打“”或填上相应内容。保密学位论文 应是已经厦门大学保密委员会审定过的学位论文，未经厦门大学保密 委员会审定的学位论文均为公开学位论文。此声明栏不填写的，默认 为公开学位论文，均适用上述授权。) 声明人( 签孙斗嘶 j 年2 只s 日 第一章绪论 i c t i ( a ，口) = s p a n v ，a v ，a 2 u ，a 俨1 t ， ( 入2 m + a d + k ) x = 0 ( 1 1 ) _ - 。k a x = 入mh 即在c 1 2 ，中，c = - ，d 一0 k ，g = m 。0 ， ，可= 求解这里日= g 一1 c = 一 ? 1 。一1 k = a 三 ，其中a = 一m d ，b = 一m k 这样，二次特征值问题( 1 1 ) 就转化为通常的特征值问 第一章绪论 2 采用这种方法求解二次特征值问题的优势在于，它可以充分利用般特征值 问题的成熟、有效的解法来解二次特征值问题然而，这种方法有如下缺点：第 一 线性化之后的广义特征值问题的阶数是泵二次特征值问题的两倍，第二，原问 题的矩阵结构没被利用或被破坏如原问题的矩阵m ，d ，k 具有对称，正定【12 】 之类的性质，那么线性化之后的问题的矩阵不一定能保留这些结构和性质 近年来，学者们直在研究不进行匕述转化，而能直接应用于二次特征值 问题的数值方祛【7 】， 4 1 这类方法不再将二次特征值问题转化为半的特征值问 题，而是选择个低维的子空间，对二次特征值问题进行投影，将其转化为维数 较小的二次特征值问题，再列刀、型的二次特征值问题进行处理 处理外型的二次特征值问题有很多的方法，j a c o b i - d a v i d s o n 方法【5 1 ，【2 】，【6 】 就是其中的种该方法次计算个特征值，具有局部收敛的性质a r n o l d i ， l a n c z o s 类型的方法 8 ，11 】也可用来对二次特征值问题投影然而，这些方法与 应用k r y l o v 空间的方法处理线陛化后的问题相比，它们的收敛速度要慢后来， 又产生了使用q e p 的扰动理论的子空间近似的方法 14 ，对于该方法，尽管可以 使用r a y l e i g h q u o t i e n t 迭代加速收敛，但该方法强烈的依赖于原始的近似， 所以也有其局限陛 在参考文献【1 6 】中，b a i 和s u 描述了种= 阶的k r y l o v 子空间方法 方面，它能够直接应用于问题q e p ，保留它的结构另方面，它具有类似于 k r y l o v 子空间方法的好的收敛 生 本文就是在它的基础上所作的改进首先，我们修改产生二阶的k r y l o v 子空 间的初始向量，称修改初始向量后产生的子空间为广义的二阶k r y l o v 子空间这 种彭础提由线陛化之后的问题( 1 2 ) 的特征向量的特殊的形式所决定的然后， 我们建立该子空间与k r y l o v 子空间的关系，即使修改后的子空间能够包含相应 k r y l o v 子空间的全部的基向量的信息所以使用该种子空间对q e p 进行投影， 与列甥龇后的广义问题用k r y l o v 子空间进儆b 理相比，可达到相同的效屎之 后，我们给出的广义的二阶k r y l o v 子空间的基向量的形成方法与文献 1 6 】给出 第一章绪论 3 的力秘省雏1 本文的主要贡献是：将本文提出的广! ；c = 阶k r y l o v 子空间与m o r g a n 重启的思想【1 3 】相结合，提出种有效的重启方法最后我们给出些数值实 验，从不同的角度说明改进后的算法是有其优势的 第二章二阶k r y l o v 子空间 2 1 二阶k r y l o v 子空间 设a ，b 是n 阶方阵 t 0 是维向量，记基于a ，b ，t i 的二阶k r y l o v 子空间为。 9 n ( a ，b ，u ) = s p a n v o ，乔，蔬一1 ) r 02u ， 再= a 而， 弓= a 弓一1 + b 5 2 ， 歹= 2 ，他一1 2 2 广义= 阶k r y l o v 子空间 在原来的二阶k r y l o v 子空间基础上，我们改变产生序列的方式，得到广义的 子空间：记广义的二阶k r y l o v 子空间为吼( 4 ，b ，p ，u ) ：且 瓯( a ，b ，p ，牡) = s p a n t o ，r l ，r n _ 1 ) 而序列 ) 的产生的方式修改为z r o2p r l = a p + b u ， 乃= a r j 一1 + b 勺2j = 2 ，n l 该子空间是二阶k r y l o v 子空间的推广，即 鲰( a ，o ，p ，乱) = 庀n ( a ，p ) 第二章二阶k r y l o v 子空间 众所周知，对于二阶k 珂l o v 子空间| i c n ( a ，p ) ，有如下的性质： v z 尼。( a ，p ) ，那么z 可以表示为z = 一1 ( a ) p 广义的二阶子空间瓯( a ，b ，p ，t 1 ) 也有类似的性质 当p = o u 时， r o = o u ，r l = o a u + b u = ( o a + b ) u 5 r 2 = ( o a 2 + a b + o b ) u r 3 = ( o a 3 + a 2 b + o a b + o b a + b 2u 综上，巧= p i ( a ，b ) u 而这里的功( q ，p ) 是o t ，p 的多项式，并有如下的递推关 系式： 胁( a ，p ) = a p j l ( q ，p ) + p 功一2 ( q ，) p o ( a ，卢) = 0 ，p l ( a ，p ) = p a + p 所以， vy 吼( a ，b ，p ，u ) ，也有y = 磊一i ( a ，b ) u 2 3 广义= 阶k r y l o v 子空间与二阶k r y l o v 子空间的关系 假如我们使用k r y l o v 子空间类的方法求解( 1 3 ) 的矩阵h 的特征对，以矩 阵日及初始向量石= u 。 形成k 珂o v 基向量，并记 j i c 。( 日，功= s p a n 石，h 6 ，h 2 ，h n - 1 ：刃 则通过计算可直接得到二阶k w y l o v 子空间与标准的k r y l o v 子空间的联系： 阱魄纠 ( 2 1 ) ( 2 1 ) 也可写为。 印n n t 一，日一，日2 一，扩一1 砚= s p n n ? 凳耄r 2 。 耄r n - 一：1 ( 2 2 ) 由此可知，二阶的k r y l o v 子空间的基 弓) 包含了疋。( ，功的所有基的信 息，所以子空间鲧( a ，b ，t ) 提供了直接求解二次特征值问题( 1 1 ) 的充分的信 息，而不需对问题( 1 1 ) 事先进f 亍线 生- 化的处理 ft | 但是，( 2 2 ) 式中用来扩展成h 的k r 、 l o v 子空间的初始向量石= ll 太 【0j 特殊了，它不具般性，必然会遗漏些信息 而我们知道：初始向量的好坏会直接影响到特征值收敛的速度鉴于这种考 虑，我们选取更具_ 骰性的初始向量：将石的第二个元素改为非零的，即取初始 i。l 向量t ，：l p 1 这时，通过计算我们得到： 【t 正j j i c 。( 日，口) ：印n 礼 u ，日u ，日：移，何。一。u ) ：s p n 扎f pr i u r 0 札1 i r n - 2 l j 其中， r 0 = p ，所以子空间g n ( a ，b ，p ，t 1 ) 的基向量序列 巧 n ：- o i 包含了几乎 瓦n ( 日，t ，) 的所有基向量的信息，只是不含有关u 的信息 但是，当我们取p = o u ，口为常数时，就会有 s p a n v ，h v ，h 2 ，日俨1 u ) = s p a n 此时，向量序列 巧 j n ：- - 0 1 就包含了j i c 。( h ，u ) 全部基向量的信息 这样，使用基于吼( a ，b ，p ，乱) 的子空间方法求解问题( 1 1 ) 与使用j i c 。( ，? u ) 的子空间方法求解问题( 1 3 ) 应可达到相同的效果 您 n 32 ，- 1j 1 2 一 一 n n r r 您 n 1 0 r r 钆 。l 第三章广义二阶k r y l o v 子空阏基向量的墅成 一j _ - _ _ _ _ _ _ - _ _ - _ _ _ - _ _ h _ _ _ - - - - - _ _ _ _ _ - - _ _ _ _ - - _ _ _ _ _ _ _ _ _ - _ _ _ - _ _ _ _ _ 一一。 一 一 第三章广义二阶k r y l o v 予空间基向量的形成 3 1 广义的二阶a m o l d i 过程( g s o a r 过程) 算法1 。g s o a r 过程 j q l = p l i p f 2 p l = 钍圳p 1 只o r 歹一1 ，2 m d o 彳。r = a 彩+ b p i 5 。 s = q l 院 o ri = 1 ，2 ，j d o z 一毋r 8 r ：一r q i t q 奠 s ：一嚣一p i t i j j 口 e n d o r 1 1 ， 屯+ i j 一l i 2 ，t ft i + l , j = 0 ，s t o p 1 3 q 1 。1 一r t j + l j l 毒。p j + l s | t 啦毒 1 5 e n df o r 在该算法中，若记n 髭矩阵q 拜一( q l ，盘，散，n 矬矩隆 只一 p 1 ，p 2 ，加) ，佗n 阶的上h e s s e n b e r g 矩阵，瓦一( t 巧) 则这些矩阵成立以 第三章广义二阶k r y l o v 子空间基鱼量鲍彤成 8 觚坛 ，则一一： b 计q n q n + l 磊 惴脱捌t 对名。一枷3 懈舰籽蜘 = 一= ：= 闰： 。子空间方法求解会发生中断，此时，算法1 也中断但若序列 i 。 1 ) 线性 第三章广义二阶k r y l o v 子空间基向量鲍形虐 g 间方法求解线i 生北问题( 1 3 ) 就不会发生中断，此吨自然也希望算法1 也不会 中断，因此修改算法1 如下； 算法2 g s o a r 法 第j - j f 步同算法1 1 2 i ，t + l j = 0 1 3 i l s s p a n p iii ：q i = 0 ，1 i 歹) f 彳r e t u r n ( 此时该算法中断) 1 5e l s e 1 6 岛+ 1 j = 1 1 7 q j + l = 0 1 8 p i + i = s 1 9 e n d i f 2 0e l s e 2 1 q j + l = r # j + l d 2 2 p i + 1 = s t j + l 。j 2 3e n dt 2 4e n df o r 该算法有几点要说明的： 第1 2 1 9 步是对于中断、压缩的处理当t j 1 , j = 0 时，分两种情况：第种， 当满足1 3 步条件的时候，此时称为中断使用该条件的原因可由以下的定理3 2 进行证明第二种，当不满足1 3 步的条件时，跳至第1 6 步，令t j + l ，j = 1 ，算法 继续进行这种情况称为压缩 第三章广义二阶k r y l o v 予空圆基鱼量勇乡虫 由于该算法使用了压缩技巧，所以序列 佛) 中存在零向量，其中的非零的向量构 成磊( a ，b ，p ，t ) 的组基我们记为q m ， m ，l 在般的a r n o l d i 过程中，如果算法中断，则说明( 日，秒) 是h 的不变子空间， 且 1 1 ，耽，v 3 ) 是该子空间的组标准正交基类似的，该算法如果发生中断， 则i q i 形成h 的不好空间但不同的是，该组基不是列正交的 1 弓l 定理3 2 如果用算法2 实现的g s o a r 过程在第j 步中断，则以h ，秒进行的 a r n o l d i 过程在第j 步中断反之亦然 证明见参教献口可中的定理舅j 1 0 第四章一种基于g s o a r 的投影方法 第四章种基于g s o a r 的投影方法 在这节中，我们采用子空间投影方法，将广义的二阶k r y l o v 子空间应用到求 解二次特征值问题中 对于问题( 1 1 ) ，我们有a = 一3 1 d ，b = 一m - 1 k ，应用基于广义二阶 子空间吼( a ：b ：p ，t 1 ) 的r a y l e i g h - r i t z 过程，我们寻求近似特征对( 0 ，z ) ，z 鲰( a ，b ，p ，竹) ，设置g a l e r k i n 条件= ( 口2 m + p d + k ) z 上9 n ( a ，b ，p ，t 正) 等价的， q t 。( 口2 m + o d + k ) z = 0 ，名= q m g q 。是由g s o a r 生成的瓯( a ，b ，p ，t ) 的标准正交基，m 钆e 述方程也即 ( 9 2 朋，m + o d m + k | m ) 9 = 0 ，( 4 1 ) 其中 m r = q r 。m q m ，d m = q 。td q m ，k m = q v 。k q 。 ( 4 2 ) 特征对( 口：g ) ( 即方程( 4 1 ) 的解) ，称为问题( 1 1 ) 的原始r i t z 对，而 ( 0 ，z ) ，z = q m g 称为问题( 1 1 ) 的r i t z 对直接作用于二次特征值问题可以将问 题中的矩阵 ，d ，k 的结构保留下来，即如果m 是对称正定的，则l 也是对 称正定的，d ，k 是对称的，则d 。，k n 也是对称的这样，投影之后形成的新 的二次问题与原问题有相同的结构，并且该新问题的阶数远小于原问题而对于 该小型的二次特征值问题( 4 1 ) ，我们有很多方法球解，般使用q z 或q r 算 法这样，我们就可以得到原问题的近似特征对( 口，z ) 算法3 直接用于解二次特征值同题的g s o ar 法 f 首先，使用初始向量t l ，令q 1 = u ：i ，1 = q i j r q l ，d 1 = q t d q lk 1 = q t k q l ， 求解特征值问题 ( 1 9 2 a ，1 + o d l + k 1 ) g l = 0 第四章一种基于g s o a r 的投影方法 1 2 并取p = o i q l g l ，牡= q l g h 将p ，牡作为初始向量，然后应用g s o a r 法形成空间 舅求解似，式的小型的二次特征值问题( p ，g ) 是它的特征对，则原问题的r i t z 彳通过残向量的相对误差来检测近似特征对( p ，z ) 的精确度，即 朋= 删崭瑞韶 3 ， 他s2 而币瓦习砷可丽 j 如果r e s t o l ，则该近似特征对收敛t o l 为需要设置的值，般为机器精 在实际计算中，不需要保存t i j 的值，矩阵t 只用于进行理论推导，不参与特征 对于初始向量的选取，p = 口1 q 1 9 1 ，t = q ：g l ，根据第5 节中的定理5 1 ，u = f ：1 是日的近似特征向量，而以近似特征向量作为初始向量厶使以即进 行的a r n o l d i 过程收敛的更陕而g s o a r 算法与对应的a r n o l d i 算法可达到相 在第三步中求解小型q e p ，可先将其进行线性化，转化为广义特征值问题，然后就 可以使用任何种求解广义特征值问题的方法，般采用q z 算法来求解所有的 特征值和特征向量也可进步将其转化为般的特征值问题，然后再进行求解 第五章重启 1 3 第五章重启 5 1 算法3 的不足之处 在算法3 中，当n 增大时，运算量也将逐渐增大方面，在第1 步形成基 的过程中，新的向量需要与前面的向量做正交，这个运算量会逐渐增大而且， 由于舍入误差的影响，当n 逐渐增大时，正交性逐渐失去另方面，在第3 步 中需要求解投影后的二次特征值问题，该问题的阶数为仇，而m 是由n 直接决 定的，当n 变大，该问题的求解也将耗费更多的运算并且，随着礼的增大，在 第二步中，q m ，甬靠， 的存储量世骅手变大综上，我们考虑重启的算法 5 2 一种重启的思路 对于般的特征值问题，若直接使用近似特征向量i 基彳亍重启，那么重启前所形 成的k r y l o v 子空间的大部分信息都会丢失m o r g a n 在3 喃13 】中提出了种 改进的摅 先设置两个参数m ，k ：仇表示子空间的最大维数，k 表示重启后子空间扩展 的维数当算法进行到第m 步时，我们保留最接近我们要求的特征值的m - k + 1 个r i t z 对，记为( 咄，玩) ，其中( u 1 ，玩) 为最符合要求的r i t z 特征对这样，新的 m 维的子空间由以下方式可得，前k 个向量是由a ，玩产生的k 维子空间的， 后m k 个是我f f 褓留的近似特征向量，也即 s p o 礼 玩，a 玩，a 2 历，a k - 1 玩，玩，虱一k + 1 ) 新的子空间能有效的保留重启前的子空间的大部分信息用该子空间继续进行求 解会收敛得更陕 以下，我们将此法应用到广义的二阶k r y l o v 子空间上也设置两个参数k ，m ， 它们的含义同上当用算法2 进行到第m 步时，不再进行扩展而是重新启动， 我们同样地保留这步中最接近我们要求的特征值的m k + 1 个r i t z 对，记为 ( 仇：z i ) 而( 口l ，z 1 ) 为最符合要求的近似特征对 第五章重启 1 4 选择初始向量t = z l ，p = 0 1 z l 重新形成k 维的子空间，记为吼( a ，b ，p ，u ) 再将余下的m k 个r i t z 向量加入到该空间来，即重启后的空间有如下的形式： s p a n p l z l ，r l ，r 2 ，r 七一1 7 如物，0 3 2 3 ，日m 一七十l ；m 一七+ 1 ) 、_ _ i _ _ _ l _ _ 、，o - _ - _ _ - _ 一 e 述空间包含了如下空间 ( 5 1 ) r1 s p n n i 9 l z lr l 您r 一1 如勿以勿o m - k + 1 - k - l - 1 1 ) ( 5 2 ) i z lr or l r k 一2勿施 钿一k + ll 令玑= o 磊i z i ，则由c z l ，式可得 s p n 礼t 秒- ，日y ，日2 y ，日七一1 y t ，= s p 。佗 0 魂1 z l r 绚l r r 2 。： 所以( 5 2 ) 式中的空间又可记为： s p a n y l ，h y l ，h 2 y 1 ，日七一y 1 ，y 2 ，一七+ 1 因为玑为线性化后的问题( 1 2 ) 的近似特征向量，也即日的近f 以特征向量该 性质可由以下的定理5 1 证明，所以( 5 2 ) 式中的空间也是矩阵日使用m o r g a n 的重启方法所生成的空间，而( 5 1 ) 式的空间包含了( 5 2 ) 式空间的所有基的信 息，所以由( 5 1 ) 式形成的空间是可以达到重启的目的的，即我们采用的方法形 成的空间是有效的 r iabi 定理5 1 已知矩阵h = li ，其中，a = 一m d ，b = 一m k ，如果 i - ，0j ( u ，) 是用基q m 对问题f ，_ f f j f a 2 m + a d + k ) x = 0 第五章重启1 5 曼 栅删耻如一 渊；首先，闻越c y = a 劬与h h y = a y ”e “t f f 一叫甜，帕棚证 卜m - d - 。km q , , l0 川w u = 叫圳k 0 w u 一q 了q m q 警q m ： = 。 q 氛：q m ： ： 用 凇 u 绷 磁 为 引 陆 鲫 够 谢 蝴 、t ， r ， 崭 融 擞 胁 第五章重启 1 6 算法4 j 首先，使用初始向量牡，令q l = t ，m 1 一q t m q l ，d i = q t d q lt ( 1 一 q r lk q l ，求解特征篡闻题 ( e 2 m 1 + o d l + k 1 ) g l 一0 可得p = o i q i g l ，t | 一q l g l 将p u 作为初始向量 褒进入循坏i = 王，2 。m 一1 2 。1 ，利用算法2 形戎子空阁磊( a ，b ，p ，牡) 盼基向量矩阵酝。 2 2 懒阵m = q ；m q l ，d i q ；d q i ，k = q ；k q i 2 。童求霹二次特征值闻题； ( 铲坛+ 护照+ 鲍) g = 0( 5 3 ) ( 0 1 ，9 1 ) 是最符合要求的r i t z 对，则原问题的近似特征对是( 0 1 ，z 1 ) ，z l q l g l | i q l g l | 当i m 一1 时，保留最接近我们要的那m 一七十1 个r i t z 对( 以，忍) ， 乏= q g li = 1 ，。，粥一k + 1 ，将袅锞存在矩阵要y 的对角线主，z i 存 在矩阵e u 的列中 2 4 ，如果矗。夥式中的r e 8 满足：r e $ t o l 则跳出整个算法，否鲥继续 舅重启： 进入循环；歹= 1 ，2 ，k l 3 1 ， 将p 一0 1 z l ，乱一z l 作为初始向量，形成子空间9 3 ( a ，b ，p ，u ) 的基向量心 s 2 计算坞= 骘m 岛，d j 一碍d 玛，= 骘k 恐 第五章重启 1 7 ( 口2 坞+ o d , + 巧) g = 0 ( 5 4 ) ( p - ，9 1 ) 是最符合要求的特征对，则原问题的近似恃征向量是( 口，z 1 ) ，z 1 = r l g l i l 冗1 9 1 i l 3 4 ，如果w e $ t o l 则跳出整个算法，否则继续 彳形成基向量： 4 j ，从e v , e u 中将以，磊提取出来，q i = 以五，i = 2 ，m k + 1 将 q 2 ，q a ，一七+ 1 与第3 步中形成的r o ，r l ，r 2 ，仉一1 作正交化过程，形成 组标准正交基记为q m 彳易计算m _ m = q * m q m ，d m = q 二d q 。，k 麓= q k q m 名只求解二次特征值问题： ( 萨砀，m + 砀m + 矾) 歹= 0( 5 5 ) ( 瓦，甄) 是最接近我们想要的特征对，则原问题的近似r 毗对是( 0 1 ，五) ，五= o 。y i i o m 玩0 彳彳，如果r e 8 t o l 则跳出，否则回到第3 步 该算法要说明的是： 如果我们已经有近似的特征向量了，那么该算法可直接从第3 步开始，大大简化 了计算 初始向量的选取与算法2 相同，在数值实验中可证实这样的选取对于重启会更好 第六章数值实验 1 8 第六章数值实验 6 1 数值实验 在铡l ，例2 和例3 中，我们按照如下的方式选取矩降 m t r i l ( r a n d ( n ) ) + t r i l ( r a n d ( n ) ，- 1 ) ；m = m + 2 0 幸e 爹( 铭) ； d = t r i l ( r a n d ( n ) ) 十t r i l ( r a n d ( n ) ，- 1 ) ；k = - e y e ( n ) 初始向蛩誊隧诹为t 譬= o n e s ( n ，1 ) 艺述选取是为了保证材是对称蹴阵， d 是对称的，纠是相对残量的界，选取为： 1 0 例1 我们选取矩阵的阶数n 一2 0 0 ，不使用重启直接使用g s o a r 方法与文献 f 1 6 】的s o a r 方法计算有b 述方式生战的二次特征值问题，所要汁算的特征值 为模最小的特锰道比鞍哒两种方蓓敝敛所需的迭代步骤，g s o a r 方鞋棉 7 l 步收敛，而s o a r 方法程第8 5 步收敛图1 是为g s o a r 方法与s o a r 方法的相对残量范数与迭代次数的关系图此实验说明有g s o a r 方法生成广 义二阶k r y l o v 子空间比s o a r 方法生成的二阶k r y l o v 予空间要好，更适合用 于求二次特征值问题 图1 。g s o a r 方法与s o a r 法相对残量范数的比较 例2 1 9 选取矩阵的方法和要计算的特征值同实验1 ，此实验比较s o a r ：b 怯和g s o a r - r s 重启的g s o a r ) 方法，在g s o a r - r s 中，选取k 一5 ，m = 1 5 。 即子空间的最大维数为1 5 ，保留5 个模最小特征值和所对应的特征向量观察这 鹾狰算法收敛断嚣的迭代次数，计算时闻。发现在该实验中，g s o a r r s 法 的收敛所需的迭代步数是9 2 步，而s o a r 法所需的是8 5 步，重启的算法虽然 在送代步数多了凡步，坦是计算的时闲却步了很多。在计算时阉上，s o a r 法 需要5 9 2 2 0 秒，而g s o a r i t s 法只需要0 4 0 6 0 秒相对残量范数与迭代次 数酶关系如图2 赝泰 例3 。 图2 s o a r 法与g s o a r r s 耜对残量范数豹毖较 选取矩阵的方法和要计算的特征值同实验1 ，比较g s o a r r s 法与s o a r r s 法；这里的s o a r r s 表示对s o a r 方法采甩第纛带的重襄方法。选取 后= 5 ，m = 1 5 ，通过图3 可知，s o a r r s 根本没有收敛，而g s o a r r s 法可收筑s o a r r s 重窟磊的子空闻是： 8 p n 犯 乡l 荔，r l ，一7 2 ，氙一1 7 如荔，如磊，一七+ l 孺一七十1 ) ( 6 1 ) 1 _ w - 这里0 1 ，乏表示重启前s o a r 方法算得的 析，此空间包含了以下空间的全部基的信息 r i t z 就根据2 3 节对s o a r 分 巩n 一七+ l 乏n 一七+ 1 z m k + l 题使用m o g r a n 的重启，那重启后的空间是 s p a n t 1 ，h t l ，h 2 t a ，旷t x ，t 2 ，t m - k + l ( 6 2 ) ( 6 3 ) = 褂嗍2 娜3 ，糯稀 图3 g s o a r r s 法与s o a r r s 法相对残量的比较 例4 在这个例子中，按回转动态系统中的矩阵形式选取矩阵，执行m a t l a b 命令 n = 2 0 0 ；m = r a n d n ( n ) ；m = t r i l ( m ) + t r i l ( m ，- 1 ) 7 ；e = e 可e ( 7 1 ) ；m = m + 5 0 木e ；d = r a n d n ( n ) ；d = t r i l ( o ) 一t r i l ( d ，- 1 ) 7 ；d ( i ，i ) = 0y o r i2 1 ，k = r a n d n ( n ) ；k = t r i l ( k ) + t r i l ( k ，- 1 ) 7 ；k = k + 5 丰e ；k = 一； 即m 是对称正定的，d 是反对称矩阵， k 是对称负定的这个系统的一 个重要的性质是它的特征值分布是关于实轴和虚轴对称的 确磊确兹 一 一仇氙 您 q n 确o -。l n口 p 第六章数值实验 2 1 使用s o a r 方法和g s o a r r s 方法计算其模最大的特征值发现g s o ar - 兄s 法的收敛巨f f 需的迭代步骤是1 2 8 步，而s o a r 法所需的是7 3 步，但s o a r 法需要7 7 9 8 0 秒，而g s o a r r s 法只