第八章特征值問題的計(jì)算方法

第八章特征值問題的計(jì)算方法

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

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

andReversed

PowerMethod*/冪法是計(jì)算一個(gè)矩陣的模最大的特征值和對(duì)應(yīng)的特征向量的一種迭代方法（又稱為乘冪法）。一、冪法的基本思想與算法假設(shè)是可對(duì)角化的，即存在如下分解：其中不妨假設(shè)對(duì)于第八章特征值問題的計(jì)算方法說明：當(dāng)k充分大時(shí),的一個(gè)近似特征向量為特征向量可以相差一個(gè)倍數(shù)第八章特征值問題的計(jì)算方法因?yàn)橄蛄恐泻形粗浚瑢?shí)際不能計(jì)算但我們關(guān)心的僅是的方向，故作如下處理：令其中為的模最大分量第八章特征值問題的計(jì)算方法

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

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

是屬于的一個(gè)特征向量第八章特征值問題的計(jì)算方法幾點(diǎn)說明：

定理8.2.1條件不滿足時(shí)，冪法產(chǎn)生的向量序列可能有若干個(gè)收斂于不同向量的子序列；

冪法的收斂速度取決于的大小；加速方法：適當(dāng)選取，對(duì)應(yīng)用冪法稱之為原點(diǎn)平移法原點(diǎn)平移法不改變矩陣的特征向量第八章特征值問題的計(jì)算方法

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

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

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

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

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

經(jīng)典Jacobi方法設(shè)令非對(duì)角“范數(shù)”當(dāng)時(shí)，趨于一個(gè)對(duì)角陣先來研究一下矩陣的元素和矩陣的元素之間的關(guān)系。Givens變換記為，下面通過Givens變換對(duì)矩陣進(jìn)行約化，使得第八章特征值問題的計(jì)算方法例如取記第八章特征值問題的計(jì)算方法選取適當(dāng)?shù)模蒅ivens變換將矩陣的下三角元素盡可能多的化為零：即非對(duì)角“范數(shù)”盡可能的小。如果，則取否則，令

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

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

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

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

方法

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

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

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

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

矩陣，然后再對(duì)進(jìn)行迭代。

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

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

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

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

此時(shí)的QR分解可采用Givens變換來實(shí)現(xiàn)；

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

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

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

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