上海交通大學(xué)計算方法課件(宋寶瑞)CH.9

《上海交通大學(xué)計算方法課件(宋寶瑞)CH.9》由會員分享，可在線閱讀，更多相關(guān)《上海交通大學(xué)計算方法課件(宋寶瑞)CH.9（21頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1第九章 矩陣特征值與特征向量計算矩陣特征值問題有物理、工程背景特征值， 對應(yīng)的特征向量:nAx????: x特征多項式 ()detIA??特征值 0? 特征向量 的基礎(chǔ)解系。()Ix??定理 1. 如果 為 A 的特征值的集合，則：1{,.}nA?11()2det()3()noiinioatrABB??????: 若 x 是 B 對應(yīng)于 的特征向量，則 Tx 是 A 對應(yīng)于同一特征1,T??值的特征向量。定理 2 (Gerschgorin 圓盤定理)設(shè) ，則 得每一個特征值必屬于下述某個圓盤之中：)ijnAa??1(1,2.,)niijjain?????? 證：設(shè) 特征值， 對應(yīng)的特征向量 x()0IAx???21(,.)0;maxTnikxx??? 第 個方程 i 1niija?????/1ji iijjxa?? 有 ：得證，且 對應(yīng)的特征向量第 個分量絕對值最大，在第 個圓盤中。? iReyleigh 商：設(shè) --實對稱矩陣， 的 Reyleigh 商定義為：A0x? (,))AxR?定理 3：設(shè) 對稱，特征值 ，對應(yīng)特征向量 n??:12n???組成標(biāo)準(zhǔn)正交組 則：1,.nx(,)ijijx??○ 1 1(,)nAx??○ 2 1 00main()nxxRR???????:: 冪法與反冪法設(shè) 有完全特征向量組（n 個線性無關(guān)的特征向量）()ijAa??1231.n?????: 冪法 任取初值 10010,,.kkvvAvAv????: 3，以后我們用符號 表示向量 的第 i 個分量。1()limkiv?????()kivkv一般 為避免溢出1()ki?表示向量 絕對值最大的分量001112221max()..()kkkvuvAvuv?????? 不 會 溢 出 ()kvkv此時 ，1max()k?? 收 斂 速 度 1max()()kkvOr???21? 當(dāng) 時也可用12 1.ss??? 方法的證明：設(shè) 的特征向量為 （線性無關(guān)） ，A,.nxA?:1(,.)ndiag??Tx?1122102(,.)(,.),..nnnAxxxTTvaax?????????????? 41021121211..(().()().()0()kkk knk knkkknkvAvaxaxxaxax????????????? 1()()limkiikikiv???????????加速. 原點平移法BApI??12(){,.,}n??適當(dāng)選 ，使p2211??求 的主特征值B?? Rayleigh 加速設(shè) 對稱 A123.n??? 則 11(,)()kkuO???5反冪法， 有完全特征向量系A(chǔ)123.0nn?????: 的特征值為 ， 且 ?1,,n?? 11.n?????通過求 的主特征值 來間接求1A?n?迭代公式： 01max()kkkvuA??????? 1k kvvu??通 過 求 解 方 程 ： 求 得 。相似變換法方法的思想是找適當(dāng)?shù)?P 通過 相對好算來計算 A 的特征1:,()AB???值，如果對 不加限制，則從 求 ，很可能是病態(tài)方程，所以只能用酉相似變換法，即限制 為酉陣（注意特征值一般是復(fù)的） 。酉陣 ()()HijnjinAaa???? HUI6酉相似變換的優(yōu)點 求逆容易 ○ 1 1HU??○ 2 ()1mincondU?酉變換能把任意矩陣變換成怎樣的矩陣？定理（Schur 分解定理）　設(shè) ，則存在 n 階酉陣 ，使nA??:， 為上三角形矩陣。HAUT?證明：設(shè) 的一個特征值為 ，對應(yīng)的特征向量為 ， 找1?1x2? 使得 為酉陣。(1)n????:， (,)xU?? (,)AU??1111,0HHHUAhxA?????????????????????? 2()1212210nAAUU??? ???????????: 12122*()()0HU???????為酉陣，….. 如此進行下去，即得： －酉陣12 U1*:HnUAT??????????定理：（實的 Schur 分解定理）, 存在正交陣 ，使n??:R712120kTkTRA?????????? ?為一階或二階矩陣。i實際上，一階對應(yīng)實特征值， 二階矩陣對應(yīng)一對共軛復(fù)特征值關(guān)鍵在于求 或 R，Chur 定理的證明中，有了特征值，特征向量才有 ，UU不能直接用于求特征值。求一般矩陣全部特征值的 QR 算法我們把算法分為 5 步講解 初等反射陣.○ 1問題：給定 中的向量 x， y，如何找正交陣 使得 ？由于正交變n:Hxy?換保內(nèi)積，給定的 x， y 必須滿足條件 ||xy給定單位向量 ，構(gòu)造矩陣 ，這樣定義的2,1nw?? 2TIw?H 稱為初等反射陣，易驗證初等反射陣具有性質(zhì) ， 是正1??H交陣，對稱陣，對合陣。有 2, ,nxyxyxyu??:， 可 得 到 ： 存 在 使 ，事實上只須 令21TuIu??H8即可。2()uxy???②QR 分解定理： A 可表示為 A=QR 其中 Q 為正交陣而 R 為上三角陣。(),ijna?證明：把 A 寫成列向量形式 ，不妨設(shè) （否則跳過這1(,.)na?10a?一步）根據(jù) 的結(jié)果可知存在初等反射陣 ，使得○ 1 1H1,e??， 1HA(2)*0a?????????(2)(1)nA???R同理存在 n-1 階初等反射陣 ，使得2H?，令 ，(2)(2)(3)*0aHAA??????????2210????????1HA?1(2)(3)*0aA??????????…...如此繼續(xù)下去，存在一系列初等反射陣 ，使得11,nH??9，令 即得。121.nHAR?? 1nQH??QR 分解一般不唯一，至少主對角線上的元可 。若 A 非奇異，且限制?的對角元為正，則唯一。 R證：設(shè) ，由于 A 非奇異， ，兩邊均為上三21AR? 112TR??角正交陣，對角陣 ， 的對角元為正1(,.)nidiag?? ? 12,注意 A 的 QR 分解中的 不相似于122i I??? A，求 A 的特征值還須更復(fù)雜的方法。QR 方法○ 3設(shè) （分解好）令 以 代入得 QR?BRQ?TTAQB?TBA對 B 仍可作 QR 分解，再算 RQ……:基本 QR 算法： 1kkkAQR??????（ 的 分 解 ）k=1,2…..易知：定理 1： 1 12()2,.3 (QR)TkkkkkkAQQRRA??? 的 分 解定理 2：設(shè) ，其特征值滿足， ，A 有標(biāo)nx?:12.0n????10準(zhǔn)形， 1AxD??， 有 分解， ＝ ，1(.)ndiag?1LU1x?L則 *k nR?????? ? ? ?????本 質(zhì) 上即 ()0limkjiijaij????????不 一 定 存 在注意 Q 的列向量不收斂于特征向量集合若 A 對稱，滿足定理條件，則 收斂于對角陣，若不滿足， 可能不??kA??kA收斂于對角陣。A 本身為正交陣 ,eg01???????1Q?1RI1?kA?一般情形的 QR 算法收斂性較為復(fù)雜，特殊的，若 A 的等模特征值只有重實特征值或多重共軛復(fù)特征值，則 QR 算法產(chǎn)生的 本質(zhì)上收斂于分塊上??k三角陣。1111*mlB?????????? ?為 A 的實特征值， 塊 的特征值為 A 的復(fù)共軛特征值，注意1.m?2?iB的元素不一定收斂，但特征值收斂。iB一次迭代計算次數(shù)（即一次 QR 分解）計算量 不可接受。3()On改進的方法：正交相似變換成上 H 陣，再對上 H 陣用 QR 算法。④Householder 方法定義：方陣 ，如果當(dāng) ，則稱 為上×()ijnBb?10ijijb???時 ， BHessenberg 陣，即：12121,,0nnnbbB??????????? ? ?問題：如何用正交相似變換化一般 為上 Hessenberg 陣nA??:現(xiàn)考慮用一系列初等反射陣，將 化為上—H 陣( 如同大多數(shù)矩陣分解我們還是用減縮的方法 )12把矩陣寫成列向量的形式： 找初等反射陣 使1(,.)nAa?1H， ,如前，很容易找到2112(,.,)nAHd?*0,Td?使得 取 的形式（不唯一） ，設(shè) 但現(xiàn)在a112HIu? 的第一列要取 的形式。 為使右乘 后， 的第一列不變，1()?1 A的第一列應(yīng)為1H110(1,0.)TH?????????? 因此必須 。1()u?下 ， ，由 知：d求 與 11()ad? 1da， ，2121(),nis??? 111u?，1121311)(0,,.,)Tnwadasa???? ???可能 ，為避免相近數(shù)相減，取 。從而2s?2sg(121gn()s?令 ， ，2211aw???1THIw???(,sgn(),0.,)Tda?? 13第 步變換，僅是第一步的重復(fù)，只不過把變換應(yīng)用與 階方陣上。i 1ni??若 為對稱， （上 陣） 顯然 為對稱。 為三對角矩陣。ATRB?H B一次變換的計算量 。35()4n:但對上 H 陣作一次 QR 分解計算量僅為 ―― 預(yù)處理的方法。2()On⑤對上 H 陣作 QR 分解的 Givens 變換在 中， 2:cosinP????????? Px 把向量 逆時針方向旋轉(zhuǎn) 角度，P 稱為旋轉(zhuǎn)矩陣。x推廣到 稱為平面旋轉(zhuǎn)矩陣。(,)nij1(,)1csiPijscjij? ?? ?? ???? ?? ?? ? ? ， （可以認為 ）21cs??cos,in??設(shè) 2(,.,.)Tijnxaa?:14， 則1(,),.)TnPijxb?(,)iijjijkcassacbaij?????? 如果取 則22jijijs?， （1）,0iijbab???為正交陣， 左乘： 只改變 的第 行和第 行。右乘： (,)Pij ()PAij只改變 的第 列和第 列。 改變 的的第 行、Aij(,)(,)TijPAi第 行，第 列和第 列其余元素不動。ij這樣的 稱為 Givens 矩陣或 Givens 旋轉(zhuǎn)變換，它具有下(,)ij?列性質(zhì)：1． 為正交矩陣；P2． 與單位陣相比，只有在 4 個位置上的元素不同；(,),(),ijij3． 作用于向量 ，只改變 的第 兩個元素：x,ij4. 的前(i-1)行和前(i- 1)列與單位陣 I 相同。P通過（1）式，我們看到作旋轉(zhuǎn)變換可 有針對性地使某個元素變零，而用初等反射陣則一次使一串元素變?yōu)榱恪ｏ@然，用旋轉(zhuǎn)變換也可實現(xiàn)矩陣的 QR分解，特別是當(dāng) A 為上 Hessenberg 陣時，每一列用一次，總共用 n-1 次旋轉(zhuǎn)變換即可實現(xiàn) QR 分解，大大減少了計算量。算法對上 Hessenberg 矩陣 ，用 QR 算法迭代一次可分兩步：A15(1) 用 Givens 變換作 QR 分解：左乘 將 化 0， ，左乘 將 化 0， ，左乘12Pa? ? ,1iP?,ia? ?將 化 0，得上三角陣 R,n?,n?(2) 右變換 2A1231,TnR???定理 設(shè) 為上 Hessenberg 矩陣，那么由 開始作 QR 算法所產(chǎn)生的矩陣1 1A序列 的每個矩陣 均為上 Hessenberg 矩陣。??kk證明：只需要證明一步就可以了。設(shè)對上 Hessenberg 矩陣 用 Givens 旋k轉(zhuǎn)變換作 QR 分解，即 ，或1,2,312nkPPR????，F(xiàn)作反乘 。1231,TknkkAPRQ??? kAQ?1231,TnP??分兩步來證明 仍然為上 Hessenberg 矩陣。?（1）容易證明 是上 Hessenberg 矩陣，這是因為12k?1212*0k nrcsRPr????????????????? ??。1212*00*crsc?? ?? ??? ?? ??????? ? ?（2 ） 任一上 Hessenberg 矩陣 與 的乘積仍是上 Hessenberg 矩陣。H1,iP??作分塊乘法16，其中1 121, 3 30sssii pi pxx xHXIHXPPP??????????????????????，2iiics??????而 ,1 ,1.11, 1, 1.,ii iiiiiipihchsshccsHP? ????????? ??????? ?????? ?顯然，最后結(jié)果仍為上 Hessenberg 矩陣。 最后一個問題，在 1(,).(1,2)(,).(1,)TTk kAPnAPn????中，左乘和右乘是否能同時進行，以減少存儲量，簡化程序？實際上關(guān)鍵的問題是要能找到正確的 ，注意 是由,i?(,)Pm?(,).(,)km的第 m 列確定改變的是上述矩陣的第 m 行和 m+1 行，而對任意矩陣 B，的第 m 列與 B 的第 m 列相同，因此對1,2.2,1TTBP?的第 m 列作同樣目()()().(2,1)TTkAP?標(biāo)的 Givens 變換，也能得到正確的 ，所以左右變換可以按下?列順序同時進行： (2,3)1(2,3)1(,)(3,4),(2)(1,)4(,),2T Tkk kTkPPAPPA???帶位移的 QR 算法數(shù)列 構(gòu)造 算法??ksk17（1 ） A?（2 ）對 分解??ksIQR?k=1,2,...（3 ）新矩陣1TkkkARsIA??（4 ） TKQ?（5 ） 12():)(.()ksIsI???有 QR 分解式 kAR??如果選 ，則可把 分離，迭代進行到 充分小， 有形()knSan?(),1||kna?kA式 (4?為 例 440B?????????????????? ：對 B（減一階）續(xù)續(xù)用 QR 算法。收斂快。QR 算法的證明、細節(jié)與改進定理 2.1 的證明：18引理 ，當(dāng) 時若 ，則kkMQR???kMIkQRI?，證： TTTk?， 第一行為()kijnr?k()()()1121,,knr? ?()2()kkr()0,2,ijjn?? ? 同理逐行計算得11,kkkkRIIQMRI????定理的證明 11()()kkkkijAxDLUxDLl???? 元素：01()kijkijij??????????由于 ij?? 另一方面：1: 0()()maxkkkkijijkjjDLIEEOic???????? 可設(shè)1()()k kkXQRAIDUQIREDU????? 19當(dāng) K 充分大時， 非奇異1 1k kREIRE???? ()kQII???由引理()()k ()()kkARDU的另一形式，QR 分解112(,.)ndiaguu???上式改寫成()1()212(kkkkAQDRDU?正 交 陣 對 角 元 為 正與上式同一 QR 分解。kkR?()21()1kkU?代入定理 1 之（2） 得：1AQRD??()()21 21([]TkTkkkkkAQ??為上 所以有()I?R?()1()1kTkkBDR??（對角線保持次序）1*n?????????2012121()()()kTkkijiijjADB??為對角陣，2i?1()0kij??()j?1ikijiiABRD???Householder 算法：假定對 進行了 步變換，得到()(1,2.,)kAn?? ()()()121310kkk kaAU????????21H用 左 乘 都 不 改 變 第 一 列()()()()()1223knknkA??????::: 要求 階正交陣()20ka?()21kkkRae??， 使()()21/1()()2()11,sgn ()3nkkk iikkkaRue????????? () 0() kkTkn InIuUR??????????階 (不須做矩陣乘法，做一系列內(nèi)積)()()()12131 20kkkkkAaAURA????21()21()()()323(41113) ()()23223(4)56(7)kkkTkk kkTkkRaeAuARu????） 算法：對 做 ,.,n?? 在(4)—(7)中，新的沖掉老的(6),(7)可合并，一個 的矩陣右乘 階方陣。()k?()nk