第八章 特征值問題的計算方法

第八章特征值問題的計算方法

第八章特征值問題的計算方法

/*ComputationalMethodofEigenvalueProblem*/本章主要介紹矩陣的特征值和特征向量的計算方法。

特征值和特征向量的基本概念與性質§1基本概念與性質設，若存在向量和復數滿足，則稱是矩陣的特征值，是特征值相應的特征向量。特征多項式的根的集合：譜集第八章特征值問題的計算方法其中稱為的代數重數（簡稱重數）；為的幾何重數。設，對于矩陣的特征值，如果，則稱該特征值為的一個半單特征值。若的所有特征值都是半單的，則稱是非虧損的。是非虧損的等價條件是有n個線性無關的特征向量第八章特征值問題的計算方法設，若存在矩陣，使得則稱和是相似的。相似矩陣有相同的特征值設尋求已知矩陣的相似矩陣，要求：矩陣的特征值和特征向量容易計算本章QR算法的基本思想：第八章特征值問題的計算方法設，有r個互不相同的特征值，其重數分別為，則一定存在非奇異矩陣使得（Jordan分解）其中且除了的排列次序外，是唯一的。稱作的Jordan標準型第八章特征值問題的計算方法設，則存在酉矩陣，使得：（Schur分解）其中是上三角矩陣，且適當選擇，可使的元素按任意指定的順序排列。設，令（圓盤定理）/*DiscTheorem*/則第八章特征值問題的計算方法設為對稱矩陣，則存在正交矩陣（譜分解定理）/*SpectralDecomposition*/其中是的n個特征值。使得設為對稱矩陣，且的特征值為（極大極小定理）其中表示中所有k維子空間的全體。則有第八章特征值問題的計算方法設為對稱矩陣，其特征值分別為（Weyl定理）則有說明：對稱矩陣的特征值總是良態(tài)的。注意：實際問題中矩陣一般都是由計算或實驗得到，本身必然存在誤差，不妨假設第八章特征值問題的計算方法§2冪法與反冪法/*PowerMethod

andReversed

PowerMethod*/冪法是計算一個矩陣的模最大的特征值和對應的特征向量的一種迭代方法（又稱為乘冪法）。一、冪法的基本思想與算法假設是可對角化的，即存在如下分解：其中不妨假設對于第八章特征值問題的計算方法說明：當k充分大時,的一個近似特征向量為特征向量可以相差一個倍數第八章特征值問題的計算方法因為向量中含有未知量，實際不能計算但我們關心的僅是的方向，故作如下處理：令其中為的模最大分量第八章特征值問題的計算方法

冪法迭代算法：Fork=1,2,3,…if輸出和設和均收斂，由算法知冪法可以計算矩陣的模最大的特征值和對應的特征向量第八章特征值問題的計算方法解：Step1例1：利用冪法求下列矩陣的模最大的特征值及相應的特征向量.(取初始向量為)Step2第八章特征值問題的計算方法Step3Step4特征值及相應的特征向量精確值為:第八章特征值問題的計算方法

冪法的收斂性：設有p個互不相同的特征值滿足：且模最大特征值是半單的，如果初始向量在的特征子空間上的投影不為零，則由冪法算法產生的向量序列收斂到的一個特征向量，且數值序列收斂到。特征子空間：第八章特征值問題的計算方法證明：設有如下Jordan分解：是屬于的Jordan塊構成的塊上三角矩陣是半單的特征值令將和如下分塊：第八章特征值問題的計算方法第八章特征值問題的計算方法記

是屬于的一個特征向量第八章特征值問題的計算方法幾點說明：

定理8.2.1條件不滿足時，冪法產生的向量序列可能有若干個收斂于不同向量的子序列；

冪法的收斂速度取決于的大??；加速方法：適當選取，對應用冪法稱之為原點平移法原點平移法不改變矩陣的特征向量第八章特征值問題的計算方法

冪法可以計算第二個模最大特征值常用的方法：降階方法（收縮技巧）設已經計算出模最大特征值及其特征向量對向量，采用復的Household變換計算酉矩陣其中是n-1階方陣為的模最大特征值第八章特征值問題的計算方法二、反冪法的基本思想與算法反冪法是求一個矩陣的模最小的特征值和對應的特征向量的一種迭代方法（又稱為反迭代法）。設，則對應用冪法就可以求得矩陣的模最小的特征值和相應的特征向量。不妨假設的特征值為則的特征值為第八章特征值問題的計算方法

反冪法算法：Fork=1,2,3,…if輸出和若和均收斂，由冪法知收斂速度取決于的大小反冪法每次迭代都需要求解方程組第八章特征值問題的計算方法

帶位移的反冪法：實際應用中，反冪法主要用于求特征向量。且用某種方法已經得到的特征值的近似值對矩陣采用反冪法迭代格式為：記假設的特征值滿足Fork=1,2,3,…因為方程組的系數矩陣Doolittle分解化為兩個三角方是固定的，通常采用(選主元)程組求解，從而減少工作量。第八章特征值問題的計算方法求解方程組化為：帶位移的反冪法迭代格式：

Fork=1,2,3,…收斂速度取決于的大小當時，收斂速度會非?？煸O矩陣存在Doolittle分解：第八章特征值問題的計算方法解：例2：用帶位移的反冪法求矩陣）的近似特征向量。對應特征值（精確值為其中Step1第八章特征值問題的計算方法反冪法具有一次“迭代性”Step2所求近似特征向量為：第八章特征值問題的計算方法§3Jacobi方法Jacobi法：計算實對稱矩陣全部特征值和相應特征向量

基本思想對存在正交矩陣，滿足記則尋找正交相似變換，將矩陣約化為對角陣即可正交相似變換求法：通過Givens變換來實現第八章特征值問題的計算方法

經典Jacobi方法設令非對角“范數”當時，趨于一個對角陣先來研究一下矩陣的元素和矩陣的元素之間的關系。Givens變換記為，下面通過Givens變換對矩陣進行約化，使得第八章特征值問題的計算方法例如取記第八章特征值問題的計算方法選取適當的，由Givens變換將矩陣的下三角元素盡可能多的化為零：即非對角“范數”盡可能的小。如果，則取否則，令

首先由確定第八章特征值問題的計算方法

其次確定旋轉平面由F-范數的正交不變性設經過一次正交相似變換后變?yōu)榫仃嚨诎苏绿卣髦祮栴}的計算方法注意到旋轉平面的選取方法：經典Jacobi方法的迭代格式：對于經典Jacobi方法產生的矩陣序列，存在的特征值的一個排列滿足證明見教材第八章特征值問題的計算方法

經典Jacobi方法的迭代算法給定矩陣選取最佳旋轉平面：Fork=1,2,3,…計算計算直到需比較個元素第八章特征值問題的計算方法習慣上稱次Jacobi迭代為一次“掃描”

循環(huán)Jacobi方法每一次Jacobi迭代不是去選擇最佳旋轉平面，而是直接按照某種預先指定的順序來“掃描”自然順序：按照自然順序的循環(huán)Jacobi方法是漸進平方收斂的第八章特征值問題的計算方法§4QR

方法

基本思想利用正交相似變換將一個給定的矩陣逐步約化為上三角矩陣或擬上三角矩陣的一種迭代方法

QR方法的迭代格式設令對矩陣進行QR分解再對矩陣進行QR分解一、QR基本迭代方法QR方法是目前計算矩陣全部特征值的最有效的方法之一；具有收斂快、算法穩(wěn)定等特點。第八章特征值問題的計算方法一般地有：矩陣序列中每一個矩陣都與原矩陣相似QR方法的迭代算法：Form=1,2,3,…直到近似為上三角陣由迭代格式同時還得到：記代入第八章特征值問題的計算方法等式兩端同時右乘記即其中是的第一列，是的相應元素可以看作是對矩陣用為初始向量的冪法所得到的向量。QR方法與冪法的關系：第八章特征值問題的計算方法

QR方法的收斂性設的特征值滿足，且的則由QR迭代算法產生的矩陣的對角線以第i行是對應于的左特征向量；若有分解，下的元素趨于0，同時對角元素趨于（QR方法的收斂性質）證明：令則有其中第八章特征值問題的計算方法且當m充分大時，存在唯一QR分解：且當m充分大時（QR分解）記的QR分解為：第八章特征值問題的計算方法為保證上述QR分解中上三角矩陣的對角元為正，令由QR分解唯一性知：代入趨于上三角陣第八章特征值問題的計算方法實際應用中遇到的多數特征值問題都是關于實矩陣的，所以自然希望設計只涉及實數運算的QR迭代。

實QR迭代格式設二、實Schur標準形Fork=1,2,3,…為正交矩陣為上三角陣（實Schur分解）設，則存在正交矩陣，滿足：其中為實數或具有一對復共軛特征值的2階方陣第八章特征值問題的計算方法特征值為，其中為虛單位見文獻[13]矩陣稱為的Schur標準形定理8.4.2說明：只要求得矩陣的Schur標準形，就很容易求得矩陣的全部特征值。缺陷：很難得到第八章特征值問題的計算方法稱下述形狀的矩陣為上Hessenberg矩陣三、上Hessenberg化第八章特征值問題的計算方法設，尋求非奇異矩陣，使得為上Hessenberg

矩陣，然后再對進行迭代。

基本思想和約化過程：記矩陣下面采用Householde變換尋找Step1

選取Householde變換，使得其中令第八章特征值問題的計算方法其中Step2

選取Householde變換，使得下面對作同樣的處理，以此類推其中令第八章特征值問題的計算方法令其中記為正交陣第八章特征值問題的計算方法按照前述方法，經過n-2步后，可以得到：其中第八章特征值問題的計算方法記，則稱分解式為矩陣的上Hessenberg分解

上Hessenberg分解算法（8.4.1）Fork=1:n-2然后對上Hessenberg矩陣進行QR迭代設第八章特征值問題的計算方法上Hessenberg矩陣的QR迭代算法：Form=1,2,3,…直到的次對角元素趨于零注意：

此時的QR分解可采用Givens變換來實現；

用Givens變換得到的RQ仍然為上Hessenberg矩陣；

上Hessenberg分解不唯一。若上Hessenberg矩陣的次對角元素均不為零，則稱之為不可約的上Hessenberg矩陣。定理8.4.3說明：在不可約的條件下，上Hessenberg分解在相差一個正負號的意義下唯一。見文獻[6]第八章特征值問題的計算方法

實用的QR迭代算法（僅計算特征值）Step1由算法8.4.1計算上Hessenberg矩陣：Step2（QR分解）Fork=1:n-1Step3（計算RQ）Step4

重復步驟Step2–3，直到下次對角元素趨于零第八章特征值問題的計算方法四、三對角化（對稱矩陣的上Hessenberg化）