克雷洛夫子空间

克雷洛夫子空间 (Krylov Subspace)

克雷洛夫子空间（Krylov Subspace）是数值线性代数中最核心的概念之一，由苏联数学家暨船舶工程师阿列克谢·克雷洛夫（Alexei Nikolaevich Krylov, 1863–1945）于1931年在其关于特征值计算的论文中首次引入。给定一个 n × n 矩阵 A 和一个 n 维非零向量 b，m 阶克雷洛夫子空间定义为：

即由初始向量 b 在 A 的反复作用下生成的所有向量的张成空间。这一构造极其自然——它恰恰是 b 在 A 所定义的线性动力系统中可达的所有方向的集合，也是现代大规模矩阵计算的算法基石。

核心思想

克雷洛夫子空间之所以重要，是因为它将高维问题投影到低维子空间中求解。对于大规模稀疏线性方程组 $Ax = b$ 或特征值问题 $Ax = \lambda x$，直接求解在计算上不可行（复杂度为 O(n³)）。克雷洛夫子空间方法的共同策略是：在低维子空间 $\mathcal{K}_m(A, b)$（其中 m ≪ n）中寻找最佳近似解。这一思想的基础是Cayley-Hamilton定理：A 的逆可以表示为 A 的幂的线性组合，因而精确解理论上落在某个克雷洛夫子空间中——虽然 m 可能很大，但在实践中只需很小的 m 就能获得高精度近似。

主要算法

几乎所有现代迭代法都建立在克雷洛夫子空间之上，最重要的包括：

共轭梯度法（Conjugate Gradient, CG）

由Hestenes和Stiefel于1952年提出，适用于对称正定矩阵。CG在克雷洛夫子空间中极小化能量范数 $\|x - x_*\|_A$，每次迭代仅需一次矩阵-向量乘法，存储和计算开销极低。CG奠定了克雷洛夫子空间方法的基础框架：在 $\mathcal{K}_m$ 中构造一组共轭方向，将 n 维问题解耦为 m 个一维优化问题。

GMRES（广义极小残量法）

由Saad和Schultz于1986年提出，适用于一般非对称矩阵。GMRES在 $\mathcal{K}_m(A, b)$ 中极小化残量 $\|b - Ax_m\|_2$，使用Arnoldi迭代构造子空间的一组正交基。其代价随 m 线性增长，因此实践中常使用重启（Restart）策略。

Arnoldi 与 Lanczos 迭代

Arnoldi迭代构造克雷洛夫子空间的一组标准正交基，同时生成一个上Hessenberg矩阵，是GMRES等方法的子程序。当矩阵对称时，Arnoldi退化为Lanczos迭代，生成的矩阵为三对角矩阵，计算量大幅降低。Lanczos方法是求解大规模稀疏对称矩阵部分特征值的首选算法，被广泛应用于量子物理的能级计算和图论中的谱聚类。

其他重要方法

包括适用于对称不定矩阵的MINRES，适用于非对称矩阵的BiCGSTAB，以及在克雷洛夫子空间中同时处理左右两侧的双正交化方法等。每种方法都针对特定的矩阵结构和谱性质做了优化。

理论视角

克雷洛夫子空间方法与多项式逼近有深刻联系：$\mathcal{K}_m$ 中任意向量可写为 $p(A)b$，其中 p 是次数不超过 m−1 的多项式。因此CG等价于在区间 $[\lambda_{\min}, \lambda_{\max}]$ 上寻找最优逼近多项式，其收敛性由Chebyshev多项式的最优性质刻画。这一视角将数值线性代数与逼近论、复分析（通过伪谱和值域）紧密联系起来。迭代的收敛速度由矩阵特征值分布的聚集程度决定：特征值越集中，收敛越快。

应用与影响

克雷洛夫子空间方法是大规模科学计算的支柱。它们在有限元分析、计算流体力学、结构力学、电磁场模拟、PageRank计算、机器学习中的核方法和图拉普拉斯问题中广泛使用。每当问题涉及数十万乃至数亿个未知数且矩阵稀疏时，克雷洛夫子空间方法几乎是不二选择。这些方法的共同优势在于：仅需矩阵-向量乘法操作，无需显式存储矩阵元素，适合无矩阵（Matrix-Free）实现，且收敛速度由矩阵的谱性质而非规模决定。

在经济与金融计算中，克雷洛夫子空间方法被用于求解高维动态规划问题、大规模CGE模型的线性化系统、以及金融衍生品定价中的偏微分方程离散化系统。随着计算经济学向高维复杂模型演进，这类迭代方法的重要性持续上升。此外，在大语言模型和深度学习中的神经ODE求解、图神经网络的消息传递等前沿领域，克雷洛夫子空间的思想同样展现出新的活力。