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

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