计算特征值问题的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次即可求出一个特征值。因此，当选取合适的精度时，最快可以近似的达到每迭代一次求出一个特征值。这样，整个算法的计算量就减小了。

五、结语

目前，矩阵特征值问题的应用越发广泛，各个领域中都有其身影。随着科技的发展，矩阵的特征值问题将被研究的更加透彻，计算矩阵特征值的算法也将发展的更为高效，能够极大地减少运算量和运算时间。