计算方法-特征值2.

一、基本QR方法§2.QR方法60年代出现的QR算法是目前计算中小型矩阵的全部特征值与特征向量的最有效方法。实矩阵、非奇异。理论依据：任一非奇异实矩阵都可分解成一个正交矩阵Q和一个上三角矩阵R的乘积，而且当R的对角元符号取定时，分解是唯一的。()(1)(1)11111(2)1(2)111()(1)QRQR(1,2,).,,(2,3,)kkkkkkkAQRkARQAAQRQARARQQAQAAAAkAA基本方法的基本思想是利用矩阵的分解通过迭代格式由即。于是即与相似。同理可得，。故它们有相同的特征值。将化成相似A的上三角阵（或分块上三角阵），从而求出矩阵的全部特征值与特征向量。可证，在一定条件下，基本QR方法产生的矩阵序列｛A(k)｝“基本”收敛于一个Schur型阵。即主对角线及以下元素均收敛，主对角线以上元素可以不收敛。特别的，如果A是实对称阵，则｛A(k)｝“基本”收敛于对角矩阵。基本QR方法每次迭代都需作一次QR分解与矩阵乘法，计算量大，而且收敛速度慢。因此实际使用的QR方法是先用一系列矩阵相似变换将A约化成拟上三角矩阵(称为上Hessenberg矩阵)，然后对此矩阵用基本QR方法。因为拟上三角矩阵具有较多零元素，故可减少运算量。化A为相似的拟上三角阵的方法有多种。1HouseholderAHouseholderA（）用变换将矩阵化成上海森柏格矩阵H。(2)用变换将对称矩阵化成对称三对角矩阵。为了求矩阵特征值先进行初等变换把矩阵变成较简单形式()22,,,,nxyRxyHouseholderHHxy定理:设为中任意非零向量且则存在矩阵使得。222222,(2)2().22().TTTTxywHIwwxyxyxyHxIwwxxxxyxyxyxyxxyxyxyHxy证：令于是由－范数的定义.代入上式得二、豪斯豪尔德(Householder)方法221122112122122212(,,)1,1222212222212TnnnTnnnn设向量满足则称为矩阵或反射矩阵。豪斯豪尔德(Householder)变换11;(2)det()1;THHHHH可证其具有以下性质：（）是实对称的正交矩阵，即三、化一般矩阵为拟上三角阵111211121222123233311(2,3,,),nnnnnnnnniihhhhhhhhHhhhhhhin称形如的矩阵为拟上三角阵，也称为上海森堡（Hessenberg)阵。如果此对角线元全不为零则称该矩阵为不可约的上Hessenberg矩阵。HouseholderA讨论用变换将一般矩阵相似变换成Hessenberg阵.11111111,100001HouseholderHHHAHHHHHnHouseholder首先，选取矩阵使得经相似变换后的矩阵的第一列中有尽可能多的零元素。为此，应取为如下形式其中为阶矩阵。11121112131111122122221213122211111(,,,),(,,,),.(1,0,,0),2TTnnTnnnnTaaHHAHaaaaHaHAHaaaaaaAaaHHaHAHn于是有其中由上节定理，只要取使得就会使得变换后的矩阵的第一列出现个零元。111111211111122221122,()()1000****0100****00*****00waaesignawHHaaesignaHouseholderHHHAHHH为避免在计算时会产生较大的误差取。同理，可构造如下列形式矩阵使得*12222112222,,,,.nnnnnHouseholderHHHHHHAHHHHHHessenbergAH如此进行次，可以构造个矩阵使得其中为上矩阵。特别地，当为实对称矩阵，则经过上述正交变换后，变为三对角阵。:522232105222202100241HouseholderAA例用变换将矩阵化成拟上三角阵。1111122(1,0,0),(1,00).21,02TTaHaHIHIHouseholderHH解：因由为使矩阵满足222'''(),()(2,2)2(1,0)(22,2)222,2222iiiiTTTTxxesignxwxxesignx由公式，。2222222210442220122222442210000100220022220022THIwwH211210005222320100105222222000210222202410022100052510100103222000223220012220022HHHAHH于是有四、拟上三角矩阵的QR分解2121(2)(2)(2)11112131(2)(2)(11222322110(cossin00sincos000011nnHnGivensHQRhVrhhhhhhVH因为拟上三角阵的特殊形状，通常用个旋转变换（又称变换）可将它化成上三角矩阵，从而得到的分解式。具体步骤为：设否则进行下一步），取旋转矩阵则2)(2)(2)(2)32333(2)(2)1(2)221121111112111cos,sin,.nnnnnhhhhhhhHrhhrr其中232222232(3)(3)(3)(3)11213111(3)(3)(3)223212(3)(3)(3)23331332(3)(3)(434140(10cossinsincos11nnnnnnnnhVrhhhhrhhhhhhVHhhh（）（）设否则进行下一步），再取旋转矩阵－则(3)3)(3)(3)1(2)(2)(2)2(2)23222222223222cos,sin,()().nnnnHhhhhrhhrr其中()(1)1()()()()1111111()()()11111()()()1()()()1111()()11kkkkkkkkkknnkkkkkkknknkkkkkknknkkkkkknknkknnnnkHVHrhhhhrhhhhhhhhhhh假设上述过程已进行了步，有()11()()1()2()210,11cossinsincos1cos,sin,()().kkkkkkkkkkkkkkkkkkkkkkkkkkhVhhrrrhh设取其中(1)(1)(1)11111(1)(1)1()(1)(1)(1)(1)111111(1)(1)(1)21212(1)(1)11kkkkknkkkkkknkkkkkkkkkknknkkkkkknknkknnnnrhhhrhhVHHhhhhhhhhn于是因此，最多做次旋转变()()()112131()()2232()()1122133nnnnnnnnnnnnnnnrhhhrhhHVVVHRrhr换，即得1213212132123(2,3,,)4,()iiTTTnnTTTnnVinHVVVRQRQVVVnQROnHRQQRQR因为均为正交矩阵，故其中仍为正交矩阵。可算出完成这一过程的运算量约为比一般矩阵的分解的运算量少一个数量级。可证明仍是拟上三角阵，于是可按上述步骤一直迭代下去，这样得到的方法的运算量比基本方法大为减少。需要说明QR的是，通常用方法计算特征值，然后用反幂法求其相应的特征向量。'22''2532644445(6,4)64(1,0)(652,4)(0.957092,0.289784)2100.9160250.2773500.8320500.552010.2773500.0839747TTTTTQRAA用方法求矩阵的全部特征值。首先将化成拟上三角阵解：，取例：147000.5547000.83205010000.8320500.55470000.5547000.832050H于是11(1)2211112151.3867503.3282007.2111021.2307688.15384000.1538462.230767,5(7.21102)8.774964cos50.56980.sin0.821781HHAHHAHQRHHrrV即为与相似的拟上三角矩阵。将进行分解，记取0.5698030.82178100.8217810.5698030001(1)2122222228.7749641.8015968.59708900.4383101.91103000.1538462.230767(0.438310)(0.153846)0.464526,cos0.4383100.943564,sin0.1538460.331189VHrrr于是再取32(1)3221110000.9435640.33118900.3311890.9435648.7749641.8015968.59708900.4645262.541982001.471953VVVHR于是12132(2)110.5698030.7754030.2721650.8217810.5376430.18871200.3311890.9435643.5194824.92549110.8401170.3817391.0916272.31065300.4874951.38888,113TTQVVHRQ第一次迭代得重复上述过程迭代次(12)1232.9920321.000385312.0133920.0074962.0046951.94197100.0003250.9998952.992032,2.004695,0.9998953,2,1.0.007496HQR得精确值下三角非对角元的最大模为。方法“基本”收敛较慢。五、带原点移位的QR方法()()121()()1121QR,(),,kknnnnkknnnnnnnHhAAHhkuuuuu理论分析和实际计算均表明，方法产生的矩阵序列的右下角对角元素最先与的特征值接近。可以证明，若矩阵的特征值满足则的右下角对角元且收敛速度是线性的，速率为。于是考虑原点移位的技巧来加快收敛速度，即取位移使其满足且11()nnuHuIQRuQR