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

《特征值和特征向量的數(shù)值算法.ppt》由會員分享，可在線閱讀，更多相關《特征值和特征向量的數(shù)值算法.ppt（24頁珍藏版）》請在裝配圖網(wǎng)上搜索。

7.4QR算法,,,7.4.3帶原點位移的QR算法,7.4.2QR算法及其收斂性,7.4.1化矩陣為Hessenberg形,7.4.1化矩陣為Hessenberg形,定理7.9（實Schur分解定理）,為（初等）鏡面反射矩陣，或Householder變換矩陣。,Houholder矩陣H=H（w）有如下性質(zhì)：,,(1),(2),(3)記S為與w垂直的平面,則幾何上x與y=Hx關于平面S對稱。事實上,由,對應于性質(zhì)（2），有下面的定理。,證,由此可得,定理得證。,（7.4.2）,（7.4.3）,例7.4,解,證,變換，有,如此類推，經(jīng)n-2步對稱正交相似變換，得到Hessenberg形矩陣。,7.4.2QR算法及其收斂性,上式左邊為正交陣，即,這個式子左邊是下三角陣，則右邊是上三角陣，所以只能是對角陣。設,定理得證。,一般按平面旋轉(zhuǎn)變換或鏡面反射變換作出的分解A=QR，R的對角元不,（7.4.5）,證容易證(1)從它遞推得,例7.5用QR方法求下列矩陣的全部特征值。,該矩陣A非對稱，從計算結果看，收斂于上三角陣。,（2）的計算結果為,從計算結果來看，迭代收斂于Schur分塊上三角形，對角塊分別是1階和2階子,一般在實際使用QR方法之前，先用鏡面反射變換將A化為Hessenberg形矩陣H，然后對H作QR迭代，這樣可以大大節(jié)省運算工作量。因為上Hessenberg陣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)。可以驗證是一個下Hessenberg陣，即U是一個上Hessenberg陣。這樣，得到H的QR分解H=UR。在作QR迭代時，下一步計算RU，容易驗證RU是一個上Hessenberg陣。以上說明了QR算法保持了H的上Hessenberg結構形式。,,,解,重復上面的過程，計算11次得,至此，不難看出，一個特征值是4，另一個特征值是-1，其他兩個特征值是方程,上述用QR方法求得的特征值是該特征方程的準確解。,7.4.3帶原點位移的QR算法前面我們介紹了在反冪法中應用原點位移的策略，這種思想方法也可用于QR算法。一般我們針對上Hessenberg矩陣討論QR算法，并且假設每次QR迭代中產(chǎn)生的都是不可約的，否則，可以將問題分解為較小型的問題。這樣，帶原點位移的QR算法可以描述為：,根據(jù)QR算法的收斂性質(zhì)，位移量有下列兩種取法：,例7.7用帶原點位移的QR算法求下列矩陣的特征值：,解先用鏡面反射變換把A化為上Hessenberg矩陣。按（7.4.3）式有,該問題如果不用帶原點位移的QR算法，而是用基本QR算法，則收斂速度很慢，計算結果為,,