12. 最速下降与共轭梯度

对称正定线性系统 $Ax=b$ 等价于最小化严格凸二次函数

$$\varphi (x)=\frac{1}{2}{x}^{T}Ax-b^{T}x.$$

这一视角把线性代数、优化和 Krylov 子空间方法统一起来。

12.1 最速下降法

梯度为 $\mathrm{\nabla }\varphi (x)=Ax-b=-r$，因此最速下降方向是残差 $r_k=b-A{x}_k$。沿该方向精确线搜索得到

$${\alpha }_k=\frac{r_k^T{r}_k}{r_k^{T}A{r}_k},x_{k+1}=x_k+{\alpha }_k{r}_k.$$

若 $A$ 的等高线很狭长，迭代会在两侧来回“之”字形移动。真正决定速度的是谱的离散程度，尤其是条件数 ${\kappa }_2(A)$。

12.2 共轭方向

两个方向 $p_i,p_j$ 若满足

$$p_i^{T}A{p}_j=0$$

则称它们关于 $A$ 共轭。沿一组 $A$-共轭方向依次精确最小化，后续步骤不会破坏此前方向上的最优性。

12.3 共轭梯度法

令 $r_0=b-A{x}_0$，$p_0=r_0$。标准 CG 递推为

$${\alpha }_k=\frac{r_k^T{r}_k}{p_k^{T}A{p}_k},$$$$x_{k+1}=x_k+{\alpha }_k{p}_k,r_{k+1}=r_k-{\alpha }_{k}A{p}_k,$$$${\beta }_k=\frac{r_{k+1}^T{r}_{k+1}}{r_k^T{r}_k},p_{k+1}=r_{k+1}+{\beta }_k{p}_k.$$

每轮只需一次矩阵—向量乘法、若干内积和向量更新，且只保存少量向量。

12.4 几何与最优性

精确算术下：

• 残差两两正交；
• 搜索方向两两 $A$-共轭；
• $x_k$ 是 $x_0+{\mathcal{K}}_k(A,r_0)$ 中使 $A$-范数误差最小的点。

因此 CG 不是“加速版最速下降”，而是利用整个 Krylov 空间的投影方法。若 $A$ 只有 $s$ 个不同特征值，精确算术下至多 $s$ 步即可终止。

更准确地，CG 满足

$$x_k=\arg \underset{x\in x_0+{\mathcal{K}}_k(A,r_0)}{min}\parallel x_{\ast }-x{\parallel }_A,$$

并等价于 Galerkin 条件

$$r_k\perp {\mathcal{K}}_k(A,r_0).$$

由于 $r_k=A(x_{\ast }-x_k)$，$A$-范数误差最小也等价于残差的 $A^{-1}$-范数最小。它并不保证普通 2-范数残差每步单调下降。

12.5 收敛界

经典 Chebyshev 界为

$$\parallel e_k{\parallel }_A\le 2{\left(\frac{\sqrt{\kappa }-1}{\sqrt{\kappa }+1}\right)}^k\parallel e_0{\parallel }_A,\kappa ={\kappa }_2(A).$$

它只用极端特征值，往往比较保守。实际速度还与特征值是否成簇有关：少数离群特征值被多项式压低后，收敛可能突然加快。

12.6 预条件 CG

选择易求解且近似 $A$ 的对称正定矩阵 $M$，每轮解

$$M{z}_k=r_k.$$

PCG 的效果取决于 $M^{-1}A$ 的谱是否聚集，同时还要权衡构造和应用 $M$ 的代价。常见选择包括 Jacobi、块对角以及不完全 Cholesky 分解。

12.7 有限精度注意事项

舍入误差会破坏正交性与共轭性，递推残差也可能逐渐偏离真实残差 $b-A{x}_k$。稳健实现应定期显式重算真实残差，并以它作为最终验收依据。

12.8 从全正交化推导短递推

若直接在 Krylov 空间中构造 $A$-正交方向，原则上需要把新残差对所有旧方向正交化。对称性带来关系

$$p_i^{T}A{p}_j=0(i\ne j),$$

并使远距离系数自动为零，最终只需保留上一步方向：

$$p_{k+1}=r_{k+1}+{\beta }_k{p}_k.$$

这就是 CG 只需短递推的根本原因。一般非对称矩阵缺少这一正交结构，GMRES 必须保留长基或付出双正交化等额外代价。

12.9 多项式最优性

误差可写成

$$e_k=p_k(A)e_0,p_k\in {\mathrm{\Pi }}_k,p_k(0)=1.$$

因此

$$\parallel e_k{\parallel }_A\le \underset{p(0)=1}{min}\underset{\lambda \in \sigma (A)}{max}|p(\lambda )|\parallel e_0{\parallel }_A.$$

CG 实际上在谱点集合上选择最有利的多项式。经典条件数界把离散谱粗略包进区间 $[{\lambda }_{min},{\lambda }_{max}]$，因而会忽略聚簇带来的超预期快速收敛。

12.10 Chebyshev 界的来源

把 $[{\lambda }_{min},{\lambda }_{max}]$ 仿射映射到 $[-1,1]$，使用第一类 Chebyshev 多项式

$$T_k(t)=\cos (k\arccos t),|t|\le 1.$$

它在区间上满足 $|T_k(t)|\le 1$，而区间外按指数速度增长。用区间外的 $t_0$ 归一化，使 $p_k(0)=1$，便得到

$$\parallel e_k{\parallel }_A\le 2{\left(\frac{\sqrt{\kappa }-1}{\sqrt{\kappa }+1}\right)}^k\parallel e_0{\parallel }_A.$$

最速下降对应的因子约为 $(\kappa -1)/(\kappa +1)$，CG 把对 $\kappa$ 的依赖从线性改善到平方根量级。

12.11 PCG 的对称实现

若 $M=C{C}^T\succ 0$，理论上是在变换后系统

$$C^{-1}A{C}^{-T}y=C^{-1}b,x=C^{-T}y$$

上运行 CG。实践中不形成变换矩阵，只在每轮解 $M{z}_k=r_k$，并使用

$${\alpha }_k=\frac{r_k^T{z}_k}{p_k^{T}A{p}_k},{\beta }_k=\frac{r_{k+1}^T{z}_{k+1}}{r_k^T{z}_k}.$$

$M$ 必须对称正定且在迭代中固定，才能保留标准 CG 理论。若预处理器变化，应改用 flexible 变体。

12.12 预条件器的选择

• Jacobi/块 Jacobi：便宜、并行，但改善有限；
• 不完全 Cholesky：利用稀疏结构，需控制填充和 breakdown；
• 多重网格：对椭圆型 PDE 常接近最优复杂度；
• 领域分解：适合并行和多物理子结构。

评估预处理器要看“总时间 = 构造时间 + 迭代次数 × 单步成本”，而不是只看迭代次数。

自检

1. 为什么 CG 只适用于对称正定系统？
2. CG 的 Krylov 最优性使用的是哪一个范数？
3. 好的预处理器为什么既要改善谱，又要便宜地求解？
4. CG 最小化的是哪一种误差范数，残差对应什么范数？
5. 为什么标准 PCG 要求固定的对称正定预处理器？