GMRES 方法

形式陈述 ​

给定方阵线性系统理路线性方程组System of linear equations可写为矩阵方程 Ax=b 的有限个一次方程系统。 $Ax=b$ 和初值 $x_0$，按二范数理路矩阵范数与诱导算子范数Matrix norm · Induced matrix norm · Operator norm of a matrix用诱导范数和常用可计算矩阵范数度量线性映射的放大能力，并区分算子范数、Frobenius 范数与谱半径。衡量残差，令

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

选择 $x_k$，使原系统的二范数残差理路残差、误差估计与停止准则Residual and error estimation · Stopping criterion区分可计算残差与未知真误差，并说明把缺陷转成误差界和停止证书所需的条件。最小：

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

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

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

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

当 $A$ 非奇异且已生成的 Krylov 基线性无关时，小问题的极小点唯一；奇异情形可能有多个极小点，需明确选解规则，例如在小问题中选最小范数系数。实现通常用逐步 QR 更新维护该问题和残差范数，不在每轮从头求解。输入还应包括最大矩阵—向量乘次数、绝对与相对容差、重启长度以及预条件算子；输出必须包含 $x_k$、真实或估计残差、矩阵—向量乘次数和退出状态。

对稀疏 $A$，若存储 $s$ 个条目（计入显式零与重复坐标），每一步矩阵—向量乘的成本为 $O(s+n)$，其中 $O(n)$ 用于初始化输出向量。第 $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$ 降低存储和正交化成本，也可能造成明显停滞。

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

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