計算特征值問題的QR算法的收斂性分析

王麗 首都經(jīng)濟貿(mào)易大學(xué)

一、引言

矩陣特征值問題的應(yīng)用十分廣泛，各個方面都有它的身影。在數(shù)學(xué)方面，可以利用矩陣特征值問題來解決類似非線性規(guī)劃和常微分方程等各種數(shù)學(xué)計算問題；在工程上，可以利用其來解決類似自動控制、結(jié)構(gòu)設(shè)計以及振動系統(tǒng)等相關(guān)的各類問題；在科學(xué)上，如一些力學(xué)方面的研究、統(tǒng)計計算、化學(xué)工程等等實際問題的計算也需要用到矩陣的特征值；此外，矩陣特征值在幾何、概率、物理學(xué)、經(jīng)濟學(xué)、天文、信息論等各個方面，以及管理科學(xué)、社會科學(xué)等各個領(lǐng)域也有廣泛的應(yīng)用，很多實際問題的求解往往最終都會轉(zhuǎn)化為矩陣特征值問題。本文將介紹計算特征值問題的基本QR算法及其改進算法。

二、基本QR算法

（一）QR算法基本思想

假設(shè)矩陣A∈Rn×n，并且對矩陣A進行QR分解有A=QR，其中，矩陣Q為正交陣，矩陣R為上三角陣，于是可以得到一個新的矩陣

很明顯，矩陣D是由矩陣A通過正交相似變換得到的，所以矩陣D與矩陣A具有相同的特征值。接著對矩陣D作QR分解，就又可以得到一個新矩陣，重復(fù)這一過程，可以得到矩陣序列：

QR算法其實就是利用矩陣的QR分解，按照上述的遞推法則來構(gòu)造矩陣序列的過程。只要矩陣A是非奇異矩陣，那么由QR算法就完全確定矩陣序列

（二） QR算法的收斂性分析

如果對稱矩陣A滿足上述兩個條件，則通過QR算法產(chǎn)生的矩陣序列收斂于對角陣

三、 帶位移的QR算法

（一） 帶位移的QR算法

帶位移的QR算法：

形成一個新的矩陣

以此類推，求得矩陣Ak之后，再對矩陣進行QR分解

形成一個新的矩陣

在上述算法中，位移t為λn的一個估計，并且，對矩陣A-tI運用QR算法，那么元素將會以收斂因子線性收斂到零，(n,n)元素將會比基本QR算法中的收斂更快。

（二）位移的選取

為了實現(xiàn)快速收斂，在算法中納入一個有效的位移至關(guān)重要。常用的位移有Rayleigh商位移以及Wilkinson位移。

一般來說，帶Rayleigh商位移的QR算法的收斂性，對于對稱矩陣A，算法幾乎全局收斂，并且為漸近平方階收斂。帶Wilkinson位移的QR算法的收斂性，對于對稱矩陣A，算法可保證全局收斂，收斂速度為幾乎漸近立方階收斂.

四、數(shù)值實驗

（一）基本QR算法數(shù)值實驗

在前面部分，主要給出了計算特征值問題的基本QR算法，帶原點位移的QR算法。當(dāng)然，給出的基本QR算法及其改進算法都是理論上的研究，需要實際去驗證一下。

基本QR算法想要收斂，矩陣A需要滿足兩個條件，矩陣A的特征值要滿足：，以及矩陣A有的標(biāo)準(zhǔn)型，其中矩陣因此，為了避免出現(xiàn)這種由于條件不滿足而導(dǎo)致的不收斂情況，在用Matlab軟件生成矩陣A時，可以先給定矩陣的特征值為，接著再構(gòu)造矩陣A。由基本QR算法的收斂性分析可知，基本QR算法在。因此，在理論上，對于矩陣A，QR算法的收斂速度為。接著，利用所編寫的函數(shù)驗證其基本QR算法的收斂性，并畫出理論上與實際上的收斂曲線，為了使所畫曲線更直觀，對收斂誤差取完對數(shù)后再作圖，得出實際的收斂曲線，對理論的收斂速度取對數(shù)得并作圖，得到理論上的收斂曲線，如下圖所示。

圖1 基本QR算法收斂曲線

由上圖可以看出，基本QR算法的實際收斂曲線與理論收斂曲線重疊，收斂性基本一致，都可以近似為線性收斂。

（二）帶位移的QR算法數(shù)值實驗

由前面的章節(jié)可知，引入一個具體的位移可以明顯的加快收斂速度，減少迭代次數(shù)，并且選取不同的位移，會產(chǎn)生不同的收斂效果。在這一部分，將會驗證帶Rayleigh商位移的QR算法與帶Wilkinson位移的QR算法同原算法相比，收斂速度是否有所改善，并利用Matlab軟件作出幾種算法的收斂曲線進行對比分析，結(jié)果如下。

圖2 帶Rayleigh商位移的QR算法收斂曲線

圖3 帶Wilkinson位移的QR算法收斂曲線

由圖2帶Rayleigh商位移的QR算法收斂曲線可以看出，帶Rayleigh商位移的QR算法收斂，并且為漸近平方階收斂，符合理論結(jié)果。由圖3帶Wilkinson位移的QR算法收斂曲線可以看出，帶Wilkinson位移的QR算法也是收斂的，收斂速度為漸近立方階收斂.

圖4 基本QR算法與改進算法的收斂曲線對比圖

由圖4基本QR算法與改進算法的收斂曲線對比圖，可以很明顯的看出，帶位移的QR算法的收斂速度明顯快于基本的QR算法，即位移起到了加速效果。并且，兩種不同的位移加速效果也是不同的，其中帶Rayleigh商位移的QR算法的收斂速度較之原算法有明顯的提高，而帶Wilkinson位移的QR算法比帶Rayleigh商位移的QR算法要收斂的更快，加速效果更好。

由圖4基本QR算法與改進算法的收斂曲線對比圖還可得看出，在取精度為10-8時，基本QR算法求出矩陣A的一個特征值需要迭代27次，帶Rayleigh商位移的QR算法迭代4次可求出一個特征值，而帶Wilkinson位移的QR算法僅需迭代3次即可求出一個特征值。因此，當(dāng)選取合適的精度時，最快可以近似的達到每迭代一次求出一個特征值。這樣，整個算法的計算量就減小了。

五、結(jié)語

目前，矩陣特征值問題的應(yīng)用越發(fā)廣泛，各個領(lǐng)域中都有其身影。隨著科技的發(fā)展，矩陣的特征值問題將被研究的更加透徹，計算矩陣特征值的算法也將發(fā)展的更為高效，能夠極大地減少運算量和運算時間。