GMRES 方法

形式陈述 ​

给定方阵线性系统 $Ax=b$ 和初值 $x_0$，令

$$r_0=b-A{x}_0,\beta =\Vert r_0{\Vert }_2.$$

若 $\beta =0$，初值已经是精确算术下的解。否则 GMRES 在第 $k$ 步从仿射 Krylov 空间

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

选择 $x_k$，使原系统的二范数残差最小：

$$x_k=\underset{x\in x_0+{\mathcal{K}}_k(A,r_0)}{\mathrm{argmin}}\Vert b-Ax{\Vert }_2.$$

这项最优性只针对当前 Krylov 仿射空间和 $2$-范数，不是对前向误差、其他范数或全部向量的全局最优。

Arnoldi 过程公理库Krylov 子空间Krylov subspace · Arnoldi iteration · Lanczos iteration从初始向量反复施加矩阵，生成只依赖矩阵—向量乘法的递增子空间及其 Arnoldi、Lanczos 正交基。生成正交基 $V_k=[v_1,\dots ,v_k]$，其中 $v_1=r_0/\beta$，并满足

$$A{V}_k=V_{k+1}{\bar{H}}_k.$$

${\bar{H}}_k\in {\mathbb{F}}^{(k+1)\times k}$ 为上 Hessenberg 矩阵。写 $x_k=x_0+V_{k}y$ 后，残差化为

$$r_k=V_{k+1}(\beta e_1-{\bar{H}}_{k}y),$$

正交性因而给出小型最小二乘问题公理库用 QR 与 SVD 求最小二乘Least squares via QR · Least squares via SVD · Numerical least squares以 QR 作为满列秩最小二乘的默认计算路线，并用 SVD 处理秩亏、欠定和最小范数解。

$$y_k=\underset{y\in {\mathbb{F}}^k}{\mathrm{argmin}}\Vert \beta e_1-{\bar{H}}_{k}y{\Vert }_2.$$

实现通常用逐步 QR 更新维护该问题和残差范数，不在每轮从头求解。输入还应包括最大矩阵—向量乘次数、绝对与相对容差、重启长度以及预条件算子；输出必须包含 $x_k$、真实或估计残差、矩阵—向量乘次数和退出状态。

对稀疏 $A$，每一步需要一次 $O(\mathrm{nnz}(A))$ 的矩阵—向量乘。第 $k$ 个 Arnoldi 向量要与前面 $k$ 个基向量正交化，成本为 $O(kn)$，累计到 $k$ 步为 $O(k^{2}n)$；保存 $V_{k+1}$ 需要 $O(kn)$ 存储，保存 Hessenberg 与 QR 数据需要 $O(k^2)$。因此 full GMRES 即使矩阵—向量乘便宜，也会被正交化和基存储拖住。

GMRES($m$) 在每个长度为 $m$ 的周期末接受当前近似，重新计算残差，并以它建立新的 Krylov 空间。周期内部仍最小化当前残差，但重启丢弃了此前基向量；经过多个周期后，结果不再是使用全部累计矩阵—向量乘所得空间上的 full-GMRES 最优解。较小 $m$ 降低存储和正交化成本，也可能造成明显停滞。

停止准则可使用真实残差的尺度化形式

$$\Vert b-A{x}_k{\Vert }_2\le \mathrm{atol}+\mathrm{rtol}(\Vert A{\Vert }_2\Vert x_k{\Vert }_2+\Vert b{\Vert }_2).$$

QR 递推提供廉价的残差估计，但有限精度下 Arnoldi 基会失去正交，估计值可能与显式重算的 $b-A{x}_k$ 漂离。实现应周期性重算真实残差，并在达到最大迭代、残差长期没有实质下降、基向量非有限或 Arnoldi 无法产生新方向时给出不同状态。

直觉 ​

GMRES 只通过反复应用 $A$ 探索初始残差能够到达的方向。Arnoldi 把这些方向整理成正交坐标，随后每轮只需在一个逐渐增大的小型最小二乘问题中寻找最能抵消残差的组合。full GMRES 的空间嵌套，所以精确算术下残差范数单调不增。

重启相当于定期丢弃已经学到的方向，只带着当前残差重新开始。它保住固定内存，却可能忘掉只有多个旧方向共同作用才能消去的残差分量；新的周期即使每一步都局部最优，也未必恢复 full GMRES 的历史路线。

例子与边界 ​

取非正规矩阵

$$A=\left(\begin{array}{ccc}1& 3& 0\\ 0& 1& 3\\ 0& 0& 1\end{array}\right),b=(1,1,1{)}^{\mathsf{T}},x_0=0.$$

三个特征值全为 $1$，但矩阵不是正规矩阵。用 binary64、modified Gram–Schmidt Arnoldi 计算，可复查的残差历史为：

累计矩阵—向量乘	full GMRES $|r{|}_2$	GMRES(1) $|r{|}_2$
0	$1.732051$	$1.732051$
1	$0.738549$	$0.738549$
2	$0.709299$	$0.719704$
3	$O({10}^{-15})$	$0.718919$
4	—	$0.718889$
8	—	$0.718887$

full GMRES 在三维精确算术中至多三步到达解；表中的 $O({10}^{-15})$ 表示不同 binary64 实现会给出不同末位的舍入平台。GMRES(1) 每次只保留一个新方向，残差很快停在约 $0.718887$。这是同一个实验对 full 与 restart 的比较，不是用另一组参数制造重复例子。它也显示只看特征值集合无法预测非正规问题的收敛历史。

残差下降仍不等于前向误差同样下降。若 $A$ 病态，

$$x_k-x_{\ast }=A^{-1}{r}_k$$

会把某些很小的残差方向放大；必须结合条件数或结构化误差界公理库线性方程组的条件数与扰动Conditioning of linear systems · Matrix condition number把一般问题条件性具体化为可逆线性系统的右端、系数矩阵与联合扰动界。解释解的可信度。上表只验证残差最小化和重启停滞，不能外推成普遍的前向精度结论。

若 Arnoldi 出现 $h_{k+1,k}=0$，Krylov 空间已对 $A$ 不变。此时应检查小型最小二乘残差：它可能已经为零，形成“happy breakdown”并给出精确解；在奇异或不相容问题中也可能仍有非零残差，不能把所有 breakdown 都写成成功。

推论与应用 ​

预条件公理库预条件Preconditioning · Preconditioner用易应用的近似逆改变等价线性系统的尺度与 Krylov 几何，并计入构造、存储和每步应用成本。用易求解的算子改变 Krylov 看到的几何，常比单纯增大重启长度更有效；左预条件与右预条件所最小化和报告的残差并不相同，必须在接口中说明。对称正定系统可利用专门的共轭梯度结构，GMRES 则不要求对称或正定，但要支付完整正交化成本。

可靠报告应给重启长度、正交化策略、预条件位置、真实残差历史、矩阵—向量乘次数和退出原因。只给“迭代次数”会隐藏不同重启和预条件配置下每一步完全不同的工作量。

参考资料

• Yousef Saad and Martin H. Schultz, “GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems,” SIAM Journal on Scientific and Statistical Computing 7(3), 1986.
• Richard Barrett et al., Templates for the Solution of Linear Systems, 2nd ed., SIAM, 1994.
• Yousef Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., SIAM, 2003, Ch. 6.