數(shù)值分析QR方法PPT課件

1、第八講矩陣特征值與特征向量的計(jì)算（2） -Jacobi方法和QR方法第三章 矩陣特征值與特征向量的計(jì)算第1頁/共50頁常用的求特征值的方法有第2頁/共50頁上次課內(nèi)容回顧 冪法可以用來求矩陣模最大的特征值和特征向量； 反冪法可以用來求矩陣模最小的特征值和特征向量； 理論上可以用帶原點(diǎn)平移的反冪法求得矩陣所有特征值和特征向量； 在用冪法與反冪法求矩陣特征值和特征向量時(shí)，初始值u0的第一個(gè)分量不要為零； 當(dāng)|1|=| 2 |，但1= -2 時(shí)，直接冪法失敗；當(dāng)|n-1|=| n |，但n-1= -n 時(shí)，直接反冪法失敗； 當(dāng)是多重特征值時(shí)，冪法和反冪法仍有效。第3頁/共50頁Jacobi法 第4頁

2、/共50頁矩陣的兩個(gè)重要的基本性質(zhì)：（1）如 A 為實(shí)對稱矩陣，則一定存在正交矩陣 Q ，使之相似于一個(gè)對角矩陣，而該對角矩陣的對角元正是 A 的特征值。（2）一個(gè)矩陣左乘一個(gè)正交矩陣或右乘一個(gè)正交矩陣，其F范數(shù)(Frobenius)不變。1,QQQQIQAQ 22211()()nnijFFijAatrace A Atrace A Q QAQA22222()FFFFFAAQ AAQAQ第5頁/共50頁Jacobi法的基本原理第6頁/共50頁下面的矩陣是一個(gè) n 階正交矩陣：1cossin( , , )1sincos1U p q( p )( q )第7頁/共50頁cosppqquu1,iiuip

3、 qsinpqu sinqpu0, ,ijuij i jp q，(1)TpqpqUAUA(1)(1)0pqqpaa 第8頁/共50頁(1)TpqpqUAUA(1)22(1)22(1)(1)(1)(1)(1)(1)cossin2cos sinsincos2cos sincossin , ,1,2,sincos , ,1,2,1()sin2c2ppppqqpqqqppqqpqpiippiqiqiiqpiqipqqpqqppppaaaaaaaaaaaaip q inaaaaip q inaaaaa (1)(1)os2, ,ijjiijaaa i jp q cot22ppqqpqaaa(1)(1)0p

4、qqpaa第9頁/共50頁1. 令令k1，R（1）I，給定矩陣，給定矩陣A（A（1），收斂條件），收斂條件2. 找絕對值最大的找絕對值最大的3. 計(jì)算計(jì)算，sinsin 和和 coscos，其中，其中滿足滿足4.4. 計(jì)算計(jì)算A A（k k1 1）5.5. 計(jì)算計(jì)算R R（k+1)k+1)6.6. 如果如果 則停止，否則返回第則停止，否則返回第 2 2 步步( )kkkp qa( )( )( )cot2kkkkkkkkp pq qkp qaaa(1)( )2( )2( )(1)( )2( )2( )(1)(1)( )( )(1)(1)( )cossin2cos sinsincos2cos si

5、ncossin ,1,2,kkkkkkkkkkkkkkkkkkkkkkkkkkkp qp pq qp qkkkkq qp pq qp qkkkkp iipp iq ikkkkkq iiqp iaaaaaaaaaaaaip q inaaa( )cossin ,1,2,kkq ikkaip q in(1)( )kkkkp qRR U(1)( )( )(1)( )( )cossin ,1,2,sincos ,1,2,kkkkkkkkkipipiqkkkiqipiqrrainrrrin (1)2,1,()nkiji jija第10頁/共50頁( )2,1()nkki ji jijalim0kk第11頁

6、/共50頁 cf:矩陣計(jì)算矩陣計(jì)算，G.H. Golub& F. Van Loan 袁亞湘等譯，第五章袁亞湘等譯，第五章 （5.1、5.2節(jié)）節(jié)）第12頁/共50頁 QR方法是計(jì)算中小型矩陣特征值和特征向量的有效方法之一； QR方法最重要的一步是對A進(jìn)行正交分解使得AQR，其中Q為一特殊正交矩陣； 理論上，QR方法可以應(yīng)用于任何矩陣，但對以下幾類矩陣效率很高：1）對稱三對角矩陣；2）Hessenberg矩陣；3）對稱帶狀矩陣第13頁/共50頁實(shí)Schur分解定理11121222.0.0.0ssssTTTTTT第14頁/共50頁11 (1,2,.)kkkkkkAAAQ RAR Qk1Tk

7、kkkkkAR QQ A Q第15頁/共50頁(2)22,xyHxyRxn有記對任何(3) 記S為與w垂直的平面,則幾何上x與y=Hx關(guān)于平面S對稱。事實(shí)上,由得知xwwIHxyT)2( 。wxwyxT)(2第16頁/共50頁幾何意義xwyx-y上式表明向量x-y與w平行，注意到y(tǒng)與x的長度相等，于是x經(jīng)變換后的象y=Hx是x關(guān)于s對稱的向量，如圖所示。第17頁/共50頁|Ts s第18頁/共50頁與平面旋轉(zhuǎn)不同的是，鏡面反射變換可成批的消去向量的非零元。第19頁/共50頁第20頁/共50頁第21頁/共50頁第22頁/共50頁第23頁/共50頁第24頁/共50頁第25頁/共50頁第26頁/共5

8、0頁第27頁/共50頁第28頁/共50頁第29頁/共50頁第30頁/共50頁第31頁/共50頁第32頁/共50頁第33頁/共50頁第34頁/共50頁第35頁/共50頁第36頁/共50頁(1)11 (1,2,.)nkkkkkkAAAQ RAR Qk第37頁/共50頁帶原點(diǎn)位移的QR 方法(1)11 (1,2,.)kkkkkknAQAR QkRAA第38頁/共50頁帶原點(diǎn)位移的QR 方法為加速收斂，每次選取位移 ，作該矩陣序列有如下性質(zhì)：（1）（2）如 為擬上三角，則 也為擬上三角矩陣（擬上三角矩陣指的是次對角線下的元素為零的矩陣）（3）如取位移 為 ，則 最后一行非對角元二階收斂于零（特別對于對

9、稱矩陣，能達(dá)到三階收斂），其余次對角元收斂于零的速度會(huì)慢一些。1(1,2,)kkkkkkkkAs IQ RAR Qs Ikks1kkAA相似于kAkAks( )knnakA第39頁/共50頁加速技術(shù)下的算法：（1）確定計(jì)算精度10E-m（2）對矩陣 取加速因子 進(jìn)行加速（3）判斷矩陣 的最后一行非對角元素是否小于要求的精度，如果不小于，繼續(xù)加速迭代，如已經(jīng)小于精度，停止計(jì)算，并劃掉矩陣的最后一行和最后一列，產(chǎn)生一個(gè)子矩陣（4）對子矩陣重復(fù)進(jìn)行上面的加速計(jì)算kA( )knnakA第40頁/共50頁帶原點(diǎn)位移的QR 方法的總結(jié)：（1）利用Householder矩陣，將矩陣 A 相似于擬上三角矩陣（尤其，對于對稱矩陣可以化為三對角矩陣）（2）利用帶原點(diǎn)位移的QR 方法構(gòu)造矩陣序列（3）對矩陣 取加速因子 進(jìn)行加速（4）判斷矩陣 的最后一行非對角元素（由于是擬上三角矩陣，只有一個(gè)元素 ）是否小于要求的精度（5）如已經(jīng)小于精度，停止計(jì)算，并劃掉矩陣的最后一行和最后一列，產(chǎn)生一個(gè)子矩陣，對子矩陣重復(fù)進(jìn)行上面的加速計(jì)算。kAkA( )knnakA( )1knn