（计算数学专业论文）关于精化近似特征向量的一些性质研究.pdf

摘要 本文丰要研究精化近似特征向量的性质，其中包括求解对称特征问题时精 化向量之间的正交性以及如何用精化a r n o l d i 方法求解矩阵重特征值的问题。 全文共分为二二章。 第一章介绍大觇模矩阵问题的米源、解决这类问题的摹本方法及其本学科 发展动态，并概述本文主要工作。 第二章研究精化r i t z 向量的j 下交性。在有限精度下，如何用精化a r n o l d i 方法求对称矩阵的一组正交程度可达到机器精度的近似特征向量组。本章首先 给出精化r i t z 向量的一个新的表达式，该表达式表明理论上对不同的近似特征 值，一般地无法保汪精化a r n o l d i 方法所确定的精化r i t z 向量组是止交的。进 一步，采再正交化方法便可得到一组正交化程度可达到机器精度的标准正交近 似特征向量组。最后的数值结果验证结论的准确性，同时再诈交化后得到新的 近似对的残量是不变的。 第三章主要研究如何用精化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 方法；精化r i t z 向量 ab s t r a c t t h i st h e s i sm a i n l yp r e s e n t st h ep r o p e r t yo ft h er e f i n e de i g e n v e c t o r s ，i n c l u d i n g t h eo r t h o g o n a l i t yo ft h er e f i n e dv e c t o r sw h e ns o l v i n gt h es y m m e t r i ce i g e n v a l u e p r o b l e m sa n dh o wt os o l v i n gm a t r i xd o u b l ee i g e n v a l u ep r o b l e m sb yt h er e f i n e d a n o l d im e t h o d i tc o n s i s t so ft h r e ep a r t s c h a p t e ro n eg i v e st h eb a c k g r o u n do fl a r g em a t r i c e se i g e n p r o b l e m sa n db a - s i cn u m e r i c a la l g o r i t h m sf o rs o l v i n gt h e m w er e v i e wt h es t a t eo ft h ea r to ft h i s s u b j e c t f i n a l l y ，w ed e s c r i b et h ew o r ko ft h i st h e s i s c h a p t e rt w oi n v e s t i g a t e st h eo r t h o g o n a l i t yo ft h er e f i n e dr i t zv e c t o r s h o w t og e tag r o u po fa p p r o x i m a t ee i g e n v e c t o r sw h i c hc o u l dg e tt ot h em a c h i n et o l e r - a n t ef o rs y m m e t r i cm a t r i c e sb yt h er e f i n e da r n o l d im e t h o d f i r s t ，w eg i v ean e w e x p r e s s i o nf o rt h er e f i n e dr i t zv e c t o r s ，i ti m p l i e st h a t ，g e n e r a l l y ，f o rt h ed i f f e r e m a p p r o x i m a t ee i g e m r e c t o r s ，w ec a nn o tp r o m i s et h er e f i n e da r n o l d im e t h o da n d t h er e f i n e dr i t zv e ( ：t o r sa r eo r t h o g o n a l f u r t h e r m o r e ，a p p l yt h eo r t h o g o n a lm e t h o d a g a i n ，w ec o u l dg e tag r o u po fs t a n d a r do r t h o g o n a le i g e n v a l u e sw h i c hc o u l dg e t t ot h em a c h i n et o l e r a n c e f i n a l l y , t h en u m e r i c a lr e s u l t sp r o v et h ea c c u r a c yo ft h e m e t h o d ，m e a n w h i l e ，t h en e wa p p r o x i m a t er e s i d u a l sr e m a i nt h es a m ea f t e rt h er e o r t h o g o n a l n 1 i nc h a p t e rt h r e e ，w ei n v e s t i g a t eh o wt og e tt h ea p p r o x i m a t ee i g e n v a h ma n d t oe s t i l n a t et h em u l t i p l y f i r s t ，w ei n v e s t i g a t et h ep r o p e r t yo ft h ea p p r o x i m a t e e i g e n v a l u e i ts h o w st h a tw ec a n tg e tt h em u l t i p l yo ft h eg i v e ne i g e n v a l u ed i r e c t l y w h a t sm o r e ，i nt h i sc h a n p t e r w es o l v et h i sm u l t i p l yb yar e f i n e da r n o l d i m e t h o ( t t h en u m e r i c a lr e s u l t sp r o v et h ea c c u r a c yo ft h i sm e t h o d k e y w o r d s ：t h ee i g e n v a l u ep r o b l e m s ；r e f i n e da r n o l d im e t h o d ：r c f i n e dr i t z v e c t o r s 厦门大学学位论文原创性声明 本人呈交的学位论文是本人在导师指导下取得的研究成果。本人 在论文写作中参考其他个人或集体已经发表的研究成果，均在文中以 适当方式明确标明，并符合法律规范和厦门大学研究生学术活动规 范( 试行) 。 另外，该学位论文为() 课题( 组) 研究成果，获得() 课题( 组) 经费或实验室的资 助，在() 实验室完成。( 请在以上括号内填写 课题或课题组负责人或实验室名称，未有此项声明内容的，可以不作 特别声明。) 声明人( 签名) ：当防砖 肼乎月9 1 日 厦门大学学位论文著作权使用声明 本人同意厦门大学根据中华人民共和国学位条例暂行实施办 法等规定保留和使用此学位论文，并向主管部门或其指定机构送交 论文( 包括纸质版和电子版) ，允许论文进入厦门大学图书馆及其数 据库被查阅、借阅。本人同意厦门大学将学位论文加入全国博士、硕 士学位论文共建单位数据库进行检索，将学位论文的标题和摘要汇编 出版，采用影印、缩印或者其他方式合理复制。 本学位论文属于： () 1 、经厦门大学保密委审查核定的保密论文，于年 月日解密，解密后适用上述授权。 () 2 、不保密，适用上述授权。 ( 请在以上相应括号内打“ 或填上相应内容。保密学位论文 应是已经校保密委审定过的，方可打“ ，未经审批均为公开论文 此声明栏不填写的，默认为公开论文，均适用上述授权。) 作者签名： 导师签名： 日期：年月日 日期：年 月 日 第一章引言 1 1问题的由来 在大量的应用科学和t 程计算中，如计算流体力学、量子力学、化学t 程、 结构工程和网络排队的m a r k o v 链模拟等领域，许多问题最后都可以归结为大 规模矩阵特征问题 a q a i = 九仇( 1 1 ) 的求解，其中a 为阶实( 或复) 矩阵，( 九，妒t ) i = l ，2 ，为a 的特征对( f l 协f i = 1 1 对于在实际问题离散化后得到的一。些阶数为几千有时为几万甚至是几l 万 的矩阵 1 】，需要的往往是矩阵的依实部最大或最小、依虚部最大或最小、依模最 大或最小的若干个特征值或某区域i f j 的特征值及其对应的特征向量。 b a i 等人提供的矩阵测试集f 2 】综合了一些文献所提供的在实际问题中出现 的矩阵特征问题，详细介绍了一些在应异j 领域中求解特征问题的意义。 正是南于矩阵问题在许多学科中的“泛应用，凶此矩阵特征问题数值求解 的理论研究、算法的开发和软件的研制等是当今计算数学和科学与工程计算领 域中的重人课题，在国际上对它的研究工作也极为活跃【3 j 。 1 2 变换和投影方法 求解中、小规模对称与非对称矩阵问题的特钿r 问题，最有效的方法是1 9 6 1 年 南f r a n c i s 提出q r 方法 4 】。目前，不仅在该方法的可靠性分析、数值稳定性研究 等方而取得了大量的成果，而且该方法也成功编制了软件，m a t l a b 软件包中 的计算矩阵全部特征对的函数子程序e 皤m 即以该方法的原理编制而成的。还 有一些如j a c o b i 方法和分而治之法等都是有效解决此类问题的数值方法。因此 从某种意义上蜕中、小规模矩阵特征值问题的求解基本上得到了完美的解决。 目前，求解大规模矩阵特征值问题的方法丰要分为两类：变换法和投影法。 变换法是直接对原矩阵进行处理，通过一系列变换，使之变成一系列脊易求解 特征值的形式，如。l a c c o b i 方法，q r 方法等 5 ，6 】。在变换方法中南于需要存储矩 2关于精化近似特征向量的一些性质研究 阵元素，使得存储量比较大，并且一般的变换方法会破坏矩阵的稀疏性，计算量 相当人。 另一种常用的求解方法是投影法，其思想足通过投影算子把阶数较高的矩 阵投影剑低阶空间小去，将原大规模问题约化为t f i 、小规模矩阵特征值问题，刖 标准方法求所产生的中、小规模矩阵特征对，用其作为大规模矩阵a 的部分特征 对的近似。投影类方法可采刷压缩存储技术，其特点是在计算过程t f l ，不需要 对a 做任何的改变。投影方法大致可以分为三类： 第一种是止交投影法：m 维了空间k 卜的止交投影方法即为用满足 i。，? j 协n ， n9 、 la 乒t 一入t p tj _ k 的( 天i ，西) ( i 协 i ) = 1 作为a 的特征对( 九，慨) 的近似。元，蟊分别称作a 在子空 间k 上的r i t z 值$ , r i t z l s j 量。如果 u j ，是子空间k 的一组标准正交基，定 义= ( l ，v 2 ，v m ) ，则上述关系式可以写成 f ，一 ： 爿m 玑2 八犰( 1 3 ) 【驴产玑 一 此处= 坛a 是a 在予空间k 卜在标准止交基 v ，】m - 卜的限制矩阵。显然 若( a ，y t ) 为的一个特征对，则( a i ，甄) = ( h i ，玑) 是a 的r i t z 对。 选取不l 一的求解子空间k 将会导出不同的l f 交投影方法，其中最著名的 由”广义l a n c z o s 方法”、”广义块l a n c z o s 方法”、”子空间迭代法”、”d a v i d s o n ”方法、”j a z o b i d a v i d s o n 方法”等。属于前两类方法的主要代表是”a r n o l d i 方法” 4 ，7 ，8 ，9 ，1 0 和”块a r n o l d i 方法”【8 ，1 1 ；当a 为对称矩阵时，两者即为：蒈名 的”l a n c z o s 方法”f 9 ，1 2 ，”块l a n c z o s 方法”【9 ，1 2 a r n o l d i 方法属于k r y l o v 子 空间法在其过程中需要计算一个m 阶的上h e s s e n b e r g 阵的特征值及其特征向 量，计算量为o ( m 3 ) ，由于内存、计算速度的影响，k r y l o v 子审间维数不应该 太大。因此，使用a r n o l d i 方法一般要采用荦新启动技术，而且重新启动的妤坏 足投影类方法求解能否成功的关键因素之一，理论分析表明【1 3 ，1 4 ，1 5 ，当在一 个子空间中用投影类方法求解矩阵的特征值问题时，若该子空间中含有所求特 征向最的信息越丰富，则收敛速度越快，这也是选择重新启动的原则之一。文 献 8 ，1 0 ，1 6 】中提供了a r n o l d i 方法的多种重新启动策略，其中s o r e n s e n ( 1 6 】提出 带”准确位移”隐式”重新启动a r n o l d i 方法的( i r a ) 被认为是最成功的重新启 第一章引苦 3 动策略之一。i r a 能否成功的关键因素是位移选取的准确性，位移选取越逼近 准确特征值，则该方法收敛速度越快。 第二种足斜投影类算法：给定两个m 一维子审问和k ，斜投影方法用满足 ， 一 2 忱酬， ( 1 4 ) la 西一, k i w i 上l 的( 天i ，氟) ( | | 西i i ) = 1 作为a 的特征对( a t ，忱) 的近似值。子空间k 称为冉子空 间，l 为左子审问。假定和均为n m 矩阵，5 f f j 的列向量分别足予卒 问k 幂 j l 的一组基，则上述关系+ 日j - 以写成 2 勋产九w , ：v m y “( 1 5 ) 【识= v , n y i 一 此处= 瞩a ，k 和l 的不同选取会导出不同的斜投影方法。目前研究较多 的有两种，一种为调和投影，另一种为双正交的l a n c z o s 方法。 第三种是精化投影方法：对丁非对称矩阵a ，当用正交投影方法求解它的部 分特征对时，可能收敛的非常慢甚至发敞，极不规则。为了克服这利- 方法的内 在隐患，贾提出了对于确定的近似特征值，摒弃现有的用经典投影类方法求得 的近似特征向量，而用另。在求解子空问上满足最优条件的新的向量一称之为精 化向量一作为近似特征向量【1 4 】。 对任意求解子空间k ，以及每一个近似特征值九( 可以是r i t z 值、调和r i t z 值 或其它近似特征值) ，精化投影类方法【1 5 ，1 7 为h j 满足 ( a 一元i ) f i ij j = q 嚣：，l i ( a 一元力u l | ( 6 ) 的也( i 慨i | = 1 ) 作为，与近似特征值天t 相对应的近似特征向量。称砒为a 在j 子空 问k 卜与又相对应的精化向量。对指定的求解了空间k ，精化向量砒可以通过计 算一个小规模矩阵的特征问题或小规模矩阵的奇异分解( s v d ) 来计算。 1 3 r i t z 向量和精化向量的收敛性质 定义 e = s i n 么( 妒，k m ) = i i ( j r 一砍。) 妒| i 为特征向量妒与近似子空间的夹角，其中b 岛是子空间k 。的正交投影算子。 则r i t z 值满足 4 一一 羞王塑丝堑垡堑堑塑量 堕二些堂型 _ _ - - - - _ - _ - - _ _ - _ _ - _ - _ - - _ _ _ - _ _ _ _ _ _ - _ _ - _ - _ - _ _ _ _ - - _ _ _ _ 一一一 定理1 3 1 几硝存在投影矩阵的一个特征值又及a 的特征值入满足 天一入l ( 2 1 1 a l l + i i k i i ) 1 一鬲11 l k l l 斋1 ( 1 7 ) 其中k 为仃 阶矩阵，满足| | r | i 沉鼍i l a i i 如果 令( 天，y ) 为的特征对，且b ，h 】为酉阵，满足 l 鼬川= 言b g 假设a ，一b t b 奇异，定义 s e p ( a ，b ) = l ( a j b ) _ 1 | 1 1 则下面的定理成立 s e p ( a ，b ) s e p ( a ，b ) 一 a ac 0 定理1 3 2 肛彤假设( 天，驴) ，为a 的特征对( a ，妒) 的近似，且s e p ( 天，口) 0 ，则 s i n 讹，痧) ( 1 + 万零i i a 葡l l 丽) e ( 1 8 ) ( 1 + 万氨蒜等可丽) 定理( 1 3 1 ) 表明只要：近似子空问渐近的包含准确特征向量信息，就会 有一个r i t z 值收敛到a 的特征值。然而r i t z 向量的收敛还需要一致分离条 件s e p ( 天，b ) o 或者天与其他r i t z 值的分离程度较好。 下面的定理刻画了精化近似特征向量的收敛性。假设( 入，妒) 是a 的特征 对，【妒，圣上】构成酉矩阵，且 基 a t 妒，圣上，= 言艺 第一帝引苦 5 定理1 3 3 以叫假设天是已经计算得到的近似特征值，磊是由 m 一砌l 5 裴1 1 ( a 一天啦! l ( 1 9 ) 计算得到的精化近似特征向量，如果 s e p ( a ，l ) s e p ( a ，l ) 一f 人一入i 0 ， 那么 s i n 么( 妒，面) 入m 显然理论上求得雕1 r i t z 量是一个正交的向量组。下面研究精化r i t z 向量的性 质。 引理2 3 1 设= q a q 丁是对称矩阵的特征分解，其中a = 哦n g ( 天1 ，天2 ，天。) ，q 为m 阶正交矩阵，则盯未i 。( 一a t ，m ) 为对称正定矩阵 鼠= q ( ( a 一元k ) 2 + h 。+ l , m y y t ) q 丁 ( 2 7 ) 的最小特征值，磊为与其对应的特征向量，其中可= q r e m 。 证明利用关系式( 2 5 ) 和( 2 6 ) 知仃n ( 一元l ) 是对称正定矩阵( 玩一 l i r a ) 丁( 矾一元厶) 的最小特征值，乞为与其对应的特征向量。另一方面 ( 一天t 厶) 丁( j k 一兄厶) = ( ( 砜一天；k ) t ( 砜一又k ) 十九乙扎m e 。e 夏) = q ( ( 人一元k ) 2 + h m + 1 , m y y t ) q 丁 = b i ， 其中箩= q 丁e m ，综合知引理1 结论成立口 引理2 3 2 如果= q 丁e m = ( y 1 ，y 小y m ) t , 则耽0 ，i = l ，2 ，m 1 0 关于精化近似特征i ：d 量的一螳性质研究 证明如果秒的第i o 个分量玑。= 0 ，即e t 幻q t e 。= 0 ，利用矩阵的特征分解 有 。e m = q a q r e m = q a y 利用矩阵的对称二对角结构有 q t ( m l ，。e m 一1 十h m , m e m ) = a y ( a h m , m i ) y = h , - 1 , m q t e m - 1 两端右乘e i 。有， e 。t 。q t e m 一1 = o 依此类推，我们可以得到 e 磊q 丁e j = o ，j = 1 ，2 ，m 一2 凶此 e i t 。矿= 0 ， 这与q 为止交矩阵矛盾，因此y i 0 ，i = 1 ，2 ，m 口 利用引理1 和引理2 及【2 l j 】l e m m a8 5 2 】有 引理2 3 3 矩阵( a 一元厶) 2 一2 ；。( 矾一晃厶) 是可逆的， 进一步由引理1 和 【2 0 】，t h e o r e m8 1 s l 有 引理2 3 4 2i 。( f m 一天i l ) ( 0 m 朋i n ( a j 一潲 ( 2 8 ) 下而研究精化r i t z 胤性质。 定理2 3 1 若z 。= ( ( 人一天t k ) 2 一2 i n ( 詹麓一天i 厶) ) 一1 y ，则 f 向量为矩阵( a 一五i ，) 2 + 危象+ 1 ，m y y r 与特征值仃未i 。( 如一元t ) 对应的特 征向量。 第_ 章精化r i t z ；，1 量的币交性 2 t 批r i t z 向量满足讥= 诲疳 3 向量娩满足l + 愚象+ 1 m ( 可t 孔) = 0 证明 1 利用【 2 0 】，t h e o r e m8 5 3 】可得。 2 利用引理2 3 1 矢兀忍= 褊，再注意到( 2 5 ) 便可得到结论。 3 引理2 3 1 意味着 q ( ( 人一k , t m ) 2 + h m + l , m y y 丁) q 丁= 仃m 2i n ( 一又l ) ) 乞 丰意到z t = i i z l q 丁z i ，有 ( ( a k j ) 2 一仃m 2i 。( 宙0 一定l ) ) 既+ 九毛+ l 。m y ( y 丁z t ) = 0 利用x 。的定义，上述关系式即为 y + 未+ l 。y ( y r z i ) = 0 注意到引理2 3 2 有y 0 ，故 l + 礁+ 1 。y t z i = o 口 注 1 该定理表明对于两个不i 一的近似特征值又和毛，对应的精化r i t z 向量砒和吗正 交的充分必要条件为向量z t 和巧是正交的。由关系式( 2 8 ) 可知，对角矩 阵( ( a 一天。j ) 2 一盯m 2 i 。( 砒一天。厶) ，) 除第i 个对角元为负数以外，其它对角 元均为正数，类似地对角矩阵( ( a k f l ) 2 一仃m 2i 。( 砜一砖t ) ，) 除第歹个对 7 1 j 元为负数以外，其它对角元均为正数，故向量z 和巧内积具有如下形式 z 巧= d l 可；+ 十吨y ；十+ 也谚+ + d m 碾， ( 2 9 ) 其中d 1 ，确定墨 斛，i = 1 ，2 。，7 是否为列满秩的如果其中有一个壬! 砷是列满秩的，令k ：k + 1 ， 癣到毋如果所有的截姚，i = 王，2 ，7 均是数值上秩亏损酌，则停机， 黛隐式重新开始? 对和应用带有精化位移的隐式重新启动模式，回 到彳 注算法王的理论背景参见f 2 q 3 4 数值算例 算例l 构造矩阵蠢= x 一1 a x ，麓中 a 一8 p a n c 二兰：茗 ， 二兰呈言 ， 二兰：詈 ，t 8 ，- 6 ，1 4 ，l 一- ，9 。， ，一1 0 ，1 1 ，9 0 ， x 是一个随机生成的矩阵，其条件数为c o n d ( x ) h l x 。川x 1 i 1 1 4 4 4 矩阵a 有 两个羔重特征值入一1 9 。ia n da = 1 9 + i ，其余均为单特征值。该算例与文 献f 2 4 j 中的算例类似。 厢算法3 3 1 求解9 0 9 0 矩阵a 特征闯题我们计算矩阵a 跋实部最人的 五个特征值并估计煎鼋数。k r y l o v 子空间的维数取为1 0 ，算法的停机准则为残 量范数小于t o l = 1 0 1 0 计算的近似特征值分别为为 关于精化近戗特征潮量的一龋性质研究 肛l 1 9 0 0 0 1 0 0 0 0 i ，p 2 1 9 0 0 0 + 1 0 0 0 0 i ，肛3 1 8 0 0 0 ，肛4 1 6 0 0 0 ，肚5 1 4 0 0 0 表1 给是确定计算的近似特征值重数的过程 褒3 1 ：算例l 近似特征值的重数估计 k s v d ( 甜)s v d ( 蚕笋)s v d ( 击乎)s v d ( 蚤乎)8 v d ( 蚤乎) l1 0 0 0 0 0 0 01 0 0 0 0 0 0 01 0 0 0 0 0 0 01 0 0 0 0 0 0 01 0 0 0 0 0 0 0 21 3 8 3 3 3 7 5王3 8 3 3 3 7 5圭4 1 4 21 3 6王4 1 4 2 1 3 61 4 1 4 2 1 3 6 0 2 9 3 9 0 0 30 2 9 3 9 0 0 35 8 d 1 21 2 d 1 05 3 d l l 1 6 3 1 8 9 21 6 3 1 8 9 2 30 5 1 3 6 8 0 20 5 1 3 6 8 0 2 0 2 7 0 2 6 0 70 2 7 0 2 6 0 7 1 8 6 8 2 4 41 8 6 8 2 4 4 40 5 9 2 9 1 0 9 0 5 9 2 9 1 0 9 0 3 9 7 6 4 310 。3 9 7 6 4 3 1 8 7 d 王58 6 d 1 5 按实部最大5 个近似特钲值的重数 l 特征值 】弘2p 3肛4肚5 |重数33l重l 对每一个随机选取的初始向量，精化a r n o l d i 方法对重近似特征值只计算出 一个楼对应的精化遥曩冀特征向量。在算法l 运行4 次后，对每一个近似特征值1 町 以计算澎4 个精化近似特征向量。因此可以确定待求特征值的重数。 算例2 此例构造矩阵l = x 1 a x ，其中对角矩阵 a = d i a g ( 一l ，c 4 , ，4 ，一7 ，一8 ，一9 ，一9 ，- j ) ，j = 1 1 ，1 2 ，9 0 0 ， 1 _ _ l _ 、，i _ o - ， 5 可逆矩阵x 足随机产生的，其条件数为c o n d ( x ) 一j | x 一1i ii i x l i 1 1 1 掌1 0 5 以有 两个蠛特征值a = - 4 和入= 9 ，它们的重数分别为五重和两藏，其余的特征值 均为单特征值。 第三章川精化a r n o l d i 疗法求矩阵重特征值问题 2 5 用算法3 3 1 求解9 0 0 9 0 0 矩阵a 的特征问题我们求该矩阵的按实部最大 的1 0 个特征值并确定其重数。k r y l o v 子宁间的维数m 取为2 0 算法的停机准则为 残量小于t d f = 1 0 1 2 算得的1 0 个近似特征值分别为 p l - 1 0 0 0 ，i t 2 - 4 0 0 0 ，p 3 - 4 0 0 0 ，弘4 一4 0 0 0 ，p 5 一4 0 0 0 ， p 6 - 7 0 0 0 ，p 7 + - 8 0 0 0 ，p 8 - 9 0 0 0 ，弘9 - 9 0 0 0 ，p l o - 1 1 0 0 0 表2 给出决定近似特征值重数的过程。 表3 2 ：算例2 确定近似特征值的重数 k s v d ( 引k ) )：s v d ( 击)s v d ( 击护)s v d ( ( 蚕( 4 k )s v d ( 壬驴)s v d ( 击乎)