直接方法

实践中用于解决非厄米特征值问题(NHEP)（参见公式7.1及7.2）的主要直接方法 ^[1] 是QR算法。该算法首先计算非厄米矩阵A的Schur标准型（或简称为Schur分解）：

A = U T U^{\ast}, \tag{7.5}

其中U是酉矩阵，满足U^{\ast} U = I，而T是上三对角矩阵。矩阵A的特征值\lambda即为T的对角线元素（详见第2.5节）。矩阵A的特征向量x为U s，其中s是T的特征向量，可通过求解三角形方程组获得。当A为实矩阵时，QR算法计算实Schur分解以避免复数运算，从而节省浮点运算和内存。

QR算法起源于简单的QR迭代：

设A_0 = A，
对于k = 1,2, \ldots,
对A_{k-1}进行QR分解：A_{k-1} = Q_k R_k
计算A_{k} = R_k Q_k

在一定条件下，A_k会收敛至Schur型T。然而，QR迭代的收敛速度对于实际应用而言极其缓慢。为了使QR迭代成为快速有效的Schur分解计算方法，已开发出多项关键改进措施，包括海森堡约简、隐式移位、缩减及矩阵平衡等。感兴趣的读者可参阅[198,114]及相关文献，了解相关理论及实现细节。

QR算法对于一般n \times n矩阵的计算成本为O(n^3)次浮点运算及O(n^2)内存需求。对于实n \times n矩阵，一个粗略的估计是若同时计算U和T，则需约25n^3次浮点运算；若仅需特征值，则大约需要10n^3次浮点运算。

QR算法具有向后稳定性；即，对于计算得到的酉矩阵\widehat{U}（在机器精度范围内）及上三角矩阵\widehat{T}，我们有

A + E = \widehat{U}\widehat{T}\widehat{U}^{\ast},

其中\Vert E\Vert \leq p(n)\epsilon\Vert A\Vert，p(n)是一个适度增长的n的多项式函数。

实现QR算法的子程序几乎存在于所有与线性代数相关的软件包中。在MATLAB中，它作为eig命令使用。^[2] 在LAPACK[12]中，提供了以下驱动程序例程，用于执行计算Schur分解、特征值、特征向量及计算结果精度估计的变种任务：

xGEES	计算Schur分解并按特征值排序，
xGEESX	xGEES加上条件估计，
xGEEV	特征值与特征向量，
xGEEVX	xGEEV加上条件估计，

其中{\tt x}代表数据类型，S或D表示实数单精度或双精度，C或Z表示复数单精度或双精度。

在ScaLAPACK[52]中，提供了用于并行执行海森堡约简及隐式移位QR迭代的计算例程，分别是PxGEHRD和PxLAHQR。

1. 请注意，由于在数学上，求解特征值等同于寻找多项式的零点，而针对后者不存在非迭代方法，因此直接法也必须进行迭代。我们称一种方法为直接法，是指实践证明该方法（几乎）从未在固定次数的迭代中失败过，即能够确保收敛。
2. 已经宣布，一个基于LAPACK的数值库将成为MATLAB下一个主要版本的一部分；参见《MATLAB、Simulink和工具箱用户通讯，冬季 2000》，可在以下网址获取http://www.mathworks.com/company/newsletter/clevescorner/winter2000.cleve.shtml