Krylov 子空间

假设对一个巨大的矩阵 A，你唯一能廉价做的就是用它乘一个向量。你能从这一种运算里搭出什么？从 b 出发，你能得到 Ab，再得 A(Ab) = A^2 b，如此继续。维数为 k 的 Krylov 子空间就是这些向量的张成：K_k(A, b) = span{b, Ab, A^2 b, ..., A^{k-1} b}。它是任何唯一工具就是矩阵-向量乘积的方法的天然舞台。

为何这是正确的搜索空间？因为 A 的多项式都住在这里。K_k 中任何向量都是某个次数低于 k 的多项式 p 对应的 p(A) b。所以在 K_k 中搜索 Ax = b 的良好近似解，等同于问哪个多项式 p 使 p(A) b 最接近 A^-1 b。Cayley-Hamilton 定理甚至保证 A^-1 本身就是 A 的一个多项式，故当 k 足够大时，精确解就落在 Krylov 子空间里。

现代迭代求解器几乎无一例外都是 Krylov 方法：共轭梯度、GMRES、MINRES、BiCGStab。它们的差别只在于从这个不断增长的子空间里挑哪个向量（极小化残差？让残差与该空间正交？），以及如何通过 Arnoldi 或 Lanczos 廉价地为它构造一组标准正交基。

这一思想的威力在于：当 n 极其巨大时，子空间维数 k 却可以保持很小。若 A 的特征值聚集成团，低次多项式就已能使 p(A) b 成为极佳近似，故方法在远少于 n 步内收敛。这种聚集正是预处理力图制造的东西。