Lanczos算法是由Cornelius Lanczos提出的一种迭代方法，它改编了幂法，用于寻找n×n厄米矩阵的m个“最有用”（趋向于极值最高或最低）的特征值和特征向量，其中m通常（但不一定）远小于n。虽然原则上计算效率高，但该方法最初因数值不稳定性而无法实用。1970年，Ojalvo和Newman展示了如何使该方法数值稳定，并将其应用于承受动态载荷的超大型工程结构求解。这是通过一种纯化Lanczos向量的方法实现的（即反复将每个新生成的向量与所有先前生成的向量重新正交化），以达到任意精度；若不执行此操作，生成的向量序列会受到与最低固有频率相关的向量的严重污染。
在他们的原始工作中，这些作者还建议如何选择起始向量（即使用随机数生成器选择起始向量的每个元素），并提出了一个经验确定的方法来确定m，即缩减后的向量数量（即应选择约为所需精确特征值数量的1.5倍）。不久之后，Paige跟进他们的工作，并提供了误差分析。1988年，Ojalvo撰写了该算法更详细的历史，并提出了一个高效的特征值误差检验。
算法概述
输入一个大小为n×n的厄米矩阵A，以及可选的迭代次数m（默认情况下，令m=n）。严格来说，该算法不需要访问显式矩阵，而只需要一个函数v↦Av，该函数计算矩阵与任意向量的乘积。此函数最多被调用m次。输出一个具有正交列的n×m矩阵V，以及一个大小为m×m的三对角实对称矩阵T=VAV。如果m=n，则V是酉矩阵，且A=VTV。Lanczos迭代容易产生数值不稳定性；当在非精确算术中执行时，应采取额外措施（如后续章节所述）以确保结果的有效性。
该算法通过生成一系列正交向量v1, v2, ..., vm来进行，这些向量构成Krylov子空间的一组基。从范数为1的任意向量v1开始，每一步通过应用矩阵A、与前一个向量正交化并归一化来生成一个新向量。系数αj和βj构成三对角矩阵T的对角线和非对角线元素，其特征值近似于A的特征值。
数值稳定性与重新正交化
原始的Lanczos算法因浮点舍入导致正交性丧失，从而产生虚假特征值和不精确的特征向量。1970年Ojalvo和Newman的稳定化引入了完全重新正交化：每个新生成的向量都与所有先前生成的向量进行正交化。这纯化了Lanczos向量并恢复了数值稳定性，但代价是增加了计算开销。Paige在1970年代初的误差分析为舍入效应提供了理论界限，并证明了重新正交化方法的合理性。
在机器学习中的应用
在机器学习中，Lanczos算法用于大规模特征值问题，例如计算PCA中协方差矩阵的顶部特征值或谱聚类。它还用于深度学习中近似神经网络的Hessian谱，这有助于优化和泛化分析。该算法仅需矩阵-向量乘积的能力使其适用于大型语言模型和生成式AI系统中出现的超大矩阵，在这些系统中显式矩阵存储是不可行的。
相关方法与扩展
Lanczos算法与用于求解线性系统的共轭梯度法密切相关，因为两者都构建Krylov子空间。它还与用于非厄米矩阵的Arnoldi迭代相关联。诸如块Lanczos算法之类的变体处理多个起始向量，而隐式重启Lanczos方法（用于ARPACK）改善了收敛性和内存使用。这些扩展已在LAPACK和SciPy等数值库中实现，使该算法成为科学计算中的标准工具。
历史影响与现代应用
自稳定化以来，Lanczos算法已应用于结构工程、量子化学和信号处理。在人工智能的背景下，它支撑了许多用于数据分析和模型压缩的谱方法。该算法的效率和鲁棒性使其成为数值线性代数的基石，并且持续研究致力于改进其稳定性以及针对现代硬件（如GPU和专用AI加速器）的并行化。
参见
- 幂迭代
- 特征值分解
- Krylov子空间
- 共轭梯度法