普通矩陣特征值的QR算法.doc

普通矩陣特征值的QR算法 摘 要 求矩陣的特征值有多種不同的辦法，本文主要介紹用QR法求矩陣的特征值，QR法是目前求中等大小矩陣全部特征值的最有效方法之一，使用于求實(shí)矩陣或復(fù)矩陣的特征值，它和雅可比法類似，也是一種變換迭代法。關(guān)鍵詞：QR分解 迭代序列 特征值 Matlab一 、QR方法的理論： 對任意一個(gè)非奇異矩陣（可逆矩陣）A，可以把它分解成一個(gè)正交陣Q和一個(gè)上三角陣的乘積，稱為對矩陣A的QR分解，即A=QR。如果規(guī)定R的對角元取正實(shí)數(shù)，這種分解是唯一的。若A是奇異的，則A有零特征值。任取一個(gè)不等于A的特征值的實(shí)數(shù)，則A-I是非奇異的。只要求出A-I的特征值和特征向量就容易求出矩陣A的特征值和特征向量，所以假設(shè)A是非奇異的，不是一般性。 設(shè)A=A1 ，對A1 作QR分解，得A1 = Q1R1，交換該乘積的次序，得A2 = R1Q1=，由于Q1正交矩陣，A1到A2的變換為正交相似變換，于是A1和A2就有相同的特征值。一般的令A(yù)1=A，對k=1，2，3，. 這樣，可得到一個(gè)迭代序列Ak，這就是QR方法的基本過程。2、 QR方法的實(shí)際計(jì)算步驟Householder變換：如果 v 給出為單位向量而 I 是單位矩陣，則描述上述線性變換的是 豪斯霍爾德矩陣 （v * 表示向量 v 的共軛轉(zhuǎn)置）H=I -2VV*三、化一般矩陣為Hessenberg陣 稱形如的矩陣為上海森堡（Hessenberg）陣。如果此對角線元(i=2,3,.n)全不為零，則該矩陣為不可約的上Hessenberg矩陣。用Householder變換將一般矩陣A相似變換為Hessenberg矩陣。首先，選取Householder矩陣，使得經(jīng)相似變換后的矩陣的第一列中有盡可能多的零元素。為此，應(yīng)取為如下形式 其中為n-1階Householder矩陣。于是有 只要取使得，就會使得變換后的矩陣的第一列出現(xiàn)n-2個(gè)零元。同理，可構(gòu)造如下列形式Householder矩陣使得如此進(jìn)行n-2次，可以構(gòu)造n-2個(gè)Householder矩陣，使得。其中H為上Hessenberg矩陣。特別地，當(dāng)A為實(shí)對稱矩陣，則經(jīng)過上述正交變換后，H變?yōu)槿龑顷?。用Householder方法對矩陣A作正交相似變換，使A相似于上Hessenberg陣，算法如下：（1） 計(jì)算（2） 計(jì)算（3） 計(jì)算四、上Hessenberg陣的QR分解對上Hessenberg陣只需要將其次對角線上的元素約化為零，用Given變換比用Householder變換更節(jié)省計(jì)算量。1、 平面旋轉(zhuǎn)陣（Givens變換陣）定義 n階方陣 稱為平面旋轉(zhuǎn)陣，或稱為Givens變換陣。平面旋轉(zhuǎn)陣的性質(zhì)：（1） 平面旋轉(zhuǎn)陣是非對稱的正交陣。（2） 也是平面旋轉(zhuǎn)陣。（3）平面旋轉(zhuǎn)陣的作用：（1） 將向量的第j個(gè)分量約化為零。左乘向量只改變X的第i個(gè)分量和第j個(gè)分量。若令，有調(diào)整，可將約化為零。令，得所以，取，于是（2） 將向量的第個(gè)分量到第n個(gè)分量約化為零。（3） 用對矩陣A作變換得到的結(jié)論左乘A只改變A的第i，j行。右乘A只改變A的第i，j列。只改變A的第i，j行和第i，j列。2、用Givens變換對上Hessenberg陣作QR分解對上Hessenberg陣通常用n-1個(gè)Givens變換陣可將它化成上三角矩陣，從而得到B的QR分解式。具體步驟為： 設(shè)（否則進(jìn)行下一步）取旋轉(zhuǎn)矩陣則其中，設(shè)（否則進(jìn)行下一步），再取旋轉(zhuǎn)矩陣則其中。假設(shè)上述過程已進(jìn)行了k-1步，有設(shè)，取其中，于是因此，最多做n-1次旋轉(zhuǎn)變換，即得因?yàn)榫鶠檎痪仃?，故其中仍為正交矩陣?？伤愠鐾瓿蛇@一過程的運(yùn)算量約為4,比一般矩陣的QR分解的運(yùn)算量少一個(gè)數(shù)量級。可證明仍是上Hessenberg陣，于是可按上述步驟一直迭代下去，這樣的得到的QR方法的運(yùn)算量比基本QR方法大為減少。具體實(shí)例現(xiàn)在我們就用上述所說的QR方法求解矩陣的全部特征值。第一步：將A化成上Hessenberg陣，取于是H即為與A相似的上Hessenberg陣。將H進(jìn)行QR分解，記取于是再取于是 第一次迭代得重復(fù)上述過程，迭代11次得 從得出的結(jié)果我們可以看出其結(jié)果還是很接近精確值的，其實(shí)我們完全可用Matlab實(shí)現(xiàn)上述計(jì)算。用海森伯格QR基本算法求矩陣全部特征值Matlab得到運(yùn)算結(jié)果為：源程序如下：function l = hessqrtz(A,M)%海森伯格QR基本算法求矩陣全部特征值%已知矩陣:A%迭代步數(shù):M%求得的矩陣特征值:lA=5 -3 2;6 -4 4;4 -4 5;M=11;A = hess(A);for(i=1:M) q,r=qr(A); A = r*q; l = diag(A);End而用QR基本算法求矩陣全部特征值的運(yùn)行結(jié)果如下：其Matlab源程序如下：function l = qrtz(A,M)%QR基本算法求矩陣全部特征值%已知矩陣:A%迭代步數(shù):M%求得的矩陣特征值:lA=5 -3 2;6 -4 4;4 -4 5;M=11;for(i=1:M) %M為迭代步數(shù) q,r=qr(A); A = r*q; l = diag(A);end 由以上兩種運(yùn)算結(jié)果的對比可以看