數(shù)值分析第8章-矩陣特征值問題計算

章矩陣特征值問題計算對n階方陣A求數(shù)和非零向量x,使其滿足Ax=x這樣的值稱為矩陣A的特征值，非零向量x稱為矩陣A的與特征值相對應的一個特征向量。2021/5/91定義1

設矩陣A,BRnn，若有可逆陣P，使

則稱A與B相似。定理1

若矩陣A,BRnn且相似，則 （1）A與B的特征值完全相同； （2）若x是B的特征向量，則Px便為A的特征向量。8.1

預備知識2021/5/92定理2：設ARnn具有完全的特征向量系，即存在n個線性無關(guān)其中i為A的特征值，P的各列為相應于i的特征向量。

的特征向量構(gòu)成Rn的一組基底，則經(jīng)相似變換可化A為對角陣，即有可逆陣P，使2021/5/93定理3

：ARnn，1,…,n為A的特征值，則（2）A的行列式值等于全體特征值之積，即（1）A的跡數(shù)等于特征值之和，即2021/5/94定理42021/5/95定理5

設ARnn為對稱矩陣，其特征值1≥2≥…≥n，則

（1）對任意ARn，x≠0，（2）（3）2021/5/96定理6

（Gerschgorin圓盤定理）設ARnn，則表示以aii為中心，以

半徑為的復平面上的n個圓盤。

（2）如果矩陣A的m個圓盤組成的并集S（連通的）與其余（1）A的每一個特征值必屬于下述某個圓盤之中，n–m個圓盤不連接，則S內(nèi)恰包含m個A的特征值。

2021/5/972021/5/982021/5/992021/5/9102021/5/9112021/5/912定理72021/5/9132021/5/914一冪法1基本思想任取非零向量v0

,則可唯一表示為

設n階矩陣A的特征值,滿足

,且其對應有n個線性無關(guān)的特征向量x1

,x2,…,xn

，即8.2冪法和反冪法2021/5/915則2021/5/916其中由假設條件所以當k充分大時，有從而所以2021/5/917即為矩陣A

的對應特征值1的近似特征向量。用(vk)i表示vk

的第i

個分量,則當k充分大時,有即為主特征值的近似值。且2021/5/918設有主特征值滿足個線性無關(guān)的特征向量，則對任意非零初始向量，下面的式子成立定理2021/5/919

迭代公式(1)實質(zhì)上是由矩陣A的乘冪Ak與非零向量v0相乘來構(gòu)造向量序列{xk},從而計算主特征值及其對應的主特征向量,故稱這種方法為冪法。2021/5/920設有主特征值滿足個線性無關(guān)的特征向量，則對任意非零初始向量定理按照下述方法構(gòu)造的向量序列則有2021/5/9212.冪法實用計算公式2021/5/922例1

求矩陣的主特征值與其對應的特征向量。解取v0=(0,0,1)T

,則2021/5/923直到k=8時的計算結(jié)果見下表0.5,1,0.750011.00005.5000,11.0000,8.250080.5,1,0.750011.00055.5002,11.0005,8.250170.5,1,0.750110.99745.4987,10.9974,8.249460.5,1,0.749411.01425.5075,11.0142,8.257650.5,1,0.753610.92235.4621,10.9223,8.230640.5,1,0.736011.44445.7222,11.4444,8.36130.5,1,0.861194.5,9,7.7520.5,1,0.2542,4,1,1k從而2021/5/924二、冪法的加速1、原點平移法

如果是矩陣A

的特征值,則對任意的實數(shù)p,矩陣A-pE

的特征值為

-p,且

A與A-pE

的特征向量相同.據(jù)此,如果要計算A

的主特征值1,只要選擇合適的數(shù)p,使1-p

為矩陣A-pE

的主特征值,且那么,對矩陣A-pE

應用冪法求其主特征值1-p,收斂速度將會加快.這種通過求A-pE

的主特征值和特征向量,進而得到A的主特征值和特征向量的方法叫原點平移法。2021/5/925且使顯然,當2-p=-(n-p),即P=(2+n)

2

時,上式取最小值;如果希望計算n,類似的討論可知應選取p=(1+n-1)2

。則對任意實數(shù)p,矩陣A-pE

的主特征值為1-p或n-p,要求1,則選p使2021/5/926例2

用原點平移加速法求例1中矩陣A的主特征值與其對應的特征向量。解取p=-2.5,做平移變換B=A-pE，則對B應用冪法，仍取x0=(0,0,1)T

,則2021/5/927迭代5步的計算結(jié)果見下表0.5,1,0.750013.50006.7500,13.5000,10.125050.5,1,0.750013.50076.7503,13.5007,10.125640.5,1,0.750713.51796.76,13.5179,10.140630.5,1,0.7545147,14,10.562520.5,1,0.87542,4,3.51k可得到B的主特征值113.5000特征向量v1(0.5,1.0,0.7500)T

因此,A的主特征值為1=1+p11.0000,特征向量仍為v1=(0.5,1,0.7500)T。2021/5/9282021/5/9292021/5/930設A為n階實對稱矩陣，稱為向量x

的瑞利商，其中(x,x)=xTx

為內(nèi)積。不難證明，對實對稱矩陣A，如果其特征值滿足2、瑞利商加速由冪法公式生成的xk

的瑞利商滿足由此可見，R(xk)比

mk

更快的收斂于1

。2021/5/931冪法的瑞利商加速迭代公式為其中A為n階實對稱矩陣。對給定的誤差限，當|mk–mk-1|<

時，取2021/5/932三、反冪法

反冪法是用于求非奇異矩陣A的按模最小的特征值和對應特征向量的方法.而結(jié)合原點平移法的反冪法則可以求矩陣A的任何一個具有先驗了解的特征值和對應的特征向量。設矩陣A非奇異,其特征值i(i=1,2,…,n),滿足其相應的特征向量x1

,x2,…,xn

線性無關(guān),則A-1

的特征值為1/i，對應的特征向量仍為xi

(i=1,2,…,n).2021/5/933此時,A-1

的特征值滿足因此,對A-1

應用冪法,可求出其主特征值

1/n

和特征向量xn

uk,從而求得A的按模最小特征值

n

1/和對應的特征向量xn

uk，這種方法稱為反冪法。2021/5/934為了避免求A-1,可通過解線性方程組Avk=uk-1

得到y(tǒng)k

，采用LU分解,即先對A進行LU分解A=LU,此時反冪法的迭代公式為2021/5/935對給定的誤差，當|–|<

時，得顯然，反冪法的收斂速度取決于比值，比值越小，收斂越快。例3

用反冪法求矩陣的對應于特征值的特征向量2021/5/936解取解方程組得解方程組得2021/5/937

與的對應分向量大體上成正比,所以對應于

的特征向量為

2021/5/938QR算法也是一種迭代算法,是目前計算任意實的非奇異矩陣全部特征值問題的最有效的方法之一.該方法的基礎(chǔ)是構(gòu)造矩陣序列,并對它進行QR分解.

由線性代數(shù)知識知道,若A為非奇異方陣,則A可以分解為正交矩陣Q與三角形矩陣R的乘積,即A=QR,而且當R的對角線元素符號取定時,分解式是唯一的.8.4QR算法2021/5/939

若A為奇異方陣,則零為A的特征值.任取一數(shù)p

不是A的特征值,則A-pI

為非奇異方陣.只要求出A-pI

的特征值,就很容易求出A的特征值,所以假設A為非奇異方陣,并不防礙討論的一般性.設A為非奇異方陣,令,對進行QR分解,

即把分解為正交矩陣與上三角形矩陣的乘積作矩陣繼續(xù)對進行QR分解

并定義2021/5/940一般地,遞推公式為

QR

算法就是利用矩陣的QR分解,按上述遞推公式構(gòu)造矩陣序列.只要A為非奇異方陣,則由QR算法就完全確定這個矩陣序列具有如下性質(zhì).性質(zhì)1

所有都相似,它們具有相同的特征值.2021/5/941證明

因為若令,則為正交陣,且有

因此與A相似,他們具有相同的特征值.2021/5/942性質(zhì)2

的QR

分解式為其中證明用歸納法.顯然當

k=1時,有

假設有分解式

于是2021/5/943因為,所以定理1

如果收斂于非奇異矩陣,為上三角形矩陣,則存在并且是上三角形矩陣.因為都是正交陣,所以也是正交陣,同樣也是上三角陣,從而的QR分解式為2021/5/944證明因為收斂,故下面極限存在

由于為上三角形矩陣,所以為上三角形矩陣.又因為所以存在,并且是上三角形矩陣.2021/5/945定理2(QR

算法的收斂性)設A為n階實矩陣.(1)A的特征值滿足:(2)

其中

且設有三角分解式(L的單位下三角陣,U為上三角陣).

則由

QR算法得到的矩陣序列本質(zhì)上收斂于上三角形矩陣.即滿足2021/5/946

的極限不一定存在.證明因為矩陣決定的收斂

性.又我們利用求,然后討

論的收斂性.由定理條件得2021/5/947其中的(i,j)元素為于是

由假設,當

i>j時,故設方陣X的QR

的分解式為由2021/5/948由知,對充分大的k,

非奇異,它應有唯一的

QR分解式,并且

于是但上三角陣的對角線元素不一定大于零.為此,引入對角陣以便保證的對交線元素都是正數(shù)2021/5/949從而得到的QR分解式由的QR分解式的唯一性得到

從而由于所以2021/5/950從而其中于是因為為上三角陣,為對角陣,且元素為1或-1,所以2021/5/951

的極限不一定存在2021/5/952例1

用

QR算法求矩陣特征值.A的特征值為-1,4,1+2i.

2021/5/953解令用施密特正交化過程將分解為2021/5/954將與逆序相乘,求出用代替A重復上面過程,計算11次得2021/5/955由不難看出,矩陣A的一個特征值是4,另一個特征值是-1,其它兩個特征值是方程的根.求得為

2021/5/956上Hessenberg化2021/5/9572021/5/9582021/5/9592021/5/9602021/5/9612021/5/9622021/5/963用正交變換化對稱矩陣為對稱三對角陣2021/5/964帶原點位移的QR算法2021/5/9652021/5/966用單步QR方法計算上Hessenberg特征值2021/5/9672021/5/9682021/5/9692021/5/9702021/5/9712021/5/9722021/5/9732021/5/9742021/5/9752021/5/9762021/5/9772021/5/9782021/5/9792021/5/9802021/5/9812021/5/9822021/5/9832021/5/9842021/5/9852021/5/986隱式QR算法2021/5/9872021/5/9882021/5/9892021/5/9902021/5/9912021/5/992定理6設A為n階實對稱矩陣，則必存在正交矩陣P使得其中為A的n個特征值。證設A的互不相同的特征值為它們的重數(shù)依次為根據(jù)性質(zhì)1和性質(zhì)3知，恰有個線性無關(guān)的實特征向量，對應于特征值2021/5/993把它們標準正交化，特征向量組，特征向量共有n個，并有其中為A的n個特征值。個單位正交的就可得到知，由這樣的特征值的特征向量是正交的，向量兩兩正交，以它們?yōu)榱邢蛄繕?gòu)成正交矩陣P，又由性質(zhì)2知，A的屬于不同故這n個單位特征2021/5/994由定理6可知，實對稱矩陣的對角化問題，實質(zhì)上是求正交矩陣P的問題，計算P的步驟如下：（1）（2）求出齊次線性方程組的基礎(chǔ)解系，進行正交化和單位化，得到A對于的一組標準正交的特征向量，的個數(shù)恰好是作為A的特征值的重數(shù)；求出實對稱矩陣A的全部特征值對于各個不同的特征值對基礎(chǔ)解系這個向量組所含向量2021/5/995（3）量構(gòu)成一組的標準正交基（4）則P為正交矩陣且使得為對角陣，對角線上的元素為相應特征向量的特征值。的所有標準正交的特征向?qū)⑷?021/5/996例13設實對稱矩陣求正交陣解得特征值2021/5/9972021/5/9987.2對稱QR方法對稱矩陣的三對角化2021/5/999帶原點位移的QR迭代2021/5/91002021/5/9101隱式QR迭代2021/5/91022021/5/9103定義Jacobi方法是用來計算實對稱矩陣A的全部特征值及其相應特征向量的一種變換方法.Jacobi方法的基本思想是通過一系列的平面旋轉(zhuǎn)矩陣構(gòu)成的正交變換將對稱矩陣逐步化為對角陣,從而得到A的全部特征值及其相應的特征向量.定理(1)如果n階方陣A滿足 則稱A為正交陣.

7.3Jacobi方法2021/5/9104(2)

設A是n階實對稱矩陣,則A的特征值都是實數(shù),并且有互相正交的n個特征向量.(3)

相似矩陣具有相同的特征值.

(4)

設A是n階實對稱矩陣,P為n階正交陣,則

B=PAP

也是對稱矩陣.(5)n階正交矩陣的乘積是正交矩陣。設A是n階實對稱矩陣,則必有正交矩陣P，使

2021/5/9105由(6)可知,對于任意的階實對稱矩陣A,只要能求得一個正交陣P,使則可得到A

的全部特征值及其相應的特征向量,這就是雅克比方法的理論基礎(chǔ).其中

的對角線元素是A的n個特征值，正交矩陣P的第i列是A的對應于特征值的特征向量。下面我們詳細介紹雅可比方法。首先引進中的平面旋轉(zhuǎn)變換.變換2021/5/9106ijij記為,其中2021/5/9107X=,Y=,

稱為平面內(nèi)的平面旋轉(zhuǎn)矩陣.容易得到如下性質(zhì):

則稱x=為中平面內(nèi)的一個旋轉(zhuǎn)變換,(2)

的主對角線元素中除第i個與第j個元素為外,其它元素均為1;非對角元素中除第i行第j列元素為,第j行第i列元素為外,其它元素均為零.(1)為正交矩陣2021/5/9108(3)

只改變A的第i行第j行元素,AP只改變A的第i列第j列元素,所以只改變A的第i行,

第j行,第i列,第j列元素.

設A=為n階實對稱矩陣,

為一非對角線元素.令

則為實對稱矩陣,且與A有同的特征值.通過直接計算知2021/5/91092021/5/9110當取滿足關(guān)系式時,且由于在正交相似變換下,矩陣元素的平方和不變,所以若用D(A)表示矩陣A的對角線元素的平方和,用S(A)表示A的非對角元素平方和,則由(11)式得2021/5/9111,的非對角元素平方和A的非對角元素平方

且將事先選定的非對角元素消去了這說明用對A作正交相似變換化為后,的對角線元素平方和比A的對角元素平方和增加了和減少了2021/5/9112

因此,只要我們逐次地用這種變換,就可以使得矩陣A的非對角線元素平方和趨于零,也即使得矩陣A逐步化為對角陣.

這里需要說明一點:并不是對矩陣A的每一對非對角線非零元素進行一次這樣的變換就能得到對角陣.因為在用變換消去的時候,只有第

i行,第

j行,第

i列,第

j列元素在變化,如果或

為零,經(jīng)變換后又往往不是零了.2021/5/9113

雅克比方法就是逐步對矩陣A進行正交相似變換,消去非對角線上的非零元素,直到將A的非對角線元素化為接近與零為止,從而求得A的去全特\征值,把逐次的正交相似變換矩陣乘起來,便是所要求的特征向量.Jacobi的計算步驟歸納如下:第一步在矩陣A的非對角元素中選取一個非零元素.一般來說,取絕對值最大的非對角線元素.2021/5/9114第二步由公式求出,從而得