2. 迭代求解器回顾

预条件技术并不是孤立存在的，它总是服务于某个迭代求解器。理解各迭代法的算法框架与收敛条件，才能判断“该给谁做预条件、预条件要改善什么”。本节按两条主线回顾：定常迭代法（Jacobi、Gauss-Seidel、SOR）与Krylov子空间法（共轭梯度法、GMRES），重点落在迭代格式、收敛判据以及它们对矩阵性质的依赖上。

一、定常迭代法的统一框架

设线性方程组为 Ax = b，将系数矩阵分裂为 A = M − N，其中 M 非奇异且易于求解，则迭代格式统一写为

x^(k+1) = M^(-1) N x^(k) + M^(-1) b

记迭代矩阵 G = M^(-1)N，收敛的充要条件是谱半径 ρ(G) < 1，且谱半径越小收敛越快。三种定常迭代法的差别，本质上只是 M 的取法不同。

• Jacobi：取 M = D（对角部分），N = L + U。分量形式为 x_i^(k+1) = (b_i − Σ_{j≠i} a_ij x_j^(k)) / a_ii。各分量可完全并行更新，但只用到上一轮的值，信息更新滞后。收敛的充分条件是 A 严格对角占优。
• Gauss-Seidel：取 M = D + L，N = −U。计算 x_i^(k+1) 时立即使用已更新的 x_j^(k+1)（j < i），收敛速度通常约为 Jacobi 的两倍。对对称正定矩阵，Gauss-Seidel 必收敛；对严格对角占优矩阵同样收敛。
• SOR：在 Gauss-Seidel 基础上引入松弛因子 ω：x_i^(k+1) = (1−ω)x_i^(k) + ω·(b_i − Σ_{j<i} a_ij x_j^(k+1) − Σ_{j>i} a_ij x_j^(k)) / a_ii。当 0 < ω < 1 为低松弛，1 < ω < 2 为超松弛。对对称正定矩阵，收敛区间为 0 < ω < 2；存在最优 ω_opt 使谱半径最小，但需估计 Jacobi 迭代矩阵的谱半径才能算出。

二、Krylov子空间法：CG 与 GMRES

Krylov 方法不显式构造迭代矩阵，而是在子空间 K_m(A, r_0) = span{r_0, Ar_0, …, A^(m−1)r_0} 中寻找近似解，其中 r_0 = b − Ax_0。

共轭梯度法（CG）适用于 A 对称正定。它要求搜索方向关于 A 共轭，即 p_i^T A p_j = 0 (i≠j)，从而在 m 步内（理论上）精确收敛。算法核心为：

r_0 = b − A x_0,  p_0 = r_0
for k = 0,1,2,...
    α_k = (r_k^T r_k) / (p_k^T A p_k)
    x_(k+1) = x_k + α_k p_k
    r_(k+1) = r_k − α_k A p_k
    β_k = (r_(k+1)^T r_(k+1)) / (r_k^T r_k)
    p_(k+1) = r_(k+1) + β_k p_k

CG 的收敛速度由条件数 κ(A) 控制，误差上界约为 2·((√κ−1)/(√κ+1))^k。这正是预条件技术的用武之地：用 M^(-1)A 替代 A，使 κ(M^(-1)A) ≪ κ(A)。

GMRES面向非对称、不定矩阵。它在 Krylov 子空间中最小化残差范数 ‖b − Ax‖_2，通过 Arnoldi 过程构造正交基 V_m 与上 Hessenberg 矩阵 H_m，把问题化为小规模最小二乘 min ‖βe_1 − H_m y‖_2，再用 Givens 旋转增量求解。GMRES 的代价是存储全部基向量，内存随迭代步线性增长，实际中采用重启版本 GMRES(m)。其收敛性没有像 CG 那样简洁的条件数界，对特征值分布敏感：特征值聚簇且远离原点时收敛快。

三、收敛条件与预条件的接口

把两类方法放在一起看，预条件的切入点非常清晰。对定常迭代，预条件等价于换一个分裂方式，使新迭代矩阵的谱半径更小；对 CG，预条件要求 M 对称正定，实际求解 M^(-1)A x = M^(-1)b 时通过 M 的 Cholesky 分解保持对称性；对 GMRES，左预条件 M^(-1)Ax = M^(-1)b 直接改变残差度量，右预条件 AM^(-1)y = b, x = M^(-1)y 则保持残差范数不变，便于监控真实残差。

一个常见的教学示例：取二维 Poisson 型矩阵（五点差分，网格 32×32，n = 1024），A 对称正定，条件数约 O(h^(-2))，量级在 10³ 以上。若直接使用 CG，残差下降 6 个数量级可能需要数百步；若采用不完全 Cholesky（IC(0)）作预条件，条件数可降至 10¹～10² 量级，迭代步数通常减少到原来的几分之一。这里的具体步数依赖网格与容差设置，属于示例性说明，实际数值应以运行结果为准。判断收敛时统一采用相对残差准则 ‖r_k‖₂ / ‖r_0‖₂ ≤ 1e-6，并设置最大迭代步数防止死循环。

回顾这些算法框架的意义在于：预条件器的设计目标不是“更复杂的分解”，而是让所选求解器所依赖的谱性质变得更好——对 CG 是降低条件数，对 GMRES 是让特征值聚簇，对定常迭代是压低谱半径。明确了这一点，后续选择预条件类型时就有了判断依据。