Krylov 子空间 | Codeboy's Blog

形式陈述

给定实数或复数域上的方矩阵 $A\in\mathbb F^{n\times n}$ 和非零初始向量 $r_0$ ，第 $k$ 个 Krylov 子空间定义为

\mathcal K_k(A,r_0) =\operatorname{span}\{r_0,Ar_0,\ldots,A^{k-1}r_0\}.

这些空间单调嵌套：

\mathcal K_1\subseteq\mathcal K_2\subseteq\cdots.

浮点实现通常不直接生成并保存全部幂向量 $A^jr_0$ ，因为它们可能数值上近乎相关，并产生严重尺度失衡；这不是说该数学表示无效，或每个矩阵都会发生这种失稳。Arnoldi 类实现每步调用一次 $v\mapsto Av$ ，再把新向量对已有基正交化。对稀疏矩阵，若压缩表示实际保存 $s$ 个条目（包括显式零和重复坐标），主要算子成本为一次 $O(n+s)$ 的 SpMV，其中 $O(n)$ 包括完整输出向量的初始化，正交化成本另计。

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

\mu_{A,r_0}(A)r_0=0

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

\dim\mathcal K_k(A,r_0)=\min(k,d), \qquad \mathcal K_d=\mathcal K_{d+1},

后续幂向量都已在同一张成空间中。这里的 $d$ 可能小于 $A$ 的全局最小多项式次数，因为 $r_0$ 未必含有所有不变方向。

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

v=Aq_j,

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

h_{ij}=q_i^*v,\qquad v\leftarrow v-h_{ij}q_i.

最后令

h_{j+1,j}=\|v\|_2,\qquad q_{j+1}=v/h_{j+1,j}.

若未 breakdown， $Q_k=[q_1,\ldots,q_k]$ 是 $\mathcal K_k$ 的正交规范基，并满足 Arnoldi 关系

AQ_k=Q_{k+1}\,\overline H_k,

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

Aq_j =\beta_jq_{j-1}+\alpha_jq_j+\beta_{j+1}q_{j+1}.

输入包括矩阵或 matvec 接口、 $r_0$ 、最大维数和 breakdown 容差；输出是基向量、投影矩阵、有效维数和退出状态。若精确的 $h_{j+1,j}=0$ ，当前子空间已经对 $A$ 不变；只有当具体投影问题同时达到目标时，这次终止才称为 happy breakdown。比如 GMRES 还必须检查小型最小二乘残差是否为零。若初始 $r_0=0$ ，则在开始前直接报告零残差或无生成方向。

直觉

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

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

例子与边界

取

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

则

\mathcal K_1=\operatorname{span}\{(1,1,0)^{\mathsf T}\},

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

\mathcal K_2=\operatorname{span}\{e_1,e_2\}.

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

精确算术中的正交性在浮点中可能逐渐损失。Arnoldi 常用 modified Gram–Schmidt，并在困难问题上重新正交化；Householder 等其他正交化实现也可使用，不能把某一种实现当作子空间定义。Lanczos 的短递推尤其可能重新出现已收敛特征方向，产生重复Ritz 值。压缩的特征方程只保证原残差与试验空间正交；对 Hermitian 输入，验收某个候选方向，还应使用残差与间隔证书，而不是把小矩阵的特征值直接当作原矩阵的精确谱点。接近 breakdown 时， $h_{j+1,j}$ 的小值还必须相对 $\|A\|$ 和当前尺度判断，不能用固定绝对阈值决定“不变子空间”。

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

推论与应用

CG、GMRES、Arnoldi 特征值法和 Lanczos 方法共享 $\mathcal K_k$ ，但在其中选择近似解或投影条件的方式不同。共轭梯度法利用正定内积获得短递推；一般非对称问题则需要完整 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.

形式陈述 ​

反向链接

形式陈述