第六章 非對(duì)稱特征值問題的計(jì)算方法(共11頁)

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

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

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

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

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

6、思想，我們先假定是可對(duì)角化(jio hu)的，即有如下分解 （.）其中非奇異，再假定 (6.2.2)現(xiàn)任取一向量由于的列向量構(gòu)成的一組基，故可表示為 (6.2.3)這里這樣，我們有 （6.2.4）由此即知這表明，當(dāng)而且充分大時(shí)，向量 （6.2.5）就是(jish)的一個(gè)(y )很好的近似特征向量這樣，我們(w men)自然想到用(6.2.5)來求的近似特征向量然而，實(shí)際計(jì)算時(shí)，這是行不通的其原因有二：一是我們事先并不知道的特征值；二是對(duì)充分大的計(jì)算的工作量太大，有可能造成溢出仔細(xì)觀察（6.2.5），不難發(fā)現(xiàn)(6.2.5)中的僅改變向量的長度，并不影響它的方向而我們所感興趣的只是的方向，并非它的

7、長度因此，我們不必非用來約化的長度，而可用其他方便的常數(shù)來進(jìn)行約化（為了防止溢出，約化是必要的）；其次計(jì)算也并不需要事先將算好之后再計(jì)算，只需迭代地進(jìn)行即可基于這樣的考慮，我們可設(shè)計(jì)如下的迭代格式：算法6.2.1（冪法：計(jì)算矩陣的模最大的特征向量）預(yù)始步取任意非零向量，且算法終止常數(shù)，置；主步（）計(jì)算；（）求；（）計(jì)算（）如果，則輸出近似特征向量和近似特征值終止算法；否則，置，返回（）注：算法(sun f)中：，其中(qzhng)定理(dngl).設(shè)有個(gè)互不相等的特征值滿足并且是半單的（即的幾何重?cái)?shù)等于它的代數(shù)重?cái)?shù)）如果初始向量在的特征子空間上的投影不為零，則由算法6.2.1產(chǎn)生的向量序列收斂

8、到的一個(gè)特征向量，而且由算法.2.1產(chǎn)生的數(shù)值序列收斂到證明略當(dāng)定理6.2.1的條件不滿足時(shí)，由冪法6.2.1產(chǎn)生的序列的收斂性分析將變得非常復(fù)雜，這時(shí)可能有若干個(gè)收斂于不同向量的子序列（參見本章習(xí)題）例如，假定，其中此時(shí)有兩個(gè)模最大的特征值因此定理?xiàng)l件不滿足，取初始向量為，通過簡(jiǎn)單的計(jì)算知由此即知，由冪法產(chǎn)生的向量序列有兩個(gè)收斂子列，分別收斂于向量注意(zh y)此時(shí)分別(fnbi)是屬于和的特征向量事實(shí)上，適當(dāng)(shdng)修改算法6.2.1可使冪法對(duì)于此例所述的情況下亦是收斂的請(qǐng)讀者作為練習(xí)修改算法6.2.1使其適用于而的情形此外，從算法.2.1的基本思想亦可看出，冪法的收斂速度主要取決

9、于的大小在定理6.2.1的條件下，這個(gè)數(shù)總是小于的它越小收斂就越快，當(dāng)它接近于時(shí)，收斂是很慢的為了加快算法的收斂速度，通?？刹捎梦灰频姆椒?，即應(yīng)用冪法于上，如果適當(dāng)選取可使的模最大的特征值與其他特征值的模的距離更大，就起到加速的目的例如若在上例中取，即若對(duì)上面給出的矩陣應(yīng)用冪法于，則此時(shí)產(chǎn)生的向量序列將收斂到之屬于的一個(gè)特征向量用冪法可以求矩陣的一個(gè)模最大的特征值及其對(duì)應(yīng)的一個(gè)特征向量假如我們還要求第二個(gè)模最大的特征值，直接用算法6.2.1進(jìn)行迭代是不行的，必須先對(duì)原矩陣降階才行降階就是在知道了的前提下，把矩陣降低一階，使它只包含的其余特征值用來完成這一過程的方法通常稱作收縮技巧，最簡(jiǎn)單實(shí)用的

10、收縮技巧是利用正交變換假設(shè) （6.2.9）現(xiàn)假設(shè)酉矩陣使 (6.2.10)這里，則將(6.2.10)代入（6.2.9）并整理可得，這表明(biomng)的首列為，即其中(qzhng)是階方陣(fn zhn)并且它的特征值是因此，要求只要把冪法應(yīng)用于即可而變換(6.2.10)可用復(fù)的Householder變換來實(shí)現(xiàn)作為本節(jié)的結(jié)束，我們希望指出的是，由于冪法的計(jì)算公式依賴于矩陣特征值的分布情況，因此實(shí)際使用時(shí)很不方便，特別是不適用于自動(dòng)計(jì)算，只是在矩陣階數(shù)非常高，無法利用其他更有效的算法時(shí)，才用冪法計(jì)算少數(shù)幾個(gè)模最大的特征值和相應(yīng)的特征向量然而，冪法的基本思想是重要的，由它可以誘導(dǎo)出一些更有效的算

11、法6.3 反冪法設(shè)是非奇異矩陣，可以對(duì)作冪法迭代，求出的特征值?，F(xiàn)設(shè)的特征值滿足，則的特征值滿足，即為按模最大的特征值，將冪法計(jì)算6.2.1用于，具體計(jì)算時(shí)，可不求逆矩陣，而用解方程組的方法，即反冪法迭代計(jì)算過程為 (6.3.1)與冪法相同(xin tn)的分析，有 (6.3.2)其中(qzhng)是對(duì)應(yīng)(duyng)的特征向量反冪法的收斂速度取決于假設(shè)的特征值為，對(duì)應(yīng)線性無關(guān)的特征向量為，設(shè)，則矩陣的特征值為對(duì)應(yīng)的特征向量為如果選擇接近某一特征值，滿足 (6.3.3)則對(duì)矩陣的反冪法迭代為 (6.3.4)注：算法中：，其中必有而且(r qi)，只要選擇(xunz)得能很好地滿足(6.3.3)，則收斂(shulin)速度可以很快一般(6.3.4)第一式的方程組用矩陣的選列主元的分解方法來求解可以證明，雖然越接近，越接