7.4QR算法,7.4.3帶原點(diǎn)位移的QR算法,7.4.2QR算法及其收斂性,7.4.1化矩陣為Hessenberg形,7.4.1化矩陣為Hessenberg形,定理7.9（實(shí)Schur分解定理）,為（初等）鏡面反射矩陣，或Householder變換矩陣。,Houholder矩陣H=H（w）有如下性質(zhì)：,(1),(2),(3)記S為與w垂直的平面,則幾何上x與y=Hx關(guān)于平面S對(duì)稱。事實(shí)上,由,對(duì)應(yīng)于性質(zhì)（2），有下面的定理。,證,由此可得,定理得證。,（7.4.2）,（7.4.3）,例7.4,解,證,變換，有,如此類推，經(jīng)n-2步對(duì)稱正交相似變換，得到Hessenberg形矩陣。,7.4.2QR算法及其收斂性,上式左邊為正交陣，即,這個(gè)式子左邊是下三角陣，則右邊是上三角陣，所以只能是對(duì)角陣。設(shè),定理得證。,一般按平面旋轉(zhuǎn)變換或鏡面反射變換作出的分解A=QR，R的對(duì)角元不,（7.4.5）,證容易證(1)從它遞推得,例7.5用QR方法求下列矩陣的全部特征值。,該矩陣A非對(duì)稱，從計(jì)算結(jié)果看，收斂于上三角陣。,（2）的計(jì)算結(jié)果為,從計(jì)算結(jié)果來看，迭代收斂于Schur分塊上三角形，對(duì)角塊分別是1階和2階子,一般在實(shí)際使用QR方法之前，先用鏡面反射變換將A化為Hessenberg形矩陣H，然后對(duì)H作QR迭代，這樣可以大大節(jié)省運(yùn)算工作量。因?yàn)樯螲essenberg陣H的次對(duì)角線以下元素均為零，所以用平面旋轉(zhuǎn)變換作QR分解較為方便。,對(duì)i=1,2,.n-1,依次用平面旋轉(zhuǎn)矩陣J（i,i+1）左乘H，使J（i,i+1）H的第i+1行第i列元素為零。左乘J(i,i+1)后，矩陣H的第i行與第i+1行零元素位置上仍為零，其他行不變。這樣，共n-1次左乘正交矩陣后得到上三角陣R。即=R，=J（n-1,n）J(n-2,n-1)J(1,2)。可以驗(yàn)證是一個(gè)下Hessenberg陣，即U是一個(gè)上Hessenberg陣。這樣，得到H的QR分解H=UR。在作QR迭代時(shí)，下一步計(jì)算RU，容易驗(yàn)證RU是一個(gè)上Hessenberg陣。以上說明了QR算法保持了H的上Hessenberg結(jié)構(gòu)形式。,解,重復(fù)上面的過程，計(jì)算11次得,至此，不難看出，一個(gè)特征值是4，另一個(gè)特征值是-1，其他兩個(gè)特征值是方程,上述用QR方法求得的特征值是該特征方程的準(zhǔn)確解。,7.4.3帶原點(diǎn)位移的QR算法前面我們介紹了在反冪法中應(yīng)用原點(diǎn)位移的策略，這種思想方法也可用于QR算法。一般我們針對(duì)上Hessenberg矩陣討論QR算法，并且假設(shè)每次QR迭代中產(chǎn)生的都是不可約的，否則，可以將問題分解為較小型的問題。這樣，帶原點(diǎn)位移的QR算法可以描述為：,根據(jù)QR算法的收斂性質(zhì)，位移量有下列兩種取法：,例7.7用帶原點(diǎn)位移的QR算法求下列矩陣的特征值：,解先用鏡面反射變換把A化為上Hessenberg矩陣。按（7.4.3）式有,該問題如果不用帶原點(diǎn)位移的QR算法，而是用基本QR算法，則收斂速度很慢，計(jì)算結(jié)果為,