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

1、 第八章第八章 特征值問題的計(jì)算方法特征值問題的計(jì)算方法 /*Computational Method of Eigenvalue Problem*/本章主要介紹矩陣的本章主要介紹矩陣的特征值特征值和和特征向量特征向量的計(jì)算方法。的計(jì)算方法。 特征值特征值和和特征向量特征向量的的基本概念與性質(zhì)基本概念與性質(zhì)1 基本概念與性質(zhì)基本概念與性質(zhì)1Def設(shè)設(shè) ，若存在向量，若存在向量 和復(fù)數(shù)和復(fù)數(shù) 滿足滿足n nAC nxC Axx ，則稱，則稱 是矩陣是矩陣 的的特征值特征值， 是特征值是特征值 x A 相應(yīng)的相應(yīng)的特征向量特征向量。0det()IA ( )det()ApIA 特征特征多項(xiàng)式多項(xiàng)式

2、的根的集合：的根的集合：譜集譜集( )A 1212det()() ()()pnnnpIA 其中其中12;()pijnnnnij 稱稱 為為 的的代數(shù)重?cái)?shù)代數(shù)重?cái)?shù)（簡稱（簡稱重?cái)?shù)重?cái)?shù)）；）；ini ()iimnrankIA 為為 的的幾何重?cái)?shù)幾何重?cái)?shù)。i iimn 2Def設(shè)設(shè) ，n nAC iimn 對于矩陣對于矩陣 的的特征值特征值 ，如果，如果Ai ，則稱該特征值，則稱該特征值 為為 的一個的一個半單半單特征值。特征值。Ai 若若 的所有特征值都是的所有特征值都是半單半單的，則稱的，則稱 是是非虧損非虧損的。的。AA是是非虧損非虧損的等價(jià)條件是的等價(jià)條件是 有有n個個線性無關(guān)線性無關(guān)的特征

3、向量的特征向量AA3Def設(shè)設(shè) ，,n nA BC 若存在矩陣若存在矩陣 ，使得，使得P1B P AP 則稱則稱 和和 是是相似相似的。的。AB相似相似矩陣有相同的特征值矩陣有相同的特征值1AxxPAP PxPx BPxPx Axx 設(shè)設(shè)尋求已知矩陣尋求已知矩陣 的的相似相似矩陣矩陣 ，要求：，要求：矩陣矩陣 的的特征值特征值和和特征向量特征向量容易計(jì)算容易計(jì)算ABB本章本章QR算法的算法的基本思想：基本思想：8 1 1. .Th1(, )iir 設(shè)設(shè) ，有，有 r個個互不相同互不相同的特征值的特征值 ，n nAC 其其重?cái)?shù)重?cái)?shù)分別為分別為 ，則一定存在，則一定存在非奇異非奇異矩陣矩陣11()

4、(),();iiinniikiJdiag JJCir 使得使得（Jordan分解）分解）1(, )in ir n nPC 其中其中112( (), (), ()rP APdiag JJJJ 11()iijiiJ ()jiJ 且除了且除了 的的排列排列次序次序外，外， 是是唯一唯一的。的。J稱作稱作 的的Jordan標(biāo)準(zhǔn)型標(biāo)準(zhǔn)型AJ8 1 2. .Th設(shè)設(shè) ，則存在，則存在酉酉矩陣矩陣 ，使得：，使得：n nAC （Schur分解）分解）其中其中 是是上三角上三角矩陣，且適當(dāng)選擇矩陣，且適當(dāng)選擇 ，可使，可使 的元素的元素HUAUT n nUC TUT按任意指定的順序排列。按任意指定的順序排列。

5、8 1 3. .Th設(shè)設(shè) ，令，令()n nijAaC （圓盤圓盤定理）定理）/*Disc Theorem*/則則1( ):;,iiiijj iG AzCzaain 12( )( )( )( )nAG AGAGA 8 1 4. .Th設(shè)設(shè) 為為對稱對稱矩陣，則存在矩陣，則存在正交正交矩陣矩陣n nAR （譜譜分解定理）分解定理）/*Spectral Decomposition*/其中其中 是是 的的n個特征值。個特征值。n nQR 使得使得1(,)TnQ AQdiag 1,nA8 1 5. .Th設(shè)設(shè) 為為對稱對稱矩陣，且矩陣，且 的特征值為的特征值為n nAR （極大極小極大極小定理）定理）

6、其中其中 表示表示 中所有中所有k維子空間的全體。維子空間的全體。則有則有12n A0maxminniTiTuu Auu u 10min maxnn iTTuu Auu u nk nR設(shè)設(shè) 為為對稱對稱矩陣，其特征值分別為矩陣，其特征值分別為8 1 6. .Th,n nA BR （Weyl定理）定理）則有則有1212;nn 21 2;, ,iiABin說明：說明：對稱對稱矩陣的特征值總是矩陣的特征值總是良態(tài)良態(tài)的。的。注意注意：實(shí)際問題中矩陣一般都是由：實(shí)際問題中矩陣一般都是由計(jì)算計(jì)算或或?qū)嶒?yàn)實(shí)驗(yàn)得到，得到，本身必然存在本身必然存在誤差誤差，不妨假設(shè)，不妨假設(shè) BAA 21 2;, ,iiAi

7、n 2 冪法與冪法與反冪法反冪法/*Power Method and Reversed Power Method*/冪法冪法是計(jì)算一個矩陣的是計(jì)算一個矩陣的模最大模最大的特征值和對應(yīng)的特征的特征值和對應(yīng)的特征 向量的一種向量的一種迭代迭代方法（又稱為方法（又稱為乘冪法乘冪法）。）。 一、一、冪法冪法的的基本思想與算法基本思想與算法假設(shè)假設(shè) 是可是可對角化對角化的，即的，即 存在如下分解：存在如下分解： n nAC A1AXX 其中其中1(,)ndiag 1;,n nnXxxC 不妨假設(shè)不妨假設(shè)12n 對于對于0nuC 01122;nniuxxxC011nnkkkjjjjjjjA uA xx 1

8、1121() )njkkjjjxx 011211() )knjkjjkjA uxx 11()x k 01kkkA uu 說明：當(dāng)說明：當(dāng)k充分大時充分大時, 的一個的一個近似特征向量近似特征向量為為1 特征向量可以相差一個特征向量可以相差一個倍數(shù)倍數(shù)01kkkA uu 因?yàn)橄蛄恳驗(yàn)橄蛄?中含有中含有未知量未知量 ，實(shí)際不能計(jì)算，實(shí)際不能計(jì)算1 ku但我們關(guān)心的僅是但我們關(guān)心的僅是 的的方向方向，故作如下處理：，故作如下處理：0kkkA uu 令令其中其中 為為 的的模最大分量模最大分量k 0kA u11121011121() )() )njkkjjkjnkjkkjjjxxA uxx 11()x

9、kx 冪法迭代冪法迭代算法算法：1kkkAuu 1limlimlimkkkkkkAuu 1Axx 1k For k=1,2,3,1kkyAu kky if1kkuu 輸出輸出 和和kuk kkkyu 001,uu 設(shè)設(shè) 和和 均均收斂收斂，由，由算法算法知知kuk 冪法冪法可以計(jì)算矩陣的可以計(jì)算矩陣的模最大模最大的特征值和對應(yīng)的特征向量的特征值和對應(yīng)的特征向量1ku 解：解：Step12 1013 1014A 例例1 1：利用利用冪法冪法求下列矩陣求下列矩陣 的模的模最大的特征值及相應(yīng)的最大的特征值及相應(yīng)的特征向量特征向量.A01 1 1()Tu (取初始向量為取初始向量為 )10355()T

10、yAu 15 11131 15()Tyu Step2212311555()TyAu25 222231112525()Tyu Step3321 84 24 92( .)TyAu34 92. 3330 36590 85371( .)Tyu Step4431 58543 92684 8537( .)TyAu 44 8537. 4440 32660 80901( .)Tyu 特征值及相應(yīng)的特征值及相應(yīng)的特征向量特征向量精確值精確值為為:4 7321. 0 26790 73201( .)Tu 冪法冪法的收斂性的收斂性：8 2 1. .Th12p 設(shè)設(shè) 有有 p個個互不相同互不相同的特征值滿足：的特征值滿

11、足：n nAC 且且模最大模最大特征值特征值 是是半單半單的，如果初始向量的，如果初始向量 在在的特征子空間上的的特征子空間上的投影投影不為零，則由不為零，則由冪法冪法算法產(chǎn)生的算法產(chǎn)生的1 ku向量向量序列序列 收斂到收斂到 的一個特征向量的一個特征向量 ，且，且數(shù)值數(shù)值1 0u1 1x序列序列 收斂到收斂到 。 k 1 特征特征子空間：子空間： 0Vx Axx 證明：證明：設(shè)設(shè) 有如下有如下Jordan分解：分解：A11(,)pAXdiag JJX iinniJC 是屬于是屬于 的的Jordan塊構(gòu)成的塊上三角矩陣塊構(gòu)成的塊上三角矩陣i 111nJI 是是半單半單的特征值的特征值1 10y

12、X u 令令將將 和和 如下分塊：如下分塊：yX12(,)TTTTpyyyy 12pnnn12(,)pXXXX 12pnnn1010(,)kkkpA uXdiag JJXu 111222kkkPppX J yX J yX J y 111222kkkpppX yX J yX J y 21112211()()pkkkppJJX yXyXy 0111222kkkkPppA uX J yX J yX J y 021122111()()kpkkppkJA uJX yXyXy 1111110()/()kiiiJJ 01110lim()kkkA uX y 記記11111X yxX y AXXJ 11111A

13、XX JX 11111AX yX y 111Axx 1kkkAuu 011kkkA u 0110kkkkA uA u 1111()kX yukX y 1limkkux 是屬于是屬于 的一個特征向量的一個特征向量1 1x1kkkAuu 1()kk 幾點(diǎn)說明幾點(diǎn)說明：定理定理8.2.1條件不滿足時，條件不滿足時，冪法冪法產(chǎn)生的產(chǎn)生的向量向量序列序列 ku可能有可能有若干若干個收斂于不同向量的個收斂于不同向量的子序列子序列；冪法冪法的收斂的收斂速度速度取決于取決于 的大??；的大?。?1: 021122111()()kpkkppkJA uJX yXyXy 加速加速方法：適當(dāng)選取方法：適當(dāng)選取 ，對，對

14、 應(yīng)用應(yīng)用冪法冪法AI 稱之為稱之為原點(diǎn)平移法原點(diǎn)平移法1Axx 1Axxxx 1()()AI xx 原點(diǎn)平移法原點(diǎn)平移法不改變不改變矩陣矩陣 的特征向量的特征向量A冪法冪法可以計(jì)算第二個可以計(jì)算第二個模最大模最大特征值特征值 2 常用常用的方法：的方法：降階降階方法（方法（收縮收縮技巧）技巧）設(shè)已經(jīng)計(jì)算出設(shè)已經(jīng)計(jì)算出模最大模最大特征值特征值 及其特征向量及其特征向量 1 1x111Axx 對向量對向量 ，采用，采用復(fù)復(fù)的的Household變換計(jì)算變換計(jì)算酉酉矩陣矩陣1xP11 1Pxe 1111HPAPePAx 1111Px 1 1e 10HPAPB 其中其中 是是n-1階方陣階方陣B2

15、為為 的的模最大模最大特征值特征值 B二、二、反冪法的反冪法的基本基本思想與算法思想與算法反冪法反冪法是求一個矩陣的是求一個矩陣的模最小模最小的特征值和對應(yīng)的特征的特征值和對應(yīng)的特征 向量的一種向量的一種迭代迭代方法（又稱為方法（又稱為反迭代法反迭代法）。）。 設(shè)設(shè) ，則，則Axx 11A xx 1A 對對 應(yīng)用應(yīng)用冪法冪法就可以求得矩陣就可以求得矩陣 的的模最小模最小的特征值和相應(yīng)的特征向量。的特征值和相應(yīng)的特征向量。A不妨假設(shè)不妨假設(shè) 的特征值為的特征值為11nn A則則 的特征值為的特征值為11nn 1A 1ii 反反冪法冪法算法算法：For k=1,2,3,1kkAyz kky if1

16、kkzz 輸出輸出 和和kzk kkkyz 001,zz limknkzx nnnAxx 若若 和和 均均收斂收斂，由，由冪法冪法知知kzk 1kz limknk 收斂收斂速度速度取決于取決于 的大小的大小1:nn 反反冪法冪法每次迭代都需要每次迭代都需要求解方程組求解方程組1kkAyz 帶位移的帶位移的反反冪法冪法：實(shí)際應(yīng)用中，實(shí)際應(yīng)用中，反反冪法冪法主要用于求主要用于求特征向量特征向量。且用某種方法已經(jīng)得到且用某種方法已經(jīng)得到 的特征值的特征值 的的近似值近似值A(chǔ)1 1 對矩陣對矩陣 采用采用反反冪法冪法迭代格式為：迭代格式為：AI 1 記記假設(shè)假設(shè) 的特征值滿足的特征值滿足120n A1

17、()kkAI vz kkkvzv For k=1,2,3,因?yàn)榉匠探M的系數(shù)矩陣因?yàn)榉匠探M的系數(shù)矩陣Doolittle分解化為兩個分解化為兩個三角三角方方是是固定固定的，通常采用的，通常采用( (選主元選主元) )AI 程組求解，從而減少工作量。程組求解，從而減少工作量。AILU 求解方程組求解方程組 化為：化為：1()kkAI vz 1kkkkLyzUvy 帶位移的帶位移的反反冪法冪法迭代格式：迭代格式： For k=1,2,3,1kkLyz kkUvy kkkvzv 收斂收斂速度速度取決于取決于 的大小的大小12 當(dāng)當(dāng) 時，收斂速度會非?？鞎r，收斂速度會非常快1 設(shè)矩陣設(shè)矩陣 存在存在Doo

18、little分解：分解：AI 解：解：2 1013 1014A 例例2 2：用用帶位移的帶位移的反反冪法冪法求矩陣求矩陣12679. ）的近似特征向量。）的近似特征向量。33 對應(yīng)特征值對應(yīng)特征值 （精確值精確值為為A1 2679. AILU 其中其中1136591027310 1.L 073211000366210000011.U 01 1 1()Tz 10Lyz 1100000636619999.y Step1反反冪法冪法具有一次具有一次“迭代性迭代性”11Uvy 167763938496000018158199.v Step221Lyv 2100001107960073.y 22Uvy

19、220327411488072544673.v 2221 00000 73200 2679.vzv 所求所求近似近似特征向量為：特征向量為：3 Jacobi方法方法Jacobi法：計(jì)算法：計(jì)算實(shí)對稱實(shí)對稱矩陣全部特征值和相應(yīng)特征向量矩陣全部特征值和相應(yīng)特征向量 基本基本思想思想對對,n nTARAA Q存在存在正交正交矩陣矩陣 ，滿足，滿足12(,)TnQ AQdiag 記記12(,)nQq qq 則則1 2;, ,iiiAqq in 尋找尋找正交相似正交相似變換變換 ，將矩陣，將矩陣 約化為約化為對角陣對角陣即可即可QA正交相似正交相似變換求法：通過變換求法：通過Givens變換來實(shí)現(xiàn)變換來

20、實(shí)現(xiàn) 經(jīng)典經(jīng)典Jacobi方法方法設(shè)設(shè),n nijijjiAaRaa 令令1122222111( )()()nnniiijFiijj iE AAaa 非對角非對角“范范數(shù)數(shù)”當(dāng)當(dāng) 時，時， 趨于一個趨于一個對角陣對角陣0( )E A A( , , )( , , )TGp qAG p q先來研究一下矩陣先來研究一下矩陣的元素和矩陣的元素和矩陣 的的元素元素之間的之間的關(guān)系關(guān)系。AGivens變換記為變換記為 ，下面通過，下面通過Givens變換變換( , , )G p q 對矩陣對矩陣 進(jìn)行進(jìn)行約化約化，使得，使得0( )E A A例如例如取取424;,npq cos ;sincs記記11a12

21、a24a13a14a13a22a12a23a23a33a34a14a24a34a44a10s000c000100s 0c10s000c000100s 0c11a12a 13a14a13a 23a33a34a10s000c000100s 0c 11a 13a 13a 33a ( )ipipiqbcasa;iqipiqbsaca(, )ip q 11a 13a 13a 33a 222( )pppppqqqbc ascas a 222qqpppqqqbs ascac a22()()pqpqppqqbcsasc aa 選取適當(dāng)?shù)倪x取適當(dāng)?shù)?，由，由Givens變換將矩陣的變換將矩陣的下三角元素下三角元

22、素 盡可能多的化為盡可能多的化為零零：即：即非對角非對角“范數(shù)范數(shù)”盡可能的盡可能的小小。如果如果 ，則取，則取0pqa 10;cs否則否則，令，令2tan;qqpppqaastca 2210tt 220()()pqpqppqqbcs asc aa 首先首先由由 確定確定 2210tt 21sgn( )t 14()t 2211111cossectantc ;stc 其次其次確定旋轉(zhuǎn)平面確定旋轉(zhuǎn)平面( , )p q2222211()nniiiiFFiiEBBbAb 由由F-范數(shù)的范數(shù)的正交不變性正交不變性設(shè)設(shè) 經(jīng)過一次經(jīng)過一次正交相似正交相似變換后變?yōu)榫仃囎儞Q后變?yōu)榫仃嘇B22222211()n

23、niiiippqqppqqiibaaabb222222222( )( )()( )ppqqppqqpqEBEAaabbEAa 222222ppqqppqqpqaabba 注意注意到到旋轉(zhuǎn)平面旋轉(zhuǎn)平面 的選取方法：的選取方法：( , )p q1maxpqijij naa 經(jīng)典經(jīng)典Jacobi方法的迭代格式：方法的迭代格式：101 2 3( );, ,kTkijkkkAaG AGAA k 8 3 1. .Th對于經(jīng)典對于經(jīng)典Jacobi方法產(chǎn)生的矩陣序列方法產(chǎn)生的矩陣序列 ， kA存在存在 的特征值的一個排列的特征值的一個排列 滿足滿足A12,n 12lim(,)knkAdiag 證明見教材證明見

24、教材 經(jīng)典經(jīng)典Jacobi方法的迭代算法方法的迭代算法給定矩陣給定矩陣(),ijijjiAaaa 選取選取最佳旋轉(zhuǎn)平面最佳旋轉(zhuǎn)平面 ：( , )p q1maxpqijij naa For k=1,2,3,21sgn( );t 2qqpppqaaa 計(jì)算計(jì)算211;tc ;stc ipipiqacasa ;iqipiqasaca ,ifip q 計(jì)算計(jì)算222pppppqqqac ascas a 222;qqpppqqqas ascac a 220()()pqpqppqqacs asc aa ( )E A 直到直到需比較需比較 個元素個元素12()n n 習(xí)慣上稱習(xí)慣上稱 次次Jacobi迭代為

25、一次迭代為一次“掃描掃描”12()n n 循環(huán)循環(huán)Jacobi方法方法每一次每一次Jacobi迭代不是去選擇迭代不是去選擇最佳旋轉(zhuǎn)平面最佳旋轉(zhuǎn)平面，而是而是直接按照某種直接按照某種預(yù)先指定預(yù)先指定的順序來的順序來“掃描掃描”自然自然順序：順序：1 21 312 32 42( , )( , ),( , ),( , );( , ),( , ),( , );p qnn 3 43 531( , ),( , ),( , );(, );nnn 按照按照自然自然順序的循環(huán)順序的循環(huán)Jacobi方法是方法是漸進(jìn)平方漸進(jìn)平方收斂的收斂的4 QR 方方 法法 基本基本思想思想利用利用正交相似正交相似變換將一個給定

26、的矩陣逐步約化變換將一個給定的矩陣逐步約化為為上三角上三角矩陣或矩陣或擬上三角擬上三角矩陣的一種矩陣的一種迭代迭代方法方法 QR方法的方法的迭代迭代格式格式設(shè)設(shè)0n nAAC 令令111ARQ 011AQ R 對矩陣對矩陣 進(jìn)行進(jìn)行QR分解分解0A122AQ R 再對矩陣再對矩陣 進(jìn)行進(jìn)行QR分解分解1A一、一、QR基本迭代基本迭代方法方法QR方法是目前計(jì)算矩陣方法是目前計(jì)算矩陣全部全部特征值的特征值的最最有效有效的方的方法之一；具有法之一；具有收斂快收斂快、算法、算法穩(wěn)定穩(wěn)定等特點(diǎn)。等特點(diǎn)。一般地有：一般地有：1mmmAQ R 1 2;, ,mmmAR Qm 1HmmmmAQ AQ 矩陣序列

27、矩陣序列 中每一個矩陣都與原矩陣中每一個矩陣都與原矩陣 相似相似 mAAQR方法的迭代算法：方法的迭代算法：1mmmAQ R mmmAR Q For m=1,2,3,直到直到 近似近似為為上三角上三角陣陣mA由由迭代格式迭代格式同時還得到：同時還得到：2112HHHmmmAQQ Q AQQQ HmmmAQ AQ 記記12mmQQQQ 11mmmAQR 代入代入11mmmmQ QRAQ 11mmmmQ QRAQ 等式兩端同時右乘等式兩端同時右乘21mRR R112121mmmmmmQ QRRR RAQ RR R 記記21kkRRR R 11mmmmQRAQ R 21111111mmmmmmQRA

28、 QRA Q RA mmmAQ R 即即111 1()mmA er q 其中其中 是是 的的第一列第一列， 是是 的相應(yīng)元素的相應(yīng)元素1()mq11rmQmR可以看作是對矩陣可以看作是對矩陣 用用 為為1()mqA初始向量的初始向量的冪法冪法所得到的向量。所得到的向量。1eQR方法與方法與冪法冪法的關(guān)系：的關(guān)系： QR方法的方法的收斂收斂性性8 4 1. .Th設(shè)設(shè) 的特征值滿足的特征值滿足 ，且，且 的的LU則由則由QR迭代算法產(chǎn)生的矩陣迭代算法產(chǎn)生的矩陣 的對角線以的對角線以120n Ai ()mmijAa ()miiaY第第i行是行是 對應(yīng)于對應(yīng)于 的的左特征左特征向量；若向量；若 有有

29、 分解，分解，AY下的元素趨于下的元素趨于0，同時對角元素，同時對角元素 趨于趨于1(, )iin （QR方法的方法的收斂收斂性質(zhì)）性質(zhì)）證明：證明：令令1;XY 1(,)ndiag 則有則有AXY mmmAXYXLU ()mmmXLU ()mmX IEU 其中其中mmmIEL 0limmmE 01(, )iirin且且()mmmAX IEU ()mmQR IEU 1()mmmAQ IRE RRU 1mIRE R 當(dāng)當(dāng)m充分大時，充分大時， 存在唯一存在唯一QR分解：分解：1mmmIRE RQ R 01()(, )miirin且且mmQ RI 當(dāng)當(dāng)m充分大時充分大時limlimmmmmQRI(

30、)()mmmmAQQR RU QR （QR分解）分解）記記 的的QR分解為：分解為：XQR X為保證上述為保證上述QR分解中上三角矩陣的對角元為分解中上三角矩陣的對角元為正正，令，令111(,)nnDdiag 11211;(,)nnnnuuDdiaguu 11221()()mmmmmmAQQ D DD DR RU mmQ R 由由QR分解唯一性知：分解唯一性知：2112()HHHmHHmmmmmmAQ AQDDQ Q AQQ D D 代入代入11HAXYXXQR R Q 12112()HHmHmmmmADDQ R R Q D D 趨于趨于上三角上三角陣陣實(shí)際應(yīng)用中遇到的多數(shù)特征值問題都是關(guān)于實(shí)

31、際應(yīng)用中遇到的多數(shù)特征值問題都是關(guān)于實(shí)矩陣實(shí)矩陣的，所以自然希望設(shè)計(jì)只涉及實(shí)數(shù)運(yùn)算的的，所以自然希望設(shè)計(jì)只涉及實(shí)數(shù)運(yùn)算的QR迭代。迭代。 實(shí)實(shí)QR迭代迭代格式格式設(shè)設(shè)1n nAAR 二、實(shí)二、實(shí)Schur標(biāo)準(zhǔn)形標(biāo)準(zhǔn)形kkkAQ R 1kkkAR Q For k=1,2,3,為為正交正交矩陣矩陣為為上三角上三角陣陣kQkR8 4 2. .Th（實(shí)（實(shí)Schur分解）分解）設(shè)設(shè)n nAR ，則存在，則存在正交正交矩陣矩陣n nQR ，滿足：，滿足：11121222mmTmmRRRRRQ AQR 其中其中 為為實(shí)數(shù)實(shí)數(shù)或具有或具有一對復(fù)共軛一對復(fù)共軛特征值的特征值的2階方陣階方陣iiRiiiiiiR

32、 220()iiiiIR 特征值為特征值為iij ，其中，其中 為為虛單位虛單位j見文獻(xiàn)見文獻(xiàn)1311121222mmmmRRRRRR矩陣矩陣稱為稱為 的的Schur標(biāo)準(zhǔn)形標(biāo)準(zhǔn)形A定理定理8.4.2說明：只要求得矩陣的說明：只要求得矩陣的Schur標(biāo)準(zhǔn)形，標(biāo)準(zhǔn)形，就很容易求得矩陣的就很容易求得矩陣的全部全部特征值。特征值。缺陷缺陷： 很難得到很難得到QH 011h21h0022h32h12h0023h33h13h043h21,nh 31,nh 11,nh 41,nh 11,nnh 2,nh3,nh1,nh4,nh1,nnh 22,nh 32,nh 12,nh 0001,n nh ,n nh04

33、2,nh 12,nnh 稱下述形狀的矩陣為稱下述形狀的矩陣為上上Hessenberg矩陣矩陣三、上三、上Hessenberg化化設(shè)設(shè) ，n nAR 尋求非奇異矩陣尋求非奇異矩陣 ，使得，使得 為上為上Hessenberg 矩陣矩陣，然后再對，然后再對 進(jìn)行進(jìn)行 迭代。迭代。1QAQ Q1QAQ QR 基本基本思想思想和和約化約化過程：過程：ijAa 記矩陣記矩陣Q下面采用下面采用Householde變換尋找變換尋找Step1 選取選取Householde變換變換 ，使得，使得1H111Hpe 其中其中1111aAA 令令11100HH 11111111101000aH AHHAH 1111 1

34、111aHHH AH 11a p2A0 2111AH A H 其中其中Step2 選取選取Householde變換變換 ，使得，使得2H221Hqe 下面對作下面對作 同樣的處理，以此類推同樣的處理，以此類推2A其中其中223AA 令令22100HH 2222322101000H AHAHH 22232HH A H 令令22100HH 1121122122101000aH H AH HHpeAH 111222apeH AH 3232AH A H 其中其中 11a p3A0 0 q0 22222232H A HHH A H 記記2112H H AH H 0 11h21h0 0 22h32h12h

35、 12H H為為正交正交陣陣按照前述方法，經(jīng)過按照前述方法，經(jīng)過n-2步后，可以得到：步后，可以得到：221122nnHH H AH HHH 其中其中H 011h21h0022h32h12h0023h33h13h043h21,nh 31,nh 11,nh 41,nh 11,nnh 2,nh3,nh1,nh4,nh1,nnh 22,nh 32,nh 12,nh 0001,n nh ,n nh042,nh 12,nnh 122nPH HH 記記 ，則，則TAPHP 稱分解式稱分解式 為矩陣為矩陣 的上的上Hessenberg分解分解TAPHP A 上上Hessenberg分解分解算法算法（8.4.

36、1）1 ,( (: , )vhouse A kn k For k=1:n-211(: ,: )() (: ,: )TA kn k nIvvA kn k n 1111( : ,: )( : ,: )()TAn knAn kn Ivv 然后對上然后對上Hessenberg矩陣進(jìn)行矩陣進(jìn)行QR迭代迭代設(shè)設(shè)Hyy TP APyy APyPy 上上Hessenberg矩陣的矩陣的QR迭代算法：迭代算法：1mmmHQ R mmmHR Q For m=1,2,3,直到直到 的的次對角次對角元素趨于元素趨于零零mH注意注意：此時的此時的QR分解可采分解可采用用Givens變換來實(shí)現(xiàn)；變換來實(shí)現(xiàn)；用用Given

37、s變換得到的變換得到的RQ仍仍然為上然為上Hessenberg矩陣；矩陣；上上Hessenberg分解不唯一。分解不唯一。若上若上Hessenberg矩陣的次對角元素均不為矩陣的次對角元素均不為零零，則稱則稱之為之為不可約不可約的上的上Hessenberg矩陣。矩陣。7Def定理定理8.4.3說明：在說明：在不可約不可約的條件下，的條件下，上上Hessenberg分解在相差一個分解在相差一個正負(fù)號正負(fù)號的意義下的意義下唯一唯一。見文獻(xiàn)。見文獻(xiàn)6 實(shí)用的實(shí)用的QR迭代算法（僅計(jì)算迭代算法（僅計(jì)算特征值特征值）Step1 由算法由算法8.4.1計(jì)算計(jì)算上上Hessenberg矩陣：矩陣：()TAH

38、P AP Step2（QR分解分解） For k=1:n-11 ( ), ( )( , ),(, )c k s kGivens H k k H kk 1111( )( )( :, : )( :, : )( )( )c ks kH k knH k kns kc k Step3（計(jì)算（計(jì)算RQ）Step4 重復(fù)步驟重復(fù)步驟Step23，直到，直到下次對角下次對角元素趨于元素趨于零零1111( )( )( : , :)( : , :)( )( )c ks kHn k kHn k ks kc k 四、四、三對角三對角化（化（對稱對稱矩陣的矩陣的上上Hessenberg化）化）TP APH 設(shè)設(shè) 為為對

39、稱對稱矩陣，矩陣， 的的上上Hessenberg分解為分解為n nAR A其中其中 為為對稱三對角對稱三對角矩陣。矩陣。HStep1 選取選取Householde變換變換 ，使得，使得1H111Hpe 其中其中11111TaAA 令令11100HH 111111111101000TaH AHHHA 11111 1111TaHHH AH 2111AH A H 其中其中 11ap2A0p0111H A H主要主要工作量工作量在于計(jì)算在于計(jì)算1THIvv 1111()()TTH AHIvvA Ivv 21111TTTTAAvvvv Avv Avv 21111()()TTTTAAv vv Avvv Avv 令令112;()TuAvuv