Krylov 子空间

形式陈述 ​

给定 $A\in {\mathbb{F}}^{n\times n}$ 和非零初始向量 $r_0$，第 $k$ 个 Krylov 子空间定义为

$${\mathcal{K}}_k(A,r_0)=\mathrm{span}\{r_0,A{r}_0,\dots ,A^{k-1}{r}_0\}.$$

这些空间单调嵌套：

$${\mathcal{K}}_1\subseteq {\mathcal{K}}_2\subseteq \cdots .$$

计算时不能显式形成 $A^j{r}_0$，因为幂向量会迅速失去线性独立性并放大尺度；算法每步只调用一次 $v\mapsto Av$，再把新向量对已有基正交化。对稀疏矩阵公理库稀疏矩阵表示与运算Sparse matrix · CSR matrix · CSC matrix只存非零项及其位置，以稀疏模式组织矩阵运算、图结构、重排序与填充成本。，这使主要算子成本保持在一次 $O(\mathrm{nnz}(A))$ 的 SpMV。

相对于 $r_0$ 的最小多项式，是满足

$${\mu }_{A,r_0}(A)r_0=0$$

的最低次数首一多项式。若其次数为 $d$，则精确算术中

$$\dim {\mathcal{K}}_k(A,r_0)=min(k,d),{\mathcal{K}}_d={\mathcal{K}}_{d+1},$$

后续幂向量都已在同一张成空间公理库线性组合与张成Linear combination and span有限标量加权和及由给定向量生成的最小子空间。中。这里的 $d$ 可能小于 $A$ 的全局最小多项式次数，因为 $r_0$ 未必含有所有不变方向。

Arnoldi 过程取 $\beta =\Vert r_0{\Vert }_2$、$q_1=r_0/\beta$。第 $j$ 步计算

$$v=A{q}_j,$$

再对 $i=1,\dots ,j$ 执行

$$h_{ij}=q_i^{\ast }v,v\leftarrow v-h_{ij}{q}_i.$$

最后令

$$h_{j+1,j}=\Vert v{\Vert }_2,q_{j+1}=v/h_{j+1,j}.$$

若未 breakdown，$Q_k=[q_1,\dots ,q_k]$ 是 ${\mathcal{K}}_k$ 的正交规范基公理库正交规范基Orthonormal basis由单位长度且两两正交的向量组成的基。，并满足 Arnoldi 关系

$$A{Q}_k=Q_{k+1}{\bar{H}}_k,$$

其中 ${\bar{H}}_k\in {\mathbb{F}}^{(k+1)\times k}$ 为上 Hessenberg 矩阵。若 $A=A^{\ast }$，Hermitian 结构使 $H_k$ 化为三对角矩阵，Arnoldi 缩短为 Lanczos 三项递推：

$$A{q}_j={\beta }_j{q}_{j-1}+{\alpha }_j{q}_j+{\beta }_{j+1}{q}_{j+1}.$$

输入包括矩阵或 matvec 接口、$r_0$、最大维数和 breakdown 容差；输出是基向量、投影矩阵、有效维数和退出状态。若精确的 $h_{j+1,j}=0$，当前子空间已经对 $A$ 不变；只有当具体投影问题同时达到目标时，这次终止才称为 happy breakdown。比如 GMRES公理库GMRES 方法GMRES · Generalized minimal residual method在 Krylov 仿射空间中逐步最小化线性系统的二范数残差，并权衡 Arnoldi 正交化、存储和重启代价。 还必须检查小型最小二乘残差是否为零。若初始 $r_0=0$，则在开始前直接报告零残差或无生成方向。

直觉 ​

Krylov 子空间只探索从 $r_0$ 真正可达的方向。先看 $r_0$，再看 $A$ 把它推向哪里，随后继续观察 $A$ 对这些新方向的作用；每一步都把矩阵在当前视野之外的新信息加入基中。算法因此不需要读出或分解整个大矩阵。

Arnoldi 像一台坐标记录器：每次 matvec 产生的向量被分成“已有基能够解释的部分”和一个新正交方向，系数写进 Hessenberg 矩阵。Lanczos 利用 Hermitian 对称性，让远离当前索引的投影精确为零，因而只保留三项递推。

例子与边界 ​

取

$$A=\mathrm{diag}(1,2,4),r_0=(1,1,0{)}^{\mathsf{T}}.$$

则

$${\mathcal{K}}_1=\mathrm{span}\{(1,1,0{)}^{\mathsf{T}}\},$$

而 $A{r}_0=(1,2,0{)}^{\mathsf{T}}$ 增加第二个方向，所以

$${\mathcal{K}}_2=\mathrm{span}\{e_1,e_2\}.$$

由于 $A$ 保持这个平面不变，$A^2{r}_0=(1,4,0{)}^{\mathsf{T}}$ 已在 ${\mathcal{K}}_2$ 中，空间不再增长。相对最小多项式为 $(t-1)(t-2)$；特征值 $4$ 没有出现，因为初始向量在相应特征方向上的分量为零。

精确算术中的正交性在浮点中会逐渐损失。Arnoldi 需要 modified Gram–Schmidt，并在困难问题上重新正交化；Lanczos 的短递推尤其可能重新出现已收敛特征方向，产生重复 Ritz 值。接近 breakdown 时，$h_{j+1,j}$ 的小值还必须相对 $\Vert A\Vert$ 和当前尺度判断，不能用固定绝对阈值决定“不变子空间”。

Arnoldi 做到第 $k$ 步需要 $k$ 次 matvec、$O(n{k}^2)$ 级正交化工作和 $O(nk)$ 基存储。Lanczos 在不保存全部基且不重新正交化时可用常数个长向量，但失去正交后可能需要额外存储和工作。重启可以限制内存，却会丢弃部分多项式历史，收敛行为随保留信息改变。

推论与应用 ​

CG、GMRES、Arnoldi 特征值法和 Lanczos 方法共享 ${\mathcal{K}}_k$，但在其中选择近似解或投影条件的方式不同。共轭梯度法公理库共轭梯度法Conjugate gradient method · CG method在 Hermitian 正定系统的 Krylov 子空间中最小化能量误差，以三项递推获得共轭方向和短存储迭代。利用正定内积获得短递推；一般非对称问题则需要完整 Arnoldi 正交化或重启策略。Krylov 子空间不是某一个算法的别名。

可审计实现应记录 matvec 次数、子空间维数、正交性指标、breakdown 阈值和重启历史。只报告迭代次数会掩盖正交化成本，而显式形成 $A^j$ 或 Krylov 矩阵则放弃了这一框架最重要的矩阵无关接口。

参考资料

• Walter E. Arnoldi, “The Principle of Minimized Iterations in the Solution of the Matrix Eigenvalue Problem,” Quarterly of Applied Mathematics 9(1), 1951.
• Cornelius Lanczos, “An Iteration Method for the Solution of the Eigenvalue Problem of Linear Differential and Integral Operators,” Journal of Research of the National Bureau of Standards 45, 1950.
• Lloyd N. Trefethen and David Bau III, Numerical Linear Algebra, SIAM, 1997, Lectures 33–36.
• Richard Barrett et al., Templates for the Solution of Linear Systems, 2nd ed., SIAM, 1994.