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

王麗 首都經濟貿易大學

一、引言

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

二、基本QR算法

（一）QR算法基本思想

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

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

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

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

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

三、 帶位移的QR算法

（一） 帶位移的QR算法

帶位移的QR算法：

形成一個新的矩陣

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

形成一個新的矩陣

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

（二）位移的選取

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

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

四、數值實驗

（一）基本QR算法數值實驗

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

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

圖1 基本QR算法收斂曲線

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

（二）帶位移的QR算法數值實驗

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

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

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

由圖2帶Rayleigh商位移的QR算法收斂曲線可以看出，帶Rayleigh商位移的QR算法收斂，并且為漸近平方階收斂，符合理論結果。由圖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次即可求出一個特征值。因此，當選取合適的精度時，最快可以近似的達到每迭代一次求出一個特征值。這樣，整個算法的計算量就減小了。

五、結語

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