可用的算法概览

读者或许还记得，中等规模的特征值问题，即在此情况下可以方便地存储一个完整的n \times n矩阵，通常采用直接法解决，有时也称为变换法。通过相似变换，直至特征值能够被轻易读取 ¹。我们在第4.2节对一些当前的直接法进行了简要回顾。

本书的重点在于迭代法，此时稀疏矩阵存储的优势得以发挥。在此方法中，矩阵算子作用于一个或少数几个初始向量，特征值近似从低维子空间中计算得出，迭代持续进行直至收敛到特征值的某个子集。

本章将介绍六种基本的迭代算法：

幂法

在第4.3节中描述，是最基本的迭代方法。它从一个初始向量开始，让矩阵作用于该向量，直至得到的向量与主特征向量平行。当存在唯一一个最大幅值的特征值时，该方法收敛，但即使在这些有利情况下，其速度仍慢于本章讨论的其他算法。

子空间迭代法

有时也称为同时迭代，在第4.3节中描述，让矩阵同时作用于一组向量，直至迭代向量张成主特征值的不变子空间。它是多个结构工程软件包的基础，并以其简单的实现和收敛理论著称。然而，其收敛速度慢于基于Lanczos正交化的算法。

Lanczos法

在第4.4节中描述，构建由矩阵A反复作用于初始向量产生的Krylov序列向量的正交基。在此正交基中，矩阵算子由一个三对角矩阵T表示，其特征值提供原矩阵A的若干特征值的Ritz近似。与幂法相比，其主要优势在于从一个向量序列中获得多个特征值近似，且这些近似在更少的矩阵-向量乘法后收敛。另一方面，存在潜在的复杂性：即便简单的三项递归足以给出数学上的正交基，舍入误差会在第一个特征值收敛时破坏正交性，因此需要某种形式的再正交化。如果仅需特征值，Lanczos算法在存储空间上较为经济。我们将在第4.4节描述一些变体。

隐式重启Lanczos法

在第4.5节中描述，是一种变体，其中正交基的大小保持有界并持续更新，直至其子空间包含一组预定的特征向量。在许多情况下，它能够以略多的矩阵-向量乘法次数，显著减少存储空间，实现与原始Lanczos变体相同数量收敛的特征值。此变体在需要特征向量时尤为有用。

带状Lanczos法

在第4.6节中描述，是同时幂法的Lanczos对应方法。对于存储在磁盘或内存层次结构中的矩阵，同时作用于多个向量比逐个作用更为高效。这是多个最先进的结构工程软件包采用此类算法的原因[206]。在多输入多输出控制问题中，人们实际上对基于给定的一组初始向量的降阶模型（reduced-order models）感兴趣，这是开发这一变体的主要原因。

Jacobi-Davidson法

在第4.7节中描述，是量子化学计算中流行算法的发展。它通过预处理矩阵作用于一系列子空间进行更新。如果只能使用预处理迭代来求解与底层矩阵相关的线性系统，这是获取内部特征值或特征值簇的方法。

1. 请注意，所谓“直接”方法仍需迭代，因为从数学上讲，求解特征值等同于寻找多项式的零点，而对于后者，不存在非迭代方法。我们可以称一种方法为直接法，如果经验表明它（几乎）永远不会在固定次数的迭代中失败。