矩陣特征值問題的數(shù)值方法

矩陣特征值問題的數(shù)值方法第1頁，共51頁，2023年，2月20日，星期一9.1特征值與特征向量設(shè)A是n階矩陣，x是非零列向量.如果有數(shù)λ存在，滿足，(1)那么，稱x是矩陣A關(guān)于特征值λ的特征向量.

第2頁，共51頁，2023年，2月20日，星期一如果把(1)式右端寫為，那么(1)式又可寫為:記它是關(guān)于參數(shù)λ的n次多項(xiàng)式，稱為矩陣A的特征多項(xiàng)式，其中a0=(-1)n｜A｜.

(2)第3頁，共51頁，2023年，2月20日，星期一顯然，當(dāng)λ是A的一個(gè)特征值時(shí)，它必然是的根.反之，如果λ是的根，那么齊次方程組(2)有非零解向量x，使(1)式成立.從而，λ是A的一個(gè)特征值.

A的特征值也稱為A的特征根.第4頁，共51頁，2023年，2月20日，星期一矩陣特征值和特征向量有如下主要性質(zhì)：

定理9.1.1n階矩陣A是降秩矩陣的充分必要條件是A有零特征值.定理9.1.2設(shè)矩陣A與矩陣B相似，那么它們有相同的特征值.定理9.1.3n階矩陣A與AT有相同的特征值.定理9.1.4設(shè)λi≠λj是n階矩陣A的兩個(gè)互異特征值，x、y分別是其相應(yīng)的右特征向量和左特征向量，那么，xTy=0.第5頁，共51頁，2023年，2月20日，星期一9.2Hermite矩陣特征值問題設(shè)A為n階矩陣，其共軛轉(zhuǎn)置矩陣記為AH.如果A=AH，那么，A稱為Hermite矩陣.第6頁，共51頁，2023年，2月20日，星期一9.2.1Hermite矩陣的有關(guān)性質(zhì)

設(shè)是Hermite矩陣A的n個(gè)特征值.有以下性質(zhì):全是實(shí)數(shù).有相應(yīng)的n個(gè)線性無關(guān)的特征向量，它們可以化為一組標(biāo)準(zhǔn)酉交的特征向量組,即是酉空間中的一組標(biāo)準(zhǔn)酉交基.第7頁，共51頁，2023年，2月20日，星期一記U=(),它是一個(gè)酉陣，即UHU=UUH=I，那么即A與以為對角元的對角陣相似.A為正定矩陣的充分必要條件是全為正數(shù).第8頁，共51頁，2023年，2月20日，星期一定理9.2.1設(shè)是Hermite矩陣A的n個(gè)特征值，那么

證:第9頁，共51頁，2023年，2月20日，星期一設(shè)x是一個(gè)非零向量，A是Hermite矩陣，稱為矩陣A關(guān)于向量x的Rayleigh商，記為R(x).定理9.2.2如果A的n個(gè)特征值為其相應(yīng)的標(biāo)準(zhǔn)酉交的特征向量為那么有定理9.2.3設(shè)A是Hermite矩陣，那么第10頁，共51頁，2023年，2月20日，星期一9.2.2極值定理

定理9.2.4(極值定理)設(shè)Hermite矩陣的n個(gè)特征值為，其相應(yīng)的標(biāo)準(zhǔn)酉交特征向量為.用Ck表示酉空間Cn中任意的k維子空間，那么第11頁，共51頁，2023年，2月20日，星期一9.2.3Hermite矩陣特征值問題的性態(tài)

矩陣特征值問題與求解線性方程組問題一樣，都存在當(dāng)矩陣A的原始數(shù)據(jù)有小變化(小擾動(dòng))時(shí)，引起特征值問題的變化有大有小的問題，如果引起的變化小，稱該特征值問題是良態(tài)的.

反之，稱為病態(tài)的.矩陣特征值問題的性態(tài)是很復(fù)雜的，通常分別就單個(gè)特征值或整體特征值給出狀態(tài)數(shù)進(jìn)行分析.對于Hermite矩陣，由于其特征值問題的特殊性質(zhì)，其特征值都是良態(tài)的.下面先證明Hermite矩陣特征值的擾動(dòng)定理.第12頁，共51頁，2023年，2月20日，星期一定理9.2.5設(shè)矩陣A，E，A+E都是n階Hermite矩陣，其特征值分別為

那么,證設(shè)矩陣A關(guān)于特征值λ1，λ2，…，λn

的標(biāo)準(zhǔn)酉交特征向量為u1，u2，…，un，是由ui，ui+1，…，un生成的n-i+1維子空間.

對中任意非零向量x,由極值定理,有第13頁，共51頁，2023年，2月20日，星期一由定理9.2.3，又由定理9.2.2，對任意x≠0，有從而有另一方面,A=(A+E)-E.記為矩陣-E的特征值，那么，重復(fù)上面的過程,可得從而有第14頁，共51頁，2023年，2月20日，星期一定理9.2.5通常又稱為Hermite矩陣特征值的擾動(dòng)定理

定理9.2.6設(shè)矩陣A和A′=A+E都是n階Hermite矩陣，其特征值分別為和，那么這個(gè)定理表明，擾動(dòng)矩陣E使A的特征值的變化不會(huì)超過‖E‖2.一般‖E‖2小，因此，Hermite矩陣特征值是良態(tài)的.第15頁，共51頁，2023年，2月20日，星期一9.3Jacobi方法理論上，實(shí)對稱矩陣A正交相似于以A的特征值為對角元的對角陣.問題是如何構(gòu)造這樣的正交矩陣呢?Jacobi方法就是通過構(gòu)造特殊的正交矩陣序列，通過相似變換使A的非對角線元素逐次零化來實(shí)現(xiàn)對角化的.9.3.1平面旋轉(zhuǎn)矩陣與相似約化先看一個(gè)簡單的例子.第16頁，共51頁，2023年，2月20日，星期一設(shè)是二階實(shí)對稱矩陣，即a21=a12，其特征值為λ1，λ2.令使得記容易驗(yàn)證BT=B,且第17頁，共51頁，2023年，2月20日，星期一解之得:當(dāng)時(shí)當(dāng)時(shí)

并規(guī)定第18頁，共51頁，2023年，2月20日，星期一9.3.2經(jīng)典的Jacobi方法設(shè)A是實(shí)對稱矩陣，記A1=A.Jacobi方法的基本思想是用迭代格式

Ak+1=QTkAkQk,k=1,2,…

構(gòu)造一個(gè)相似矩陣序列，使｛Ak｝收斂于一個(gè)對角陣.其中Qk為平面旋轉(zhuǎn)矩陣，其旋轉(zhuǎn)角θk由使Ak的絕對值最大元a(k)pq=a(k)qp=0或按列依次使A的非對角元零化來確定.第19頁，共51頁，2023年，2月20日，星期一定理9.3.1設(shè)A是n階實(shí)對稱矩陣，那么由Jacobi方法產(chǎn)生的相似矩陣序列｛Ak｝的非對角元收斂于0.也就是說，｛Ak｝收斂于以A的特征值為對角元的對角陣.

記其中Ek是Ak除主對角元外的矩陣.由平面旋轉(zhuǎn)矩陣的性質(zhì)中,對于,有因此,第20頁，共51頁，2023年，2月20日，星期一又由假設(shè),因此,這樣,便有從而,當(dāng)?shù)?1頁，共51頁，2023年，2月20日，星期一9.3.3實(shí)用的Jacobi方法

循環(huán)Jacobi方法必須一次又一次掃描，才能使｛Ak｝收斂于對角陣，計(jì)算量很大.在實(shí)際計(jì)算中，往往用一些特殊方法來控制掃描次數(shù)，減少計(jì)算量.下面介紹一種應(yīng)用最為廣泛的特殊循環(huán)Jacobi方法——閾Jacobi方法.閾Jacobi方法首先確定一個(gè)閾值δ，在對非對角元零化的一次掃描中，只對其中絕對值超過閾值的非對角元進(jìn)行零化.當(dāng)所有非對角元素的絕對值都不超過閾值后，將閾值減少，再重復(fù)下一輪掃描，直至閾值充分小為止.減少閾值的方法通常是先固定一個(gè)正整數(shù)M≥n，掃描一次后，讓.而閾值的下界是根據(jù)實(shí)際問題的精度要求選定的.

第22頁，共51頁，2023年，2月20日，星期一9.3.4用Jacobi方法計(jì)算特征向量假定經(jīng)過k次迭代得到Ak+1=RTk…RT1AR1…Rk，(15)這時(shí)Ak+1是滿足精度要求的一個(gè)近似的對角陣.如果記Qk=R1R2…Rk=Qk-1Rk，(16)

那么，Qk是一個(gè)正交矩陣，且(15)式又可表示為Ak+1=QTkAQk.當(dāng)Ak+1的非對角元素充分小，Qk的第j列qj可以看成是近似特征值a(k+1)jj相應(yīng)的特征向量了.第23頁，共51頁，2023年，2月20日，星期一在實(shí)際計(jì)算中，可以按(16)式在迭代過程中形成Qk，把Qk看成是Qk-1右乘一個(gè)平面旋轉(zhuǎn)矩陣得到.不妨記Q0=I，Qk的元素按下式計(jì)算：第24頁，共51頁，2023年，2月20日，星期一9.4對分法理論上，一個(gè)實(shí)對稱矩陣正交相似于一個(gè)以其特征值為對角元的對角陣.但是，經(jīng)典的結(jié)果告訴我們，一個(gè)大于4次的多項(xiàng)式方程不可能用有限次四則運(yùn)算求根.因此，我們不可能期望只用有限次相似變換將一個(gè)實(shí)對稱矩陣約化為一個(gè)對角陣.下面先介紹將一個(gè)實(shí)對稱矩陣相似約化為實(shí)對稱三對角矩陣的方法，再討論求其特征值的對分法.第25頁，共51頁，2023年，2月20日，星期一9.4.1相似約化為實(shí)對稱三對角矩陣

將一個(gè)實(shí)對稱矩陣正交相似約化為一個(gè)實(shí)對稱三對角矩陣的算法，可歸納如下：記A(1)=A,對k=1,2,…,n-2①按(4)式、(5)式和(8)式計(jì)算；②按(9)～(12)式，計(jì)算A(k+1).第26頁，共51頁，2023年，2月20日，星期一第27頁，共51頁，2023年，2月20日，星期一9.4.2Sturm序列的性質(zhì)

設(shè)實(shí)對稱三對角矩陣為其中βi≠0(i=1,2,…，n-1)

其特征矩陣為T-λI.記T-λI的第i階主子式為第28頁，共51頁，2023年，2月20日，星期一這是關(guān)于λ的i次多項(xiàng)式，當(dāng)i=n時(shí)，pn(λ)=｜T-λI｜是矩陣T的特征多項(xiàng)式.令p0(λ)≡1，則有p1(λ)=α1-λ，pi(λ)=(αi-λ)pi-1(λ)-β2i-1pi-2(λ)，i=2,3，…，n.(15)多項(xiàng)式序列｛pi(λ)｝(i=0,1,…，n)稱為Sturm序列

第29頁，共51頁，2023年，2月20日，星期一定理9.4.1｛pi(λ)｝(i=1,2,…，n)的根都是實(shí)根.

證由(14)式，pi(λ)是i階實(shí)對稱矩陣的特征多項(xiàng)式，因此，｛pi(λ)｝(i=1,2,…，n)的根全是實(shí)根.定理9.4.2定理9.4.2設(shè)α是pi(λ)的一個(gè)根，那么

①pi-1(α)pi+1(α)≠0，即相鄰的兩個(gè)多項(xiàng)式無公共根；②pi-1(α)pi+1(α)<0，即pi-1(α)與pi+1(α)反號.

定理9.4.4pi(λ)的根都是單根，并且將pi+1(λ)的根嚴(yán)格隔離.

第30頁，共51頁，2023年，2月20日，星期一9.4.3同號數(shù)和它的應(yīng)用定義1設(shè)p0(λ)≡1，｛pi(λ)｝(i=1,2,…，n)是一個(gè)Sturm序列，稱相鄰的兩個(gè)數(shù)中符號一致的數(shù)目為同號數(shù)，記為ai(λ).若某個(gè)pi(λ)=0，規(guī)定與pi-1(λ)反號.定理9.4.5設(shè)兩個(gè)實(shí)數(shù)x<y，那么，形如(13)式的實(shí)對稱三對角矩陣T的特征多項(xiàng)式在區(qū)間(x,y］上根的數(shù)目為a(x)-a(y).第31頁，共51頁，2023年，2月20日，星期一9.4.4求Hermite矩陣特征值的對分法

對分法的計(jì)算可歸納為以下4個(gè)部分①確定(13)式的矩陣T的全部特征值的分布區(qū)間.②在區(qū)間［a,b］中，用區(qū)間對分的方法找出只含T的一個(gè)特征值的子區(qū)間.③在只含一個(gè)特征值的子區(qū)間上的對分法.④同號數(shù)的計(jì)算.第32頁，共51頁，2023年，2月20日，星期一9.5乘冪法

乘冪法是適用于求一般矩陣按模最大特征值及相應(yīng)特征向量的算法.

設(shè)A是n階矩陣，其n個(gè)特征值按模從大到小排序?yàn)橛旨僭O(shè)關(guān)于λ1，λ2，…，λn的特征向量v1，v2，…，vn線性無關(guān).第33頁，共51頁，2023年，2月20日，星期一

xk→λk1a1v1(k→∞).因此，xk可看成是關(guān)于特征值λ1的近似特征向量.

迭代格式為按模最大特征值λ1及其相應(yīng)的特征向量v1的乘冪法的計(jì)算公式：

第34頁，共51頁，2023年，2月20日，星期一9.5.2收縮方法設(shè)矩陣A的n個(gè)特征值按模從大到小排序?yàn)?，其相?yīng)的n個(gè)線性無關(guān)特征向量為v1，v2，…，vn.在計(jì)算A的最大特征值λ1及相應(yīng)特征向量v1后，可以通過收縮方法，繼續(xù)用乘冪法計(jì)算λ2及其相應(yīng)的特征向量v2.第35頁，共51頁，2023年，2月20日，星期一定義n階矩陣把去掉A1的第1行和第1列的n-1階矩陣記為第36頁，共51頁，2023年，2月20日，星期一那么，B有與A1除λ1外的相同的n-1個(gè)特征值｜λ2｜>｜λ3｜≥…≥｜λn｜，可以用乘冪法計(jì)算λ2及其相應(yīng)的特征向量.在計(jì)算λ1和v１后，按(15)式形成n-1階矩陣B的計(jì)算過程稱為收縮方法.第37頁，共51頁，2023年，2月20日，星期一9.6反冪法反冪法可以求一個(gè)非奇異矩陣A的逆矩陣A-1的按模最小的特征值及相應(yīng)的特征向量，又可以求A的一個(gè)近似特征值相應(yīng)的特征向量.9.6.1求按模最小特征值及相應(yīng)特征向量的反冪法,又稱為反迭代法.第38頁，共51頁，2023年，2月20日，星期一9.6.2求近似特征值的特征向量的反冪法

先對矩陣進(jìn)行LU分解，記那么，

(7)

下面介紹一種選取特殊的初始向量x0的反冪法——半迭代法.第39頁，共51頁，2023年，2月20日，星期一假設(shè),選取初始向量x0滿足‖x0‖∞=1，這時(shí)z0=x0.對照(7)式中的第二個(gè)式子.可把z0看成滿足Le=z0.(8)

這里，e=(1,1，…，1)T，而z0的各個(gè)分量的取值多少是無關(guān)重要的.這樣，在第一個(gè)迭代步的計(jì)算中，只需求解(7)式中的上三角方程組Ux1=e.“半迭代法”的命名也由此而得.第40頁，共51頁，2023年，2月20日，星期一9.7QR方法定理9.7.1設(shè)A是n階矩陣，其n個(gè)特征值為.那么存在一個(gè)酉矩陣U，使UＨAU是以為對角元的上三角矩陣.9.7.1兩個(gè)基本定理定理9.7.2設(shè)A是n階實(shí)矩陣，那么，存在一個(gè)正交矩陣Q，使QＴAQ為一個(gè)準(zhǔn)上三角矩陣，它的對角元是A的一個(gè)特征值，對角元上的二階塊矩陣的兩個(gè)特征值是A的一對共軛復(fù)特征值.第41頁，共51頁，2023年，2月20日，星期一9.7.2相似約化為上Hessenberg矩陣

對一般n階矩陣，QR算法的每一個(gè)迭代步需要O(n３)次乘法運(yùn)算.如果矩陣階數(shù)稍大，這個(gè)算法幾乎沒有實(shí)際的應(yīng)用價(jià)值.通常采用的方法是先將矩陣相似約化為上Hessenberg形式的矩陣，在此基礎(chǔ)上應(yīng)用QR迭代.這時(shí)，一個(gè)QR迭代步的乘法運(yùn)算次數(shù)只需O(n２）次.第42頁，共51頁，2023年，2月20日，星期一所謂上Hessenberg矩陣是指一個(gè)n階矩陣A，如果當(dāng)i>j+1時(shí)，aij=0，稱A為上Hessenberg矩陣.例如：一個(gè)5階的上Hessenberg矩陣具有如下的形式：下面介紹QR方法時(shí)，都假設(shè)矩陣A是一個(gè)上Hessenberg矩陣.第43頁，共51頁，2023年，2月20日，星期一9.7.3QR算法設(shè)A是n階矩陣且有QR分解A＝QR，(2)這里，Q是酉矩陣，R是上三角矩陣.如果A是滿秩并規(guī)定R有正對角元，這個(gè)分解是惟一的.第44頁，共51頁，2023年，2月20日，星期一一、QR算法的基本思想記A＝A１且有A１＝Q1R1.將等號右邊兩個(gè)矩陣因子的次序交換，得A２＝R１Q１，且，(3)即A２～A１.不難證明:即Ak+1～Ak～…～A１，矩陣序列｛Ak｝有相同的特征值.記第45頁，共51頁，2023年，2月20日，星期一容易得到是Ak的一個(gè)QR分解如果A是一個(gè)滿秩的上Hessenberg矩陣，可以證明，經(jīng)過一個(gè)QR迭代步得到的A2＝Q－１１A1Q１仍然是上Hessenberg矩陣.因?yàn)樯螲essenberg矩陣次對角線以下的元素全為0，因此，只要證明，當(dāng)k→∞時(shí)，由迭代格式(4)產(chǎn)生的矩陣Ak的次對角元趨向于零就可以了.第46頁，共51頁，2023年，2月20日，星期一二、QR算法的收斂性定理9.7.3設(shè)n階矩陣A的n個(gè)特征值滿足|λ１