QR迭代法求矩阵特征值

《QR迭代法求矩阵特征值》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、QR迭代法求解矩阵A的特征值沈欢00986096北京大学工学院，北京1008712011年10月23日摘摘摘要要要本文用QR迭代法求解矩阵A的特征值:第一步先用豪斯荷尔德变换将矩阵A化为上海森伯格矩阵AH，第二步再对AH进行QR迭代(使用吉文斯变换)，当迭代满足精度要求时输出n个特征值。1问问问题题题描描描述述述对于给定的矩阵A(存在n个不相等的实特征值),采用QR方法求其n个特征值。本文中的矩阵A由文件"gr900900crg:mm"给出。并以:mm格式描述。2算算算法法法描描描述述述2.1得得得到到到实实实对对对称称称矩矩矩阵阵阵A本文由文件"gr900900cr

2、g:mm"得到了以:mm格式描述的系数矩阵A。A矩阵是900¤900的大型稀疏对称矩阵。于是，在matlaB中，使用"A=zeros(900,900)"语句生成900¤900的零矩阵。再按照.mm文件中的描述，分别对第i行、第j列的元素赋对应的值，就生成了系数矩阵A，并将A存为.mat文件以便之后应用。由于A矩阵是实对称的900阶矩阵，所以A矩阵有900个实特征值，可以使用QR方法求解。下面描述具体算法。2.2QR算算算法法法QR算法的核心思想是：对一个具有n个不相等的特征值的矩阵A，进行如下变换：A=Q1R1;A1=R1Q1A1=Q2R2;A2=R2Q2¢¢¢¢¢¢

3、¢¢¢1Ak=Qk+1Rk+1;Ak+1=Rk+1Qk+1¢¢¢¢¢¢¢¢¢其中Qi是正交矩阵，Ri是可逆的上三角矩阵。由于：A=QT(QR)Q=QTAQi+1i+1i+1i+1i+1i+1ii+1所以Ai+1和Ai相似，具有相同的特征根。当i!1时，Ai对角线以下元素趋于零。利用这一原理，可以对给定A进行QR迭代，最终得到上三角矩阵(对角元素不一定非零)，输出对角元素可以作为A的特征值。我们又发现，具有如下上海森伯格形式的矩阵AH：23a11a12a13:::a1n¡1a1n676a21a22a23:::a2n¡1a2n767660a32a33a34::::::77

4、AH=67(1)6::::::7674::::::500::::::an;n¡1annAH在QR迭代过程中可以保持上海森伯格形式不变。所以，QR迭代算法分两步实现，第一步将矩阵A变换为上海森伯格矩阵AH,第二步对此上海森伯格矩阵AH进行QR迭代，直至满足精度为止，输出结果。在第一步中，将矩阵A变换为上海森伯格矩阵AH，为了保持变换后的AH与A具有相同的特征值，这里采用豪斯荷尔德变换(正交变换)，本步在后文中详细说明；在第二步中，对上海森伯格矩阵AH进行QR迭代，并不去直接找出Q矩阵和R矩阵，而是采用吉文斯变换达到相同的效果，本步在后文中也有详细说明；对于QR迭代的精度

5、，在算法采用：当迭代到第k次时有：jAi+1;ij

6、为上上上海海海森森森伯伯伯格格格矩矩矩阵阵阵AH豪斯荷尔德矩阵H=I¡2wwT其中w是单位向量。所以H矩阵是正交、对称矩阵。2A⫼QR䗁ҷ⊩∖ⶽAⱘ⡍ᕕؐ䰉˄Џ⿟ᑣ˅⫼䈾ᮃ㥋ᇨᖋবᤶᇚAবЎϞ⍋ỂԃḐⶽ䰉AH䕧ߎAnᕫࠄⱘᇍ⒵䎇㒧Yes㾦ܗ㊒ᑺᴳ䖒ࠄQR䗁ҷⱘ㊒ᑺ˛㋴԰ⱘϞ⿟ϝ㾦ЎAᑣⶽ䰉ⶽ䰉NoAnⱘ⡍ᕕؐ⫼ঢ়᭛ᮃবᤶᅲ⦄ϔ⃵ㄝᬜⱘQR䗁ҷˈे˖Ai=QiRiAi+1=RiQi图1:主程序(QR迭代法求矩阵特征值)算法用豪斯荷尔德变换将A矩阵化为上海森伯格矩阵AH是实现下述过程：A1=H1AH1A2=H2A1H2¢¢¢¢¢¢An¡2=Hn¡2An¡3Hn¡2其中H1

7、、H2¢¢¢¢¢¢满足:23203a11a11676076a2176a2176767H166a3177=66077(2)6.76.74..54..5an1032323000a12a1260760076a2276a22760760076a76a763276327H2607=67(3)6a42760767676..76..74.54.50an20¢¢¢¢¢¢于是构造豪斯荷尔德矩阵Hi成为此函数的核心。对于Hi，目的是将之前得到的Ai¡1中的第i列实现如下变换：2032003a1ia1i60760076a2i76a2i760760076a76a763i76