（计算数学专业论文）双边rayleigh商及精化的双边jacobidavidson方法.pdf

双边r a y l e i g h 商及精化的双边j a c o b i d a v i d s o n 方法 摘要 本文由两部分组成，第一部分主要研究关于双边r a y l e i g h 商的一些问 题0 s t r o w s k i 定义了一种r a y l e i g h 商作为计算特征值的一些方法的加速工 具本文指出，这种r a y l e i g h 商对特征值的逼近性与相应特征值的条件数 有关，还把这类结果推广到矩阵多项式特征值问题，多参数特征值问题以及 周期特征值问题受双边r a y l e i g h 商迭代的启发，m i c h i e le h o c h s t e n b a c h 和 g e r a r dl g s l e i j p e n 提出了双边j a c 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 方法，提出了精化的双边j a c o b i d a v i d s o n 方法，且通过最终的数值例子可以看出精化方法在运算效率上的优 势 第一章，首先介绍o s t r o w s k i 定义的双边r a y l e i g h 商，针对矩阵多项式 特征值问题，多参数特征值问题以及周期特征值问题分别给出了相应的双 边r a y l e i g h 商的定义，并在此基础上对于上述几种特征值问题探讨了双边 r a y l e i g h 商对特征值的逼近性与相应特征值条件数的掘关性 第二章，利用双边r a y l e i g h 商的定义，同时结合了贾仲孝的精化思想以及 双边j a c 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 方法最后的三 个数值例子体现出精化算法的收敛速度 关键词：双边r a y l e i g h 商，矩阵多项式特征值问题，多参数特征值问题，周期特 征值问题，精化向量，双边j a c o b i d a v i d s o n 方法 t w o - s i d e dr a y l e i g hq u o t i e n ta n dr e f i n e dt w o - - s i d e d 3a c o b i d a v i d s o i l a b s t r a c t t h i st h e s i sc o n s i s t so ft w op a r t s i nt h ef i r s tp a r t ，w ec o n s i d e rt h et w o s i d e d r a y l e i g hq u o t i e n ti n t r o d u c e db yo s t r o w s k ia sc o n v e r g e n c ea c c e l e r a t i o nt o o lf o r e i g e n v a l u es o l v e r s a ni n t e r e s t i n gp r o p e r t yo ft h et w o s i d e dr a y l e i g hq u o t i e n ti s e s t a b l i s h e d ：i t sa p p r o x i m a t i o nt oe i g e n v a l u e sd e p e n d so nt h ee i g e n v m u ec o n d i t i o n n u m b e r ，w ep r o v et h a tt h i sf a c ti sv a l i dn o to n l yf o rm a t r i xb u ta l s of o rm a t r i x p o l y n o m i a l ，m u l t i p a r a m e t e rs y s t e m ，a n dp e r i o d i cm a t r i xp a i r s i nt h es e c o n dp a r t ，w et a l k e da b o u tan e wm e t h o dc a l l e dr e f i n e dt w os i d e d j a c o b i d a v i d s o n i n s p i r e db yt w o s i d e dr a y l e i g hq u o t i e n ti t e r a t i o n m i c h i e le h o c h s t e n b a c ha n dg e r a r dl g s l m j p e np r o p o s e dan e wm e t h o dc a l l e dt w o m d e dj a c o b i d a v i d s o n c o m b i n i n gt h er e f i n e ds t r a t e g yg i v e nb yj i aa n dt w o - s i d e dj a c o b i d a v i d s o nm e n t i o n e da b o v e ，w ei n t r o d u c er e f i n e dt w o - s i d e dj a c o b i - d a v i d s o nm e t h o d t h ea d v a n t a g eo ft h en e wa l g o r i t h mi sd e m o n s t r a t e db y n u m e r i c s lt e s t s k e y w o r d s ：t w o - s i d e dr a y l e i g hq u o t i e n t ，m a t r i xp o l y n o m i a le i g e n v a l u ep r o b l e m ：m u l t i p a r a m e t e re i g e n v a l u ep r o b l e m ，p e r i o d i ce i g e n v a l u ep r o b l e m ：r e f i n e dv e c t o t t w o s i d e dj a c o b i d a v i d s o n 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含未获得或其他教育机构的学位或证 书使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示谢意。 学位论文作者签名：马百日 签字日期：唧年多月日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，有权保留并 向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人 授权学校可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用 影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在解密后 适用本授权书) 学位论文作者签名： 马百日 签字日期：动刁年多月扣日 学位论文作者毕业后去向 工作单位： 通讯地址： 导师签字 涮l 研 签字日期：胛年月厂日 电话 邮编 第一章关于双边r a y l e i g h 商 1 1 r a y l e i g h 商 矩阵的r a y l e i g h 商在矩阵分析及矩阵计算中有广泛应用例如，对于 h e r m i t e 矩阵，c o u r a n t - f i s h e r 极小极大原理把矩阵的特征值表达为r a y l e i g h 商 的变分形式( 极值问题) ，由此可以得到关于h e r m i t e 矩阵特征值扰动分析的 w e y l 定理而r a y l e i g h 商的值域就是矩阵的值域，后者有广泛的应用f 1 0 1 从 矩阵计算观点看，l h y l e i g h 商主要用作计算特征值的算法加速工具【14 1 给定n 阶方阵a ，其r a y l e i g h 商通常定义为f 1 9 1 ： p ( x ) = a x x 日z ( 1 1 ) p ( x ) 有很多性质，可参阅【1 4 】【1 9 】特别，女果岔是a 的对应特征值a l 的特征向 量z l 的近似：圣= g l + d ( e ) ，a 是h e r m i t e 阵，那么【2 ，1 4 , 1 9 1 p ( 岔) 一a 1 = o ( s 2 )( 1 2 ) 这里己假设忙1 f 1 2 = 忙l | 2 = 1 上式( 1 2 ) 是r a y l e i g h 商作为特征值计算法的加 速工具的基础然而，如果a 不是正规阵，那么一般没有( 1 2 ) ，只有 p ( 岔) 一a l = d ( s ) o s t r o w s k i 1 3 j 认为，如果a 为非正规阵，a 是a 的单特征值 a x = a z ，y h a = a y 日，石，y c “，( 1 3 ) 其中z 和y 满足1 2 = l l y l l 2 = 1 ，而2 和雪分别是。和y 的近似 定义r a y l e i g h 商 p ( 童，雪) = 雪日a 圣, f l 片童 那么应如下 ( 1 4 ) 这样定义的r a y l e i g h 商被w i l k i n s o n 2 1 】称为广义r a y l e i g h 商但由于同 时使用了左、右特征向量的近似，因此可称为双边r a y l e i g h 商o s t r o w s k i 的系 双边r a y l e i g h 商及精化的双边j a c o b i - d a v i d s o n 方法 列论文【1 3 】对这类r a y l e i g h 商有详细研究下面分析p ( ，雪) 对a 的逼近性质 由于a 是a 的单特征值，因此，可把z 扩展成可逆阵x = 陋，x 1 ，使得 一一( ：盖) ，臌c 钏 扮k ( 第) 则可取y = 而1 丽可1 此时， 矿x l = 0 ，甲z = 0 ， 把圣和雪分别表示为 则 z = 丽1 ，y g a = a y h ( 1 5 ) 圣= d 1 z + h a ，雪= 口l 可+ m 卢， ( 1 6 ) 一泸a 毫= 眦百r 矿+ 8 h 世a x l o l 铲毫= 叭蚤1 矿+ 8 h q 从而 p ( 圣，雪) = ：i 否五o q 口i 丽l y h xa + 万j 黥， p c 圣，们一a = 夏i ；揣+ 五鬟戮 ( 1 7 ) 假设圣zx , 0 y ，因此可设n l ，卢l 1 ，而 i x i 删2 ，i i k 硎2 较小从而( 1 7 ) 中第 二项为o ( i i 耳1 可0 墨酬2 f | m p 0 2 ) ，第一项仅为o ( 面”i 可i p 日q 1 ) 因此，( 1 7 ) 可写为 p ( 圣，们- a = o ( 南( 忡h 。i ) + i l x l 唰m 班 ( 1 8 ) 根据 1 5 ，2 】a 的绝对条件数为 b 2 南 ( 1 9 ) ( 1 8 ) 式表明，如果a 是良态的，那么p ( 童，雪) 对a 有二阶近似性质另一方面，如 果a 是病态的，那么，即使圣和雪分别是z 和y 的好近似，那么p ( 圣，雪) 也未必 是a 的好近似 2 双边ra e i g h 商及精化的双边j a c o b i d a v i d s o n 方法 根据w i l k i n s o n 2 1 】的结果：如果a 是病态的，那么a 至少还有另外一个 特征值也是病态的又o l = ，童，卢= j 甲雪这说明，ir x l 口 1 2 及0 ，硎2 很小 时，怕恢l i , 口1 1 z 未必很小，但 卢日o = 雪日x l k h 圣= 雪h ( ，一z 暑，f ) 圣= 雪日( ，一i l y l | 1 2 x y 日) 圣 如果圣= o l 。+ u l ，雪= 卢l y + u 2 ，则 可见 定理l 1 p h 口= u 乒u l 一( u 笋。) ( y h u l ) p h q l = o ( 1 l x o i l 。f l y i p i l 2 ) p ( 圣，口) 一a = o ( k i i x l a l l 2j | h , s l l 2 ) ( 1 1 0 ) 1 2 多项式特征值问题 很多领域出现了下述多项式特征值问题( p e p ) ： m p ( a ) z = 0 ，p ( a ) = 0 如， ( 1 1 1 ) j = o 其中a j c “，( j = 0 ，1 ，m ) t i s s e u r 的综合性论文【2 0 】对p e p 的应用背景、理论结果及数值方法有 好的综述在数值方法中，有一些方法( 比如r a y l e i g h 商迭代) 用r a y l e i g h 商 作为加速工具，所用的r a y l e i g h 商是( 1 1 ) 的推广我们注意到，一般而言，对 于矩阵多项式，系数矩阵a o ，a 。很难同时相似对角化，因而，可以考虑把 o s t r o w s k i 定义的双边r a y l e i g h 商推广到矩阵多项式 先看一个较简单情形一广义特征值问题( g e p ) 设a ，b c “”， a ，b 为正则矩阵对， a x = a b z ，y z a = a y h b ，z ，掣0 ( 1 1 2 ) 设a 为 a ，b 的单特征值，从而y h b x 0 ，且 a = y h a ：c y 日b x ，( y h b x ) a x = ( 可日a x ) b x ( 1 1 3 ) 3 双边r a y l e i g h 商及精化的双边j a c o b i d a v i d s o n 方法 如果量= z + 如，多= y + 5 y 分别是z 和y 的近似，则考虑双边r a y l e i g h 商 计算可知 p = 尹a 盒t ) h b 量 p a = ( y g b x ) s y 酽h a 瓦s x 而- ( 巧y h a 万x ) s y h b s x【可“a z 八y “d z j 6 可( a a b ) 6 z 。1 砺f 一。 由于在一阶近似下有雪h b 圣2 暑b x ，从而，如果令 b = 娅l y h b x l ( 1 1 4 ) ( 1 1 5 ) ( 1 1 6 ) 则 i p - ) 、j = d ( b 万杀矿( a - a b ) 嘲 ( 1 1 7 ) 这说明，p 近似a 的程度与咒 有关 下面讨论一般的矩阵多项式特征值问题( 1 i i ) 设 p ( a ) x = 0 ，y h 尸( a ) = 0( 1 1 8 ) 设a 是p ( a ) 的非零单特征值，i l x l l 2 = l ，l l y l l 2 = 1 ，从而【1 3 】 p 7 ( a ) z 0 ( 1 1 9 ) 考虑( 1 1 8 ) 的线性化 1 3 其中 心= a 厌，矿a = a 矿b 4 = ( 一兰。二：。) ； 一三一， ，b = ( i 三：；：三 ( 1 2 0 ) 双边r a y l e i g h 商及精化的双边j a c o b i - d a d s o n 方法 e 乜h 沙 移= 一嘉严( 山+ a a - + + 一1 码。，j = 1 ，2 ，n t 并记 f 壬 i始 = 1 1 ： i 爻”i 一1 圣 ，而- 、i 归 矽= 一砉矿( 山+ 又a - + + p 。1 如一- ) ，歹= 1 ，2 ，m 那么，由( 1 1 5 ) 式有 而= 叩+ d 叩，= + d f p = 铲鳗 自h b 一= 警 由于 自h b = n h b + 厶= 6 q h b 十n h b 6 + 6 矿b 6 因此，在一阶近似下，有 而 俨厌= 而日b f 7 7 h b f 一 m g h a o z + ( f n 一1 ) 可日a l z + + 可胃。4 m l z ) 、 对于尸( a ) z = 0 ，令p = 1 a ，得 1 赤( 矿山+ 矿- 1 a l + + a m ) z = o 5 ( 1 2 2 ) ( 1 2 3 ) ( 1 2 4 ) ( 1 2 5 ) 、 双边r a y l e i g h 商及精化的双边j a c o b i d a v i d s o n 方法 微分得 刍协矿- 1 山+ + - 1 z 丘+ 嘉“p a 。+ + 4 。 z + 去t a 。+ p ”一1 a - + + a m 士= 。 前乘y h 并把l 肛”乘入括号内，则 掣h m a 。+ ( m 一1 ) a a - + + 妒一1 一t z 丢丘 + 可h a a o + a a a l + + a ”a a m z = 0 注意豇= 一击a ，因此 一下1 h m a o + ( 竹l 一1 ) a a l + + a m - 1 a m 一1 ) z 天 + 片 a a o + a a a , + + a ”) z = 0 ( 1 2 6 ) 由t i s s e u r 2 0 】的结果，a 的条件数为 ”巫铲 而由( 1 2 5 ) ( 1 2 6 ) 及瓦 的定义即知 因此 易知 耻巫铲 一= 。( i q 若爷笔薪 必1 1 2 = o ( m a x 1 5 x l ，1 1 缸忆) ) 0 卸1 1 2 = o ( m a x 1 6 a i ，l l a y l l 2 ) 故( 1 2 8 ) 表明，r a y l e i g h 商近似a 的程度与条件数疋 有关 6 ( 1 2 7 ) ( 12 8 ) 双边r a y l e i g h 商及精化的双边j a c o b i - d a v i d s o n 方法 l 3多参数特征值问题 用分离变量法讨论数学物理方程时会导出多参数特征值问题【1 ，1 l 】 考虑非齐次多参数系统 i ( a ) = o ，j = 1 ，2 ，七 j ( a ) = 铷一a l k l 一a k v j k ( 1 2 9 1 i 巧i c j ，j = 1 ，2 ，砖江0 ，1 ，k 。 【咏为己知矩阵，a = ( a 1 ，一，k ) 有关多参数系统的谱理论可参阅a t k i n s o n 1 】及k o g i r 【1 l 】设a = ( a l ，儿) 为( 1 2 9 ) 的特征值，从而存在翰，y i ，使得 l 仉( a ) z i = 0 ，鲈，w ；( a ) = 0 ，0 z 1 1 2 = 1 ，i i 仇j | 2 = 1 ，i = 1 ，2 ，k ( 1 3 0 ) 岛一剖 面 k ，( ) = k 。+ t 日。，1 r 后，0 s 七， k 【a 。w 。( t ) 一w o ( ) 】研= 0 ，7 = 1 ，2 ，七 ( 1 3 2 ) 5 = l 考虑( 1 2 9 ) 和( 1 3 2 ) 关联的广义特征值问题( 见a t k i n s o n 1 d ，用孙继广【1 7 】的 方法，可证下述结论： 引理1 3 1 存在常数e o 0 及在b o 兰 | | t l e o ) 内解析的函数九( ) 和脚( t ) 使得 k 【儿( t ) l 球) 一k 。( t ) l x r ( t ) = 0 ，r = l 州2 一，南， ( 1 3 3 ) 8 = 1 且 a 。( o ) = a 。，2 ：r ( o ) = z ， 7 双边r a y l e i g h 商及精化的双边j a c o b i - d a v i d s o n 方法 根据r i c e 1 5 】的想法，可以定义a 的条件数如下： 定义1 3 1 a 的条件数定义如下 杨。枷 i m + 。风s u p i i ee , o l l 。 丽i i t翰maxlrk h 0 十m ，耳女，2 1 。刈2 i 一i i j 1 2 其中a ( t ) = ( a l ( ) ，a ( t ) ) 定理1 3 1 等聂簪。酊。b 娠篇磊孥l l 靠。， s s ， 其中伽= 。m ；，a ；x 。| | w 一恢 证明对1 3 3 两端关于t 求导，然后令t = 0 得： 兄( o ) k 。品+ a 。露。一日。) 珥一职( a ) 茸( o ) = 0 用前乘上式，则有 硼惦卜 1 1 i ( 0 ) 1 1 。弧厢i i b 0 1 i i 。 ( 1 3 6 ) 记= ( ：) ，考虑方程 铲 k b 。一日。) 珥= 、1 + 盼幡蜥，1 r 七 ( 1 3 7 ) 8 = 、 肌 珊 曲 曲 研 邑 一 一 毋；取 k k 盛 盛 ，i_-il + 、 h k ，一 双边r a y l e i g h 商及精化的双边j a c o b i - d a v i d s o n 方法 用s u n 的一条结果( 见【1 6 】引理1 3 ) 可以知道，( 1 3 7 ) 关于【毋l ，风，耳d j 有解，且最小2 范数解满足 【b l ，睇，踟讹= l 脚f 1 ( 1 r 七) 故 b 锰警b 口 ( 1 3 5 ) 式表明，a 的敏度取决于i i b 0 1 怯下面讨论r a y l e i g h 商，设 毫j = z j + 6 嚣j 。吼= 现+ 6 扔。j = 1 ；2 ，k 把o s t r o w s k i 的想法与h o c h s t e n b a c h 和p l e s t e n j a k 4 定义张量r a y l e i g h 商 的想法相结合，有下述定义： 定义1 3 2 系统( 1 2 9 ) 关于圣：圣i o 孟2 0 固氟及雪= 9 l 圆乳固圆鲰 的双边r a y l e i g h 商p = ( p l ，p k ) 由下式规定： (篡臻v k 扁k k k ) ( ： p k 馁l 易知，只要i 悼z j 忆l 陋协| j 20 = l ，2 ，) 都适当小，( 1 3 8 ) 有唯一解 注意 由于( 1 3 8 ) 等价于 风时眨) 鲈( p ) 南= 00 = 1 ，2 ，南) ( 1 3 9 ) 即 ( 鲈十6 谬) ( p ) ( 巧+ 嘞) = 00 = 1 ，2 ，七) ( 1 4 0 ) 而( 1 3 9 ) 可改写为 矽1 1 j ( a ) q = 0 9 双边r a y l e i g h 商及精化的双边j a c o b i - d a v i d s o n 方法 把聊= 岛一6 协，巧= 白一6 巧代入，则 秽( ) 、) 白= j ( a ) 屿0 = 1 ，2 ，七) ( 1 ，4 i ) 把( 1 3 8 ) 与( 1 4 1 ) 相减，得 ) - 却，- h ( a ) j 。l 、 ； i ( 1 也) 6 掣w 名( a ) 6 z 瓦馁| ：；：竺) 怕一a 1 1 z 驯酊1 1 1 2 1 1 l ； 卜掣f ，眦( a ) 妇1 j 稚眦( a ) 玩 ( 1 4 3 ) 1 4 周期特征值问题 设如，马c “4 ， ( 山，易) ) 名l 为正则的周期矩阵对，对应的特征值问题 为【1 2 1 ： 8 j a i z - l = i e i z j ，8 j _ l o ；a j = 旺j u h - i e j 。，u a 这里要求( ，7 r p ) 兰( 兀譬。哟，兀箕1 岛) ( 0 ，o ) ，巧，协0 ，0 = 1 ，2 ，南) 并 约定y o = y k ，e o = 晚此时，称( ，即) 为 ( 如，易) ) 1 的一个特征值， 协 名l 和 巧 坠l 为对应的左特征向量及右特征向量 对于周期矩阵对有一个重要的分解，称为p - s c h u r 分解它的一个变型如 下： 引理1 4 。1 ( p - s c h u rd e c o m p o s i t i o n ，s e e 1 2 1 ) 设 ( a j ，马) 铬i 是正则 的，( 丌0 ，即) 为其特征值，则存在酉阵q j ，历使得 钟山乃一- = ( 0 爱) ，够弓乃= ( 0 菱) ，屯z ， c 街， 1 0 1 七 a a 一； 一 以 船 ，j-illi、 双边r a y l e i g h 商及精化的双边j a c o b i - d a v i d s o n 方法 毛毫二乏弓毛善囊弓乏i 季1 ) ：= ( ( 。a jz01 i 。2；，c-ae，( 。叫) ( 鲁乏) ( ：哆) = ( 毪) ，u “叫 码1 l 哆) ，巧1 吩；) ， t ， 垆鸟= ( q 0 锄0 ) ，垆易码= ( 台嘞0 ) 4 s ， 耻( 乏) ，则 证明 ：由膨( 乏) = 疵- = ”t - + a t 得 ( 如1 ) = m - l m l + m - 1 5 1 = ( ：) t 双边r a y l e i g h 商及精化的双边j a c o b i d a v i d s o n 方法 从而1 1 2 1 1 2 i i m - 1 i 以怯 口 下面考虑双边r a y l e i g h 商，令 圣3 = z j + x j 3 ，舀j = 强 + y i n 6 j 都非零，则 ( 山，易) ) 知l 关于 白 和 缈) 的双边r a y l e i g h 商定义为 其中 由( 1 4 9 ) 式易得 ( ， j 三谤a j 量 - l ，岛三谚e i 壹j j = 1 ，2 ，七 a j = q j + 弘j ，哆j = 6 ；y 毒a j x i - 1 p 叱以 8 j = 8 i + i 。岛= 铲y 器e j x j q j = 1 ，2 ，七 从而，如果m a x i 脚f 及m a x i 勺i 都足够小，则有 其中 ( 1 5 2 ) ( 1 ，5 3 ) ( 1 5 4 ) ( 1 5 5 ) 丌a 2 j 马= l 岛2 + j e i 。j 蚴+ 叫- m j a x t b n ( 1 5 6 ) j = i 4 ，1 c 、 、， 即2 里岛2 即+ j = l 即j 勺+ o ( 焉冬i 勺1 2 ) j 2 i ” 丌a j = 啦 - 由 嚣b 、j = i i8 t l j 从而，经过计算可知( 有关p ( ( q ，卢) ，( j ，) ) 的定义见【1 2 】) ( 1 5 7 ) 心邯训刮瞎j = 1 ) | | 2 + 肋只 黝 。问 吁 。州 = 和 双边ra e i g h 商及精化的双边j a c o b i d a v i d s o n 方法 又由 瑞乌玛- 1 ，o = 鸟2 瑞易恐，o = 易。 从而 a 1 2 麟。， a 2 2 髅刨圳。， a = m a x a l ，2 则综上所述得到下述结果： 定理1 4 1 如果a 足够小。则 ( i 1 2 ，i 即1 2 ) p ( ( ，和) ，( ，即) ) f i 马酬z 怕i i z l 3 1 不等式( 1 6 1 ) 说明，( 7 r a ，和) 逼近( 丌o ，即) 关于至少是二阶的 下面分析0 曲恢i i 幻i i z 何时会很小 首先，由玛 i i ( 1 | 5 9 ) 可知巧= 历e - ，巧= 协，巧，0 】= 2 = 1 ，。= 厮，j = 1 ，2 ，k 记 巧= 志南嘞码= 赤彩一赤珊， 6 。3 = i j 一j ，6 蝣= 砒一现， 1 3 ( 1 6 2 ) 吩0弓 k q ， 幻2“1 忖产 妨勺 如 已果如 唧叫 q q 幻 d ，； + 即2 纠 ” 畅 = 吾 西 幢 i m ， 仉 k a 忙 。m加。m 垆，说 二：o 这 ，一、 乃 脚 | 一 目，一 酝 仍 垆 | i 得 够 醴 0 n 双边r a y l e i g h 商及精化的双边j a c o b i d a s o n 方法 那么 1 一l l 吻1 1 2 1 1 奶1 1 2 1 + | | 锄1 1 2 ， 协0 2 一i i 勘1 1 2 | 1 国1 1 2 1 1 鲫1 1 2 + | | 如1 1 2 记 灯= i f 锄| | 2 ，鲥= | | 1 1 2 l l y j l l 2 则 1 岛1 1 2 | | 蜥| 1 2 i i # a i , 1 1 - - a 。i 1 1 - a u i 从而 l i t , f 1 2 2 巧， 0 q l i s 2 鲥 由( 1 5 1 ) 式及引理1 4 3 得 1 1 吩1 1 2 0 蕾。1 1 1 2 1 1 4 1 1 2 ，1 1 如1 1 2 l i 下1 1 1 2 1 1 勘1 1 2 又由1 4 7 可得 ( 1 6 5 ) ( 1 6 6 ) ( 1 ，6 7 ) ( 1 6 8 ) ( 1 6 9 ) ( 1 7 0 ) ( 1 7 1 ) 瘫嚣裴霭筹臻 旺7 z ， 川硼0 耳1 f | ：以识硼， ”7 j = 1 ，2 ，七 注意i l u l l 。= f 可再，因此 1 1 吩1 1 2 、2 、l + l i q 幢i i 曲i l 。，1 1 妨1 1 2 v 5 1 1 约1 1 2 1 1 1 1 2 现在考虑l i n 和s u n 1 2 】导出的条件数： 删。南善( 咖m 。 + o 即| | 丌町巧一l 1 1 珊1 1 2 ， ( 1 3 ) 其中乃和乃为正参数，这里取为巧= i i 马1 1 2 ，乃= l i a , ：1 1 2 由( 1 6 0 ) 式得 p ( ( ，和) ，( ，丌口) ) 2 p e ( ，邓) 3 + o ( a 3 ) ， ( 1 ，7 4 ) 其中p2 攫饕、r 干1 r 习匹，。2m a x 删如- i i z ，i l 以i i 。，o - t l 。，i i “t i i z ) ( 1 7 4 ) 意味着( ，) 对( n ，和) 的逼近性很可能与( 丌口，即) 的条件数有关， 1 4 双边r a y i 正i g h 商及精化的双边，i a c o b i - d a v i d s o n 方法 1 5 数值例子 本节给出一些数值例子，用于说明前四节中得到的理论结果 1 ，计算 nn 一1 嚣一ln 一1 + a = l0 n 一2 !o 0o 特征值的条件数在计算过程中，利用q r 方法计算a 的近似特征值，利用逆 迭代求上述近似特征值相应的左、右精化向量由计算可知，它有部分特征值 会病态，一部分特征值是良态的对于病态的特征值，考虑其双边r a y l e i g h 商 对于此类特征值的逼近性。由结果可知此时双边r a y l e i g h 商并不是病态特征值 的好近似 。* 焉粼忠：篙。岱 图1 a ：双边r a 舛e i g h 商与病态特征值的误差( n = 1 0 0 ) 1 5 双边ra e i g h 商及精化的双边j a c o b i d a d s o n 方法 t 。0 ；铡盎篇。一 图1 2 ：双边r a y l e i g h 商与病态特征值的误差n = 5 0 0 ) 其中在x 轴标示出了不同阶数下( 指矩阵a 的阶数) 病态特征值的数目，y 轴表 示病态特征值与其相应双边r a y l e i g h 商的误差 2 a = x d x ，其中d = d i a g ( a l ，a 。) 任选，取一正交阵q ，并将此正 交阵的某两列( 如q l ，q 2 ) 作如下处理：令钇= q i + e ，其中e 为随机扰动，在此程 序中利用随机产生的列向量，其元素为均匀分布的随机数此时得到的q 作为 x 最后作z 。的随机扰动i 在此程序中利用随机矩阵，其元素为均匀分布的随 机数) ，并将其规范化记为，计算p ( 童) 一a 2 可知p ( 畲) 并不是a 2 的好近似在 计算中，壬2 = z 2 + o ( 1 0 一4 ) ，而p ( 童) 一a 2 o ( 1 0 ) 且随着n 的增大，这种差异会 更明显如图1 3 所示 1 6 双边r a y l e i g h 商及精化的双边j a c o b i - d a d s o n 方法 净 ： 一 v 电 譬 j + 一 e ，1 。 罐 图1 3 ：双边r a y l e i g h 商与其病态特征值的误差( n = 1 0 0 ) 其中，横坐标为矩阵的阶数n ，纵坐标为l p ( 童) 一a 2 i ，由此可以看出对于病态的特 征值，双边l h y l e i g h 商并不是好近似，且由计算发现当a 的阶数变大，i p ( 仝) 一a 2 i 有增大的趋势。 3 对于矩阵多项式，本例只讨论( a 2 a 2 + a a l + a o ) z = 0 其中a j = q d ，q 一，任选d ，= 反叼( d p ，r 一，幽) ，j = 0 ，l ，2 n 为矩阵a 的阶数这样选 择系数阵的主要考虑是易获得精确特征值，从而可与计算结果对比取一正交 阵铂并将铂的某两列如( q 1 ，q 2 ) 作如下处理：q 2 = g l + e ( 处理方法同例2 ) ，从 而得到q 在计算过程中，特征值由a 2 + d ：u a + d ：u = 0 ( 岛= 1 ，2 ，n ) 的根确定由上述构造可知，q 的列是右特征向量茹，q 。的行是左特征向量y 丑 作z 及可日的小扰动后( 在计算中取均匀分布的随机数作元素组成的列向量作 为扰动项) 分别记为圣、雪在计算过程中取扰动阶数约为o ( t 0 _ 3 ) ，而由计算结 果发现双边r a y l e i g h 商对a 的逼近性效果较好，如图1 4 所示 1 7 双边r a y l e i g h 商及精化的双边j a c o b i d a v i d s o n 方法 图1 4 ：p e p 问题中的i p ( i 功，i ) ) 一a 其中n 为矩阵a 的阶数，纵坐标e r r o r 为i p ( 岔，雪) 一a 第二章精化的双边j a c o b i d a v i d s o n 方法 2 1 双边r a y l e i g h 商及精化投影法 在前一章的第一节我们提到过o s t r o w s k i 定义的双边r a y l e i g h 商，即设a 为n 阶矩阵，a 为a 的单特征值，z 和y 为a 的右、左特征向量 a x = a z ，剪a = a 兰，h ，。z ，y 口( 2 1 ) 其中z 和满足忙l | 2 = i l y i l 2 = 1 ，而圣和口分别是z ，y 的近似右、左特征向量， 故双边r a y l e i g h 商定义如下： 脚) = 喾 ( 2 2 ) 对于非对称矩阵a ，若用传统的正交投影法求解其部分特征对时，可能收 敛非常慢甚至发散为克服此问题，贾仲孝提出了对于确定的近似特征值，用其 精化向量( 在投影子空间上满足最优条件的向量) 来代替传统方法中的r i t z 向 量 7 ，其思想是：对于近似特征值天，从任意求解子空间q 中寻求单位向量矗满 足下面的最优性条件： 1 1 ( a a j ) 磊l l = 。n r a ，l i 。n | i ：1l l ( a a j ) 珏l 用面作为与近似特征值天相对应的近似特征向量，称矗为a 在子空间q 上与 天相对应的精化向量对于指定的求解子空间n ，精化向量可以通过计算一个 小规模矩阵特征值问题或小规模矩阵奇异值分解得到【9 】， 2 2 精化的双边j a c o b i d a v i d s o n 方法 m i c h i e le h o c h s t e n b a c h 和g e r a r dl g ，s l e i j p e n 受双边r a y l e i g h 商迭代方 法的启发，提出了双边j a c o b i - d a v i d s o n 方法【5 】本文结合贾仲孝的精化思想与 双边j a c 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 9 双边r a l 凡e i g h 商及精化的双边j a c o b i - d a v i d s o n 方法 给定k 维子空间“和y ，u 与v 均为nxk 维矩阵，其列向量分别组成“ 和v 的一组标准正交基称矗和舌分别为a 在子空间“和1 2 上与天对应的右、 左精化向量，即：矗和矛分别满足： i i ( a a ，) 面i f = 。“m ，忙i n ：1i i ( j 4 一a ，) u l l ( 2 3 ) 伊( a x o i i 。删m i 悄n 4 一天r ) l l ( 2 4 ) v v ，u i l = l 且蚕h 云0 矗，i 关于a 的双边r a y l e i g h 商定义如下： p = p ( 五，雷) ：= _ i i h 耳a 了f i ， ( 2 5 ) 定理2 1 = 氲一廊( 2 6 ) 如= a 日移一面( 2 7 ) 则有：i 日r t = 0 ，矗7 勺= 0 为寻找恰当的向量来扩张子空闻“与1 ，令z = 磊+ f ，y = 雷+ ，则 a ( 云+ f ) = a ( 豇+ 7 7 ) ， + 7 7 ) h a = a ( d + 7 7 ) h ( 2 8 ) 重新整理( 2 8 ) ，得： ( a a ，) f = 一( a 面一a 豇) = - - t f i , + ( a p ) 面 ( 2 9 ) 同理： 一 ( a 日一天，) 耳= 一如+ ( 天一刃吾 考虑映射r = ，一端由于上5 ，故得 ( z - 蔫) ( a - p i ) f = 一心 ( 2 1 0 ) 同理，考虑r = ，一蒜由于r f i 上面，故得 ( ，一篙) ( 4 h - - 阳叩= 吨 ( 2 1 1 ) 双边r a y l e i g h 商及精化的双边j a c o b i d a v i d s o n 方法 下面分两种情形确立修正方程： ( 1 ) 矩阵对( u v ) 双正交 在此种情形下，u 和y 的列向量互相正交，即y 日u 为对角阵，因此在这种 情况下我们寻找的修正向量为f 上0 ，叩上矗 故由上述性质得到的修正方程为： ( r - 麓) ( a - p i ) ( ，一篇肛叱 ( i - 凳) ( a n _ 加( ，一甏) 叩一一如 算法2 1 ( v 双正交) ( 2 1 2 ) ( 2 1 3 ) 1 任意选择初始向量u ，n 计算：u 1 = l j l = f ( u h f ) ，l = a u l ，p = 。f f l h w l ，冠= u l ，雷= t j l ，r f i = a 5 一p f i ，r f i = a h o 一卢i ，h = u l 】，u = 【 u 1 】 2 k = 0 ，1 ，2 ( a ) 求解f 上面，叩上面，使得 ( ，一篇) ( a - p i ) ( ，一甏肛一玩 ( r - 篙) ( 叫m 一篙) q = 1 ( 2 1 4 ) ( 2 1 5 ) ( b ) 利用b i m g s 方法将f 与圪正交，叼与巩正交，得到u + l ，y k + l ， 并分别将魄，k 扩充为仉+ l 和k + l ( c ) 计算w k = a ，以及h k = 昭巩 ( d ) 计算风的最大特征值a ，并计算其相应的右、左精化向量面，o ( e ) 计算p = 雷日a 蟊，= a ( z - p 矗，= a 日矛一面，测试收敛：m i n 圳i n l l e ，若满足则停止 ( 2 ) u 和v 均为列正交阵在此种情形下，我们寻找修正向量f ，q ，使得 上a ，即上雷，则修正方程为： ( ，_ 甏) ( a 叫) ( ，娟= 飞 ( 2 1 6 ) ( 卜蒜) ( a h _ 觯娟= 一粕 ( 2 1 7 ) 算法2 2 ( 以v 均为正交阵) ： 2