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

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

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

3、向量的特征向量AA3Def設(shè)設(shè) ，,n nA BC 若存在矩陣若存在矩陣 ，使得，使得P1BP AP 則稱(chēng)則稱(chēng) 和和 是是相似相似的。的。AB相似相似矩陣有相同的特征值矩陣有相同的特征值1AxxPAP PxPx BPxPx Axx 設(shè)設(shè)尋求已知矩陣尋求已知矩陣 的的相似相似矩陣矩陣 ，要求：，要求：矩陣矩陣 的的特征值特征值和和特征向量特征向量容易計(jì)算容易計(jì)算ABB本章本章QR算法的算法的基本思想：基本思想：8 1 1. .Th1(, )iir 設(shè)設(shè) ，有，有 r個(gè)個(gè)互不相同互不相同的特征值的特征值 ，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稱(chēng)作稱(chēng)作 的的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按任意指定的順序排列。按任意指定的順序排列。8

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

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

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

8、1121() )njkkjjjxx 011211() )knjkjjkjA uxx 11()x k 01kkkA uu 說(shuō)明：當(dāng)說(shuō)明：當(dāng)k充分大時(shí)充分大時(shí), 的一個(gè)的一個(gè)近似特征向量近似特征向量為為1 特征向量可以相差一個(gè)特征向量可以相差一個(gè)倍數(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 1kFor k=1,2,3,1kkyAu kky if1kkuu 輸出輸出 和和kuk kkkyu 001,uu 設(shè)設(shè) 和和 均均收斂收斂，由，由算法算法知知kuk 冪法冪法可以計(jì)算矩陣的可以計(jì)算矩陣的模最大模最大的特征值和對(duì)應(yīng)的特征向量的特征值和對(duì)應(yīng)的特征向量1ku 解：解：Step12 1013 1014A 例例1 1：利用利用冪法冪法求下列矩陣求下列矩陣 的模的模最大的特征值及相應(yīng)的最大的特征值及相應(yīng)的特征向量特征向量.A01 1 1()Tu (取初始向量為取初始向量為 )10355()Ty

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

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

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

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

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

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

16、出 和和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 對(duì)矩陣對(duì)矩陣 采用采用反反冪法冪法迭代格式為：迭代格式為：AI 1 記記假設(shè)假設(shè) 的的特征值滿(mǎn)足特征值滿(mǎn)足120n A1()kkAI v

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

18、：分解：AI 解：解：2 1013 1014A 例例2 2：用用帶位移的帶位移的反反冪法冪法求矩陣求矩陣12679. ）的近似特征向量。）的近似特征向量。33 對(duì)應(yīng)特征值對(duì)應(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 22032741

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

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

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

22、化為盡可能多的化為零零：即：即非對(duì)角非對(duì)角“范數(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)過(guò)一次經(jīng)過(guò)一次正交相似正交相似變換后變?yōu)榫仃囎儞Q后變?yōu)榫仃嘇B22222211()nniiiipp

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

24、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 直到直到需比較需比較 個(gè)元素個(gè)元素12()n n 習(xí)慣上稱(chēng)習(xí)慣上稱(chēng) 次次Jacobi迭代為一次迭代為一次“

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

26、換將一個(gè)給定的矩陣逐步約化為為上三角上三角矩陣或矩陣或擬上三角擬上三角矩陣的一種矩陣的一種迭代迭代方法方法 QR方法的方法的迭代迭代格式格式設(shè)設(shè)0n nAAC 令令111ARQ 011AQ R 對(duì)矩陣對(duì)矩陣 進(jìn)行進(jìn)行QR分解分解0A122AQ R 再對(duì)矩陣再對(duì)矩陣 進(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、個(gè)矩陣都與原矩陣中每一個(gè)矩陣都與原矩陣 相似相似 mAAQR方法的迭代算法：方法的迭代算法：1mmmAQ R mmmAR Q For m=1,2,3,直到直到 近似近似為為上三角上三角陣陣mA由由迭代格式迭代格式同時(shí)還得到：同時(shí)還得到：2112HHHmmmAQQ Q AQQQ HmmmAQ AQ 記記12mmQQQQ 11mmmAQR 代入代入11mmmmQ QRAQ 11mmmmQ QRAQ 等式兩端同時(shí)右乘等式兩端同時(shí)右乘21mRR R112121mmmmmmQ QRRR RAQ RR R 記記21kkRRR R 11mmmmQRAQ R 21111111mmmmmmQRA QRA Q R

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

29、Y下的元素趨于下的元素趨于0，同時(shí)對(duì)角元素，同時(shí)對(duì)角元素 趨于趨于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充分大時(shí)，充分大時(shí)， 存在唯一存在唯一QR分解：分解：1mmmIRE RQ R 01()(, )miirin且且mmQ RI 當(dāng)當(dāng)m充分大時(shí)充分大時(shí)limlimmmmmQRI()()mmmmA

30、QQR RU QR （QR分解）分解）記記 的的QR分解為：分解為：XQR X為保證上述為保證上述QR分解中上三角矩陣的對(duì)角元為分解中上三角矩陣的對(duì)角元為正正，令，令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ù)特征值問(wèn)題都是關(guān)于實(shí)際應(yīng)用中遇到的多

31、數(shù)特征值問(wèn)題都是關(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 ，滿(mǎn)足：，滿(mǎn)足：11121222mmTmmRRRRRQ AQR 其中其中 為為實(shí)數(shù)實(shí)數(shù)或具有或具有一對(duì)復(fù)共軛一對(duì)復(fù)共軛特征值的特征值的2階方陣階方陣iiRiiiiiiR 220()ii

32、iiIR 特征值為特征值為iij ，其中，其中 為為虛單位虛單位j見(jiàn)文獻(xiàn)見(jiàn)文獻(xiàn)1311121222mmmmRRRRRR矩陣矩陣稱(chēng)為稱(chēng)為 的的Schur標(biāo)準(zhǔn)形標(biāo)準(zhǔn)形A定理定理8.4.2說(shuō)明：只要求得矩陣的說(shuō)明：只要求得矩陣的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 nh042,nh 12,

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

34、AH 11a p2A0 2111AH A H 其中其中Step2 選取選取Householde變換變換 ，使得，使得2H221Hqe 下面對(duì)作下面對(duì)作 同樣的處理，以此類(lèi)推同樣的處理，以此類(lèi)推2A其中其中223AA 令令22100HH 2222322101000H A HAHH 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 12H H為

35、為正交正交陣陣按照前述方法，經(jīng)過(guò)按照前述方法，經(jīng)過(guò)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 稱(chēng)分解式稱(chēng)分解式 為矩陣為矩陣 的上的上Hessenberg分解分解TAPHP A 上上Hessenberg分解分解算法算法（8.4.1）1 ,(

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

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

38、ep2（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，直到，直到下次對(duì)角下次對(duì)角元素趨于元素趨于零零1111( )( )( : , :)( : , :)( )( )c ks kHn k kHn k ks kc k 四、四、三對(duì)角三對(duì)角化（化（對(duì)稱(chēng)對(duì)稱(chēng)矩陣的矩陣的上上Hessenberg化）化）TP APH 設(shè)設(shè) 為為對(duì)稱(chēng)對(duì)稱(chēng)矩陣，矩

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