第8章-矩陣特征值計(jì)算..ppt

1、第8章 矩陣特征值計(jì)算,8.1 特征值性質(zhì)和估計(jì) 8.2 冪法及反冪法 8.3 正交變化與矩陣分解 8.4 QR方法,8.1 特征值性質(zhì)和估計(jì),工程技術(shù)中有多種振動(dòng)問題，如橋梁或建筑物的振動(dòng)，機(jī)械零件、飛機(jī)機(jī)翼的振動(dòng)，及一些穩(wěn)定性分析和相關(guān)分析在數(shù)學(xué)上都可轉(zhuǎn)化為求矩陣特征值與特征向量的問題.,下面先復(fù)習(xí)一些矩陣的特征值和特征向量的基礎(chǔ)知識(shí)及性質(zhì).,8.1.1 特征值問題及性質(zhì),求A的特征值問題(1.1)等價(jià)于求A的特征方程,設(shè)矩陣ARnn，特征值問題是求C和非零向量xRn，使,的根. 在5.1.3節(jié)已經(jīng)給出特征值的一些性質(zhì)，下面再補(bǔ)充一些基本性質(zhì).,Ax=x (1.1),其中是矩陣A的特征值，

2、x是矩陣A屬于特征值的特征向量. 本章討論計(jì)算矩陣特征值的數(shù)值方法, 在科學(xué)和工程技術(shù)中很多問題在數(shù)學(xué)上都?xì)w結(jié)為求矩陣的特征值問題.,定理1 設(shè)為ARnn的特征值, 且Ax=x, x0，則有,(2) -為A-I的特征值，即(A-I)x=(-)x ；,(1) c為的cA特征值(c0為常數(shù))；,(3) k為Ak的特征值，即Akx=kx ；,(4) 設(shè)A為非奇異矩陣，那么0 , 且-1為A-1的特征值，即A-1x=-1x .,定理2 (1) 設(shè)矩陣ARnn可對(duì)角化，即存在非奇異矩陣P使,的充分必要條件是A具有n個(gè)線性無關(guān)的特征向量.,(2) 如果矩陣ARnn有m個(gè)(mn)不同的特征值1, 2, m，

3、則對(duì)應(yīng)的特征向量 x1, x2, , xm 線性無關(guān).,定理3(對(duì)稱矩陣的正交約化) 設(shè)ARnn為對(duì)稱矩陣，則,(3) 存在一個(gè)正交矩陣P使的,且1, 2, n為A的特征值，而P(u1,u2,un)的列向量uj為A的對(duì)應(yīng)于j 的單位特征向量.,(1) A的特征值均為實(shí)數(shù)；,(2) A有n個(gè)線性無關(guān)的特征向量；,定義 設(shè)ARnn為對(duì)稱矩陣，對(duì)于任一非零向量x0，稱,為對(duì)應(yīng)于向量x的瑞利(Rayleigh)商.,定理4 設(shè)ARnn為對(duì)稱矩陣(其特征值依次記為12n)，則,(1). (對(duì)任何非零xRn)；,(2). ； (1.3),證明 只證(1)，關(guān)于(2)自己作練習(xí).,由于A為實(shí)對(duì)稱矩陣，可將

4、1, 2, n 對(duì)應(yīng)的特征向量 x1,x2,xn 正交規(guī)范化，則有 (xi, xj)=ij，設(shè)x0為Rn中任一向量，則有,于是,從而(1)成立. 結(jié)論(1)說明瑞利商必位于n和1之間.,8.1.2 特征值估計(jì)與擾動(dòng),定義1 設(shè)n階矩陣A=(aij)，令,(1) ；,(2) 集合 稱為復(fù)平面上以aii為圓心，以ri為半徑的n階矩陣A的n個(gè)格什戈林(Gerschgorin)圓盤.,定理5 (Gerschgorin圓盤定理),特別地，如果A的一個(gè)圓盤Di是與其它圓盤分離(即孤立圓盤)，則Di中精確地包含A的一個(gè)特征值.,(1) 設(shè)n階矩陣A(aij)，則A的每一個(gè)特征值必屬于下面某個(gè)圓盤之中,(2)

5、 如果A有m個(gè)圓盤組成一個(gè)連通的并集S，且S與余下n-m個(gè)圓盤是分離的，則S內(nèi)恰包含A的m個(gè)特征值.,或者說 A的特征值都在n個(gè)圓盤的并集中.,證明 只就(1)給出證明. 設(shè)為A的特征值，即,Ax=x，其中 x=(x1,x2, xn)T0.,或,記 ，考慮Ax=x的第k個(gè)方程，即,于是,即,這說明，A的每一個(gè)特征值必位于A的一個(gè)圓盤中，并且相應(yīng)的特征值一定位于第k個(gè)圓盤中(其中k是對(duì)應(yīng)特征向量x絕對(duì)值最大的分量的下標(biāo)).,利用相似矩陣性質(zhì)，有時(shí)可以獲得A的特征值進(jìn)一步的估計(jì)，即適當(dāng)選取非奇異對(duì)角陣,并做相似變換 .適當(dāng)選取 可使某些圓盤半徑及連通性發(fā)生變化.,例1 估計(jì)矩陣A的特征值范圍，其中

6、,解 矩陣A的3個(gè)圓盤為,由定理8，可知A的3個(gè)特征值位于3個(gè)圓盤的并集中，由于D1是孤立圓盤，所以D1內(nèi)恰好包含A的一個(gè)特征值1(為實(shí)特征值)，即,A的其它兩個(gè)特征值2, 3包含在D2, D3的并集中.,現(xiàn)在取對(duì)角陣,做相似變換,矩陣A1的3個(gè)圓盤為,顯然，3個(gè)圓盤都是孤立圓盤，所以，每一個(gè)圓盤都包含A的一個(gè)特征值(為實(shí)特征值)，且有估計(jì),定理6(Bauer-Fike定理) 設(shè)是A+IRnn的一個(gè)特征值，且P-1AP=D=diag(1, 2, n)，則有,其中|p為矩陣的p范數(shù)，p=1,2,.,證明 由于(A)時(shí)顯然成立,故只考慮(A).這時(shí)D-I非奇異，設(shè)x是A+I對(duì)應(yīng)于的特征向量，由(A

7、+I-I)x=0左乘P-1可得,而對(duì)角矩陣(D-I)-1的范數(shù)為,所以有,這就得到(1.5)式. 這時(shí)總有(A)中的一個(gè)取到m值.,由定理6可知|P-1| |P|=cond(P)是特征值擾動(dòng)的放大系數(shù)，但將A對(duì)角化的相似變化矩陣不是唯一的，所以取cond(P)的下確界,稱為特征值問題的條件數(shù). 只要v(A)不很大，矩陣微小擾動(dòng)只帶來特征值的微小擾動(dòng). 但是v(A)難以計(jì)算,有時(shí)只對(duì)一個(gè)P，用cond(P)代替v(A).,特征值問題的條件數(shù)和解線性方程組時(shí)的矩陣是兩個(gè)不同的概念，對(duì)于一個(gè)矩陣A，兩者可能一大一小，例如二階矩陣A=diag(1, 10-10)，有v(A) =1，但解線性方程組的矩陣

8、條件數(shù)cond(A)=1010.,關(guān)于計(jì)算矩陣A的特征值問題，當(dāng)n=2,3時(shí)，我們還可按行列式展開的辦法求特征方程p()=0的根. 但當(dāng)n較大時(shí)，如果按展開行列式的辦法, 首先求出p()的系數(shù)，再求p()的根，工作量就非常大，用這種辦法求矩陣特征值是不切實(shí)際的，由此需要研究A的特征值及特征向量的數(shù)值方法.,本章將介紹一些計(jì)算機(jī)上常用的兩類方法，一類是冪法及反冪法(迭代法)，另一類是正交相似變化的方法(變化法).,8.2 冪法及反冪法,冪法與反冪法都是求實(shí)矩陣的特征值和特征向量的向量迭代法，所不同的是冪法是計(jì)算矩陣的主特征值(矩陣按模最大的特征值稱為主特征值，其模就是該矩陣的譜半徑)和相應(yīng)特征向

9、量的一種向量迭代法，特別適用于大型稀疏矩陣. 而反冪法則是計(jì)算非奇異(可逆)矩陣按模最小的特征值和相應(yīng)特征向量的一種向量迭代法，特別是計(jì)算海森伯格陣或三對(duì)角陣的對(duì)應(yīng)一個(gè)給定近似特征值的特征向量的有效方法之一. 下面分別介紹冪法與反冪法.,8.2.1 冪法(又稱乘冪法),現(xiàn)討論求1及x1的方法.,設(shè)實(shí)矩陣A=(aij)有一個(gè)完全的特征向量組，即A有n個(gè)線性無關(guān)的特征向量，設(shè)矩陣A的特征值為1, 2,n, 相應(yīng)的特征向量為x1,x2,xn. 已知A的主特征值1是實(shí)根，且滿足條件,冪法的基本思想是: 任取非零的初始向量v0 , 由矩陣A構(gòu)造一向量序列vk,稱為迭代向量，由假設(shè)，v0可唯一表示為,于是

10、,其中,由假設(shè) 故 從而,為1的特征向量.,所以當(dāng)k充分大時(shí)，有,即為矩陣A的對(duì)應(yīng)特征值1 的一個(gè)近似特征向量.,用(vk)i 表示vk的第i個(gè)分量，則當(dāng)k充分大時(shí)，有,即為A的主特征值1的近似值.,由于,這種由已知非零向量v0及矩陣A的乘冪Ak構(gòu)造向量序列vk以計(jì)算A的主特征值1(利用(2.7)式)及相應(yīng)特征向量(利用(2.5)式)的方法就稱為(乘)冪法.,迭代公式實(shí)質(zhì)上是由矩陣A的乘冪 Ak與非零向量v0相乘來構(gòu)造向量序列vk=Akv0，從而計(jì)算主特征值1及其對(duì)應(yīng)的特征向量，這就是冪法的思想.,的收斂速度由比值,來確定，r 越小收斂越快，但當(dāng)r1時(shí)收斂可能很慢.,總結(jié)上述討論，有下面的定理

11、.,定理7 設(shè)ARnn有n個(gè)線性無關(guān)的特征向量，主特征值1滿足,|1|2|n|，,則對(duì)任何非零向量v0(a10)，(2.4)式和(2.7)式成立.,又設(shè)A有n個(gè)線性無關(guān)的特征向量，1對(duì)應(yīng)的r個(gè)線性無關(guān)的特征向量為x1,x2,xr，則由(2.2)式有,如果A的主特征值為實(shí)的重根, 即1=2=r, 且,|r|r+1|n|，,為1的特征向量，這說明當(dāng)A的主特征值是實(shí)的重根時(shí)，定理7的結(jié)論還是正確的.,應(yīng)用冪法計(jì)算A的主特征值1及其對(duì)應(yīng)的特征向量時(shí)，如果|1|1(或|1|1)，迭代向量 vk的各個(gè)不等于零的分量將隨 k 而趨向于無窮(或趨向于零)，這樣在計(jì)算機(jī)實(shí)現(xiàn)時(shí)就可能 “溢出”. 為克服這個(gè)缺點(diǎn)，

12、就需要將迭代向量加以規(guī)范化.,設(shè)有一向量v0，將其規(guī)范化得向量為,其中max(v)表示v的絕對(duì)值最大的分量. 即如果有,則max(v)=vq，且q為所有絕對(duì)值最大的分量中的最小下標(biāo).,在定理7的條件下冪法可這樣進(jìn)行：任取一初始向量v00(a10)，構(gòu)造規(guī)范化向量序列為,由(2.3)式,這說明規(guī)范化向量序列收斂到特征值對(duì)應(yīng)的特征向量.,收斂速度由比值r=|2/1|確定. 總結(jié)上述結(jié)論，有,同理，可得到,定理8 設(shè)ARnn有n個(gè)線性無關(guān)的特征向量，主特征值1滿足|1|2|n|，則對(duì)任意非零初始向量v0=u0(a10)，有冪法計(jì)算公式為(uk,vk),(2),例2 用冪法計(jì)算矩陣,的主特征值和相應(yīng)的

13、特征向量.,解取 v0=u0=(1,1,1)T, 則,計(jì)算結(jié)果如下表,這個(gè)結(jié)果是用8位浮點(diǎn)數(shù)字進(jìn)行運(yùn)算得到的, uk的分量值是舍入值. 于是得到,及相應(yīng)的特征向量(0.7482, 0.6497, 1)T. 1和相應(yīng)的特征向量的真值(8位數(shù)字)為,例 用冪法計(jì)算矩陣,的主特征值與其對(duì)應(yīng)的特征向量.,解取 v0=u0=(0,0,1)T , 則,直到k=8 時(shí)的計(jì)算結(jié)果見下表,從而,8.2.2 加速方法,1、原點(diǎn)平移法,由前面討論知道，應(yīng)用冪法計(jì)算A的主特征值的收斂速度主要由比值 r=|2/1|來決定，但當(dāng)r 接近于1時(shí)，收斂可能很慢. 這時(shí)，一個(gè)補(bǔ)救辦法是采用加速收斂的方法.,其中p為參數(shù)，設(shè)A的

14、特征值為i，則對(duì)矩陣B的特征值為i-p ，而且A, B的特征向量相同.,引進(jìn)矩陣 B=A-pI .,如果要計(jì)算A的主特征值1, 只要選擇合適的數(shù)p，使1-p為矩陣B=A-pI 的主特征值，且,那么，對(duì)矩陣B=A-pI應(yīng)用冪法求其主特征值1-p, 收斂速度將會(huì)加快. 這種通過求B=A-pI的主特征值和特征向量，而得到A的主特征值和特征向量的方法叫原點(diǎn)平移法. 對(duì)于A的特征值的某種分布，它是十分有效的.,例3 設(shè)AR44有特征值,比值r=|2/1|0.9. 做變換,B=A-12I (p=12),則B的特征值為,應(yīng)用冪法計(jì)算B的主特征值1的收斂速度的比值為,雖然常常能夠選擇有利的p值, 使冪法得到加

15、速, 但設(shè)計(jì)一個(gè)自動(dòng)選擇適當(dāng)參數(shù)p的過程是困難的.,下面考慮當(dāng)A的特征值是實(shí)數(shù)時(shí)，怎樣選擇p使采用冪法計(jì)算1得到加速.,且使收斂速度的比值,設(shè)A的特征值都是實(shí)數(shù)，且滿足,則對(duì)實(shí)數(shù)p，使矩陣A-pI的主特征值為1-p或n-p時(shí)，當(dāng)我們計(jì)算1及x1時(shí)，首先應(yīng)選取p使,顯然，當(dāng)2-p=-(n-p )時(shí)，即P=(2+n)/2P*時(shí)為最小值，這時(shí)收斂速度的比值為,當(dāng)希望計(jì)算n時(shí)，應(yīng)選取 p=(1+n-1)/2P* 使得應(yīng)用冪法計(jì)算n得到加速.,當(dāng)A的特征值都是實(shí)數(shù)，滿足(2.10)式,且2, n能初步估計(jì)出來，我們就能確定P*的近似值.,例4 用原點(diǎn)平移加速法求例2中矩陣A的主特征值與其對(duì)應(yīng)的特征向量.

16、,對(duì)B應(yīng)用冪法，仍取 v0=(1,1,1)T , 則,解 取p=0.75, 做平移變換B=A-pI，則,計(jì)算結(jié)果如下表,由此得B的主特征值為11.7865914，A的主特征值1為 1 = 1 +0.75 2.5365914.,原點(diǎn)位移的加速方法，是一個(gè)矩陣變換方法. 這種變換容易計(jì)算，又不破壞矩陣A的稀疏性，但p的選擇依賴對(duì)A的特征值分布的大致了解.,及相應(yīng)的特征向量為 x1(0.7482, 0.6497, 1)T.,與例2結(jié)果比較，上述結(jié)果比例2迭代15次還好. 若迭代15次11.7865258(相應(yīng)的12.5365258)就是真值.,設(shè)ARnn為對(duì)稱矩陣，稱,為向量x的瑞利商，其中(x,

17、x)=xTx為內(nèi)積. 由定理4知道，實(shí)對(duì)稱矩陣A的特征值1及n可用瑞利商的極限值表示. 下面我們將瑞利商應(yīng)用到用冪法計(jì)算實(shí)對(duì)稱矩陣A的主特征值的加速上來.,2、瑞利商(Rayleigh)加速,定理9 設(shè)ARnn為對(duì)稱矩陣，特征值滿足,對(duì)應(yīng)的特征向量xi滿足(xi, xj)=ij (單位正交向量), 應(yīng)用冪法公式(2.9)計(jì)算A的主特征值1，則規(guī)范化向量uk的瑞利商給出1的較好的近似值為,由此可見，R(uk)比k更快的收斂于1.,證明 由(2.8)式及,得,冪法的瑞利商加速迭代公式可以寫為,其中A為n階實(shí)對(duì)稱矩陣.,對(duì)給定的誤差限，當(dāng)|kk-1|時(shí)，取近似值,8.2.3 反冪法,反冪法是用于求非

18、奇異矩陣A的按模最小的特征值和對(duì)應(yīng)特征向量的方法. 而結(jié)合原點(diǎn)平移法的反冪法則可以求矩陣A的任何一個(gè)給定近似特征值對(duì)應(yīng)的特征向量.,設(shè)矩陣A非奇異,其特征值i (i=1,2,n) ,滿足,其相應(yīng)的特征向量x1,x2,xn線性無關(guān)，則 A-1 的特征值為1/ i ，對(duì)應(yīng)的特征向量仍為xi (i=1,2,n).,此時(shí), A-1的特征值滿足,因此, 對(duì)A-1應(yīng)用冪法,可求出其主特征值 1/nk 和特征向量 xnuk .,從而求得A的按模最小特征值 n 1/k 和對(duì)應(yīng)的特征向量 xnuk ， 這種求A-1的方法就稱為反冪法.,為了避免求A-1, 可通過解線性方程組Avk=uk-1得到vk，采用LU分解

19、法，即先對(duì)A進(jìn)行LU分解A=LU, 此時(shí)反冪法的迭代公式為,反冪法的迭代公式為:任取v0=u00，構(gòu)造,對(duì)給定的誤差，當(dāng)|kk-1| 時(shí)，得,顯然，反冪法的收斂速度取決于比值 ，比值越小，收斂越快.,定理10 設(shè)ARnn為非奇異矩陣，且有n個(gè)線性無關(guān)的特征向量，其對(duì)應(yīng)的特征值滿足 |1|2|n-2|n|0， 則對(duì)任意非零初始向量u0(an0) ，由反冪法計(jì)算公式構(gòu)造的向量序列vk，uk滿足,(1),(2),收斂速度的比值r=|n/n-1|.,在反冪法中也可以用原點(diǎn)平移法加速迭代過程，或求其它特征值與其對(duì)應(yīng)的特征向量.,如果矩陣(A-pI)-1存在，顯然其特征值為,對(duì)應(yīng)的特征向量仍然是x1,x2

20、,xn，現(xiàn)對(duì)矩陣(A-pI)-1應(yīng)用冪法，得到反冪法的迭代公式,如果p是A的特征值j的一個(gè)近似值，且設(shè)j與其它特征值是分離的，即,就是說1/(j-p)是矩陣 (A-pI)-1的主特征值，可用反冪法(2.12)計(jì)算特征值j及特征向量xj.,設(shè)ARnn有n個(gè)線性無關(guān)的特征向量x1,x2, xn,則,其中,同理可得下面的定理.,定理11 設(shè)ARnn有n個(gè)線性無關(guān)的特征向量， 矩陣A的特征值及對(duì)應(yīng)的特征向量分別記為i 及xi (i=1,2,n)，而p為j的近似值，(A-pI)-1存在，且,(1),(2),則對(duì)任意非零初始向量u0(aj0) ，由反冪法計(jì)算公式(2.12)構(gòu)造的向量序列vk，uk滿足,且

21、收斂速度為,由該定理知，對(duì)A-pI(其中pj)應(yīng)用反冪法，可用來計(jì)算特征向量xj，只要選擇p是j的一個(gè)較好的近似且特征值分離情況較好，一般r很小，常常只要迭代一二次就可完成特征向量的計(jì)算.,反冪法迭代公式中的vk是通過解方程組,求得的, 為了節(jié)省工作量, 可以先將A-pI進(jìn)行三角分解,于是求vk相對(duì)于解兩個(gè)三角形方程組,實(shí)驗(yàn)表明, 按下述方法選擇u0是較好的: 選u0使,用回代求解三角形方程組(2.13)即得v1，然后再按公式(2.12)進(jìn)行迭代.,反冪法計(jì)算公式：,1.分解計(jì)算P(A-pI)=LU,且保留L, U及P信息,2.反冪迭代法,(1) 解Uv1=(1,1,1)T求v1,(2) 解k

22、=2,3, 解Lyk=Puk-1求yk,解Uvk=yk求vk, k=max(vk), 計(jì)算uk=vk/k,例5 用反冪法求,的對(duì)應(yīng)于計(jì)算特征值=1.2679(精確特征值為 )的特征向量(用5位浮點(diǎn)數(shù)進(jìn)行計(jì)算).,解 用部分選主元的三角分解將A-pI(其中p=1.2679)分解為,P(A-pI)=LU,其中,由Uv1=(1,1,1)T,得,由LUv2=Pu1 ,得,3對(duì)應(yīng)的特征向量是,由此看出u2是x3的相當(dāng)好的近似.,特征值,3的真值為,8.3 正交變化與矩陣分解,正交變化是計(jì)算矩陣特征值的有力工具，本節(jié)介紹豪斯霍爾德(Householder)變換和吉文斯(Givens)變換，并利用它們討論矩

23、陣分解. 主要討論實(shí)矩陣和實(shí)向量.,8.3.1 豪斯霍爾德變換,定義2 設(shè)向量wRn，且wTw=1，稱矩陣,為初等反射矩陣，這個(gè)矩陣也稱為豪斯霍爾德變換. 如果記w=(w1,w2, ,wn)，則有,定理12 設(shè)有初等反射矩陣，其中H=I-2wwT，其中wTw=1，則,(1) H是對(duì)稱矩陣，即HT=H.,(2) H是正交矩陣，即H-1=H.,(3) 設(shè)A為對(duì)稱矩陣，那么 A1=H-1AH=HAH 即亦是對(duì)稱矩陣.,證明 只證H的正交性，其中顯然.,HTH=H2=(I-2wwT)(I-2wwT)=I-4wwT+4w(wTw)wT=I.,設(shè)向量u0，則顯然,是一個(gè)初等反射矩陣.,下面考察初等反射矩陣

24、的幾何意義. 參見圖8-1，考慮以為w法向量且過原點(diǎn)O的超平面S:wTx=0. 設(shè)任意向量vRn, 則v=x+y, 其中xS, yST. 于是,Hx=(I-2wwT)x=x-2wwTx=x.,對(duì)于yST，易知Hy=-y, 從而對(duì)任意向量vRn，總有,Hv=x-y=v.,其中v為v關(guān)于平面S的鏡面反射(見圖8-1).,初等反射矩陣在計(jì)算上的意義是它能用來約化矩陣，例如設(shè)向量Hx0，可選擇一初等反射矩陣H，使Hx=y.,定理13 設(shè)x,y為兩個(gè)不相等的n維向量, |x|2=|y|2,則存在一個(gè)初等反射矩陣H，使Hx=y.,證明 令 , 則得到一個(gè)初等反射矩陣,而且,因?yàn)?所以,容易說明，w是使Hx

25、=y成立的唯一長(zhǎng)度等于1的向量(不計(jì)符號(hào)).,定理14(約化定理) 設(shè)x=(x1,x2,xn)T0, 則存在初等反射矩陣H，使Hx=-e1，其中,證明 記y=-e1，設(shè)x y，取=|x|2，則有|x|2=|y|2，于是由定理13存在H變換 H=I-2wwT ， 其中 ，使Hx=y=-e1.,記u=x+e1=(u1,u2,un)T，于是,其中記u=(x1+,x2,xn)T， . 顯然,如果和x1異號(hào)，那么計(jì)算x1+時(shí)有效數(shù)字可能損失，我們?nèi)『蛒1有相同的符號(hào)，即取,在計(jì)算時(shí)，可能上溢或下溢，為了避免溢出，將x規(guī)范化,則有H使 H x =e1，其中,例6 設(shè)x=(3, 5, 1, 1)T，則|x|

26、2=6. 取=6,可直接驗(yàn)證Hx=-e1=(-6, 0, 0, 0)T.,8.3.2 吉文斯變換,設(shè)向量x,yR2，則變換,或,是平面上向量的一個(gè)旋轉(zhuǎn)變換，其中,為正交變換.,Rn中變換,其中x=(x1,x2,xn)T, y=(y1,y2,yn)T，而,稱為Rn中平面xi, xj的旋轉(zhuǎn)變換，也稱為吉文斯變換. P=P(i, j, )=P(i, j)稱為平面旋轉(zhuǎn)矩陣.,顯然，P=P(i, j, )具有性質(zhì)：,(1) P與單位陣I只是在(i, i), (i, j), (j, i), (j, j)位置元素不一樣，其它相同.,(2) P為正交矩陣(P-1=PT).,(3) P(i, j)A(左乘)只需

27、計(jì)算第i行與第j行元素，即對(duì)A=(aij)mn有,其中c=cos, s=sin.,(4) AP(i, j)(右乘)只需計(jì)算第i列與第j列元素,利用平面旋轉(zhuǎn)變換，可得向量x中的指定元素變?yōu)榱?,定理15(約化定理) 設(shè)x=(x1,xi,xj,xn)T, 其中不全為零，則可選擇平面旋轉(zhuǎn)陣P=P(i, j, )，使,其中,于是，由c, s的取法得,證明 取c=cos=xi/xi , s=sin =xj/xi ，由P(i, j,)x =x=(x1,xi,xj,xn)T, 利用矩陣乘法, 顯然有,8.3.3 矩陣的QR分解與舒爾分解,定理16 設(shè)ARnn非奇異，則存在正交矩陣P，使PA=R，其中R為上三

28、角矩陣.,證明 我們先用吉文斯變換給出構(gòu)造P的方法,(1) 第1步約化，由設(shè)有j(j=1,2, ,n)使aj10，則可選擇吉文斯變換P(1, j)，將aj1處的元素化為零. 即若aj10 (j=2,3, ,n)，則存在P(1, j)使得,可簡(jiǎn)記為P1A=A(2)，其中P1=P(1,n)P(1,2).,(2) 第k步約化，設(shè)上述過程已完成第1步至第k-1步，于是有,由設(shè)有j(njk)使ajk(k)0 (j=k+1,n)，則可選擇吉文斯變換P(k, j) (j=k+1,n)使,PkA(k)=P(k, n)P(k, k+1)A(k)=PkPk-1P1A=A(k+1),其中 Pk=P(k, n)P(k

29、, k+1) .,(3) 繼續(xù)上述約化過程，最后則有,Pn-1P2P1A=A(n)=R (上三角形矩陣).,令P=Pn-1P2P1, 它是一個(gè)正交矩陣, 有PA=R.,也可以用豪斯霍爾德變換構(gòu)造出正交矩陣P，記A(0)=A，它的第一列記為u1，不妨設(shè)a1(0)0，可按公式(3.2)找到矩陣 使,于是,其中,一般地，設(shè),其中D(j-1)為j-1階方陣，其對(duì)角線以下元素均為0，矩陣A(j-1)為n-j+1階方陣，設(shè)其第一列為a1(j-1)，可選擇n-j+1的豪斯霍爾德矩陣變換,使,根據(jù)Hj構(gòu)造nn階的變換矩陣Hj為,于是有,它和A(j-1)有類似的形式，只是D(j)為j階方陣，其對(duì)角線以下元素是0

30、，這樣經(jīng)過n-1步運(yùn)算得到,Hn-1H2H1A=A(n-1)=R (上三角形矩陣).,其中P=Hn-1H2H1是一個(gè)正交矩陣, 從而有PA=R.,定理17 (QR分解定理) 設(shè)ARnn為非奇異矩陣,則存在正交矩陣Q與上三角矩陣R，使,A=QR，,且當(dāng)R的對(duì)角元素為正時(shí)，分解是唯一的.,證明 從定理16可知，只要令Q=PT就有A=QR. 下面證明分解的唯一性，設(shè)有兩種分解,A=Q1R1=Q2R2，,其中Q1, Q2為正交矩陣，R1, R2為對(duì)角元素均為正的上三角矩陣，則,由假設(shè)及對(duì)稱正定矩陣ATA的楚列斯基分解的唯一性，則得R1=R2，從而可得Q1=Q2. 證畢.,定理16保證了A可分解為A=Q

31、R. 若A非奇異，則R也非奇異. 如果不規(guī)定R的對(duì)角元素為正，則分解不是唯一的. 一般按吉文斯變換或豪斯霍爾德變換方法作出的分解A=QR，R的對(duì)角元不一定是正的，設(shè)上三角矩陣R=(rij)，只要令,則 為正交矩陣， 為對(duì)角元是|rii|的上三角矩陣，這樣 便是符合定理17的唯一QR分解.,例7 用豪斯霍爾德變換作矩陣A的QR分解：,解 按(3.2)式找豪斯霍爾德矩陣H1R33，使,則有,再找H2R22, 使H2(1.44949, 3.44949)T=(*, 0)T, 得,這是一個(gè)上三角矩陣，但對(duì)角元素皆為負(fù)數(shù).,只要令D=-I，則有R=-H2H1A是對(duì)角元素為正的上三角矩陣，取,則得A=QR.

32、,除了QR分解, 矩陣的Schur分解也是重要的工具, 它解決矩陣ARnn可約化到什么程度的問題，對(duì)復(fù)矩陣ACnn，則存在酉矩陣U, 使UHAU為一個(gè)上三角矩陣R，其對(duì)角線元素就是A的特征值, A=URUH稱為A的舒爾分解，對(duì)于實(shí)矩陣A，其特征值可能有復(fù)數(shù)，A不能用正交相似變換約化為上三角矩陣，但它可約化為以下形式.,其中對(duì)角塊Rii(i=1,2,m)為一階或二階方陣, 且每個(gè)一階Rii是A的實(shí)特征值，每個(gè)二階對(duì)角塊Rii的兩個(gè)特征值是 A的兩個(gè)共軛復(fù)特征值.,定理18 (實(shí)Schur分解) 設(shè)ARnn，則存在正交矩陣Q使,記(3.4)式右端的矩陣為R，它是特殊形式的塊上三角矩陣, 由(3.4

33、)式有A=QRQT稱為A的實(shí)舒爾分解,有了定理18，可以考慮實(shí)運(yùn)算的舒爾型快速計(jì)算，通過逐次正交變換使A趨于實(shí)舒爾型矩陣，以求A的特征值.,8.3.4 用正交相似變換 約化一般實(shí)矩陣為上海森伯格矩陣,設(shè)ARnn，下面來說明, 可選擇初等反射矩陣U1,U2,Un-2使A經(jīng)正交相似變換約化為一個(gè)上海森伯格陣.,(1) 設(shè),其中c1=(a21,an1)TRn-1，不妨設(shè)c10 , 否則這一步不需要約化. 于是, 可選擇初等反射陣 使 ，其中,令,則,其中,(2) 第k步約化：重復(fù)上述過程，設(shè)對(duì)A已完成第1步,第k-1步正交相似變換，即有,或,且,其中 為k階上海森伯格陣，,設(shè)ck0, 是可選擇初等反

34、射陣Rk使 其中，Rk計(jì)算公式為,令,則,其中 為k+1階上海森伯格陣，第k步約化只需計(jì)算 及 (當(dāng)A為對(duì)稱矩陣時(shí)，只需要計(jì)算 ).,(3) 重復(fù)上述過程，則有,定理19 (豪斯霍爾德約化矩陣為上海森伯格陣) 設(shè)ARnn則存在初等反射矩陣U1,U2,Un-2 使,為上海森伯格矩陣.,總結(jié)上述結(jié)論，有,本算法約需要5n3/3次乘法運(yùn)算. 如果要把U0也算出來還需要增加2n3/3次乘法.,例8 用豪斯霍爾德方法將矩陣,約化為上海森伯格陣.,解 選取初等反射陣R1使 , 其中c1=(2,4)T.,(1) 計(jì)算R1:,則有,(2) 約化計(jì)算: 令,則得到上海森伯格陣為,如果A是對(duì)稱的，則H=U0TAU

35、0也對(duì)稱，這時(shí)H是一個(gè)對(duì)稱三對(duì)角矩陣.,定理20 (豪斯霍爾德約化對(duì)稱矩陣為對(duì)稱三對(duì)角矩陣) 設(shè)ARnn為對(duì)稱矩陣，則存在初等反射矩陣U1,U2,Un-2使,為對(duì)稱三對(duì)角矩陣.,證明 由定理19, 存在初等反射矩陣U1,U2,Un-2 使 為上海森伯格陣，且An-1亦是對(duì)稱矩陣，因此， An-1為對(duì)稱三對(duì)角矩陣.,由上面討論可知，當(dāng)A為對(duì)稱陣時(shí)，由AkAk+1 =Ak Uk Ak一步約化計(jì)算中只需計(jì)算Rk及Rk A22(k)Rk . 又由于A的對(duì)稱性，故只需計(jì)算Rk A22(k)Rk的對(duì)角線以下元素. 注意到,引進(jìn)記號(hào),則有,對(duì)對(duì)稱陣A用初等反射陣正交相似約化為對(duì)角三對(duì)角陣大約需要2n3/3次乘法.,用正交矩陣進(jìn)行相似約化有一些特點(diǎn)，如構(gòu)造的 Uk容易求逆，且Uk的元素?cái)?shù)量級(jí)不大，這個(gè)算法是十分穩(wěn)定的.,8.4 QR 方 法,8.4.1 QR算法,Rutishauser(1958)利用矩陣的三角分解提出了計(jì)算矩陣特征值的LR算法，F(xiàn)rancis(1961,1962)利用矩陣的QR分解建立了計(jì)算矩陣特征值