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

1第九章 矩陣特征值與特征向量計算矩陣特征值問題有物理、工程背景特征值， 對應的特征向量:nAx: x特征多項式 ()detIA特征值 0 特征向量 的基礎(chǔ)解系。()Ix定理 1. 如果 為 A 的特征值的集合，則：1,.nA11()2det()3()noiinioatrABB: 若 x 是 B 對應于 的特征向量，則 Tx 是 A 對應于同一特征1,T值的特征向量。定理 2 (Gerschgorin 圓盤定理)設(shè) ，則 得每一個特征值必屬于下述某個圓盤之中：)ijnAa1(1,2.,)niijjain 證：設(shè) 特征值， 對應的特征向量 x()0IAx21(,.)0;maxTnikxx 第 個方程 i 1niija/1ji iijjxa 有 ：得證，且 對應的特征向量第 個分量絕對值最大，在第 個圓盤中。 iReyleigh 商：設(shè) -實對稱矩陣， 的 Reyleigh 商定義為：A0x (,)AxR定理 3：設(shè) 對稱，特征值 ，對應特征向量 n:12n組成標準正交組 則：1,.nx(,)ijijx 1 1(,)nAx 2 1 00main()nxxRR: 冪法與反冪法設(shè) 有完全特征向量組（n 個線性無關(guān)的特征向量）()ijAa1231.n: 冪法 任取初值 10010,.kkvvAvAv: 3，以后我們用符號 表示向量 的第 i 個分量。1()limkiv()kivkv一般 為避免溢出1()ki表示向量 絕對值最大的分量001112221max().()kkkvuvAvuv 不 會 溢 出 ()kvkv此時 ，1max()k 收 斂 速 度 1max()()kkvOr21 當 時也可用12 1.ss 方法的證明：設(shè) 的特征向量為 （線性無關(guān)） ，A,.nxA:1(,.)ndiagTx1122102(,.)(,.),.nnnAxxxTTvaax 41021121211.().()().()0()kkk knk knkkknkvAvaxaxxaxax 1()()limkiikikiv加速. 原點平移法BApI12(),.,n適當選 ，使p2211求 的主特征值B Rayleigh 加速設(shè) 對稱 A123.n 則 11(,)()kkuO5反冪法， 有完全特征向量系A(chǔ)123.0nn: 的特征值為 ， 且 1,n 11.n通過求 的主特征值 來間接求1An迭代公式： 01max()kkkvuA 1k kvvu通 過 求 解 方 程 ： 求 得 。相似變換法方法的思想是找適當?shù)?P 通過 相對好算來計算 A 的特征1:,()AB值，如果對 不加限制，則從 求 ，很可能是病態(tài)方程，所以只能用酉相似變換法，即限制 為酉陣（注意特征值一般是復的） 。酉陣 ()()HijnjinAaa HUI6酉相似變換的優(yōu)點 求逆容易 1 1HU 2 ()1mincondU酉變換能把任意矩陣變換成怎樣的矩陣？定理（Schur 分解定理）設(shè) ，則存在 n 階酉陣 ，使nA:， 為上三角形矩陣。HAUT證明：設(shè) 的一個特征值為 ，對應的特征向量為 ， 找11x2 使得 為酉陣。(1)n:， (,)xU (,)AU1111,0HHHUAhxA 2()1212210nAAUU : 12122*()()0HU為酉陣，. 如此進行下去，即得： 酉陣12 U1*:HnUAT定理：（實的 Schur 分解定理）, 存在正交陣 ，使n:R712120kTkTRA 為一階或二階矩陣。i實際上，一階對應實特征值， 二階矩陣對應一對共軛復特征值關(guān)鍵在于求 或 R，Chur 定理的證明中，有了特征值，特征向量才有 ，UU不能直接用于求特征值。求一般矩陣全部特征值的 QR 算法我們把算法分為 5 步講解 初等反射陣. 1問題：給定 中的向量 x， y，如何找正交陣 使得 ？由于正交變n:Hxy換保內(nèi)積，給定的 x， y 必須滿足條件 |xy給定單位向量 ，構(gòu)造矩陣 ，這樣定義的2,1nw 2TIwH 稱為初等反射陣，易驗證初等反射陣具有性質(zhì) ， 是正1H交陣，對稱陣，對合陣。有 2, ,nxyxyxyu:， 可 得 到 ： 存 在 使 ，事實上只須 令21TuIuH8即可。2()uxyQR 分解定理： A 可表示為 A=QR 其中 Q 為正交陣而 R 為上三角陣。(),ijna證明：把 A 寫成列向量形式 ，不妨設(shè) （否則跳過這1(,.)na10a一步）根據(jù) 的結(jié)果可知存在初等反射陣 ，使得 1 1H1,e， 1HA(2)*0a(2)(1)nAR同理存在 n-1 階初等反射陣 ，使得2H，令 ，(2)(2)(3)*0aHAA22101HA1(2)(3)*0aA.如此繼續(xù)下去，存在一系列初等反射陣 ，使得11,nH9，令 即得。121.nHAR 1nQHQR 分解一般不唯一，至少主對角線上的元可 。若 A 非奇異，且限制的對角元為正，則唯一。 R證：設(shè) ，由于 A 非奇異， ，兩邊均為上三21AR 112TR角正交陣，對角陣 ， 的對角元為正1(,.)nidiag 12,注意 A 的 QR 分解中的 不相似于122i I A，求 A 的特征值還須更復雜的方法。QR 方法 3設(shè) （分解好）令 以 代入得 QRBRQTTAQBTBA對 B 仍可作 QR 分解，再算 RQ:基本 QR 算法： 1kkkAQR（ 的 分 解 ）k=1,2.易知：定理 1： 1 12()2,.3 (QR)TkkkkkkAQQRRA 的 分 解定理 2：設(shè) ，其特征值滿足， ，A 有標nx:12.0n10準形， 1AxD， 有 分解， ，1(.)ndiag1LU1xL則 *k nR 本 質(zhì) 上即 ()0limkjiijaij不 一 定 存 在注意 Q 的列向量不收斂于特征向量集合若 A 對稱，滿足定理條件，則 收斂于對角陣，若不滿足， 可能不kAkA收斂于對角陣。A 本身為正交陣 ,eg011Q1RI1kA一般情形的 QR 算法收斂性較為復雜，特殊的，若 A 的等模特征值只有重實特征值或多重共軛復特征值，則 QR 算法產(chǎn)生的 本質(zhì)上收斂于分塊上k三角陣。1111*mlB 為 A 的實特征值， 塊 的特征值為 A 的復共軛特征值，注意1.m2iB的元素不一定收斂，但特征值收斂。iB一次迭代計算次數(shù)（即一次 QR 分解）計算量 不可接受。3()On改進的方法：正交相似變換成上 H 陣，再對上 H 陣用 QR 算法。Householder 方法定義：方陣 ，如果當 ，則稱 為上×()ijnBb10ijijb時 ， BHessenberg 陣，即：12121,0nnnbbB 問題：如何用正交相似變換化一般 為上 Hessenberg 陣nA:現(xiàn)考慮用一系列初等反射陣，將 化為上H 陣( 如同大多數(shù)矩陣分解我們還是用減縮的方法 )12把矩陣寫成列向量的形式： 找初等反射陣 使1(,.)nAa1H， ,如前，很容易找到2112(,.,)nAHd*0,Td使得 取 的形式（不唯一） ，設(shè) 但現(xiàn)在a112HIu 的第一列要取 的形式。 為使右乘 后， 的第一列不變，1()1 A的第一列應為1H110(1,0.)TH 因此必須 。1()u下 ， ，由 知：d求 與 11()ad 1da， ，2121(),nis 111u，1121311)(0,.,)Tnwadasa 可能 ，為避免相近數(shù)相減，取 。從而2s2sg(121gn()s令 ， ，2211aw1THIw(,sgn(),0.,)Tda 13第 步變換，僅是第一步的重復，只不過把變換應用與 階方陣上。i 1ni若 為對稱， （上 陣） 顯然 為對稱。 為三對角矩陣。ATRBH B一次變換的計算量 。35()4n:但對上 H 陣作一次 QR 分解計算量僅為 預處理的方法。2()On對上 H 陣作 QR 分解的 Givens 變換在 中， 2:cosinP Px 把向量 逆時針方向旋轉(zhuǎn) 角度，P 稱為旋轉(zhuǎn)矩陣。x推廣到 稱為平面旋轉(zhuǎn)矩陣。(,)nij1(,)1csiPijscjij ， （可以認為 ）21cscos,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分解，特別是當 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 kAQ1231,TnP分兩步來證明 仍然為上 Hessenberg 矩陣。（1）容易證明 是上 Hessenberg 矩陣，這是因為12k1212*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標的 Givens 變換，也能得到正確的 ，所以左右變換可以按下列順序同時進行： (2,3)1(2,3)1(,)(3,4),(2)(1,)4(,),2T Tkk kTkPPAPPA帶位移的 QR 算法數(shù)列 構(gòu)造 算法ksk17（1 ） A（2 ）對 分解ksIQRk=1,2,.（3 ）新矩陣1TkkkARsIA（4 ） TKQ（5 ） 12():)(.()ksIsI有 QR 分解式 kAR如果選 ，則可把 分離，迭代進行到 充分小， 有形()knSan(),1|knakA式 (4為 例 440B ：對 B（減一階）續(xù)續(xù)用 QR 算法。收斂快。QR 算法的證明、細節(jié)與改進定理 2.1 的證明：18引理 ，當 時若 ，則kkMQRkMIkQRI，證： TTTk， 第一行為()kijnrk()()()1121,knr ()2()kkr()0,2,ijjn 同理逐行計算得11,kkkkRIIQMRI定理的證明 11()()kkkkijAxDLUxDLl 元素：01()kijkijij由于 ij 另一方面：1: 0()()maxkkkkijijkjjDLIEEOic 可設(shè)1()()k kkXQRAIDUQIREDU 19當 K 充分大時， 非奇異1 1k kREIRE ()kQII由引理()()k ()()kkARDU的另一形式，QR 分解112(,.)ndiaguu上式改寫成()1()212(kkkkAQDRDU正 交 陣 對 角 元 為 正與上式同一 QR 分解。kkR()21()1kkU代入定理 1 之（2） 得：1AQRD()()21 21(TkTkkkkkAQ為上 所以有()IR()1()1kTkkBDR（對角線保持次序）1*n2012121()()()kTkkijiijjADB為對角陣，2i1()0kij()j1ikijiiABRDHouseholder 算法：假定對 進行了 步變換，得到()(1,2.,)kAn ()()()121310kkk kaAU21H用 左 乘 都 不 改 變 第 一 列()()()()()1223knknkA: 要求 階正交陣()20ka()21kkkRae， 使()()21/1()()2()11,sgn ()3nkkk iikkkaRue () 0() kkTkn InIuUR階 (不須做矩陣乘法，做一系列內(nèi)積)()()()12131 20kkkkkAaAURA21()21()()()323(41113) ()()23223(4)56(7)kkkTkk kkTkkRaeAuARu） 算法：對 做 ,.,n 在(4)(7)中，新的沖掉老的(6),(7)可合并，一個 的矩陣右乘 階方陣。()k()nk