11. Arnoldi、FOM 与 GMRES

当矩阵很大且只能高效计算 $Av$ 时，直接分解不再合适。Krylov 方法只访问矩阵—向量乘法，并把原问题投影到逐步扩大的低维空间。

11.1 Krylov 子空间

给定初始残差 $r_0=b-A{x}_0$，定义

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

我们在仿射空间 $x_0+{\mathcal{K}}_m$ 中寻找近似解。关键不是显式形成幂次，而是构造稳定的正交基。

11.2 Arnoldi 过程

令 $v_1=r_0/\beta$，$\beta =\parallel r_0{\parallel }_2$。逐步正交化 $A{v}_j$ 可得到

$$A{V}_m=V_{m+1}{\overline{H}}_m,$$

其中 $V_{m+1}$ 列正交，${\overline{H}}_m$ 是上 Hessenberg 矩阵。第 $j$ 步的基本操作是：

1. 计算 $w=A{v}_j$；
2. 对已有基向量做投影并减去；
3. 用剩余向量的范数归一化得到 $v_{j+1}$。

经典或修正 Gram–Schmidt 都会受舍入误差影响。若正交性明显丢失，应进行一次或选择性重正交化。

若 $h_{j+1,j}=0$，Krylov 空间已经成为不变子空间；若此时小问题给出零残差，就是“幸运终止”。

第 $j$ 步需要一次 $A{v}_j$ 和约 $j$ 次内积/向量更新。累计到 $m$ 步，矩阵乘成本为 $m$ 次 matvec，正交化成本为 $O(m^{2}n)$，基存储为 $O(mn)$。当 $m$ 变大，正交化和全局归约可能比稀疏 matvec 更贵。

11.3 FOM：Galerkin 条件

设 $x_m=x_0+V_{m}y$。FOM 要求

$$r_m\perp {\mathcal{K}}_m(A,r_0),$$

代入 Arnoldi 关系得到小型线性系统

$$H_{m}y=\beta e_1,H_m=V_m^{\ast }A{V}_m.$$

FOM 让残差对试探空间正交，但不直接最小化残差范数。

11.4 GMRES：最小残差

GMRES 解的是

$$\underset{x\in x_0+{\mathcal{K}}_m}{min}\parallel b-Ax{\parallel }_2.$$

利用 Arnoldi 关系，原来的大问题等价为

$$\underset{y}{min}\parallel \beta e_1-{\overline{H}}_{m}y{\parallel }_2.$$

每加入一列，只需用 Givens 旋转更新小型 QR 分解；无需每轮重新求整个最小二乘问题。旋转后的最后一个分量还能廉价给出递推残差范数。

具体地，若已有旋转把 ${\overline{H}}_{m-1}$ 化为上三角形，第 $m$ 步只把旧旋转作用到新列，再构造一个新旋转消去 $h_{m+1,m}$。同时把这些旋转作用于 $\beta e_1$，其末尾分量的绝对值就是 Arnoldi 关系下的残差范数。

11.5 重启与预处理

完整 GMRES 的基向量存储和正交化成本随 $m$ 增长。GMRES($m$) 每 $m$ 步重启，可限制内存，但会丢失部分多项式信息，甚至停滞。

预处理的目标是改善谱分布：

• 左预处理：$M^{-1}Ax=M^{-1}b$；
• 右预处理：$A{M}^{-1}y=b$，再令 $x=M^{-1}y$。

右预处理便于用原方程的真实残差判断停机。无论采用哪一种，都应通过“解 $Mz=r$”应用预处理器，不要显式形成 $M^{-1}$。

11.6 算法选择

• 一般非对称矩阵：GMRES 是标准选择之一。
• Hermitian 不定矩阵：可用保持短递推的 MINRES。
• 对称正定矩阵：优先考虑共轭梯度法。

结构专用算法通常能节省存储和正交化成本，不应无条件把所有问题都交给 GMRES。

11.7 GMRES 的多项式解释

任意 $x_m\in x_0+{\mathcal{K}}_m(A,r_0)$ 的残差都可写成

$$r_m=p_m(A)r_0,p_m\in {\mathrm{\Pi }}_m,p_m(0)=1.$$

GMRES 选择使 $\parallel p_m(A)r_0{\parallel }_2$ 最小的多项式。若 $A=X\mathrm{\Lambda }{X}^{-1}$ 可对角化，可得上界

$$\frac{\parallel r_m{\parallel }_2}{\parallel r_0{\parallel }_2}\le {\kappa }_2(X)\underset{p(0)=1}{min}\underset{\lambda \in \sigma (A)}{max}|p(\lambda )|.$$

这个界说明谱聚簇可能有利，但非正规性会通过 $\kappa (X)$ 破坏预测。更强地说，仅凭特征值集合不能决定 GMRES 残差曲线；实际收敛还与特征向量、初始残差和伪谱有关。

11.8 递推残差与真实残差

Givens 递推得到的是“小问题所预测的残差”。有限精度下 Arnoldi 关系和正交性都会有误差，因此它可能逐渐偏离

$$r_m^{\mathrm{true}}=b-A{x}_m.$$

稳健实现应周期性显式重算真实残差，并最终以真实残差验收。若二者偏差显著，应考虑重正交化、残差替换或更可靠的停止准则。

11.9 重启、停滞与保留信息

GMRES($m$) 在每个周期末以当前残差重新开始。它限制了存储与正交化成本，却把长多项式截断为多个短多项式，可能反复丢失刚学到的谱信息。

改进方法包括：

• 增大重启长度；
• 在重启时保留近似不变子空间（deflated/recycled GMRES）；
• 使用灵活 GMRES 允许预处理器随步数变化；
• 根据残差停滞诊断预处理而非只修改容差。

11.10 其他 Krylov 线性求解器

结构	代表方法	主要特征
Hermite 正定	CG	三项短递推，$A$-范数最优
Hermite 不定	MINRES	短递推并最小化 2-范数残差
一般非对称	BiCG、QMR、BiCGSTAB	短递推，存储小，但残差可能不单调
一般非对称	GMRES	残差单调不增，但存储和正交化增长

短递推通常以更复杂的收敛行为或潜在 breakdown 为代价。选择算法时应先利用矩阵结构，再权衡内存与单调残差需求。

11.11 预条件的实际形式

左预条件 GMRES 最小化的是 $\parallel M^{-1}r{\parallel }_2$，它不一定反映原问题真实残差；右预条件则在变量 $x=M^{-1}y$ 上构造空间，仍可直接监控 $\parallel b-Ax{\parallel }_2$。若 $M_k$ 每步变化，必须使用 flexible GMRES，不能把变化的预处理器当作固定线性算子。

好的预处理器不只让条件数变小，更希望把特征值聚在远离零的区域、削弱非正规性，并且构造与应用成本可控。

自检

1. Arnoldi 关系为何把大规模残差最小化化为小型最小二乘？
2. FOM 与 GMRES 对残差施加的条件分别是什么？
3. 为什么重启能节省资源，却可能破坏收敛？
4. 为什么 GMRES 的特征值分布不足以单独预测收敛？
5. 左、右预处理分别影响哪一个残差或变量？