第六章 非對稱特征值問題的計算方法

1、第六章 非對稱特征值問題的計算方法這一章我們來介紹矩陣特征值和特征向量的計算方法。大家知道，求一個矩陣的特征值問題實質(zhì)上是求一個多項式的根的問題。而數(shù)學上已經(jīng)證明：5階以上的多項式的根一般不能用有限次運算求得。因此，矩陣特征值的計算方法本質(zhì)上都是迭代的。目前，已有不少非常成熟的數(shù)值方法用于計算矩陣的全部或部分特征值和特征向量。而全面系統(tǒng)地介紹所有這些重要的數(shù)值方法，會遠遠超出我們這門課程的范圍，因而這里我們僅介紹幾類最常用的基本方法。6·1 基本概念和性質(zhì)設(shè)，一個復(fù)數(shù)稱作是的一個特征值是指存在非零向量使得復(fù)向量稱作是關(guān)于特征值的特征向量復(fù)數(shù)是的一個特征值的充分必要條件是，因而稱多項式

2、為的特征多項式顯然階矩陣的特征多項式是一個首項系數(shù)為的次多項式，而且有個特征值記的特征值的全體為，通常稱之為的譜集假定有如下分解其中，則稱為的代數(shù)重數(shù)（簡稱重數(shù)）；而稱數(shù)為的幾何重數(shù)。易知如果，則稱是A的一個單特征值；否則，稱是A的一個重特征值。對于一個特征值，如果，則稱其是A的一個半單特征值。顯然，單特征值必是半單特征值。如果A的所有特征值都是半單的，則稱A是非虧損的。容易證明，A是非虧損的充分必要條件是A有個線性無關(guān)的特征向量（即A是可對角化矩陣）。設(shè)若存在非奇異陣使得則稱與是相似的，而上述變換稱作是相似變換若與相似，則和有相同的特征值，而且是的一特征向量的充分必要條件是是的一個特征向量這

3、樣，如果我們能夠找到一個適當?shù)淖儞Q矩陣，使的特征值和特征向量易于求得，則我們就可立即得到的特征值和相應(yīng)的特征向量很多計算矩陣特征值和特征向量的方法正是基于這一基本思想而得到的從理論上講，利用相似變換可以將一個矩陣約化成的最簡單形式是Jordan標準型，即有定理··（Jordan分解定理）設(shè)有個互不相同的特征值，其重數(shù)分別為，則必存在一個非奇異矩陣使得其中并且除了的排列次序可以改變外是唯一確定的。上述定理中的矩陣稱作A的Jordan標準型，其中每個子矩陣稱作Jordan塊。如果限定變換陣為酉矩陣，則有如下著名的Schur分解定理。定理6·1·2（Schur

4、分解定理） 設(shè)，則存在酉矩陣使得其中是上三解矩陣；而且適當選取，可使得的對角元素按任意指定的順序排列。這一定理無論在理論上還是在實際應(yīng)用上都是非常重要的，著名的QR方法就是基于這一定理而設(shè)計的。下述定理對于估計某些特征值的界限是十分方便而有用的。定理6·1·3（Gerschgorin圓盤定理）設(shè)，令則有從數(shù)值計算的角度來看，首先應(yīng)弄清楚的問題是要計算的特征值和特征向量是否是病態(tài)的，也就是說矩陣的元素有微小的變化，是否會引起所關(guān)心的特征值和特征向量的巨大變化。對于一般的方陣來說，這一問題是非常復(fù)雜的，即于篇幅，這里我們只介紹一個簡單而又非常重要的結(jié)果。假定是的一個單特征值，是

5、屬于它的單位特征向量（即）。令是酉矩陣（），即的列向量構(gòu)成的一組標準正交基，則有其中階方陣。由是的一個單特征值的假定，知且于是我們可定義此外，由于，故必存在非零向量使。通常稱為這屬于的左特征值。是單特征值的條件蘊含著故可選取使若給矩陣以微小的擾動使其變?yōu)?，記，則存在的一個特征值和對應(yīng)的特征向量，使得這表明和的敏感性分別與和的大小有關(guān)因此，我們分別稱和為特征值和特征向量的條件數(shù)，記作有關(guān)特征值和特征向量的敏感性問題的較詳細討論參見·冪法冪法是計算一個矩陣的模最大特征值和對應(yīng)的特征向量的一種迭代方法為了說明冪法的基本思想，我們先假定是可對角化的，即有如下分解  

6、60;                                （.）其中非奇異，再假定                &#

7、160;                  (6.2.2)現(xiàn)任取一向量由于的列向量構(gòu)成的一組基，故可表示為                           (6.2.

8、3)這里這樣，我們有                     （6.2.4）由此即知這表明，當而且充分大時，向量                        

9、           （6.2.5）就是的一個很好的近似特征向量這樣，我們自然想到用(6.2.5)來求的近似特征向量然而，實際計算時，這是行不通的其原因有二：一是我們事先并不知道的特征值；二是對充分大的計算的工作量太大，有可能造成溢出仔細觀察（6.2.5），不難發(fā)現(xiàn)(6.2.5)中的僅改變向量的長度，并不影響它的方向而我們所感興趣的只是的方向，并非它的長度因此，我們不必非用來約化的長度，而可用其他方便的常數(shù)來進行約化（為了防止溢出，約化是必要的）；其次計算也并不需要事先將算好之后再計算，只需迭代

10、地進行即可基于這樣的考慮，我們可設(shè)計如下的迭代格式：算法6.2.1（冪法：計算矩陣的模最大的特征向量）預(yù)始步取任意非零向量，且算法終止常數(shù)，置；主步（）計算；（）求；（）計算（）如果，則輸出近似特征向量和近似特征值終止算法；否則，置，返回（）注：算法中：，其中定理.設(shè)有個互不相等的特征值滿足并且是半單的（即的幾何重數(shù)等于它的代數(shù)重數(shù)）如果初始向量在的特征子空間上的投影不為零，則由算法6.2.1產(chǎn)生的向量序列收斂到的一個特征向量，而且由算法.2.1產(chǎn)生的數(shù)值序列收斂到證明略當定理6.2.1的條件不滿足時，由冪法6.2.1產(chǎn)生的序列的收斂性分析將變得非常復(fù)雜，這時可能有若干個收斂于不同向量的子序列

11、（參見本章習題）例如，假定，其中此時有兩個模最大的特征值因此定理條件不滿足，取初始向量為，通過簡單的計算知由此即知，由冪法產(chǎn)生的向量序列有兩個收斂子列，分別收斂于向量注意此時分別是屬于和的特征向量事實上，適當修改算法6.2.1可使冪法對于此例所述的情況下亦是收斂的請讀者作為練習修改算法6.2.1使其適用于而的情形此外，從算法.2.1的基本思想亦可看出，冪法的收斂速度主要取決于的大小在定理6.2.1的條件下，這個數(shù)總是小于的它越小收斂就越快，當它接近于時，收斂是很慢的為了加快算法的收斂速度，通常可采用位移的方法，即應(yīng)用冪法于上，如果適當選取可使的模最大的特征值與其他特征值的模的距離更大，就起到加

12、速的目的例如若在上例中取，即若對上面給出的矩陣應(yīng)用冪法于，則此時產(chǎn)生的向量序列將收斂到之屬于的一個特征向量用冪法可以求矩陣的一個模最大的特征值及其對應(yīng)的一個特征向量假如我們還要求第二個模最大的特征值，直接用算法6.2.1進行迭代是不行的，必須先對原矩陣降階才行降階就是在知道了的前提下，把矩陣降低一階，使它只包含的其余特征值用來完成這一過程的方法通常稱作收縮技巧，最簡單實用的收縮技巧是利用正交變換假設(shè)                

13、60;                         （6.2.9）現(xiàn)假設(shè)酉矩陣使                       

14、                     (6.2.10)這里，則將(6.2.10)代入（6.2.9）并整理可得，這表明的首列為，即其中是階方陣并且它的特征值是因此，要求只要把冪法應(yīng)用于即可而變換(6.2.10)可用復(fù)的Householder變換來實現(xiàn)作為本節(jié)的結(jié)束，我們希望指出的是，由于冪法的計算公式依賴于矩陣特征值的分布情況，因此實際使用時很不方便，特別是不適用于自動計算，只是在矩陣階數(shù)非常高

15、，無法利用其他更有效的算法時，才用冪法計算少數(shù)幾個模最大的特征值和相應(yīng)的特征向量然而，冪法的基本思想是重要的，由它可以誘導(dǎo)出一些更有效的算法6.3 反冪法設(shè)是非奇異矩陣，可以對作冪法迭代，求出的特征值?，F(xiàn)設(shè)的特征值滿足，則的特征值滿足，即為按模最大的特征值，將冪法計算6.2.1用于，具體計算時，可不求逆矩陣，而用解方程組的方法，即反冪法迭代計算過程為                    

16、0;       (6.3.1)與冪法相同的分析，有                         (6.3.2)其中是對應(yīng)的特征向量反冪法的收斂速度取決于假設(shè)的特征值為，對應(yīng)線性無關(guān)的特征向量為，設(shè)，則矩陣的特征值為對應(yīng)的特征向量為如果選擇接近某一特征值，滿足   

17、                         (6.3.3)則對矩陣的反冪法迭代為                                   (6.3.4)注：算法中：，其中必有而且，只要選擇得能很好地滿足(6.3.3)，則收斂速度可以很快一般(6.3.4)第一式的方程組用矩陣的選列主元的分解方法來求解可以證明，雖然越接近，越接近奇異，但用以上的反冪法迭代能夠得到精確的結(jié)果所以它是目前求特征值和特征向量的有效方法之一稱為原點位移的反冪