北航數(shù)值B第三章課件Ch3

計(jì)算上Hessenberg陣的全部特征值計(jì)算對(duì)稱三對(duì)角陣的全部特征值收斂快、算法穩(wěn)定利用正交相似變換（Householder變換）、QR分解將矩陣A化

QR算法的應(yīng)用：優(yōu)點(diǎn)：理論基礎(chǔ)：

QR算法：變換法§4QR算法特征值相同

思想方法：為簡(jiǎn)單矩陣。如上Hessenberg陣、對(duì)稱三對(duì)角陣。A相似于B的定義：設(shè)矩陣，如果存在可逆矩陣X使上Hessenberg陣的定義：（2）若，稱B為不可約上Hessenberg陣。B=X-1AX，則稱B相似于A，記為時(shí)，bij=0,稱B為上Hessenberg陣，即（1）設(shè)，如果當(dāng)i>j+1一、基本QR方法二、帶原點(diǎn)位移的QR方法三、上Hessenberg陣的單步QR方法本節(jié)內(nèi)容：（加速收斂的方法）一、基本QR方法B的構(gòu)造如下：（一）過程（1）QR分解：（2）逆序相乘（作矩陣）：B=RQQ-1=QT顯然，B是由A經(jīng)過正交相似變換(Householder)得到。因此，A=QR，R是上三角陣，Q為正交陣。,從而，B與A有相同的特征值。構(gòu)造序列{Ak}

設(shè),先分解：A1=Q1R1，再分解：A2=Q2R2，Ak=QkRk,…………這樣由矩陣的QR分解，按正交相似變換構(gòu)造矩陣序列{Ak}的過程稱為QR算法。=QTAQ，R=Q-1A=QTAAk+1=RkQk=QkTAkQk；作矩陣：A2=R1Q1=Q1TA1Q1

；作矩陣：A3=Q2TA2Q2

；{Ak}的性質(zhì)：（1）Ak+1相似于Ak，即Ak+1=QkTAkQk

；定理13QR序列{Ak}滿足：（2）Ak+1=(Q1Q2…Qk)TA1(Q1Q2…Qk)（3）Ak的QR分解式為：分析:(1)因?yàn)锳k→Ak＋1是正交相似變換，因此（2）由記，及QR算法Ak+1=RkQk

=QkTAkQk,(k=1,2,…)得Ak+1=QkT

(Qk-1TAk-1Qk-1)Qk=…=QkTQk-1T…Q1TA1Q1Q2…Qk=(Q1Q2

…

Qk)TA1(Q1Q2

…

Qk)矩陣的結(jié)合律（3）要證用歸納法證。即要證Ak=(Q1Q2…Qk)(Rk…R2R1),Ak=QkRk，Ak+1=RkQk=QkTAkQk（k=1,2,…)又因?yàn)樽C明：當(dāng)k=1時(shí)，有假設(shè)Ak-1{Ak}的性質(zhì)：（1）Ak+1相似于Ak，即Ak+1=QTkAkQk

；定理13QR序列{Ak}滿足：（2）Ak+1=(Q1Q2…Qk)TA1(Q1Q2…Qk)（3）Ak的QR分解式為：=(Q1Q2

…

Qk-1

)(Rk-1

…

R2R1

),則=(Q1Q2

…

Qk-1Qk)

（RkRk-1

…

R2R1

)=(Q1Q2

…

Qk-1

)Ak(Rk-1

…

R2R1

)所以#Ak+1=(Q1Q2…Qk)TA1(Q1Q2…Qk)Ak)(QkRk)(QkRk=(Q1Q2

…

Qk-1Qk)

（Rk)=(Q1Q2

…

Qk-1

)Ak=A

(Q1Q2

…

Qk-1

)

QkTAk=Rk從而

Ak+1=QkT

AkQk方法：（1）左變換：Pn-1…P2P1

Ak＝Rk

（上三角陣）（2）右變換：Rk

P1TP2T

…

Pn-1T=

Ak+1

,(k=1,2,…)(二)由Ak計(jì)算Ak+1的方法，將Ak進(jìn)行QR分解，即是對(duì)Ak施行正交變換（左變換）化為上三角陣Rk，即QkT=Pn-1…P2P1,Pi(i=1,2,…,n-1)為正交陣,k=1,2,…=Pn-1…

P2P1

Ak

P1T

P2T

…

Pn-1T上三角陣定理14設(shè)（1）A的特征值滿足：；（2）A有標(biāo)準(zhǔn)型，即存在非奇異陣X使A=XDX-1，其中則由QR算法產(chǎn)生的序列{Ak}本(三)QR方法的收斂性本質(zhì)收斂:設(shè)稱本質(zhì)上收斂于上三角陣R,當(dāng)收斂定理L--單位下三角陣，U--上三角陣。D=diag[]（對(duì)角陣），且設(shè)X-1有三角分解X-1=LU，質(zhì)上收斂于上三角陣，即A的特征值滿足：定理15設(shè)為對(duì)稱矩陣且滿足定理14的條件(1),則由QR算法產(chǎn)生的矩陣說明：QR算法收斂性進(jìn)一步結(jié)果，若A的等模特征值中只有實(shí)若A為對(duì)稱矩陣，則由QR算法產(chǎn)生的序列{Ak}仍為對(duì)稱矩陣。序列{Ak}收斂于對(duì)角矩陣D=diag[]。特征值或復(fù)的共軛特征值，則由QR算法產(chǎn)生的矩陣序列{Ak}本質(zhì)上收斂于分塊上三角矩陣（對(duì)角塊為一階或二階子塊），且對(duì)角塊每一個(gè)2×2子塊給出一對(duì)共軛復(fù)特征值，或每一個(gè)一階對(duì)角塊給出實(shí)特征值。二帶原點(diǎn)位移的QR方法（加速收斂的方法）設(shè)A的特征值滿足：。由QR算法產(chǎn)生的矩陣序列{Ak}元素,其收斂速度依賴于，那么當(dāng)|rn|很小時(shí)，收斂較快。若是一個(gè)估計(jì)，且對(duì)運(yùn)斂于0。此時(shí)，(n,n)元素將比在基本QR算法中收斂更快。因此，用QR算法，則(n,n-1)元素將以收斂因子線性收為了加速收斂，選擇數(shù)列，從而有帶原點(diǎn)位移的QR算法。(一)帶原點(diǎn)位移的QR算法設(shè)，QR分解：作矩陣：QR分解：若已求得Ak，QR分解：作矩陣：若已求得Ak，結(jié)論：(3)帶位移QR算法變換一步的計(jì)算：右變換：先用正交變換（左變換）將化為上三角陣，即左變換：，其中（二）矩陣A化為上Hessenberg陣的QR算法(1)一般算法設(shè),有，為上Hessenberg陣,以下考慮上QR算法:Hk=QkRkQR分解當(dāng)k=1,2,…時(shí),(a)假設(shè)由（4.3）式產(chǎn)生的每一個(gè)Hessenberg陣Hk都是可約pn-pPn-pHessenberg陣的QR算法。Hk+1=RkQk的,即若在某步有問題就分離為H11與H22的兩個(gè)較小的問題。特別當(dāng)p=n-1或p=n-2時(shí)，有當(dāng)p=n-1時(shí)，當(dāng)p=n-2時(shí)，n-22n-22問題就分離為H11與H22的兩個(gè)較小的問題。特別當(dāng)p=n-1或p=n-2,H的特征值，H的特征值可由Hk+1下這樣，求H特征值問題可降階求H11特征值。角二階矩陣的特征值得到。pn-pPn-p特別當(dāng)p=n-1或p=n-2時(shí)，有例如時(shí)，就把視為零，其中(2)用位移加速收斂當(dāng)k=1,2,…時(shí)(QR分解)(作矩陣Hk+1