第七章對(duì)稱特征值

第七章對(duì)稱特征值問題的計(jì)算方法基本性質(zhì)對(duì)稱QR方法Jacobi方法7.1基本性質(zhì)對(duì)稱矩陣特征值均為實(shí)數(shù)，而且其特征向量可以構(gòu)成Rn的一組標(biāo)準(zhǔn)正交基，即有定理1(譜分解定理）若A是n階對(duì)稱矩陣，則存在正交矩陣Q使得定理2（極小極大定理）設(shè)A是n階對(duì)稱矩陣，并假定A的特征值為λ1≥…≥

λn,則有其中表示中所有k維子空間的全體。定理3設(shè)n階對(duì)稱矩陣A和B的特征值分別為則有該定理表明對(duì)稱矩陣的特征值總是十分良態(tài)的。定理4設(shè)A和A+E是兩個(gè)n階實(shí)對(duì)稱矩陣，并假定q1是A的一個(gè)單位特征向量，Q=[q1,Q2]是n階正交矩陣，QTAQ和QTEQ分塊如下若則存在A+E的一個(gè)單位特征向量使得定理4表明，特征向量的敏感性依賴于對(duì)應(yīng)特征值與其他特征值之間的分離程序。定理5設(shè)A是m×n階實(shí)矩陣，則存在正交矩陣U和V，使得其中注：定理5給出的是矩陣A的奇異值分解，數(shù)稱為A的奇異值。V的列向量稱為A的右奇異向量；U的列向量稱為A的左奇異向量。定理6設(shè)A和B均為m×n實(shí)矩陣，并假定它們有奇異值分別為則有該定理表明矩陣的奇異值也是十分良態(tài)的。作業(yè)：習(xí)題72，3，47.2對(duì)稱QR方法實(shí)對(duì)稱矩陣的三對(duì)角化隱式對(duì)稱QR迭代隱式對(duì)稱QR算法7.2.1三對(duì)角化

對(duì)稱矩陣的三對(duì)角化就是把一個(gè)對(duì)稱矩陣經(jīng)一系列正交約化使其成為對(duì)稱的三對(duì)角矩陣。

顯然，把第6章“矩陣的上Hessenberg化”算法應(yīng)用于實(shí)對(duì)稱矩陣A，則由對(duì)稱性可知，所得到的上H矩陣就是對(duì)稱的三對(duì)角矩陣。

注意到A的對(duì)稱性，上Hessenberg化算法可以改進(jìn)，以減少運(yùn)算量。這就是本節(jié)要介紹的實(shí)對(duì)稱矩陣的三對(duì)角化算法。即經(jīng)n-2次Householder約化，把A化成三對(duì)角矩陣T第1步：把矩陣A分塊寫成依v構(gòu)造n-1階Householder變換,并令用H1約化A(0)得到顯然，第1步約化的主要工作量是計(jì)算，設(shè)則有上式的推導(dǎo)過程：由對(duì)稱性，的計(jì)算過程為：算法7.2.1(實(shí)對(duì)稱矩陣三對(duì)角化：Householder變換法)時(shí)間復(fù)雜度：7.2.2隱式對(duì)稱QR迭代實(shí)現(xiàn)了對(duì)稱矩陣的三對(duì)角化之后，下面的任務(wù)就是選取適當(dāng)?shù)奈灰七M(jìn)行QR迭代。由于實(shí)對(duì)稱矩陣的特征值均為實(shí)數(shù)，只需進(jìn)行帶原點(diǎn)單步位移即可。帶原點(diǎn)位移的QR迭代格式：由于QR迭代保持上Hessenberg形和對(duì)稱性的特點(diǎn)，則迭代產(chǎn)生的Tk都是對(duì)稱三對(duì)角矩陣。和非對(duì)稱QR方法一樣，仍然假定迭代中所出現(xiàn)的Tk均是不可約的，即次對(duì)角線元均不為零。（1）位移的選?。旱膬蓚€(gè)特征值中靠近αn的那一個(gè)，即取其中這就是著名的威爾金森(Wilkinson)位移.Wilkinson證明了這兩種位移最終都是三次收斂的，并且說(shuō)明了為什么后者比前者好[12].第1種選法：選取μk=T(n,n).第2種：取μk為Tk右下角子矩陣（2）如何具體實(shí)現(xiàn)一次QR迭代

當(dāng)然，可以利用Givens變換直接實(shí)現(xiàn)的QR分解，進(jìn)而完成一步QR迭代。但是，更漂亮的做法是以隱含的方式來(lái)實(shí)現(xiàn)由T到的變換。QR迭代實(shí)質(zhì)是用正交變換將T約化為，即.因此,根據(jù)定理6.4.3，本質(zhì)上是由Q的第1列完全確定的。從利用二元正交變換實(shí)現(xiàn)QR迭代的過程可知，Qe1=G1e1，其中G1=G(1,2,?)，且?滿足因此，可以先對(duì)T用G1做一次正交約化，得到然后調(diào)用算法7.2.1，把B正交約化為三對(duì)角陣，即得到算法7.2.2(帶Wilkinson位移的隱式對(duì)稱QR迭代)時(shí)間復(fù)雜度：10n.7.2.3隱式對(duì)稱QR算法算法7.2.3(計(jì)算實(shí)對(duì)稱矩陣的譜分解：隱式QR方法)（1）輸入A;（2）三對(duì)角化：T=QTAQ;（3）收斂性判定：i）將滿足的元素置零。ii）確定最大的非負(fù)整數(shù)m和最小的非負(fù)整數(shù)l,使得其中均為三對(duì)角陣，且iii）若m=n，輸出有關(guān)信息，結(jié)束;否則進(jìn)入下一步.（4）QR迭代：對(duì)T22調(diào)用算法7.2.2迭代一次，即（5）然后返回（3）.作業(yè)：習(xí)題79，11，137.3

Jacobi方法Jacobi方法是求實(shí)對(duì)稱矩陣全部特征值和特征向量的最古老的方法之一，是由Jacobi于1846年提出的。他依據(jù)實(shí)對(duì)稱矩陣可通過正交相似變換約化為對(duì)角陣這一特點(diǎn)，用一系列適當(dāng)選取的平面旋轉(zhuǎn)變換將一個(gè)實(shí)對(duì)稱矩陣逐步約化為對(duì)角陣。盡管該算法收斂速度與QR算法無(wú)法相比，但該算法具有編程簡(jiǎn)單、并行效率高等特點(diǎn)，近年來(lái)又重新受到人們的重視。7.3.1經(jīng)典Jacobi方法

設(shè)A=[αij]是n階實(shí)對(duì)稱矩陣。Jacobi方法的目標(biāo)是將A的非對(duì)角“范數(shù)”逐步約化為零.所用的基本工具就是Givens正交變換：其中，1≤p<q≤n,ep,eq均是單位向量.Jacobi方法每迭代一步需要完成：1）確定p和q；確定旋轉(zhuǎn)角?，使得2）用G=G(p,q,?)對(duì)A一次正交約化：A:=GTAG.（1）Jacobi迭代法的正交約化過程：顯然，每迭代一步，倘若將A約化為B.

則A,B僅第p行（列）與第q行（列）不一樣，其余元素均相同。且以上計(jì)算式子的推導(dǎo)，可借下兩式：（2）c和s的計(jì)算：從最后一個(gè)式子知c和s應(yīng)滿足如果αpq=0，則只需取c=1,s=0即可。如果αpq≠0，則令于是有解得取t為絕對(duì)值較小者，即由于則有（3）p和q的選擇：注意到Jacobi