（计算数学专业论文）semiseparable矩阵结构分析及qr迭代.pdf

s e m i s e p a r a b l e 矩阵结构分析及q r 迭代 摘要 半分离矩阵是_ 类有着特殊结构的矩阵，特别是对称半分离矩阵，它只需要 两个向量就可以被构造出来半分离矩阵是随着对三对角矩阵研究的深入而出现 的半分离矩阵与三对角矩阵之间有着紧密的联系这集中体现在个众所周知 的结论，即可约对称三对角矩阵的逆总是半分离矩阵此外，半分离矩阵与三对 角矩阵桃相关理论上有着一些完全类似的结论例如它t t r 有完全相似的隐式 q 一定理，两者在q r 方法下矩阵结构都总能保持封闭性等 在本文，我们首先分析了半分离矩阵在结构组成t 的特点并陈述了它及相关 矩阵的定义，在基础上，我们利用半分离矩阵的结构特点给出了个判断半分离 矩阵的定理我们知道，任何个对称矩阵可以经过正交相似变换得到个三对 角矩阵与此类似，我们定义了种反k r y l o v 矩阵并= 考虑它的q 兄分解，利用得到 的正交矩阵对先前的对称矩阵实施正交相似变换得到的正是个半分离矩阵我 们表明了他它们之间的这种联系证明了这结果此外，我们陈述了半分离矩阵 的不可约定义并讨论了保证其不可约的充分必要条件。紧接着，我们着眼子半分 离矩阵的q r 分解并给出了一j 竖理论上的结果重点研究了这类矩阵在进行q r 分解之后得到的正交矩阵和上三角矩阵的结构特点然后，我们讨论了半分离矩 阵的隐式q 一定理并目利用半分离矩阵与三对角矩阵的关系提供了一种简洁的证 明最后，我们考察半分离矩阵包括对角加半分离矩阵的q r 迭代充分利用半 分离矩阵的结构巧妙的证明了它们在q r 方法下始终保持结构封闭性 关键词；半分离矩阵；正交矩阵；特征值；q r 迭代 a b s t r a c t t h es e m i s e p a r a b l em a t r i xi so n ec l a s so fm a t r i xw i t hs p e c i a lm a t r i xs t r u c - t u r e e s p e c i a l l y , t h es y m m e t r i cs e m i s e p a r a b l em a t r i xc a l lb er e p r e s e n t e db y t w ov e c t o r 8 t h es e m i s e p a r a b l em a t r i xa p p e a r sw h e nw ed e e p l ys t u d yt h ei n v e r s eo ft r i d i a g o n lm a t r i x t h ec l a s so fs e m i s e p a r a b l em a t r i e sh a si m p o r t a n t c o n n e c t i o n sw i t ht h ec l a s so ft r i d i a g o n a lm a t r i c e s i ti st h ew e l lk n o w np r o p - e r t i e sw h i c ht h ei n v e r s eo fan o n s i n g u l a r ，i r r e d u c i b l es y m m e t r i ct r i d i a g o n a l m a t r i xi sa s y m m e t r i cs e m i s e p a r a b l em a t r i x m o r e o v e r ，t h e r ea r em o r es i m i l a r c o n c l u s i o n so ns o m et h e o r i e s f o re x a m p l e ，t h ei m p l i c i t qt h e o r e mf o rt h e s e m i s e p a r a b l em a t r i xa n dt r i d i a g o n a lm a t r i xi sa b s o l u t e l ys i m i l a r a n dt h e i r m a t r i xs t r u c t u r ei si n v a r i a n tu n d e rq ri t e r a t i o n s f i r s t l y , w ea n “y 鼬t h es t r u c t u r eo fs e m i s e p a r a b l em a t r i c e s w ea l s os t a t e t h ed e f i n i t i o n so fs e m i s e p a r a b l em a t r i c e sa n ds o m er e l a t i v em a t r i c e s f u r t h e r m o r e ，w ep r o v eat h e o r e mw h i c hc a ni d e n t i f yt h es e m i s e p a r a b l em a t r i c e s i ti s w e l lk n o w na n ys y m m e t r i cm a t r i xc a nb er e d u c e db ya no r t h o g o n a ls i m i l a r i w t r a n s f o r m a t i o ni n t ot r i d i a g o n a lf o r m s i m i l a r l y , w es h o wt h a tt h eo r t h o g o n a l m a t r i xa p p e a r i n gi nt h eq rf a c t o r i z a t i o no fas u i t a b l ed e f i n e di n v e r t e dk r y l o v m a t r i xt r a n s f o r m sas y m m e t r i cm a t r i xi n t oa s e m i s e p a r a b l em a t r i x 。w en o t o n l ys h o wt h el i n kb e t w e e nt h ei n v e r t e dk r y l o vm a t r i xa n dt h es e m i s e p a r a b l e m a t r i xb u ta l s op r o v et h er e s u l t 。m o r e o v e r ，w ed i s c u s sh o wt h es e m i s e p a r a b l e m a t r i xi si r r e d u c i b l e w ea l s os t u d yt h en e c e s s a r ya n ds u f f i c i e n tc o n d i t i o n s e n s u r i n gt h i sc a s e n e x t ，w eg i v es o m et h e o r e t i c a ls t r u c t u r a lp r o p e r t i e so ft h e q rf a c t o r i z a t i o no ft h es e m i s e p a r a b l em a t r i x w ea n a l y s i st h es t r u c t u r eo f t h eo r t h o g o n a lm a t r i xa n dt h eu p p e r - t r i a n g u l a rm a t r 玟a n dt h e nw es t u d y s e m i s e p a r a b l e 矩阵结构分析及q 冗迭代 v t h ei m p l i c i t - qt h e o r e mf o rt h es e m i s e p a r a b l em a t r i c e s i np a r t i c u l a r ，w eg i v e ap r o o fb yu s i n gt h e i ri n v e r s e sw h i c ha r et r i d i a g o n a lm a t r i c e s f i n a l l y , w e s t u d yt h eq ri t e r a t i o n so ft h es e m i s e p a r a b l em a t r i xa n dt h ed i a g o n a lp l u s s e m i s e p a r a b l em a t r i x a n dw ep r o v et h a tt h e i rs t r u c t u r e sa r ei n v a r i a n tu n d e r q ri t e r a t i o n sb ya d e q u a t e l yu s i n gp r e v i o u sr e s u l t s k e yw o r d ：s e m i s e p a r a b l em a t r i x ；o r t h o g o n a lm a t r i x ； e i g e n v a l u e ； q ri t e r a t i o n 厦门大学学位论文原创性声明 兹呈交的学位论文，是本人在导师指导下独立完成的 研究成果本人在论文写作中参考的其它个人或集体的研 究成果，均在文中以明确方式标明本人依法享有和承担 由此论文而产生的权利和责任 责任人( 签名) ： 2o o7 年乡月2 多日 孑l 每旭 厦门大学学位论文著作权使用声明 本人完全了解厦门大学有关保留、使用学位论文的规定。 厦门大学有权保留并向国家主管部门或其指定机构送交论 文的纸质版和电子版，有权将学位论文用于非赢利目的的 少量复制并允许论文进入学校图书馆被查阅，有权将学位 论文的内容编入有关数据库进行检索，有权将学位论文的 标题和摘要汇编出版保密的学位论文在解密后适用本规 定 本学位论文属于 1 、保密() ，在年解密后适用本授权书。 2 、不保密( ) ( 请在以上相应括号内打” ”) 作者签名：孔絮旭日期：卅年岁月沾日 导师签名： 峨 日期。劬7 年占月厂口日 第一章引言 1 第一章引言 一半分离矩阵的来源背景 1 9 5 0 年，g a n t m a c h e r 和k r e i n 在他们的书中首次提到通过计算得到不可 约非奇异三对角矩阵的逆矩阵具有半分离结构，半分离矩阵( s e m i s e p a r a b l em a - t r i c e s ) 最早被定义为不可约非奇异三对角矩阵的逆矩阵- 在些早期的论文中， 半分离矩阵也曾被称为。格林矩阵”、。o n e - p a i r 矩阵”，。s i n g l e - p a i r 矩阵”1 9 6 0 年，作者r o y ，g r e e n b e r g 等 研究了作为统计学领域的类所谓p a t t e r n e d 矩 阵的快速算法，其谈到的p a t t e r n e d 矩阵毙足半分离矩阵和对角加半分离矩阵 1 9 7 1 年，b a r a n g e r 等 证明了半分离矩阵的逆是三对角矩阵并给出了显式计算 公式1 9 8 6 年，r o z s a 的文献在个定理中提出了严格带宽矩阵的逆矩阵具有 半分离结构，并首先将它命名为半分离矩阵 半分离矩阵出现在许多不同的领域，例如线性系统理论，微分方程和积分方程 的离散化【9 】( 1 1 】，些边值问题f 1 4 和某些图象模型问题等，也出现在时间变量 线性系统，统计学【1 8 ，高斯一马尔可夫过程【1 6 】等理论中多项式有理插值问 题( 2 0 ，声波与电磁波的散射理论【19 】等也用到半分离矩阵 二研究现状 近年来，半分离矩阵的研究引起了人们极大的兴趣，如v a nb a r e lm ，f a s i n o d ，g e m i g n a n il ，m a s t r o n a r d in ，e i d e l m a ny ，g o h b e r gi 等人在矩降结构和特 征值的计算方面对半分离矩阵进行了深入的研究d f a s i n oa n dl g e m i g n a n i 在文献 3 】中研究了在半分离矩阵的逆特征值问题既然半分离矩阵是不可约非 奇异三对角矩阵的逆矩阵，很自然的利用矩阵的半分离结构求解线性系统和求解 矩阵特征值的快速算法被设计出来而且在运算方面与三对角矩阵相比所花费的 代价几乎是相同的对于半分离矩阵自身来说，也存在些实用而有效的算法， 例如d f a s i n o ，n m a s t r o n a r d i ，m v a nb a r e l ，c h a n d r a s e k a r a n ，a n ds v a n h u f f e l 中提出了种将半分离矩阵约化为双对角或三对角矩阵的方法 2 3 2 5 】， 第一章引言 2 e v a nc a m p ，n m a s t r o n a r d i ，a n dm v a nb a r e l 等人利用分而治之法实现半 分离矩阵特征值的求解【7 】 更般的讲，半分离类矩阵实际上包括上半分离矩阵，下半分离矩阵，对角 加半分离矩阵，类海森伯格( h e s s e n b e r g - l i k e ) 矩阵等类型，而且也分对称型与非 对称型，我们研究的般是对称类型的半分离矩w 串- - - 与不可约非奇异三对角矩阵 之间有着紧密的联系人们很自然的关心它在求解矩阵特征值方面扮演着何种角 色对个对称矩阵总可以利用个正交矩阵，通过正交相似变换得到个三对 角矩阵，再进行特征值的求解事实上，我们也可以利用正交相似变换将个对 称矩阵化为个半分离矩阵或对角加半分离矩阵，再利用q r 算法实现特征值的 求解，两者所花费的代价基本是相同的v a nb a r e lm ，m a s t r o n a r d in 等提出 了可以先将利用正交相似变换将个对称矩阵转化为个半分离矩阵，在半分离 矩阵的基础之上再求解特征值，并目给出了个与将对称矩阵化为三对角矩阵花 费同样代价的算法而且他们证明了在计算半分离矩阵的特征值的过程中实际上 就是利用l a n c z o s 过程求初始矩阵r i t z 值文献 6 】中提到了种l a n c z o s - l i k e 算法可以将个对称矩阵转化为半分离矩阵 对于不可约三对角矩阵，隐式q 一定理告诉我们，利用正交矩阵将个对称 矩阵进行正交柑似变换得到三对角矩阵是由正交矩阵的第列完全决定的隐式 q 一定理保证至多差个符号，由两个第列相同正交矩阵静个对称矩阵正交 相似变换得到的两个三对角矩阵不可能不相同而且，我们知道三对角矩阵的q r 迭代是封闭的，既如果t 是对三对角矩阵t 进行次q r 迭代后得到的矩阵， 那么于也是个三对角矩阵事实上，由三对角矩阵与半分离矩阵的对偶关系， 我们对于半分离矩阵也有类似的结果假定a 为个非奇异对称矩阵，q 和y 为两个正交矩阵且分别将矩阵a 变换为两个半分离矩阵，如果q 和y 的第一 列相同，那么他们每列至多差个符号，得到的两个半分离矩阵在本质匕是相 同的这就使得对个对称矩阵a 而言。一旦给定正交矩阵的第列，那么就存 第一章引言 3 在个唯确定的半分离矩阵使得其与矩阵a 相似如果我们考察半分离矩阵 的q r 迭代，可以得出如果s 是对半分离矩阵s 进行次q r 迭代后得到的矩 阵，那么s 也是个半分离矩阵矩阵，即半分离矩阵在q r 算法下同样保持结 构不变性 利用l a n c z o s 算法作用于个对称矩阵a 的过程实际匕就是在k r y l o v 子 空间中寻找组正交基将a 化为个三对角矩阵假设a 的特征值均为单箱证 值，k 为由a 和个列向量口定义的k r y l o v 矩阵，在k 非奇异的情形下考 虑k 的正交分解k = q r ，那么t = q r a q 是个不可约三对角矩阵隐式 q 一定理使得矩阵t 不必由矩阵k 进行显式计算我们定义种反k r y l o v 矩 阵坼，在其非奇异的情形下，设对其进行正交分解后得到的正交矩阵为q j ，那 么s = q r a q ，是个不可约半分离矩阵当我们得到不可约半分离矩阵的隐式 q 一定理之后，知道s 也不需要由硒进行显式计算这与三对角矩阵是完全类 似的考虑到半分离矩阵与三对角矩阵之间的关系，这样的个结果也在情理之 中 半分离矩阵的特点不仅仅体现在它与三对角矩阵之间的关系上，更体现在它 独特的结构形式上个nxn 对韵泮分离矩阵可以由两个佗维列向量：表示出 来这跟秩一1 矩阵f 艮相似但又有区别当我们考察半分离矩阵的q r 分解时， 会发现得到的政矩阵q 和匕三角矩阵r 在结构匕也有非常特别的形式 三本文主要内容及作者主要工作 在本文中，我们先在第二章给出了半分离矩阵与相关矩阵的定义及性质。并简 单探讨了他们之间的关系，特别建立了半分离矩阵与种定义了反k r y l o v 矩阵 之间的联系；在第三章，我们着重讨论了半分离矩阵的不可约性，并总结了保证 半分离矩阵和丁约的充分必受条件，此外，分析了半分离矩阵在进行q r 分解之 后得到的正交矩阵q 和上三角矩阵r 的些结构性质；在第四章，我们主要给 出了半分离矩阵的隐式q 一定理，并通过半分离矩阵与三对角矩阵之问的关系给 第一章引言4 出了个简洁的证明，此外利用半分离矩阵的结构特点证明了半分离矩阵包括对 角加半分离矩阵对q r 迭代下的矩降结构保持不变 本文作者的主要工作体现在得出一种判别半分离矩阵的巧妙方法，并在文中 多次用到这种方法另外阐述了半分离矩阵与反k r y l o v 矩阵之间的联系，得出一 个对称矩阵可以经过正交相似变换得到半分离矩阵这样个重要结论此外。结 合半分离矩阵与三对角矩阵的关系证明半分离矩阵的隐式q 一定理本文的另一 个重要工作是利用半分离矩阵的结构特点得到其在q r 迭代下的结构不变性 作者不但证明了对半分离矩阵有这样的结果，更进步证明了当我们取对角加半 分离矩阵时这个结论仍然是成立的，即每进行完步q r 迭代后，得到的仍然是 个对角加半分离矩阵且其中的对角矩阵保持不变 第二章半分离矩阵定义及性质 5 第二章半分离矩阵定义及性质 广义e 讲，半分离矩阵实际匕是大类矩阵，它不仅包括般意义上的对称和 非对称形式的半分离矩阵，还包括对角加半分离( d i a g o n a l - p l u s - s e m i s e p a r a b l e ) 矩阵，类海森伯格( h e s s e n b e r g - l i k e ) 矩阵等类型这些矩阵与三对角矩阵和一种 定义了的反k r y l o v 矩阵之问存在着密切的联系 2 1 半分离矩阵 最初，半分离矩阵被定义为不可约三对角矩阵的逆矩阵( 可以参考文献【l 】) ， 后来也被定义为不可约带宽矩阵的逆矩阵【4 】，半分离矩阵主要有以下几种定义形 式【5 】在下面的讨论中，如果不做特别说明，我们总是用t r i u ( a ) 表示矩阵a 的严格匕三角部分，用t r i l ( a ) 表示矩阵a 的下三角部分 定义2 1 如果存在两个秩为7 的矩阵r 1 和恐，使得 s = t r i u ( r 1 ) + t r i l ( r 1 ) ， 则称矩阵s 为个半分离秩为r 的半分离矩阵 特别的，我f f 丁有 定义2 2 设让，v ，s ，t 均为钆维向量，若有 s = t r i u ( u v t ) + t r i l ( s t t ) ， 则称矩阵s 为半分离秩为1 的半分离矩阵，并称向量u , u ，s ，t 为矩阵s 的生成 向量 对于对称形式的半分离矩阵，我们有 定义2 3 对个n n 对称矩阵s ，若满足对于任意i ，有 r a n k ( s ( i ：n ，1 ：i ) ) 1 第二章半分离矩阵定义及性质 6 其中1 i n ，则称矩阵s 为半分离秩为1 的对称半分离矩阵 匕述几种定义基本体现了半分离矩阵的特征，包含的矩阵类型也是相当广泛 的但在实际应用中，我们讨论最多的是下面的这种定义形式 定义2 4 对个n 佗对称矩阵s ，如果存在两个n 维向量u ，秽使得 s = u l u l 让2 7 2 1 牡n t ，l u 2 u 1 u 2 v 2 u n t ) 2 t 正n v l t i n t j 2 让n 或写作 s = t r i l ( u v t ) + t r i u ( v u t ) ， 则称矩阵s 为半分离秩为l 的对称半分离矩阵，并称向量口，口为s 的生成向 量记为s = s ( 让，t ，) 在这种定义下，半分离矩阵的结构特点表现得更加直观，我们很容易地通过两 个向量就可以表示出个对称半分离矩阵特别指出，在下面的讨论中，如果不 作特别说明，则我们提及的半分离矩阵都是在定义4 下的这种对称半分离矩阵 在不产生歧义的情况下，我们可以简称其为半分离矩阵 观察在定义2 4 中出现的半分离矩阵的结构，我们不难得出对个对称矩阵 来说，只要它的上三角部分或下三角部分( 均要包含对角线上的元素) 与个秩1 矩阵的上三角部分或下三角部分完全对应就能知道它为个半分离矩阵进而， 我们有如下的结论 定理2 1 设s = s ( u ，口) 为个对称半分离矩阵，则s 可以表示成个秩 1 矩阵与个严格上三角矩阵和式的形式 证：因为s = t r i l ( u v t ) + t r i u ( v u r ) ，取t v = t r i 札( 矿一t r i u ( u v t ) ) ，我们 可以得到 s = 仳矿+ t v 第二章半分离矩阵定义及性质 7 从而矩阵s 表示成了秩1 矩阵u v r 与严格上三角矩阵和式的形式 得证 定义2 5 假设我们有个半分离矩阵s = 5 ( u ，t ，) 和个对角矩阵d = ( d 1 ，d 2 ，厶) ，称矩阵 d + s 为对角力峭纷离( d i a g o n a l - p l u s - s e m i s e p a r a b l e ) 矩阵 为了论述的方便，在不引起歧义的情况下我们将其简记为d p s s 矩阵 定义2 6 对个半分离矩阵s = s ( u ，移) 和个严格上三角矩阵f 幻，称矩 阵 s + h u 为懈森伯格( h e s s e n b e r g - l i k e ) 矩阵 对于半分离矩阵s = 8 ( u ，口) 与三对角矩阵，我们有如下的结论 1 非奇异不可约对称三对角矩阵的逆是半分离矩阵； 2 非奇异可约对称三对角矩阵的逆是个块对角阵，其中对角块为半分离矩阵 大家可以参照文献【1 】 【1 2 】得到更多细节 2 2 半分离矩阵与反k r y l o v 矩阵 对个对称矩阵a ，利用l a n c z o s 算法相当于在k r y l o v 子空间中寻找一 组正交基将a 化为个三对角矩阵假设a 的特征值均为单特征值，k 为由 a 和个列向量 定义的k r y l o v 矩阵，可以在k 非奇异的情形下考虑k 的正 交分解k = q r ，那么t = q 丁a q 是个不可约三对角矩阵隐式q 一定理表 明这时矩阵q 和t 是由q 的第列完全决定的对于半分离矩阵我们也有完 全类似的结果首先定义一种反k r y l o v 矩阵所，在其非奇异的情形下，假设 对其进行正交分解后得到的正交矩阵为q j ，那么s = q 歹a q ，是个不可约半 分离矩阵 g ：- 章半分离矩阵定义及性质8 定义2 7 设a 为个n n 阶矩阵，t ，为个几维向量，称 k = i v ，a v ，小- 1 口】 为由矩阵a 和向量t ，生成的k r y l o v 矩阵 下面我们来看如何保证k r y l o v 矩阵的非奇异性 引理2 1 设 为对称矩阵a 的特征值，t ，为个佗维向量，a = u a 乙 为矩阵a 的谱分解，令己声u = 0 3 = ( 1 1 3 1 ，w 2 ，w 。) t ，则由矩阵a 和向量t j 生成的k r y l o v 矩阵k = p ，a v ，a n - 1 u 1 非奇异的充分必要条件是： 入， 毗0 这里i ，j = 1 ，2 ，n ；i j 证l 由a = uau r 和k = p ，a v ，a 铲1 】易得 k = ，( u a v c ) v ，( u a 沪) 铲1 秽1 利用条件u r v = w ，则有 k = v w ，a v ，a 铲1 叫 考虑到铆= ( w l ，w 2 ，) t ，不难验证 【w ，a v ，a 肛1 u 】_ d i a g ( w l ，w 2 ，) y 这里y 是个v a n d e r m o n d e 矩阵 从而，我们得到 y = 久1 a ? 一 h a ：一 k = u d i a g ( w x ，她，w n ) y g ：- 章半分离矩阵定义及性质 9 显然，矩阵k 非奇异的充分! 燃件是所有的a 两两互异且所有的w 非零 得证 定义2 8 设a 为个7 l 凡阶矩阵， 为个n 维向量，称 坼= 【a 一1 u ，a 一2 口，a 一”口】 为由矩阵a 和向量v 生成的反k r y l o v 矩阵 借助引理2 1 ，我们可以得到保证反k r y l o v 矩阵非奇异的充要条件 定理2 2 设a = uau r 为对称非奇异矩阵a 的谱分解，这里a = d i a g ( a ：，a 2 ，a 。) ，令旷t ，= w = ( w l ，w 2 ，) t ，则反k r y l o v 矩阵 所= 【a _ 1 t j ，a 2 t ，a 1 叫 非奇异的充分! 明影黼所有的凡两两互异且所有的毗非零 证t 由于a 是个对称非奇异矩阵，显然我们有 a ”k r = 【a n - 1 v ，a v ，砂】= p k 这里p 是个排苑i 矩阵， k 是个k r y l o v 矩阵显然d e t ( k i ) 0 的充分必 要条件是d e t ( k ) 0 从而由引理1 就可以得到要证明的结果 得证 有了上面的条件，我们就可以在反k r y l o v 矩阵非奇异的前提下考察它的q r 分解我们知道这时的q r 分解是唯一的而且得到的上三角矩阵具有非零对角 元下面就可以考察利用得到的正交矩阵对生成反k r y l o v 矩阵的对称矩阵a 进 行正交相似变换后的结果首先，我们看个引理 引理2 2 设矩阵j f 0 是个由对称矩阵a 和向量口生成的非奇异反k r y l o v 矩阵，则k r 是矩阵方程 a k z k z b = 钉e 第二章半分离矩阵定义及性质 l o b：厂二三：三、 ( a j 订一1 ( i b ) e l = a a 一1 秒一0 = u 当i = 2 ，礼时，有 ( a 硒一k i b ) e i = a k r e i 一尬岛一1 = 0 左边= ( u ，0 ，0 ) = 西= 右边 得证 下面的定理表明了反k r y l o v 矩阵与半分离矩阵之间的关系，即对反k r y l o v 做q r 分解，利用得到的正交矩阵对反k r y l o v 矩阵的生成矩阵a 实施正交相 似变换可以得到个半分离矩阵 定理2 3 设矩阵k i 是个由对称矩阵a 和向量 生成的非奇异反k r y l o v 矩阵，并且k i = q r 是对矩阵j 0 的q r 分解，那么q t a q 是个对称半分 离矩阵 证；对任何矩阵c = 如j ) ，我们仍然用t r i u ( c ) 表示它的严格上三角部分 由引理2 2 并考虑到所= q r 得 a q r q r b = 秽e 第二章半分离矩阵定义及性质 1 1 由于矩阵r 是个非奇异上三角矩阵，对b 避行变形得 q t a q = r b r 。1 + q t u e 冗一1 = t r i u ( r b r 以) + ( q t v ) ( e t r 1 ) 显然，q t a q 是_ 个严格匕三角矩阵与个秩1 矩阵的和式，再考虑到它的对 称性，由定理2 1 知道它是个对称半分离矩阵 得证 第三章不可约半分离矩阵与q r 分解 1 2 第三章不可约半分离矩阵与q r 分解 3 1 不可约半分离矩阵 定义3 1 【1 3 】若半分离矩阵s = s ( u ，秽) 对于i = 1 ，2 ，n 满足： jr a n k ( s ( i + 1 ：几，1 ：i ) ) = 1 ir a n k ( s ( i ：n ，1 ：i + 1 ) ) 1 这里r a n k ( a ) 表示矩阵a 的秩 称半分离矩阵s = s ( u ，u ) 为不可约的 式( 0 或o 沙劂 第三章不可约半分离矩阵与q r 分解 1 3 着= u i v j = 0 也就是只能u i = 0 或吻= 0 或u i ，同时为0 而这会导致 矛盾因为 1 碱a - 0 而v j 0 由最初的条件u i 与地同时为0 ，知道此时饥0 既 然s 不是晒设中的分块形式，必有s 的最后行不为0 ，这表明t | ，i 0 所以 = u v j 0 ，而且j s 0 = 岛= u n v i 0 这表明了在s 的相关图中存在由i 通过n 到达j 的路径矛盾 2 u i 0 而v 1 = 0 同理知道岛l 0 ，s i l 0 这表明了在s 的相关图中 存在由i 通过1 到达j 的路径矛盾 3 u i = 0 ，= 0 ，由假设知v i 0 ，u j 0 ，由s 的最后行不为0 ，我们有 u 。0 ，因此s 0 = t ，l 哦0 由s 的第列不为0 ，我们有岛1 = 可1 0 而 且& l = u n l ) 1 0 这表明了存在由i 经过佗和1 到达j 的路径矛盾 通过这个引理，我们很自然地可以得出个对称半分离矩阵若可约，则它至少 有行和列为零，f z z _ ，亦然 定理3 1 设s = s ( 牡，口) 为对称半分离矩阵，若s 非奇异，则s 是不可约 阵 证：既然s 非奇异，则它无零行也无零列，由上个引理，可以知道显然此 时s 是不可约矩阵 得证 3 2q 兄分解 在上章，我们陈述了半分离类型矩阵的诸多定义，特别的，个对称半分离 矩阵s = s ( u ，口) 只需要由两个向量就可以表示出来，它的这结构特点不但在 计算存储匕占有优势，而且为我们判别这类矩阵带来了极大的方便为了进步 讨论半分离矩阵的隐式q 一定理和在q r 迭代下的结构不变性，我们有必要首 先分析半分离矩阵的q r 分解 第三宅不可约半分离矩阵与q r 分解 一1 4 h 蠹州 r ( n - 1 ) = g t r ( “) = 乱l 1 i s 2 t ) l u t $ - - 1 u i o u 2 u 1 u 2 v 2 u n 一1 u 2 0 u n - - 1 秒l 钍n v l u n - - l v 2u n v 2 ： ， u n i u nu n v n 0 依此进行下去，当作用完n 一1 个g i v e n s 旋转后得到的矩阵兄( 1 ) = r 就为个 上三角矩阵因为每个矩阵g 都是正交矩阵，所以矩阵q = 醒g 0 l g 研 作为正交矩阵的乘积也是正交矩阵而且，每个g i 仅仅作用于第i 一1 和第i 行，很容易得出矩阵q 是个下h e s s e n b e r g 矩阵 得证 定理3 3 设q 是个不可约正交下h e s s e n b e r g 矩阵，则存在向量7 ，3 ，使得 t r i l ( q ) = t r i l ( r s t ) 证：由于q 为不可约下h e s s e n b e r g 矩阵，从而它的次对角线元素均不为零， 第三章不可约半分离矩阵与q r 分解 一 1 5 即q i t t + 1 0 ，i = 1 ，2 ，n 一1 考虑个分块矩阵 c ：q ) ， 、， 1 或q 斗1 ，所以矩阵c 非奇异由基于矩阵s c h u r 分解的逆公式( 见参考文献 【2 1 】) 可以得到c - 1 具有如下的形式 c 一1 = ( 三b l t ) ， q 一- ：l 一生 由于q 为正交矩阵，故有q _ 1 = q t ，但q t 为上h e s s e n b e r g 矩阵，由匕式不 难得出q 丁的上三角部分包括对角线上的元素与秩1 矩阵一譬的对应位置匕的 元素是完全相同的从而我f f 拎r = b ，8 = 一詈，则有 t r i g ( q ) = t r i l ( r s r ) 定理3 4 设s = s ( u ，可) 为个对称不可约半分离矩阵，s = q r 是它的 t r i u ( r ) = t r i u ( z u t + s t t ) 第三章不可约半分离矩阵与q r 分解 1 6 证：因为半分离矩阵s 不可约，我们得出矩阵q 为不可约矩阵由定理3 3 我们有 q = q t = l + s r r ， 从而，我们取t = s r ，就有 r = q s = l s + s ， 注意到矩阵l 是个严格下三角矩阵，我们得到 t r i u ( l s ) = t r i u ( l v u t ) ， 令z = l v ，进步得到 t r i u ( r ) = t r i u ( z u r + ) 得证 半分离矩阵的不可约性是个重要概念，我们在此基础上研究了半分离矩阵 的q r 分解在下面将要讨论的半分离矩阵的隐式q 一定理与q r 迭代中多次 谈到了不可约半分离矩阵 第四章隐式q 一定理与q r 迭代 1 7 第四章隐式q 一定理与q r 迭代 4 1 正交相似变换 给出个对称矩阵a ，总可以找到个正交矩阵，使得矩阵a 可以通过相似 变换化为三对角矩阵 v a nb a r e lm ，v a n d e b r i lr ，m a s t r o n a r d in 等作者在他 们的文献中证明了对任意个对称矩阵都可以找到个正交矩阵，可以将对称矩 阵正交相似变换得到半分离矩阵或对角加半分离矩阵我们【17 】并且在此基础上 讨论了半- 9 离矩阵的隐式q r 算法 1 3 】他们的证明是从算法的角度采用了数学 归纳法由最初的对称矩阵逐步得到了个半分离矩阵整个过程只需要一系列的 g i v e n 旋转就可以做到考虑到整个过程较为烦琐，我们下面仅列出相关的结论 定理4 1 【1 7 设矩阵a 为个对称矩阵，那么存在个正交矩阵q 使得 q t a q = & 这里s 是个半分离矩阵 我f f 何以将这个结果与定理2 3 进行比较，会发现它们有许多相似之处都 是将个对称矩阵进行正交相似变换得到个半分离矩阵定理4 1 中所谈到的 半分离矩阵其实是定义2 3 谈到的半分离矩阵，它包含的矩阵类型比定义2 4 要 广泛，比如可以包括可约半分离矩阵而定义2 4 谈到的半分离矩阵基本匕就是 对不可约半分离矩阵而言的，定理2 3 的条件相对而言更加严格，它得到的半分 离矩阵实际上是不可约且非奇异的 另外，我们知道，对于非对称矩阵来说，通过相似变换可以得到h e s s e n b e r g 矩阵与此类似的，在文献【1 7 中提到对非对称矩阵实施正交相似变换可以得到 h e s s e n b e r g - l i k e 矩阵 定理4 2 【17 】设4 是个n 死矩阵，则存在个对称半分离矩阵s ，个 第四章隐式q 一定理与q r 迭代 一 1 8 严格上三角矩阵r ，个正交矩阵u ，有 旷a u = s + r s = ( q t a q = & p t a p = ( a 1 兰) ， 由上面的讨论对a 1 有q t a 。q l = & ，我们只要取 q = p ( q 0 1 ；) 和s = ( 詈兰) ， 第四章隐式q 一定理与q r 迭代 1 9 就可以得到q t a q = s 得证 4 2 隐式q 一定理 不可约三对角矩阵的隐式q 一定理告诉我们将个对称矩阵实施正交相似变 换得到不可约三对角矩阵时，在忽略正负号的意义下其正交矩阵和三对角矩阵只 由正交矩阵的第列唯一决定这时得到的三对角矩阵是本质唯一的即有如下 的定理， 定理4 4 【1 5 】设矩阵a 为个：对称矩阵，存在两个正交矩阵q 1 和q 2 ，使 得 q t a q l = 乃，q t 2a q 2 = t 2 其中丑，死均为不可约三对角矩阵若q 1 e 1 = q 2 e 2 ，则有 q 1 e i = d , q 2 e t ，t 1 d = d t 2 ，d = d i a g ( c h ) 这里i = 1 ，2 ，礼哦= 士1 半分离矩阵也有完全类似的结论，既然个不可约三对角矩阵的逆是半分离 矩阵，我们就可以通过不可约三对角矩阵的隐式q 一定理来证明不可约半分离矩 阵的隐式q 一定理 定理4 5 【1 3 】设矩阵a 为个对称非奇异矩阵，存在两个正交矩阵矾和 巩，使得 呼a 巩= 研，呀a 巩= 岛 其中s ，岛均为不可约半分离矩阵若巩e l = u 2 e 2 ，则有 u 1 e = 吨巩e i ，研d = d 岛，d = d i a g ( d ) 这里i = 1 ，2 ，n 画= 士1 第四章隐式q 一定理与q r 迭代 2 0 证，因为矩阵a 非奇异，所以a 一1 存在且也为对称矩阵由于& 和岛均 为不可约半分离矩阵，考虑到不可约三对角矩阵与半分离矩阵互为逆矩阵，我们 设 噩= s f lt 2 = 与1 易知乃与死必为不可约三对角矩阵，否则& ，岛不可能是半分离矩阵由题 设 曙a 矾= 毋，呀a 巩= 岛 在匕述每个鲁笋式两边分别取逆，得 呼a - 1 仉= 噩，哩a 4 = i 2 且此时阢e 1 = 玩e 2 由不可约三对角矩阵的隐式q 一定理我们知道矩阵五与 疋本质相同，即 乃d = d 正 等茧两边同时取逆得 & d = d s 2 得证 4 3 在q 兄迭代下的结构封闭性 利用q r 方法计算三对角矩阵的特征值时个重要的特点是在迭代过程中矩 阵总保持三对角矩阵的结构形式对于半分离矩阵，我们也有完全类似的结论 对半分离矩阵进行q r 迭代的过程中，矩阵总是保持半分离矩阵的结构 对于个不可约半分离矩阵s = s ( 钍，t ，) ，我们在前面分析了它的q r 分解 得到正交矩阵和上三角矩阵在结构上的特点，特别是在矩阵s 不可约的条件下， 得到的正交矩阵总是不可约的我们可以利用这些结果来证明半分离矩阵对q r 迭代的结构不变性 第四章隐式q 一定理与q r 迭代 2 1 定理4 7 设s = s ( 缸，u ) 是个不可约对称半分离矩阵，雪是对s 进行一 次q r 之后得到的矩阵， s = q r s = r q 则矩阵s 仍然是个半分离矩阵 证：由题设，我们可以得到 雪= 矿s q 而且矩阵q 不可约，则显然s 仍为对称矩阵由定理3 3 的结论我们有q r = 矿+ r 5 7 ，从而 雪= r q = r ( l t + r ，) 注意到l 是个严格下三角矩阵，从而r l r 为严格上三角矩阵因此，我们有 勿露( 雪) = t r i l ( r r s t ) 即雪的下三角部分与个秩1 矩阵的下三角部分完全相同，考虑到雪的对称 性，由定理2 1 知s 仍然是个粉离矩阵 得证 在定义半分离矩阵的过程中，我们谈到个对称半分离矩阵可以由两个向量 表示出来，而且我们指出在这种定义下半分离矩阵可以表示成个秩1 矩阵和一 个严格上三角矩阵的和的形式利用这些结果我们也可以证明半分离矩阵在q r 迭代的过程中的结构不变性下面，我们将按照这种思路对带位移的情况加以证 明 定理4 8 设s = s ( u ，u ) 是个非奇异半分离矩阵，盯是个常数，雪是 对s 进行一；次带位移的q r 迭代之后得到的矩阵l s a i = q r ，s = 冗q + a i 第四章隐式q 一定理与q r 迭代 2 2 则矩阵雪仍然是个半分离矩阵 证t 由题设，我们显然有 s r = r q r + a r = r ( s c r i ) + 盯，= r s 由于s 非奇异( 由定理3 1 可知定s 不可约) ，所以矩阵兄可逆，从而 雪：r s r 一1 由定理2 1 可以得到s = 伽r + 瓦，由此我们得到 雪= r ( u v r + 兀) r 一1 = ( r t 上) ( ”t r 一1 ) + 矾r 一1 注意到死是个严格上三角矩阵，因此r 咒冗一1 必为严格上三角矩阵所以雪 可以表示为个秩l 矩阵和个严格上三角矩阵的和的形式由定理2 1 可知雪 为半分离矩阵得证 定理4 9 给出个非奇异对角加半