數(shù)值分析(11)QR方法教學(xué)文稿

1、數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析 第四節(jié)第四節(jié) 求矩陣全部求矩陣全部(qunb)(qunb)特征值特征值的的QRQR方法方法一、矩陣一、矩陣(j zhn)的正交分解的正交分解, ( ),m nm nn nn nn nARmn r AnAQRQRRRRmnQRRR 是是列列滿滿秩秩矩矩陣陣（），存存在在分分解解式式其其中中列列法法正正交交矩矩陣陣，非非奇奇異異上上三三角角陣陣。若若限限定定 陣陣對對角角元元符符號號，定定理理4-44-4則則分分解解式式是是唯唯一一的的。當(dāng)當(dāng)時時正正交交陣陣非非奇奇異異上上三三角角陣陣。第一頁，共64頁。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值數(shù)值(shz)分析分析數(shù)

2、值數(shù)值(shz)分析分析11112112112111221111221,nnn nnTnnTTkkknnAHHHRH HHRQRQH HHRRQ AQ AHHH H AHHHQQHHH H其中其中為正交陣為正交陣 1、用Householder變換(binhun)對A作QR分解 有兩種情況1221(1,2,1)1n nknnnnHouseholderHRknHHH HAARR（構(gòu)造陣構(gòu)造陣則（上三角陣）則（上三角陣）非奇異）非奇異 第二頁，共64頁。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值數(shù)值(shz)分分析析數(shù)值數(shù)值(shz)分析分析(1)(1)(1)(1)111121(2)(2)(2)11121

3、(2)(2)(2)(2)(2)(2)22212(2)(2)2,0,0nnnnnnnH AHHHaaaaaAaa n nARA 化化矩矩陣陣為為上上三三角角陣陣, ,只只須須依依次次將將各各列列對對角角線線下下元元素素化化為為零零(1)(1)(1)(1)12(1)(1)(1)11111,(,0,0)nTAAAHH 記記對的第一列構(gòu)造使對的第一列構(gòu)造使第三頁，共64頁。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值數(shù)值(shz)分分析析數(shù)值數(shù)值(shz)分析分析(2)(2)(2)(2)2222122,(2)(2)(2)(2)221222(2)(2)(2)(2)1112131(3)(3)(3)22232(3)

4、(3)(3)(3)(3)1233(3)(3)3(,0,0),0,000TnnnnnnnAHHaH AHHHaaaaaaaAaaa 對的第二列構(gòu)造使對的第二列構(gòu)造使( )( )( )( )( )12( )( )( )11,(,0,0)kkkkknkkkTkkkkkkkAAHHaa 一般地,設(shè)按列分塊，一般地,設(shè)按列分塊，構(gòu)造使構(gòu)造使 )1()1(2)1(1)1()()(2)(1)(, knkkkknkkkkkkkAHHHAH 第四頁，共64頁。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值數(shù)值(shz)分析分析數(shù)值數(shù)值(shz)分析分析(2)(2)(2)1111( )( )( )( )( )( )12(

5、)( )(2)(2)(2)(2)1111,11(1)(1),1,(1)1,11,0,000000knkkkkkkkkkkknkkknkknknnkknkkkk kk nkkkknaaaH AHHHHaaaaaaaaaaaa (1)(1)(1)(1)12(1)(1)(1),1,00kkkknkkkn kn nAaa 第五頁，共64頁。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值數(shù)值(shz)分析分析數(shù)值數(shù)值(shz)分析分析( )( )1( )( )22( )( )( )( )( )1,1()()() )()(0,.,0,.,)kkTkknkkkkkiki kkkkkkkkkkkkkkkknkHIUUs

6、ign aaaUaaa (1)( )(1)(1)(1)( )( )( )1212,kkkkkkkkknkkknAH AHHH 計計算算，即即( )(1)( )( )( )( )( )( )( )( )( )( )( )1() )1 ()1 ()(,1, )kkkkTkkjjjkkkkTkjjkkkTkkjjkHIUUUUUUjk kn ，第六頁，共64頁。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值數(shù)值(shz)分分析析數(shù)值數(shù)值(shz)分析分析(1)(1)(1)? (1,., ).kkkkkkkikaaaikn 可以不用上面公式計算，？；可以不用上面公式計算，？；思考：思考：()()(1)()(),

7、1,1(1)()(2),1,nkkjlljlkkkkkijijjijk kntuaik knaat u ( )(1)( )( )( )( )( )( )( )( )( )( )( )1() )1 ()1 ()(,1, )kkkkTkkjjjkkkkTkjjkkkTkkjjkHIUUUUUUjk kn ，第七頁，共64頁。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值數(shù)值(shz)分析分析數(shù)值數(shù)值(shz)分析分析化化為為上上三三角角陣陣。矩矩陣陣可可將將陣陣連連乘乘矩矩陣陣用用一一系系列列AAHHHHAAHnn1221)1 (,1221( )( ) 11,2,1,1,1 1 () ,1, 2nnnkjl

8、ljl kkkijijjiHHH H Aknjk kntuaik knaat uAA 計計算算。、（ ）（2 2）、輸輸出出結(jié)結(jié)果果。計計算算值值覆覆蓋蓋 ，輸輸出出 即即為為最最終終計計算算結(jié)結(jié)果果。第八頁，共64頁。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值數(shù)值(shz)分分析析數(shù)值數(shù)值(shz)分析分析121nQH HH 計算正交陣計算正交陣(1)(2)(1)1(1)( )( )121,1,.1.kkknnQIQQHQQHknQH HH TknTkknnknknkkqqqqQ)()(1)()(1)(1)(11)(. 記記第九頁，共64頁。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值數(shù)值(shz)分析分

9、析數(shù)值數(shù)值(shz)分析分析)1(.)()()()(1)()(1)(1)(11)()1()1()1(1TkkkTknTkkknnknknkkkkTknTkUUIHqqqqHQQ (1)( )( )( )( )1()kTk Tk Tkk TiiikUU )()()1()()(,.,1,)2(1)1(,.,1kjikijkijnklklkilkiutqqnkkjuqtni 第十頁，共64頁。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值數(shù)值(shz)分析分析數(shù)值數(shù)值(shz)分析分析用用Household方法對矩陣方法對矩陣(j zhn)A作正交分解作正交分解,A=QR。1( )( )2( )2( )( )

10、( )1,( )1,2,.,1()() ) ,()(0,.,0,.11.(),)nkkkkkkikkkkkki kkkkkTkkkkknkkkTkkknsign aaaUHIUUaaa 計計算算( )(1)2.,kkkRH AA 計計算算上上三三角角陣陣( )( )(1)( )( ),1,1(1)() (2),1, nkkjlljl kkkkkijijjijk kntuaik knaat u 第十一頁，共64頁。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值數(shù)值(shz)分析分析數(shù)值數(shù)值(shz)分析分析(1)( )(1)3.kkkQIQHQQ 計計算算正正交交陣陣( )( )(1)( )( )1,1(

11、1)(2),1,.,nkkiilll kkkkkijijijintqujk knqqt u 第十二頁，共64頁。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值數(shù)值(shz)分析分析數(shù)值數(shù)值(shz)分析分析nmnnTmmnnnnRAHHHHAQRRHHHHQQRRHHHHA 121121121為為正正交交陣陣其其中中2, ()m nARmn r An （ ）列列滿滿秩秩上上三三角角陣陣則則陣陣構(gòu)構(gòu)造造nnnmnnmmkRRRORORAHHHHnkRHrHouseholde 0), 2 , 1(121第十三頁，共64頁。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值數(shù)值(shz)分析分析數(shù)值數(shù)值(shz)分析分析n

12、mmmnmRRORQAHnnnmnmRQASmnn ,法法法法Matlab調(diào)用格式調(diào)用格式(g shi)： q,r=qr(a) q,r=qr(a,0):緊湊格式緊湊格式(g shi)緊湊格式緊湊格式法結(jié)果不一樣。法結(jié)果不一樣。法和法和方法結(jié)果一樣。方法結(jié)果一樣。正交化方法和正交化方法和HSmnArnmRArHouseholdeSchmidtRAnmnn)(,(, 第十四頁，共64頁。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值數(shù)值(shz)分析分析數(shù)值數(shù)值(shz)分析分析算法算法(sun f)：用：用Household方法對矩陣方法對矩陣A作正交分解作正交分解,A=QR。1( )( )2( )2(

13、)( )( )()( )1,1,2,.,()() ) ,()(0,.,0,11.(),.,)mkkkkkkikkkkkTkkki kkkkkTkkkkkkkmkknsign aaaUaaHIUaU 計計算算( )(1)2.,kkkRH AA 計計算算上上三三角角陣陣( )( )(1)( )( ),1,1(1)() (2),1, mkkjlljl kkkkkijijjijk kntuaik kmaat u (, ( )m nARmn r An 第十五頁，共64頁。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值數(shù)值(shz)分析分析數(shù)值數(shù)值(shz)分析分析(1)( )(1)3.kkkQIQHQQ 計計算算

14、正正交交陣陣 ( )( )(1)( )( )1,1(1)(2),1,.,nkkiilll kkkkkijijijimtqujk knqqt u第十六頁，共64頁。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值數(shù)值(shz)分析分析數(shù)值數(shù)值(shz)分析分析例：用例：用HouseholderHouseholder方法方法(fngf)(fngf)求矩陣求矩陣A A的正交分的正交分解，解， 即即A=QRA=QR，其中，其中211010211A ( 2,1,2) ,(3,0,0) ,( 5,1,2)125510105101121512514215151102410211331410510110551421115

15、010211TTTTTxyuxyuuHIu uHARQH 一一：0 0法法第十七頁，共64頁。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值數(shù)值(shz)分析分析數(shù)值數(shù)值(shz)分析分析11111111111222( 2,1,2) ,( 3,0,0) ,(1,1,2)11122121121112122331224221331413114(14/11,3/11, 4/11) ,(14/11, 5/11,0) ,TTTTTTTxyuxyu uHIu uH AAxy 法法二二0 0：0 02222222212(0,8/11, 4/11)100050011210840345510420431051033141

16、15142,0515111021100TTTTuxyu uHIu uQH HRQ A 第十八頁，共64頁。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析Householder變換變換(binhun)的應(yīng)用的應(yīng)用12第十九頁，共64頁。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析2、用Givens變換(binhun)對A作QR分解2、用Givens變換(binhun)對A作QR分解第二十頁，共64頁。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值數(shù)值(shz)分分析析數(shù)值數(shù)值(shz)分析分析 0:.:.QRAnnnnnmnmQRA 0:.:.nmmmnmQRA 0.00:.:.第二十一頁，共64頁。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分

17、析二、求矩陣二、求矩陣(j zhn)(j zhn)全部特征值的全部特征值的QRQR方法方法 60年代出現(xiàn)(chxin)的QR算法是目前計算中小型矩陣的全部特征值與特征向量的最有效方法。 理論依據(jù)：任一非奇異實(shí)矩陣都可分解成一個正交矩陣Q和一個上三角矩陣R的乘積，而且當(dāng)R的對角元符號取定時，分解是唯一的。 11 QRQR (1,2,). kkkkkkAQ RkAR QAAA 方方法法的的基基本本思思想想是是利利用用矩矩陣陣的的分分解解通通過過迭迭代代格格式式將將化化成成相相似似的的上上三三角角陣陣（或或分分塊塊上上三三角角陣陣），從從而而求求出出矩矩陣陣的的全全部部特特征征值值與與特特征征向向量

18、量。第二十二頁，共64頁。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析111111121112, ( 2,3,)kkAAQ RQARAR QQAQAAAAkAA 由由即即。于于是是即即與與相相似似。同同理理可可得得，與與相相似似。故故與與有有相相同同的的特特征征值值。 可證，在一定條件下，基本可證，在一定條件下，基本QRQR方法產(chǎn)生的矩陣序列方法產(chǎn)生的矩陣序列AkAk “ “基本基本”收斂于一個收斂于一個(y )(y )上三角陣（或分塊上三角陣（或分塊上三角陣）。即主對角線（或主對角線子塊）及其以下上三角陣）。即主對角線（或主對角線子塊）及其以下元素均收斂，主對角線（或主對角線子塊）以上元素可元素均收斂，

19、主對角線（或主對角線子塊）以上元素可以不收斂。特別的，如果以不收斂。特別的，如果A A是實(shí)對稱陣，則是實(shí)對稱陣，則Ak Ak “ “基基本本”收斂于對角矩陣。收斂于對角矩陣。第二十三頁，共64頁。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析 矩陣(j zhn)的正交相似化簡 ,1n nHACUUAURScRAhur設(shè)設(shè)存存在在酉酉矩矩陣陣使使得得式式中中 是是上上三三角角陣陣，它它的的對對角角線線元元素素是是定定理理（定定理理）的的特特征征值值. .,n nn nTSchurARAnQRQ AQRRA設(shè)設(shè)若若 的的 個個特特征征值值都都是是實(shí)實(shí)數(shù)數(shù) 則則存存在在正正交交陣陣使使得得式式中中 是是實(shí)實(shí)上上三

20、三角角陣陣 它它的的對對角角定定理理2 2（線線元元素素是是實(shí)實(shí)數(shù)數(shù)域域上上的的的的定定理理）特特征征值值. .Matlab調(diào)用調(diào)用(dioyng)形式形式 Q,R=schur(A)IAAAACAHHnn 酉酉陣陣第二十四頁，共64頁。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析,.n nn nTARQRQ AQ 當(dāng)當(dāng)?shù)徊荒苣鼙１ＷC證其其特特征征值值都都是是實(shí)實(shí)數(shù)數(shù)時時 可可以以正正交交相相似似于于一一個個擬擬上上三三角角陣陣即即存存在在正正交交陣陣使使得得定定理理3 3第二十五頁，共64頁。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析.:(3):A 的特征值有復(fù)特征值的特征值有復(fù)特征值*.*(2)*:*A的的特

21、特征征值值都都為為實(shí)實(shí)的的特特征征值值0(1)0AAn可可對對角角化化有有 個個線線性性無無關(guān)關(guān)的的特特相相似似標(biāo)標(biāo)征征形形向向量量準(zhǔn)準(zhǔn)：第二十六頁，共64頁。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析n實(shí)方陣實(shí)方陣(fn(fn zhn) zhn)的正交相似化簡的正交相似化簡: : Q,R=schur(A)Q,R=schur(A)nA1=3 1 0;-4 -1 0;4 8 -2, A1=3 1 0;-4 -1 0;4 8 -2, n Q1,R1=schur(A1) Q1,R1=schur(A1)nA2=9 -31 49 30;1 0 0 0;1 1 0 0;0 0 1 0, A2=9 -31 49 30

22、;1 0 0 0;1 1 0 0;0 0 1 0, n Q2,R2=schur(A2) Q2,R2=schur(A2)nA3=2 1 1;1 4 -1;1 -1 3, A3=2 1 1;1 4 -1;1 -1 3, n Q3,R3=schur(A3) Q3,R3=schur(A3)n實(shí)方陣實(shí)方陣(fn(fn zhn) zhn)的上的上HessenbergHessenberg分分解解:P,H=hess(A):P,H=hess(A)nA1=3 1 0;-4 -1 0;4 8 -2, A1=3 1 0;-4 -1 0;4 8 -2, n P,H=hess(A1) P,H=hess(A1)nP P*

23、*HH* *inv(P)inv(P)第二十七頁，共64頁。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析*n nACA AAAI酉酉陣陣 第二十八頁，共64頁。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析第二十九頁，共64頁。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析第三十頁，共64頁。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析QR方法的實(shí)際計算方法的實(shí)際計算(j sun)步驟步驟HouseholderAHessenbergB 用用陣陣作作正正交交相相似似變變換換上上第第陣陣一一步步.*:* 1kkkGivenkkkBQ RBBR Q 用變換產(chǎn)生迭代序列用變換產(chǎn)生迭代序列第二步第二步12*n 第三十一頁，共64頁。數(shù)值分析數(shù)值分析數(shù)值分析

24、數(shù)值分析HouseholderAB 用用陣陣作作正正交交相相似似變變換換（對對稱稱陣陣）三三對對角角陣陣* 第三十二頁，共64頁。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析1 1、化一般、化一般(ybn)(ybn)矩陣為上矩陣為上HessenbergHessenberg陣陣111211121222123233311 (2,3,), Househ old e rnnnnnnnnniihhhhhhhhhhhHhhhinA 稱稱形形如如 的的矩矩陣陣為為上上海海森森堡堡（H H e es ss se en nb be er rg g) )陣陣。如如果果此此對對角角線線元元全全不不為為零零 則則稱稱該該矩矩陣陣

25、為為不不可可約約的的上上H H e es ss se en nb be er rg g矩矩陣陣。討討論論用用變變換換將將一一般般矩矩陣陣相相似似變變換換成成H H e es ss se en nb be er rg g陣陣第三十三頁，共64頁。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析11111111 ,1000 01 HouseholderHHH AHHHHHnHouseholder 首首先先，選選取取矩矩陣陣使使得得經(jīng)經(jīng)相相似似變變換換后后的的矩矩陣陣的的第第一一列列中中有有盡盡可可能能多多的的零零元元素素。為為此此，應(yīng)應(yīng)取取為為如如下下形形式式其其中中為為階階矩矩陣陣。11121111122112

26、1311212131(,) ,(,) ,TTTnnaa HH AHH aH A Haaaaaaaa 于于是是有有 其其中中第三十四頁，共64頁。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析222222111111.(, 0) 0,2nnnnTaaAaaHH aH AHn 只只要要取取使使得得就就會會使使得得變變換換后后的的矩矩陣陣的的第第一一列列出出現(xiàn)現(xiàn)個個零零元元。第三十五頁，共64頁。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析2211221222211221000*0100*00*0022, .nnnHouseholderHH H AH HHnnHouseholderHHHHH H AH HHHHHessenb

27、erg 同同理理，可可構(gòu)構(gòu)造造如如下下列列形形式式矩矩陣陣使使得得* *如如此此進(jìn)進(jìn)行行次次，可可以以構(gòu)構(gòu)造造個個矩矩陣陣使使得得其其中中為為上上矩矩陣陣AH。特特別別地地，當(dāng)當(dāng) 為為實(shí)實(shí)對對稱稱矩矩陣陣，則則經(jīng)經(jīng)過過上上述述正正交交變變換換后后，變變?yōu)闉槿龑墙顷囮?。第三十六頁，?4頁。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析1221522 23 2105 2 22 2 021002412,022, (2,2)2(1,0)(22,2) :TTTHouseholderAAHouseholderHHu 用用變變換換將將矩矩陣陣 化化成成上上H H e es ss se e例例解解n nb be e

28、r rg g陣陣。求求矩矩陣陣滿滿：足足，第三十七頁，共64頁。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析22 22222210442220122222442210000100220022220022TTuuHIu uH 第三十八頁，共64頁。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析22 100052223201001052 22 222002202102202410022100052510100103222 000223220012220022HH AH 于于 是是 有有第三十九頁，共64頁。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析用用Household方法對矩陣方法對矩陣A作正交相似作正交相似(xin s)變變換換

29、, 使使A相似相似(xin s)與上與上Hessenberg陣，算法如下：陣，算法如下：(1)(1)111221111111(1)112,1,2,.,21(1)()()() ) ,()(0,.,0,.,)kkTkknkkkiki kkkkkkkkkkkknkknHIUUsign aaaUaaa ，計算計算1(2)kHAA計計算算 (1)11(1),1,11()21,nkjlljlkkkijijjijk kntuaiknaat u （ ）（ ）第四十頁，共64頁。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析(1)11(1)1,.,1(1)(2)1,.,nkiilll kkkijijijinta ujknaa

30、t u 1(3)kAHA計計算算 第四十一頁，共64頁。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析2 2、上、上HessenbergHessenberg陣的陣的QRQR分解分解(fnji)(fnji)對上對上Hessenberg陣只需要將其次對角線上的陣只需要將其次對角線上的元素約化為零，用元素約化為零，用Given變換比用變換比用Householder變變換更節(jié)省換更節(jié)省(jishng)計算量。計算量。第四十二頁，共64頁。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析用用 GivensGivens變換變換(binhun)(binhun)對上對上HessenbergHessenberg陣陣B B作作QRQR分解分解

31、(1)(1)(1)11121(1)(1)(1)21222(1)(1)1 1 nnnnnnbbbbbbBbbnGivensBQR 對對上上H essenberg陣H essenberg陣, ,通通常常用用個個變變換換陣陣可可將將它它化化成成上上三三角角矩矩陣陣，從從而而得得到到 的的分分解解式式。( ,1)(3,2) (2,1)J n nJJBR(2,1)(3,2)( ,1),記TTTQJJJn nBQR即：即：(2,1)(3,2)( ,1)TTTBJJJn nR第四十三頁，共64頁。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析(1)211111(2)(2)(2)112131(2)(2)(2)22232(2

32、)(2)(2)1232333(2)(2)1 0(cossin00sincos00(1,2)0011(1,2) nnnnnnnbRrbbbbbbRBBbbbbb 具具體體步步驟驟為為：設(shè)設(shè)否否則則進(jìn)進(jìn)行行下下一一步步），取取旋旋轉(zhuǎn)轉(zhuǎn)矩矩陣陣則則(1)(1)(1)(1)1121111112111 cos, sin, .bbrbbrr 其其中中J(2,1)J(2,1)J第四十四頁，共64頁。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析2322222( 3 )( 3 )( 3 )( 3 )11213111( 3 )( 3 )( 3 )223212( 3 )( 3 )( 3 )333132( 3 )( 3 )434

33、1 0(10cossinsincos (3, 2)11 (3 , 2)nnnnnnnbRrbbbbrbbbbbbRBbb （）設(shè)設(shè)否否 則則 進(jìn)進(jìn) 行行 下下 一一 步步 ） ， 再再 取取 旋旋 轉(zhuǎn)轉(zhuǎn) 矩矩 陣陣 則則3( 3 )4( 3 )( 3 )1( 2 )( 2 )( 2 )2( 2 )23222222223222 cos, sin, ()() .nnnnnBbbbbbrbbrr 其其 中中JJ第四十五頁，共64頁。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析1( )( )( )( )1111111( )( )( )11111( )( )( )1( )( )( )1111( )( )1 (1,

34、) kkkkkkkknnkkkkkkknknkkkkkknknkkkkkknknkknnnnBR kk Brbbbbrbbbbhhbbbbb 1k 假假設(shè)設(shè)上上述述過過程程已已進(jìn)進(jìn)行行了了步步，有有J第四十六頁，共64頁。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析()1()()1()2()21 0,11 (1,)cossinsincos1 cos, sin, ()() .kkkkkkkkkkkkkkkkkkkkkkkkbR kkbbrrrbb 設(shè)設(shè)取取其其中中J第四十七頁，共64頁。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析(1)(1)(1)11111(1)(1)1(1)(1)(1)111111(1)(1)(1)

35、21212(1)(1)1 (1, )1kkkkknkkkkkknkkkkkkkknknkkkkkknknkknnnnrbbbrbbR kk BBbhbbhhbbn 于于是是因因此此，最最多多做做次次旋旋轉(zhuǎn)轉(zhuǎn)變變換換，即即( )( )( )( )112131( )( )2232( )33 ( ,1) (2,1)(1,2)nnnnnnnnnnnHR n nR nnRBrbbbrbbRrbr 得得JJJJJ第四十八頁，共64頁。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析,1,22,1,1,1,1,1,1,1Hessenberg,1,2,.,1(1),(2)(1, )1,2.,(3)(1, )1,2.,i ii

36、ii iiii ki kikiki kikTk ik ik ik ik ik iA QIinaaraacsrrJ ii AAknacasaasacaQJiiQknqcqsqqsacq 輸輸入入上上陣陣計計算算計計算算,AQ輸輸出出 為為上上三三角角陣陣為為正正交交陣陣。注意此處要設(shè)置中間(zhngjin)工作單元 用用Givens方法對上方法對上Hessenberg陣陣A作正交分解作正交分解A=QR的計算的計算(j sun)步驟：步驟：第四十九頁，共64頁。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析22532644445 (6,4)64 (1,0)(652,4)10 2010.9160250.27735

37、00.8320500.55470020.2773500.08397470.5547000.832050TTTTTQRAAuuuIu u 用用方方法法求求矩矩陣陣的的全全部部特特征征值值。首首先先將將 化化成成上上H H e es ss se en nb be e例例：r rg g：陣陣，取取解解110000.8320500.55470000.5547000.832050H 于于是是 第五十頁，共64頁。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析11221111151.3867503.3282007.2111021.2307688.15384000.1538462.230767, 5( 7.21102)8

38、.774964 cos50.56980. sin0.821781 HH AHHAHQRBHrr 即即為為與與 相相似似的的上上H H e es ss se en nb be er rg g陣陣。將將進(jìn)進(jìn)行行分分解解，記記取取0.5698030.8217810(2,1)0.8217810.5698030001R 第五十一頁，共64頁。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析122222228.7749641.8015968.597089(2,1)00.4383101.91103000.1538462.230767 (0.438310)( 0.153846)0.464526, cos0.4383100.9

39、43564, sin0.1538460.331189 RBrrr 于于 是是再再 取取11100 (3, 2)00.9435640.33118900.3311890.943564 (3, 2)(2,1)8.7749641.8015968.59708900.4645262.541982001.471953RRRBR 于于 是是第五十二頁，共64頁。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析12110.5698030.7754030.272165(2,1)(3,2)0.8217810.5376430.18871200.3311890.9435643.5194824.92549110.8401170.3817

40、391.0916272.31065300.4874951.388883,11TTQRRBRQ 第第一一次次迭迭代代得得重重復(fù)復(fù)上上述述過過程程 迭迭代代次次121232.9920321.000385312.013392 0.0074962.0046951.94197100.0003250.9998952.992032,2.004695,0.999895 3,2,1.0.007496BQR 得得精精確確值值下下三三角角非非對對角角元元的的最最大大模模為為。方方法法“基基本本”收收斂斂較較慢慢。第五十三頁，共64頁。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析三、原點(diǎn)平移加速三、原點(diǎn)平移加速(ji s)(ji

41、 s)的的QRQR方法方法 ()12()11121QR,(), , kknnknnknnnnnnnnBbABBbk 理理論論分分析析和和實(shí)實(shí)際際計計算算均均表表明明，方方法法產(chǎn)產(chǎn)生生的的矩矩陣陣序序列列的的右右下下角角對對角角元元素素最最先先與與 的的特特征征值值接接近近?？煽梢砸宰C證明明，若若矩矩陣陣 的的特特征征值值滿滿足足則則的的右右下下角角對對角角元元且且收收斂斂速速度度是是線線性性的的，速速率率為為。于于是是考考慮慮原原點(diǎn)點(diǎn)平平移移的的技技巧巧來來加加快快收收斂斂速速度度，即即取取位位移移使使其其滿滿足足, ,且且11()nHIQRQR 。這這樣樣，對對用用方方法法就就可可以以加加快

42、快收收斂斂速速度度，這這就就是是帶帶原原點(diǎn)點(diǎn)平平移移的的方方法法。第五十四頁，共64頁。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析( )( )(1) 121,2, (3) . kkkkkkkkkkkkHouseholderABkHIQRHIQ RHR QIQR 具具體體步步驟驟為為：（ ）用用變變換換將將矩矩陣陣 化化成成上上H H e es ss se en nb be er rg g 陣陣 。（ ）對對取取位位移移將將進(jìn)進(jìn)行行分分解解，選選擇擇合合適適的的位位移移量量, , 對對非非對對稱稱實(shí)實(shí)矩矩陣陣的的方方法法可可以以達(dá)達(dá)到到二二階階收收斂斂第五十五頁，共64頁。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析

43、數(shù)值數(shù)值(shz)分分析析數(shù)值數(shù)值(shz)分析分析121.0(1,2,., ).m nTrrniiARA AirA 設(shè)，若的特征值為設(shè)，若的特征值為稱為矩陣稱為矩陣定定的奇異值的奇異值義義1212( ),000(,.,),.00,00000m nrTrrrrTTrARArmUnVU AVdiagAU VUVAA 設(shè)，秩則存在 階正交陣設(shè)，秩則存在 階正交陣和 階正交陣 ，使得和 階正交陣 ，使得其中且其中且稱為矩陣 的奇異值分解稱為矩陣 的奇異值分解為矩陣 的奇為矩陣 的奇定理定理異值矩陣。異值矩陣。 矩陣的奇異矩陣的奇異(qy)(qy)值分解值分解第五十六頁，共64頁。數(shù)值分析數(shù)值分析數(shù)值

44、分析數(shù)值分析數(shù)值數(shù)值(shz)分分析析數(shù)值數(shù)值(shz)分析分析22212121( ),.,.0,0TTnrrnAr A AA A 秩為半正定陣秩為半正定陣證證，故的特征值為，故的特征值為且且明明設(shè)設(shè) 11121122212222212,(,0,0)TTTTTTTTTTTrVA A VVA A VVA A V VVVA A VVA A Vdiag 于是有于是有 22212(,0,0)TTTrnVA AVA A Vdiag 于是存在 階正交陣 ，使正交相似于對角陣，即于是存在 階正交陣 ，使正交相似于對角陣，即11121121,rrnrrnVvv vvVVV VVvvVvv 其中將 分塊為其中將 分塊為其中其中 22222000TTTVA A VAVAVAV， 22221