第 XXVI–XXX 讲 · 迭代法与 Krylov 子空间

矩阵大到 $n = 10^7$（三维 POU 离散的常态），$O(n^3)$ 的直接法彻底出局。迭代法只需"矩阵-向量乘"，每步 $O(n)$ 至 $O(n\log n)$——这一组讲大科学计算的发动机：Krylov 子空间方法。

迭代法的两大流派

• 定常迭代（Jacobi、Gauss-Seidel、SOR）：按固定规则扫格子，$O(n)$ 每步但收敛慢，今天主要作为多重网格的光顺器存在。
• Krylov 迭代（CG、GMRES、Lanczos、Arnoldi）：在第 $k$ 步于 Krylov 子空间

里找最优近似解。直觉：$A^{-1}\mathbf{b}$ 的信息已经在 $A$ 反复作用在 $\mathbf{b}$ 的痕迹里，子空间维数够了就能（在精确算术下）给出精确解。

CG：对称正定的王者

对称正定阵有 Rayleigh 商极小刻画，CG 等价于在 $\mathcal{K}_k$ 上极小化误差的 $A$-范数。理论性质：$k$ 步内精确收敛，收敛速度由条件数控制——$\sqrt{\kappa}$ 量级的迭代数期望。预条件子 $M\approx A$（易逆）把迭代转嫁到 $M^{-1}A$ 上，好预条件（不完全 Cholesky、多重网格、对角预条件）能把迭代数从几千压到几十——"迭代法设计 = Krylov 方法 + 预条件设计"。

GMRES 与 Lanczos/Arnoldi

非对称矩阵没有 Rayleigh 商极小化，退而求其次：GMRES 在 $\mathcal{K}_k$ 上极小化残差范数，代价是长递推（内存与算力随步数线性涨，工程上每 $m$ 步重启）；Arnoldi 过程（海森堡化）是 GMRES 的引擎。对称情形 Arnoldi 退化为三对角的 Lanczos 过程，三对角特征值问题便宜解出——这是大规模特征值问题（ARPACK、随机矩阵算法）的地基：特征值信息藏在 Krylov 子空间的小矩阵里。

老师的提醒

• CG 只许用于对称正定——拿去解非对称问题不报错但悄悄算错，务必检查矩阵对称性。
• 迭代数卡在几百不动时，先调预条件子，别死磕重启参数。

自检

• Krylov 子空间为什么"包含"了解？
• CG 极小化什么量？GMRES 呢？
• 预条件子想扮演什么角色？举两个例子。

更深一层：Krylov 子空间的"免费信息"哲学

CG/GMRES 的思想之所以深刻，在于它发现了一个免费午餐：矩阵作用在向量上的每一步都在泄露逆的信息。$\mathcal{K}_k = \text{span}\{b, Ab, \dots, A^{k-1}b\}$ 的维数到 $n$ 就"知道一切"（精确解在 $\mathcal{K}_n$ 里），但绝大多数问题的信息集中在很小的 $k$（几十）里——因为真实矩阵的谱分布不是均匀恶意的：极端特征值少而分离、大偏差方向罕见。Krylov 方法把"解方程"重新表述为"在这个便宜的小空间里找最优投影"——用矩阵-向量乘的低成本换取对谱结构的学习。这个哲学的现代继承者是深度学习里的"随机投影+低秩假设"和大规模科学的随机化 SVD：都是"廉价探测 + 小空间求解"。

推导细读：CG 的极小化性质与"共轭"的真正含义

CG 同时是三件事：极小化 $A$-范数误差的优化算法、Lanczos 三对角化的副产品、多项式逼近 $1/\lambda$ 的构造。三个视角中"共轭"这个词最容易被误解——共轭方向 $p_i^TAp_j = 0$ 的意义是：在 $A$ 定义的内积（能量度量）下相互垂直。于是 CG = "在能量几何里做正交化最速下降"：每一步沿当前残差方向走，同时保持与历史方向能量正交，走 $n$ 步铺满全空间。二次收敛率 $((\sqrt\kappa-1)/(\sqrt\kappa+1))^k$ 里的 $\sqrt\kappa$ 正来自这个能量几何的"椭圆扁度"——预条件子做的事就是把椭圆捏圆（$M^{-1}A$ 的谱聚拢）。

在真实世界里：预条件子是现代稀疏求解的胜负手

迭代法的工程成败 90% 在预条件子，现代选项按"通用性-强度"光谱排列：对角缩放（一行代码，弱但聊胜于无）→ 不完全分解 ILU(0)/ICT（通用中等强度）→ 多重网格（椭圆问题最强，收敛与网格尺寸无关，但需要层次结构）→ 物理预条件（块结构、近逆、物理先验——专家领域）。一套典型的 CFD 不可压求解栈：压力泊松用几何多重网格、动量方程用 ILU 预条件双共轭梯度——不同的块配不同的预条件，这是多物理场求解器的标准架构决策。

常见误区与辨析

• "CG 用于一切矩阵"：CG 数学上只对 SPD 收敛；非对称问题拿 CG 硬解会悄悄给出错误答案（不报错！）——先用对称性检查卡住入口。
• "迭代法比直接法慢"：迭代数与网格无关时（多重网格），$O(n)$ 完胜 $O(n^{1.5})$ 的稀疏 Cholesky——大网格上迭代法是唯一现实选项。
• "残差降到机器精度才停"：工程精度（相对残差 $10^{-8}$）足够时继续迭代是烧电；停滞检测（残差不再降）比死磕阈值重要。

专题深入：Krylov 子空间的"免费信息"哲学完整版

CG/GMRES 的思想深刻之处在于它发现了一个免费午餐：矩阵作用在向量上的每一步都在泄露逆的信息。$\mathcal{K}_k = \text{span}\{b, Ab, \dots, A^{k-1}b\}$ 的维数到 $n$ 就"知道一切"（精确解在 $\mathcal{K}_n$ 里），但绝大多数问题的信息集中在很小的 $k$（几十）里——因为真实矩阵的谱分布不是均匀恶意的。Krylov 方法把"解方程"重新表述为"在这个便宜的小空间里找最优投影"——用矩阵-向量乘的低成本换取对谱结构的学习。这个哲学的现代继承者是随机化 SVD 与深度学习的"随机投影 + 低秩假设"。

数学细节展开：CG 的极小化性质与"共轭"的真正含义

CG 同时是三件事：极小化 $A$-范数误差的优化算法、Lanczos 三对角化的副产品、多项式逼近 $1/\lambda$ 的构造。"共轭方向" $p_i^TAp_j = 0$ 的意义是：在 $A$ 定义的内积（能量度量）下相互垂直——CG = "在能量几何里做正交化最速下降"。收敛率 $((\sqrt\kappa-1)/(\sqrt\kappa+1))^k$ 里的 $\sqrt\kappa$ 正来自这个能量几何的"椭圆扁度"——预条件子做的事就是把椭圆捏圆（$M^{-1}A$ 的谱聚拢）。

工程案例细节：预条件子的"通用性-强度"光谱

预条件子的通用性-强度光谱：对角缩放（一行代码，弱但聊胜于无）→ 不完全分解 ILU(0)/ICT（通用中等强度）→ 多重网格（椭圆问题最强，收敛与网格尺寸无关，但需要层次结构）→ 物理预条件（块结构、近逆、物理先验——专家领域）。CFD 不可压求解栈：压力泊松用几何多重网格、动量方程用 ILU 预条件双共轭梯度——不同的块配不同的预条件，这是多物理场求解器的标准架构决策。

常见误区与辨析（补充）

• "CG 用于一切矩阵"：CG 数学上只对 SPD 收敛；非对称问题拿 CG 硬解会悄悄给出错误答案（不报错！）。
• "迭代法比直接法慢"：迭代数与网格无关时（多重网格），$O(n)$ 完胜 $O(n^{1.5})$ 的稀疏 Cholesky。