特征值和特征向量的數(shù)值算法.ppt

《特征值和特征向量的數(shù)值算法.ppt》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、7.4QR算法7.4.3帶原點(diǎn)位移的QR算法7.4.2QR算法及其收斂性7.4.1化矩陣為Hessenberg形我們稱這種分塊上三交陣為矩陣A的Schur分塊上三角陣，上三角陣和對角陣是它的特殊情形。定理7.9并沒有解決如何計(jì)算全部特征的問題。7.4.1化矩陣為Hessenberg形對于實(shí)對稱矩陣，可通過正交相似變換約化為對角矩陣。那么，對于一般的實(shí)矩陣，通過正交相似變換可約化到什么程度呢？線性代數(shù)中有如下結(jié)果。定理7.9（實(shí)Schur分解定理）定義7.2(i>j+1),則稱B為上Hessenberg矩陣，簡稱Hessenberg形，即B的形狀為可

2、以用平面旋轉(zhuǎn)變換化矩陣為Hessenberg形,下面介紹另一種正交變換。為了節(jié)省運(yùn)算工作量，實(shí)用的方法是先將矩陣約化為與Schur分塊上三角陣很近似的Hessenberg形。定義7.3（7.4.1）為（初等）鏡面反射矩陣，或Householder變換矩陣。Houholder矩陣H=H（w）有如下性質(zhì)：(1)(2)(3)記S為與w垂直的平面,則幾何上x與y=Hx關(guān)于平面S對稱。事實(shí)上,由上式表明向量x-y與w平行，注意到y(tǒng)與x的長度相等，于是x經(jīng)變換后的象y=Hx是x關(guān)于s對稱的向量，如圖7-1所示。xwyx-y圖7-1對應(yīng)于性質(zhì)（2），有下面的定理

3、。定理7.10得Hx=y。證由此可得定理得證。（7.4.2）（7.4.3）穩(wěn)定性。（7.4.2）的意義是對向量作消元運(yùn)算。與平面旋轉(zhuǎn)不同的是，鏡面反射變換可成批的消去向量的非零元。例7.4解（7.4.4）定理7.11為Hessenberg形。證變換，有如此類推，經(jīng)n-2步對稱正交相似變換，得到Hessenberg形矩陣。推論7.1對稱三對角陣。上述定理7.11的證明是構(gòu)造的，即可以用鏡面反射化矩陣Hessenberg形。此定理可用平面旋轉(zhuǎn)變換來證明，即也可用平面旋轉(zhuǎn)變換化矩陣為Hessenberg如此類推，最后得到的正交矩陣Q，是平面旋轉(zhuǎn)矩陣的乘積

4、。7.4.2QR算法及其收斂性QR算法可以用來求任意的非奇異矩陣的全部特征值，是目前計(jì)算這類問題最有效的方法之一。它基于對任何實(shí)的非奇異矩陣都可以分解為正交陣Q和上三角矩陣R的乘積。定理7.2(QR分定理)上三角陣R,使得A=QR,且當(dāng)R的對角元素均取正時,分解是唯一的。證類似于定理7.11的證明，對矩陣A的左乘一系列正交變換矩陣，可以將A化為上三角形矩陣，因此，可得A的QR分解。下面證明分解的唯一性。設(shè)有兩種分解上式左邊為正交陣，即這個式子左邊是下三角陣，則右邊是上三角陣，所以只能是對角陣。設(shè)定理得證。一般按平面旋轉(zhuǎn)變換或鏡面反射變換作出的分解A

5、=QR，R的對角元不定理7.12的唯一QR分解。如下的算法：（7.4.5）或稱為基本QR算法。QR算法，證容易證(1)從它遞推得定理7.13QR算法產(chǎn)生的序列滿足:（1）（2）一般情形下，QR算法的收斂性比較復(fù)雜。若矩陣序列對角元均收斂，且嚴(yán)格下三角部分元素均收斂到零，則對求A的特征值而言已經(jīng)足夠了。此時，我們稱基本收斂到上三角陣。下面對最簡單的情性給出收斂性定理。設(shè)矩陣的特征值滿足定理7.14=LU，其中L為單位下三角陣U為上三角陣，則QR算法產(chǎn)生的序列基本收斂到上三角陣，其對角極限為更一般地，在一定條件下，由QR算法生成的序列收斂為Schur分

6、塊上三角形，對角塊按特征值的模從大到小排列，上述定理是它的特殊情形。當(dāng)收斂結(jié)果為Schur分塊上三角形時，序列的對角塊以上的元素以及2階塊的元素不一定收斂，但不影響求全部特征值。例7.5用QR方法求下列矩陣的全部特征值。解先用鏡面反射變換化矩陣A為Hessenberg形矩陣，然后用平面旋轉(zhuǎn)變換作QR分解進(jìn)行迭代，生成序列。（1）的計(jì)算結(jié)果為該矩陣A非對稱，從計(jì)算結(jié)果看，收斂于上三角陣。（2）的計(jì)算結(jié)果為從計(jì)算結(jié)果來看，迭代收斂于Schur分塊上三角形，對角塊分別是1階和2階子一般在實(shí)際使用QR方法之前，先用鏡面反射變換將A化為Hessenberg形

7、矩陣H，然后對H作QR迭代，這樣可以大大節(jié)省運(yùn)算工作量。因?yàn)樯螲essenberg陣H的次對角線以下元素均為零，所以用平面旋轉(zhuǎn)變換作QR分解較為方便。對i=1,2,….n-1,依次用平面旋轉(zhuǎn)矩陣J（i,i+1）左乘H，使J（i,i+1）H的第i+1行第i列元素為零。左乘J(i,i+1)后，矩陣H的第i行與第i+1行零元素位置上仍為零，其他行不變。這樣，共n-1次左乘正交矩陣后得到上三角陣R。即=R，=J（n-1,n）J(n-2,n-1)…J(1,2)?？梢则?yàn)證是一個下Hessenberg陣，即U是一個上Hessenberg陣。這樣，得到H的QR分解

8、H=UR。在作QR迭代時，下一步計(jì)算RU，容易驗(yàn)證RU是一個上Hessenberg陣。以上說明了QR算法保持了H的上Hes