直接方法

在这一节中，我们将简要讨论用于计算对称矩阵特征值的直接方法，这些对称矩阵可以完整存储在计算机中。这些直接方法有时被称为变换方法，并且围绕相似变换构建。

它们在LAPACK[12]、ScaLAPACK[52]以及MATLAB的eig命令中得到实现 ¹。

我们后面讨论的所有基于子空间算法都需要使用密集、三对角或带状矩阵的直接方法例程作为内部迭代，以获得子空间特征值的Ritz近似。

最常见的直接方法分为两个阶段：

1. 找到一个正交矩阵Q，使得Q^{\ast} A Q = T是一个三对角矩阵。
2. 计算三对角矩阵T的特征分解。

初始化简到三对角形式是通过一系列 n-2 个正交Householder反射实现的，需要\frac{4}{3}n^3次浮点运算，或者如果还需要计算特征向量，则需要\frac{8}{3}n^3次浮点运算。LAPACK的对称或厄米矩阵例程简单来说，实数情况是 xSYTRD 例程，复数情况是 xHETRD 例程（在ScaLAPACK中为 PxSYTRD 和 PxHETRD）。还有针对压缩和带状存储的实现。

对于三对角矩阵的特征分解，有几种方法可以选择：

QR算法：

该算法找到所有特征值，并可选地找到所有特征向量。对于找到一个三对角矩阵的所有特征值，它需要O(n^2)次浮点运算。由于将一个密集矩阵化简为三对角形式需要\frac{4}{3}n^3次浮点运算，对于足够大的n，O(n^2)是可以忽略的。对于找到所有特征向量，QR迭代平均需要略多于6n^3次浮点运算。 它在 LAPACK 中通过 xSTEQR 和 xSTERF 实现。

这也是MATLAB命令eig背后的算法 ²。

分治法：

它将三对角矩阵分成两半，分别解决每一半的特征问题，并通过求解一个特殊的有理方程将解粘合在一起。它在LAPACK中作为 xSTEVD 实现。对于大型矩阵，xSTEVD 可以比 xSTEQR 快很多倍，但需要更多的内存空间（2n^2或3n^2）。

二分法和逆迭代：

二分法可以用于仅找到一部分特征值，例如区间[a,b]内的那些。它只需要O(nk)次浮点运算，其中k是所需的特征值数量。因此，当k \ll n时，二分法可能比QR方法快得多。它可以非常精确，但如果接受较低的精度，也可以调整以更快运行。

然后可以使用逆迭代来找到相应的特征向量。在最佳情况下，当特征值很好地分离时，逆迭代也只需要O(nk)次浮点运算。这远少于QR或分治法，即使当所有特征值和特征向量都需要时（k=n）。另一方面，当许多特征值聚集在一起时，将需要Gram-Schmidt正交化以确保我们不会得到几个相同的特征向量。在最坏情况下，这将增加O(nk^2)次浮点运算。

二分法和逆迭代在LAPACK例程 xSTEBZ 和 xSTEIN 中实现，并且它们作为选项在 xSYEVX 中可用。在ScaLAPACK中，它们是子例程 PxSTEBZ 和 PxSTEIN。

相对稳健表示算法：

该算法使用LDL^T分解对多个平移T-s I进行分解，其中s是每个特征值簇附近的位移。对于每个平移，该算法计算非常精确的小特征值的特征对。它在LAPACK中作为 xSTEGR 实现。xSTEGR 比所有例程都快，除了少数情况，并且使用最少的内存空间。参见[358,128,360]。

最后，解决厄米特征值问题的一个经典方法是雅可比方法。 该方法通过一系列基本正交旋转构造一个正交变换到对角形式，

A=X\Lambda X^{\ast}

每次减少矩阵非对角元素平方和，直到它达到工作精度的对角形式。

雅可比算法非常流行，因为它的实现非常简单，并且给出的特征向量在工作精度上是正交的。然而，在操作计数方面，它无法与QR方法竞争：雅可比需要2sn^3次乘法进行s次扫描（通常s=3到5），这比三对角化所需的4/3n^3次要多。

雅可比算法有一个重要的优点。正确实现它可以提供相对误差小的特征值近似，而基于三对角化的算法只能保证误差相对于矩阵范数有界（4.3）。参见[124]。

1. 据悉，基于LAPACK的数值计算库将成为MATLAB下一大版本更新的组成部分；详情可参阅《MATLAB、Simulink及工具箱用户通讯》2000年冬季刊，网址为http://www.mathworks.com/company/newsletter/clevescorner/winter2000.cleve.shtml。
2. MATLAB会检查eig函数的参数是否对称，并在适当的情况下使用对称QR算法。