第8章_矩陣特征值問題計(jì)算

1、上頁上頁下頁下頁第第8章章 矩陣特征問題的計(jì)算矩陣特征問題的計(jì)算 8.1 引言引言 8.2 冪法及反冪法冪法及反冪法 8.3 豪斯霍爾德方法豪斯霍爾德方法 8.4 QR方法方法上頁上頁下頁下頁8.1 引引 言言 工程技術(shù)中有多種振動問題，如橋梁或建筑物的工程技術(shù)中有多種振動問題，如橋梁或建筑物的振動，機(jī)械零件、飛機(jī)機(jī)翼的振動，及一些穩(wěn)定性分振動，機(jī)械零件、飛機(jī)機(jī)翼的振動，及一些穩(wěn)定性分析和相關(guān)分析在數(shù)學(xué)上都可轉(zhuǎn)化為求矩陣特征值與特析和相關(guān)分析在數(shù)學(xué)上都可轉(zhuǎn)化為求矩陣特征值與特征向量的問題征向量的問題. 下面先復(fù)習(xí)一些矩陣的特征值和特征向量的基礎(chǔ)下面先復(fù)習(xí)一些矩陣的特征值和特征向量的基礎(chǔ)知識知識

2、.上頁上頁下頁下頁 定義定義1 已知已知n階矩陣階矩陣A=(aij)，則，則)2()(det)det()(12211212222111211的項(xiàng)的項(xiàng)次數(shù)次數(shù) naaaaaaaaaaaaAInnnnnnnnnn 稱為稱為A的的特征多項(xiàng)式特征多項(xiàng)式. 一般有一般有n個根個根(實(shí)的或復(fù)的，復(fù)根按重?cái)?shù)計(jì)算實(shí)的或復(fù)的，復(fù)根按重?cái)?shù)計(jì)算)稱為稱為A的的特征值特征值. 用用(A)表示表示A的所有特征值的集合的所有特征值的集合. A的特征方程的特征方程)1 . 1(0)det()( AI 上頁上頁下頁下頁 設(shè)設(shè)為為A的特征值，相應(yīng)的齊次方程組的特征值，相應(yīng)的齊次方程組 注：注：當(dāng)當(dāng)A為實(shí)矩陣時，為實(shí)矩陣時， (

3、)=0為實(shí)系數(shù)為實(shí)系數(shù)n次代數(shù)次代數(shù)方程，其復(fù)根是共軛成對出現(xiàn)方程，其復(fù)根是共軛成對出現(xiàn).)2 . 1(0)( xAI 的的非零解非零解x稱為矩陣稱為矩陣A的對應(yīng)于的對應(yīng)于的的特征向量特征向量. 210131012A 例例1 求求A的特征值及特征向量，其中的特征值及特征向量，其中上頁上頁下頁下頁. 0)4)(2)(1(8147210131012)det()(23 AI 解解 矩陣矩陣A的特征方程為的特征方程為求得矩陣求得矩陣A的特征值為：的特征值為：. 4, 2, 1 對應(yīng)于各特征值矩陣對應(yīng)于各特征值矩陣A的特征向量分別為：的特征向量分別為：.121,101,111321 xxx上頁上頁下頁下

4、頁 定理定理1 設(shè)設(shè)為為ARnn的特征值的特征值, 且且Ax=x (x 0)，則有則有 - -p為為A- -pI的特征值，即的特征值，即(A- -pI)x=(- -p)x ； c為的為的cA特征值特征值(c0為常數(shù)為常數(shù))； 下面敘述有關(guān)特征值的一些下面敘述有關(guān)特征值的一些結(jié)論結(jié)論： k為為Ak的特征值，即的特征值，即Akx=kx ； 設(shè)設(shè)A為非奇異矩陣，那么為非奇異矩陣，那么0 , 且且- -1為為A- -1的特的特征值，即征值，即A- -1x=- -1x .上頁上頁下頁下頁 定理定理2 設(shè)設(shè)i(i=1,2,n)為為n階矩陣階矩陣A=(aij)的特征值，的特征值，則有則有)(Atraniii

5、nii 11 稱為稱為A的的跡跡； .nA21 定理定理3 設(shè)設(shè)ARnn，則有，則有. )()(AAT 定理定理4 設(shè)設(shè)A 為分塊上三角矩陣，即為分塊上三角矩陣，即, mmmmAAAAAAA22211211其中每個對角塊其中每個對角塊Aii均為方陣，則均為方陣，則. )()(iiniAA1 上頁上頁下頁下頁 定理定理5 設(shè)設(shè)A與與B為相似矩陣（即存在非奇異矩陣為相似矩陣（即存在非奇異矩陣P使使B=P- -1AP），則），則 定理定理5說明，一個矩陣說明，一個矩陣A經(jīng)過相似變換，其特征經(jīng)過相似變換，其特征值不變值不變. 一個虧損矩陣是一個沒有足夠特征向量的矩陣，一個虧損矩陣是一個沒有足夠特征向量

6、的矩陣，虧損矩陣在理論上和計(jì)算上都存在困難虧損矩陣在理論上和計(jì)算上都存在困難. A與與B有相同的特征值；有相同的特征值； 如果如果y是是B的特征向量，則的特征向量，則Py是是A的特征向量的特征向量. 定義定義2 如果實(shí)矩陣如果實(shí)矩陣A有一個重?cái)?shù)為有一個重?cái)?shù)為k的特征值的特征值, 且對應(yīng)于且對應(yīng)于的的A的線性無關(guān)的特征向量個數(shù)的線性無關(guān)的特征向量個數(shù)|2|n|，則對任何非零向量則對任何非零向量v0(a1 0)，冪法的算式成立，冪法的算式成立.又設(shè)又設(shè)A有有n個線性無關(guān)的特征向量，個線性無關(guān)的特征向量，1對應(yīng)的對應(yīng)的r個線性個線性無關(guān)的特征向量為無關(guān)的特征向量為x1,x2,xr，則由，則由(2.2

7、)式有式有 如果如果A的主特征值為實(shí)的重根的主特征值為實(shí)的重根, 即即1=2=r, 且且 |r|r+1|n|，,)/(11110 nriikiiriiikkkxaxavAv 上頁上頁下頁下頁).0(lim111 riiiriiikkkxaxav設(shè)設(shè) 為為A的特征向量，這說明當(dāng)?shù)奶卣飨蛄?，這說明當(dāng)A的主特征值是實(shí)的重根的主特征值是實(shí)的重根時，定理時，定理5的結(jié)論還是正確的的結(jié)論還是正確的. 應(yīng)用應(yīng)用冪法冪法計(jì)算計(jì)算A的主特征值的主特征值1及其對應(yīng)的特征向及其對應(yīng)的特征向量時，如果量時，如果|1|1(或或|1|2|n|，則對任意非零初始，則對任意非零初始向量向量v0=u0(a1 0)，有冪法計(jì)算公

8、式為，有冪法計(jì)算公式為則有則有 ,)max(lim11xxukk .lim1 kk上頁上頁下頁下頁例例1 用冪法計(jì)算矩陣用冪法計(jì)算矩陣 1634310232A的主特征值與其對應(yīng)的特征向量的主特征值與其對應(yīng)的特征向量.解解取取 v0=u0=(0,0,1)T , 則則 TTvuv25. 0 , 1, 5 . 01, 4,1 , 4 , 211111 ), 2 , 1(max1 k/vuvAuvkkkkkkk 上頁上頁下頁下頁直到直到k=8 時的計(jì)算結(jié)果見下表時的計(jì)算結(jié)果見下表k1 2, 4, 1, 4 0.5, 1, 0.252 4.5, 9, 7.75 90.5, 1, 0.86113 5.72

9、22, 11.4444, 8.36111.44440.5, 1, 0.73604 5.4621, 10.9223, 8.2306 10.92230.5, 1, 0.75365 5.5075, 11.0142, 8.2576 11.01420.5, 1, 0.74946 5.4987, 10.9974, 8.2494 10.99740.5, 1, 0.75017 5.5002, 11.0005, 8.2501 11.00050.5, 1, 0.75008 5.5000, 11.0000, 8.2500 11.00000.5, 1, 0.7500TkvTku Tx7500. 0,0 . 1,5 .

10、 0,0000.1111 從而從而k 見書見書p303- -例例3.上頁上頁下頁下頁8.2.2 冪法的加速方法冪法的加速方法1、原點(diǎn)平移法、原點(diǎn)平移法 由前面討論知道，應(yīng)用冪法計(jì)算由前面討論知道，應(yīng)用冪法計(jì)算A的主特征值的的主特征值的收斂速度主要由比值收斂速度主要由比值 r=|2/1|來決定，但當(dāng)來決定，但當(dāng)r 接近于接近于1時，收斂可能很慢時，收斂可能很慢. 這時，一個補(bǔ)救辦法是采用加速這時，一個補(bǔ)救辦法是采用加速收斂的方法收斂的方法.其中其中p為參數(shù)，設(shè)為參數(shù)，設(shè)A的特征值為的特征值為 i，則對矩陣，則對矩陣B的特征的特征值為值為 i- -p ，而且，而且A, B的特征向量相同的特征向量相

11、同. 引進(jìn)矩陣引進(jìn)矩陣 B=A- -pI .上頁上頁下頁下頁 如果要計(jì)算如果要計(jì)算A的主特征值的主特征值 1, 只要只要選擇合適的數(shù)選擇合適的數(shù)p，使使 1- -p為矩陣為矩陣B=A- -pI 的主特征值，且的主特征值，且 1212max ppini那么，對矩陣那么，對矩陣B=A- -pI應(yīng)用冪法求其主特征值應(yīng)用冪法求其主特征值 1- -p, 收收斂速度將會加快斂速度將會加快. 這種通過求這種通過求B=A- -pI的主特征值和特的主特征值和特征向量，而得到征向量，而得到A的主特征值和特征向量的方法叫的主特征值和特征向量的方法叫原原點(diǎn)平移法點(diǎn)平移法. 對于對于A的特征值的某種分布，它是十分有的特

12、征值的某種分布，它是十分有效的效的.上頁上頁下頁下頁例例4 設(shè)設(shè)AR44有特征值有特征值),4 , 3 , 2 , 1(15 jji 比值比值r=|2/1|0.9. 做變換做變換B=A- -12I (p=12),則則B的特征值為的特征值為. 1, 0, 1, 24321 應(yīng)用冪法計(jì)算應(yīng)用冪法計(jì)算B的主特征值的主特征值1的收斂速度的比值為的收斂速度的比值為. 9 . 021121212 pp 雖然常常能夠選擇有利的雖然常常能夠選擇有利的p值值, 使冪法得到加速使冪法得到加速, 但設(shè)計(jì)一個自動選擇適當(dāng)參數(shù)但設(shè)計(jì)一個自動選擇適當(dāng)參數(shù)p的過程是困難的的過程是困難的.上頁上頁下頁下頁 下面考慮當(dāng)下面考慮

13、當(dāng)A的特征值是實(shí)數(shù)時，怎樣選擇的特征值是實(shí)數(shù)時，怎樣選擇p使采使采用冪法計(jì)算用冪法計(jì)算1得到加速得到加速.ppn 1且使且使收斂速度的比值收斂速度的比值.min,max112 ppppn 設(shè)設(shè)A的特征值都是實(shí)數(shù)，且滿足的特征值都是實(shí)數(shù)，且滿足)10. 2(,121nn 則對實(shí)數(shù)則對實(shí)數(shù)p，使矩陣，使矩陣A- -pI的主特征值為的主特征值為 1- -p或或 n- -p時，時，當(dāng)當(dāng)我們計(jì)算我們計(jì)算 1及及x1時，首先應(yīng)選取時，首先應(yīng)選取p使使上頁上頁下頁下頁顯然，當(dāng)顯然，當(dāng) 2- -p=- -( n- -p )時，即時，即 P=( 2+ n)/2P* 時時為最小值，這時為最小值，這時收斂速度的比值

14、收斂速度的比值為為.2212112nnnpppp 當(dāng)希望計(jì)算當(dāng)希望計(jì)算 n時，應(yīng)選取時，應(yīng)選取 p=( 1+ n-1)/2P* 使得應(yīng)用冪法計(jì)算使得應(yīng)用冪法計(jì)算 n得到加速得到加速. 當(dāng)當(dāng)A的特征值都是實(shí)數(shù)，滿足的特征值都是實(shí)數(shù)，滿足且且 2, n能初步估計(jì)出來，我們就能確定能初步估計(jì)出來，我們就能確定P*的近似值的近似值.nn 121上頁上頁下頁下頁 例例2 用原點(diǎn)平移加速法求用原點(diǎn)平移加速法求例例1中矩陣中矩陣A的主特征值的主特征值與其對應(yīng)的特征向量與其對應(yīng)的特征向量.5 . 36345 . 510235 . 4 B,1634310232 A對對B應(yīng)用冪法，仍應(yīng)用冪法，仍取取 v0=(0,

15、0,1)T , 則則 .875. 0 , 1, 5 . 01, 4,5 . 3 , 4 , 211111TTvuu ), 2 , 1(max1 k/vuvBuvkkkkkkk 解解 取取p=- -2.5, 做平移變換做平移變換B=A- -pI，則，則上頁上頁下頁下頁迭代迭代5步的計(jì)算結(jié)果見下表步的計(jì)算結(jié)果見下表k1 2, 4, 3.54 0.5, 1, 0.8752 7, 14, 10.5625 140.5, 1, 0.75453 6.76, 13.5179, 10.1406 13.51790.5, 1, 0.75074 6.7503, 13.5007, 10.1256 13.50070.5,

16、 1, 0.75005 6.7500, 13.5000, 10.1250 13.50000.5, 1, 0.7500TkuTkv可得到可得到B的主特征值為的主特征值為 1 13.5000, 主特征向量為主特征向量為 v1 (0.5 ,1.0, 0.7500)T ,因此，因此，A的主特征值為的主特征值為 1 = 1 +p 11.0000, 主特征向量仍為主特征向量仍為 x1 =(0.5,1,0.7500)T .k 上頁上頁下頁下頁 原點(diǎn)位移的加速方法，是一個矩陣變換方法原點(diǎn)位移的加速方法，是一個矩陣變換方法. 這這種變換容易計(jì)算，又不破壞矩陣種變換容易計(jì)算，又不破壞矩陣A的稀疏性，但的稀疏性，但

17、p的的選擇依賴對選擇依賴對A的特征值分布的大致了解的特征值分布的大致了解. 見書見書p306- -例例5.上頁上頁下頁下頁 設(shè)設(shè)ARnn為為對稱矩陣對稱矩陣，稱，稱.),(),()(xxxAxxR 為向量為向量x的的瑞利商瑞利商，其中，其中(x, x)=xTx為內(nèi)積為內(nèi)積. 由定理由定理11知道，實(shí)對稱矩陣知道，實(shí)對稱矩陣A的特征值的特征值 1及及 n可用可用瑞利商瑞利商的的極限值表示極限值表示. 下面我們將下面我們將瑞利商瑞利商應(yīng)用到用冪法計(jì)算應(yīng)用到用冪法計(jì)算實(shí)對稱矩陣實(shí)對稱矩陣A的主特征值的加速上來的主特征值的加速上來.2、瑞利商、瑞利商(Rayleigh)加速加速上頁上頁下頁下頁 定理定

18、理14 設(shè)設(shè)ARnn為為對稱矩陣對稱矩陣，特征值滿足，特征值滿足對應(yīng)的特征向量對應(yīng)的特征向量xi滿足滿足(xi, xj)=ij (單位正交向量單位正交向量) ，應(yīng)用冪法公式應(yīng)用冪法公式(2.9)計(jì)算計(jì)算A的主特征值的主特征值 1，則規(guī)范化，則規(guī)范化向量向量uk的的瑞利商瑞利商給出給出 1的較好的近似值為的較好的近似值為,121nn kkkkkkuuuAuuR2121, 由此可見，由此可見，R(uk)比比k更快的收斂于更快的收斂于 1.上頁上頁下頁下頁 證明證明 由由(2.8)式及式及,)max(,)max(00100uAuAAuvuAuAukkkkkkk )11. 2(.),(),(),(),

19、()(2121122112200001 knjkjjnjkjjkkkkkkkkkaauAuAuAuAuuuAuuR 得得上頁上頁下頁下頁 冪法的冪法的瑞利商加速迭代公式瑞利商加速迭代公式可以寫為可以寫為 kkkkkkkkkkvukuuuvAuv /), 2 , 1(),(),(1111其中其中A為為n階實(shí)對稱矩陣階實(shí)對稱矩陣.,11kkux 對給定的誤差限對給定的誤差限 ，當(dāng)，當(dāng)| kk- -1| 時，取近似值時，取近似值上頁上頁下頁下頁8.2.3 反冪法反冪法 反冪法是用于求非奇異矩陣反冪法是用于求非奇異矩陣A的的按模最小的特征按模最小的特征值和對應(yīng)特征向量值和對應(yīng)特征向量的方法的方法. 而

20、結(jié)合原點(diǎn)平移法的反冪而結(jié)合原點(diǎn)平移法的反冪法則可以求矩陣法則可以求矩陣A的任何一個的任何一個具有先了解的特征值和具有先了解的特征值和對應(yīng)的特征向量對應(yīng)的特征向量。設(shè)矩陣設(shè)矩陣A非奇異非奇異,其特征值其特征值 i (i=1,2,n) ,滿足滿足0121 nn 其相應(yīng)的特征向量其相應(yīng)的特征向量x1,x2,xn線性無關(guān)，則線性無關(guān)，則 A- -1 的特征的特征值為值為1/ i ，對應(yīng)的特征向量仍為，對應(yīng)的特征向量仍為xi (i=1,2,n).iiiiiixxAxAx11 上頁上頁下頁下頁此時此時, A- -1的特征值滿足的特征值滿足11111 nn因此因此, 對對A- -1應(yīng)用冪法應(yīng)用冪法,可求出其

21、可求出其主特征值主特征值1/ n k 和和特征向量特征向量 xn uk .從而求得從而求得A的的按模最小按模最小特征值特征值 n 1/k 和對應(yīng)的和對應(yīng)的特征向量特征向量 xn uk ，這種求這種求A- -1的方法就稱的方法就稱為為反冪法反冪法.上頁上頁下頁下頁為了避免求為了避免求A- -1, 可通過解線性方程組可通過解線性方程組Avk=uk- -1得到得到vk，采用采用LU分解法，即先對分解法，即先對A進(jìn)行進(jìn)行LU分解分解A=LU, 此時此時反冪反冪法的迭代公式法的迭代公式為為 , 2 , 1/max,1 kvuvvzUvzuLzkkkkkkkkkkk 求出求出解解求出求出解解 ), 2 ,

22、 1(max11 k/vuvuAvkkkkkkk knknux ,1 反冪法的迭代公式反冪法的迭代公式為為上頁上頁下頁下頁對給定的誤差對給定的誤差 ，當(dāng)，當(dāng)|kk- -1| n|0，則對任意非零初始向量則對任意非零初始向量u0(an 0) ，由反冪法計(jì)算公，由反冪法計(jì)算公式構(gòu)造的向量序列式構(gòu)造的向量序列vk，uk滿足滿足 ,)max(limnnkkxxu .1)max(limnkkv 上頁上頁下頁下頁 在反冪法中也可以用在反冪法中也可以用原點(diǎn)平移法原點(diǎn)平移法加速迭代過程加速迭代過程，或或求其它特征值與其對應(yīng)的特征向量求其它特征值與其對應(yīng)的特征向量. 如果矩陣如果矩陣(A- -pI)- -1存在

23、，顯然其特征值為存在，顯然其特征值為,1,1,121pppn 對應(yīng)的特征向量仍然是對應(yīng)的特征向量仍然是x1,x2,xn，現(xiàn)對矩陣，現(xiàn)對矩陣(A- -pI)- -1應(yīng)用冪法，得到反冪法的迭代公式應(yīng)用冪法，得到反冪法的迭代公式)12. 2()., 2 , 1()max(/.,)(, 01100 kvuupIAvvukkkkk 初始向量初始向量上頁上頁下頁下頁 如果如果p是是A的特征值的特征值 j的一個近似值，且設(shè)的一個近似值，且設(shè) j與其它與其它特征值是分離的，即特征值是分離的，即),(jippij 就是說就是說1/( j- -p)是矩陣是矩陣 (A- -pI)- -1的主特征值，可用反冪的主特征

24、值，可用反冪法法(2.12)計(jì)算特征值及特征向量計(jì)算特征值及特征向量. 設(shè)設(shè)ARnn有有 n個線性無關(guān)的特征向量個線性無關(guān)的特征向量 x1,x2, xn，則則),0(10 jniiiaxau,)max()(0)1(0upIAupIAvkkk 上頁上頁下頁下頁,)max()(00upIAupIAukkk 其中其中.)()(10 niikiikxpaupIA 同理可得：同理可得：上頁上頁下頁下頁 定理定理16 設(shè)設(shè)ARnn有有n個線性無關(guān)的特征向量，個線性無關(guān)的特征向量， 矩陣矩陣A的特征值及對應(yīng)的特征向量分別記為的特征值及對應(yīng)的特征向量分別記為 i 及及xi (i=1,2,n)，而，而p為為 j

25、的近似值，的近似值，(A- -pI)- -1存在，且存在，且 ,)max(limjjkkxxu jkjkkvppv )max(1,1)max(lim即即則對任意非零初始向量則對任意非零初始向量u0(aj 0) ，由反冪法計(jì)算公式，由反冪法計(jì)算公式(2.12)構(gòu)造的向量序列構(gòu)造的向量序列vk，uk滿足滿足. )( |jippij . |min/ |pprijij 且收斂速度為且收斂速度為上頁上頁下頁下頁 由該定理知，對由該定理知，對A- -pI(其中其中p j)應(yīng)用反冪法，可應(yīng)用反冪法，可用來計(jì)算特征向量用來計(jì)算特征向量xj，只要選擇，只要選擇p是是 j的一個較好的近的一個較好的近似且特征值分離

26、情況較好，一般似且特征值分離情況較好，一般r很小，常常只要迭很小，常常只要迭代一二次就可完成特征向量的計(jì)算代一二次就可完成特征向量的計(jì)算.反冪法迭代公式中的反冪法迭代公式中的vk是通過解方程組是通過解方程組.)(1 kkuvpIA求得的求得的, 為了節(jié)省工作量為了節(jié)省工作量, 可以先將可以先將A- -pI進(jìn)行三角分解進(jìn)行三角分解.)(LUpIAP 于是求于是求vk相對于解兩個三角形方程組相對于解兩個三角形方程組.,1kkkkyUvPuLy 上頁上頁下頁下頁實(shí)驗(yàn)表明實(shí)驗(yàn)表明, 按下述方法選擇按下述方法選擇u0是較好的是較好的: 選選u0使使)13. 2()1 , 1 , 1(011 PuLUv用

27、回代求解用回代求解(2.13)即得即得v1,然后再按公式然后再按公式(2.12)進(jìn)行迭代進(jìn)行迭代.反冪法計(jì)算公式見書反冪法計(jì)算公式見書p311.前面已提到前面已提到.見書見書p311- -例例6.上頁上頁下頁下頁8.3 豪斯霍爾德方法豪斯霍爾德方法 (1)用用初等反射矩陣作正交相似變換初等反射矩陣作正交相似變換約化一般約化一般實(shí)矩陣實(shí)矩陣A為為上海森伯格矩陣上海森伯格矩陣.8.3.1 引言引言 本節(jié)討論本節(jié)討論兩個問題兩個問題 (2)用用初等反射矩陣作正交相似變換初等反射矩陣作正交相似變換約化對稱約化對稱矩陣矩陣A為為對稱三對角矩陣對稱三對角矩陣. 于是，于是，求原矩陣特征值問題求原矩陣特征值

28、問題，就，就轉(zhuǎn)化為轉(zhuǎn)化為求上求上海森伯格矩陣海森伯格矩陣或或?qū)ΨQ三對角矩陣的特征值對稱三對角矩陣的特征值問題問題.上頁上頁下頁下頁8.3.2 用正交相似變換用正交相似變換 約化一般實(shí)矩陣為上海森伯格矩陣約化一般實(shí)矩陣為上海森伯格矩陣 設(shè)設(shè)ARnn，下面來說明，可選擇初等反射矩，下面來說明，可選擇初等反射矩陣陣U1,U2,Un- -2使使A經(jīng)正交相似變換約化為一個上海經(jīng)正交相似變換約化為一個上海森伯格陣森伯格陣.(1) 設(shè)設(shè),)1(221)1(1211212222111211 AcAaaaaaaaaaaAnnnnnn上頁上頁下頁下頁)1 . 3().(,)(sgn(2111111112/1221

29、211 aecuaanii 其中其中c1=(a21,an1)TRn- -1 ,不妨設(shè)不妨設(shè)c10，否則這一步不，否則這一步不需要約化需要約化. 于是于是, 可選擇初等反射陣可選擇初等反射陣 使使 ，其中，其中TuuIR11111 1111ecR 令令,111 RU上頁上頁下頁下頁則則 1)1(221111)1(12111112RARcRRAaUAUA,000)2(221)2(12)2(11)2()2(3)2(2)2(3)2(33)2(32)2(2)2(23)2(221)2(1)2(13)2(1211 AcAAaaaaaaaaaaaaannnnnnn 其中其中.,),()2()2()2(222)

30、2(2)2(322 nnnTnRARaac上頁上頁下頁下頁(2) 第第k步約化：重復(fù)上述過程，設(shè)對步約化：重復(fù)上述過程，設(shè)對A已完成第已完成第1步步,第第k- -1步正交相似變換，即有步正交相似變換，即有,111 kkkkUAUA或或,11111 kkkUUAUUA且且 )()(1,)()(, 1)(1, 1)(, 1)()(1,)(1)(2)(1,2)(2)1(1,2)2(221)(1)(1, 1)(1)1(1, 1)2(12)1(11knnkknknkknkkkkkkkkknkkkkkkkknkkkkkkknkkkkkkkaaaaaaaaaaaaaaaaaaaaA 上頁上頁下頁下頁,0)(

31、22)(12)(11knkAcAAknkkkkk 其中其中 為為k階上海森階上海森伯格陣，伯格陣，)(11)()(, 1,),(kknTknkkkkkARaac .)()()(22knknkRA 設(shè)設(shè)ck0, 于是可選擇初等反射陣于是可選擇初等反射陣Rk使使 其中，其中，Rk計(jì)算公式為計(jì)算公式為,1ecRkkk 上頁上頁下頁下頁)2 . 3(.),(,)()(sgn(1)(, 112/112)()(, 1 TkkkkkkkkkkkkknkikikkkkkuuIRaecuaa 令令, kkRIU則則)3 . 3(00)1(221)1(12)1(11)(22)(12)1(111 kkkkkkkkk

32、kkkkkkkAcAARARcRRAAUAUA上頁上頁下頁下頁221122 nnUUAUUUU其中其中 為為k+1階上海森伯格陣，第階上海森伯格陣，第k步約化只需計(jì)步約化只需計(jì)算算 及及 (當(dāng)當(dāng)A為對稱矩陣時，只需要計(jì)為對稱矩陣時，只需要計(jì)算算 ).)1(11 kAkkRA)(12kkkRAR)(22kkkRAR)(22(3) 重復(fù)上述過程，則有重復(fù)上述過程，則有.1)(1)1(1, 12)3(332)2(22111 nnnnnnnnnAaaaaa 上頁上頁下頁下頁 定理定理17 (豪斯霍爾德約化矩陣為上海森伯格陣豪斯霍爾德約化矩陣為上海森伯格陣) 設(shè)設(shè)ARnn則存在初等反射矩陣則存在初等反射

33、矩陣U1,U2,Un- -2 使使.00221122HAUUUUAUUUUTnn 為為上海森伯格矩陣上海森伯格矩陣.總結(jié)上述結(jié)論，有總結(jié)上述結(jié)論，有 算法算法1 (豪斯霍爾德約化矩陣為上海森伯格陣豪斯霍爾德約化矩陣為上海森伯格陣) 設(shè)設(shè)ARnn，本算法計(jì)算，本算法計(jì)算U0TAU0=H(上海森伯格型上海森伯格型)，其，其中中U0=U1U2Un- -2為初等反射陣的乘積為初等反射陣的乘積.1. U0I上頁上頁下頁下頁2. 對于對于k=1,2,n- -2(1) 計(jì)算初等反射陣計(jì)算初等反射陣Rk使使本算法約需要本算法約需要5n3/3次乘法運(yùn)算，要明顯形成次乘法運(yùn)算，要明顯形成U0還需要附加還需要附加2

34、n3/3次乘法次乘法.,1ecRkkk (2) 約化計(jì)算約化計(jì)算, kkkkRIUAUUA(3) U0U0Uk上頁上頁下頁下頁例例7 用用豪斯霍爾德方法豪斯霍爾德方法將矩陣將矩陣 7242327341AA約化為約化為上海森伯格陣上海森伯格陣. 解解 選取初等反射陣選取初等反射陣R1使使 , 其中其中c1=(2,4)T.1111ecR (1) 計(jì)算計(jì)算R1:)() 1 , 5 . 0(, 4) 4 , 2max(11規(guī)范化規(guī)范化Tcc .,472136. 4,809017. 1)5 . 0(,)1,618034. 1(,118034. 125. 11111111111TTuuIRecu 上頁上頁

35、下頁下頁.1111ecR 則有則有(2) 約化計(jì)算約化計(jì)算:,111 RU則得到則得到上海森伯格陣上海森伯格陣為為.200000. 2399999. 00400000. 0799999. 7472136. 4447214. 0602631. 74112HAUUA 上頁上頁下頁下頁8.3.3 用正交相似變換用正交相似變換 約化對稱矩陣為對稱三對角矩陣約化對稱矩陣為對稱三對角矩陣 定理定理18 (豪斯霍爾德約化對稱矩陣為對稱三對豪斯霍爾德約化對稱矩陣為對稱三對角矩陣角矩陣) 設(shè)設(shè)ARnn為對稱矩陣，則存在初等反射矩為對稱矩陣，則存在初等反射矩陣陣U1,U2,Un- -2使使.11122211122

36、1122CcbbcbbcbbcUUAUUUUnnnnnn 為為對稱三對角矩陣對稱三對角矩陣.上頁上頁下頁下頁 證明證明 由定理由定理17, 存在初等反射矩陣存在初等反射矩陣U1,U2,Un- -2 使使 為上海森伯格為上海森伯格陣，且陣，且An- -1亦是對稱陣，因此，亦是對稱陣，因此，An- -1為對稱三對角陣為對稱三對角陣.1221122 nnnAHUUAUUUU 由上面討論可知，當(dāng)由上面討論可知，當(dāng)A為對稱陣時，由為對稱陣時，由AkAk+1 =Ak Uk Ak一步約化計(jì)算中只需計(jì)算一步約化計(jì)算中只需計(jì)算Rk及及Rk A22(k)Rk . 又又由于由于A的對稱性，故只需計(jì)算的對稱性，故只需

37、計(jì)算Rk A22(k)Rk的對角線以下的對角線以下元素元素. 注意到注意到).)()(221)(221)(22TkkkkkTkkkkkkuuAAuuIRAR 上頁上頁下頁下頁引進(jìn)記號引進(jìn)記號)., 1;, 1()(22)(22ikjnkiuttuARARTkkTkkkkkk ,)(221knkkkkRuAr ,)(21knkkTkkkkRururt 則有則有對對稱陣對對稱陣A用初等反射陣正交相似約化為對角三用初等反射陣正交相似約化為對角三對角陣大約需要對角陣大約需要2n3/3次乘法次乘法.用正交矩陣進(jìn)行相似約化有一些特點(diǎn)，如構(gòu)造的，用正交矩陣進(jìn)行相似約化有一些特點(diǎn)，如構(gòu)造的， Uk容易求逆，且

38、容易求逆，且Uk的元素?cái)?shù)量級不大，這個算法是十的元素?cái)?shù)量級不大，這個算法是十分穩(wěn)定的分穩(wěn)定的.算法算法2見書見書p318.上頁上頁下頁下頁8.4 QR 方方 法法8.4.1 QR算法算法Rutishauser(1958)利用矩陣的三角分解提出了計(jì)利用矩陣的三角分解提出了計(jì)算矩陣特征值的算矩陣特征值的LR算法，算法，F(xiàn)rancis(1961,1962)利用矩利用矩陣的陣的QR分解建立了分解建立了計(jì)算矩陣特征值計(jì)算矩陣特征值的的QR算法算法.QR方法是一種變換方法，是計(jì)算一般矩陣方法是一種變換方法，是計(jì)算一般矩陣(中小中小型矩陣型矩陣)全部特征值全部特征值問題的問題的最有效方法之一最有效方法之一.

39、上頁上頁下頁下頁 (1) 上海森伯格矩陣上海森伯格矩陣的的全部特征值全部特征值問題；問題； (2) 計(jì)算計(jì)算對稱三對角矩陣對稱三對角矩陣的的全部特征值全部特征值問題，問題， 目前目前QR方法方法主要主要用來計(jì)算：用來計(jì)算：且且QR方法具有收斂快，算法穩(wěn)定等特點(diǎn)方法具有收斂快，算法穩(wěn)定等特點(diǎn). 對于一般矩陣對于一般矩陣ARnn (或?qū)ΨQ矩陣或?qū)ΨQ矩陣)，則首先用，則首先用豪斯霍爾德方法將豪斯霍爾德方法將A化為上海森伯格陣化為上海森伯格陣B(或?qū)ΨQ三對或?qū)ΨQ三對角陣角陣)，然后再用，然后再用QR方法計(jì)算方法計(jì)算B的全部特征值的全部特征值. 設(shè)設(shè)ARnn，且，且A對進(jìn)行對進(jìn)行QR分解，即分解，即A=

40、QR，上頁上頁下頁下頁其中其中R為上三角陣為上三角陣, Q為正交陣為正交陣, 于是可得到一新矩陣于是可得到一新矩陣B=RQ=QTAQ.顯然，顯然，B是由是由A經(jīng)過正交相似變換得到，因此經(jīng)過正交相似變換得到，因此B與與A的的特征值相同特征值相同. 再對再對B進(jìn)行進(jìn)行QR分解，又可得一新矩陣分解，又可得一新矩陣,重復(fù)這一過程可得到矩陣序列：重復(fù)這一過程可得到矩陣序列： 設(shè)設(shè)A=A1 將將A1進(jìn)行進(jìn)行QR分解分解A1=Q1R1 作矩陣作矩陣A2=R1Q1=Q1TR1Q1 QR算法，就是利用矩陣的算法，就是利用矩陣的QR分解，按上述遞分解，按上述遞推法則構(gòu)造矩陣序列推法則構(gòu)造矩陣序列Ak的過程的過程. 只要只要A為非奇異矩為非奇異矩陣，則由陣，則由QR算法就完全確定算法就完全確定Ak.上頁上頁下頁下頁 定理定理19 (基本基本QR方法方法) 設(shè)設(shè)A=A1Rnn, 構(gòu)造構(gòu)造QR算法算法:)1 . 4(), 2 , 1(),(1 kQRARIQQRQAkkkkkTkkkk為上三角陣為上三角陣其中其中則則有有記記,1221RRRRQQQQkkkk ;,111kTkkkkAQQAAA 即即相相似似于于）（;)()()2(1211211kTkkTkkQA