共轭梯度法

形式陈述 ​

共轭梯度法只以 Hermitian正定公理库正定与半正定矩阵Positive definite matrix · Positive semidefinite matrix · PSD matrix由二次能量严格为正或非负定义的实对称与复 Hermitian 矩阵。系统

$$Ax=b,A=A^{\ast },x^{\ast }Ax>0(x\ne 0)$$

为基本问题。它等价于最小化严格凸二次能量

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

以下递推在实数情形直接成立；复数情形的内积使用共轭转置。给初值 $x_0$，令

$$r_0=b-A{x}_0,p_0=r_0.$$

只要 $r_k\ne 0$，计算

$${\alpha }_k=\frac{r_k^{\ast }{r}_k}{p_k^{\ast }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}^{\ast }{r}_{k+1}}{r_k^{\ast }{r}_k},p_{k+1}=r_{k+1}+{\beta }_k{p}_k.$$

正定性保证 $p_k^{\ast }A{p}_k>0$，因此在尚未收敛时分母有效。输入应包括 SPD 矩阵或 matvec 接口、$b,x_0$、绝对与相对容差和迭代上限；输出应包括 $x_k$、真实残差、迭代次数、matvec 次数和退出状态。

令 $x_{\ast }=A^{-1}b$、$e_k=x_{\ast }-x_k$，并定义

$$\Vert e{\Vert }_A=\sqrt{e^{\ast }Ae}.$$

精确算术中，CG 的第 $k$ 个近似满足

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

同时，不同残差彼此正交，

$$r_i^{\ast }{r}_j=0(i\ne j),$$

不同搜索方向关于 $A$ 共轭，

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

这些性质使每个新方向在不破坏旧方向最优性的情况下扩展Krylov 子空间公理库Krylov 子空间Krylov subspace · Arnoldi iteration · Lanczos iteration从初始向量反复施加矩阵，生成只依赖矩阵—向量乘法的递增子空间及其 Arnoldi、Lanczos 正交基。。若相对于 $r_0$ 的最小多项式次数为 $d$，精确算术中至多 $d\le n$ 步得到精确解；“至多 $n$ 步”不是浮点实现的固定运行承诺。

若 ${\kappa }_2(A)={\lambda }_{max}/{\lambda }_{min}$，经典最坏界为

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

该界只用谱端点，实际收敛还取决于特征值聚集和初始误差在各特征方向的分量；它是精确算术的先验上界，不应被当作逐步等式。

每步需要一次 $A{p}_k$、若干内积和向量更新。对稀疏 $A$，工作为 $O(\mathrm{nnz}(A)+n)$，存储只需矩阵和少数长度 $n$ 的向量；并行实现的全局内积归约可能比本地 SpMV 更限制扩展性。

停止可要求重算的真实残差满足

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

还必须检查迭代上限、非有限值、非正曲率 $p_k^{\ast }A{p}_k\le 0$ 和残差停滞。递推 $r_{k+1}=r_k-{\alpha }_{k}A{p}_k$ 在浮点中会逐渐偏离 $b-A{x}_{k+1}$，所以长期运行应周期性重算真实残差，并以真实残差决定最终状态。

直觉 ​

最速下降每一步只找当前最陡方向，容易在狭长能量椭球中来回摆动。CG 让新搜索方向与旧方向在 $A$ 内积下互不干扰：沿新方向优化时，先前方向已经取得的最优分量不会被重新破坏。于是它用短递推积累整个 Krylov 历史。

正定性在这里同时承担三项工作：能量有唯一最低点，$\Vert \cdot {\Vert }_A$ 真的是范数，每个步长分母保持为正。去掉这一条件后，算法公式也许还能计算几步，却不再拥有同一最小化几何和有限步理论。

例子与边界 ​

取

$$A=\left(\begin{array}{cc}4& 1\\ 1& 3\end{array}\right),b=\left(\begin{array}{c}1\\ 2\end{array}\right),x_0=0.$$

$A$ 的顺序主子式为 $4$ 与 $11$，所以它正定；精确解为

$$x_{\ast }=\left(\begin{array}{c}1/11\\ 7/11\end{array}\right).$$

第一步有 ${\alpha }_0=1/4$，得到

$$x_1=\left(\begin{array}{c}1/4\\ 1/2\end{array}\right),r_1=\left(\begin{array}{c}-1/2\\ 1/4\end{array}\right),{\beta }_0=\frac{1}{16}.$$

第二步 ${\alpha }_1=4/11$，在精确算术中直接得到 $x_2=x_{\ast }$。完整小型历史为

$k$	$x_k$	$|r_k{|}_2$	$|e_k{|}_A$
0	$(0,0{)}^{\mathsf{T}}$	$\sqrt{5}$	$\sqrt{15/11}$
1	$(1/4,1/2{)}^{\mathsf{T}}$	$\sqrt{5}/4$	$\sqrt{5/44}$
2	$(1/11,7/11{)}^{\mathsf{T}}$	$0$	$0$

两步终止来自二维精确算术和两个可达特征方向，不意味着 binary64 必然在第 $n$ 步得到零残差。

残差与前向误差仍是不同量。由于

$$r_k=A{e}_k,$$

有

$$\frac{\Vert e_k{\Vert }_2}{\Vert x_{\ast }{\Vert }_2}\le {\kappa }_2(A)\frac{\Vert r_k{\Vert }_2}{\Vert b{\Vert }_2}.$$

小残差只有结合条件数公理库线性方程组的条件数与扰动Conditioning of linear systems · Matrix condition number把一般问题条件性具体化为可逆线性系统的右端、系数矩阵与联合扰动界。才能转成前向误差保证。CG 最小化的是 $A$-范数误差，而常用停止准则观察的是可计算残差；报告中应保留这项区别。

非对称或不定矩阵不属于 CG 的输入域。例如

$$A=\mathrm{diag}(1,-1),p_0=(1,1{)}^{\mathsf{T}}$$

给出 $p_0^{\mathsf{T}}A{p}_0=0$，第一步步长就除以零。对这类系统应选择与矩阵结构匹配的方法，不能靠给分母加 epsilon 继续冒充 CG。

浮点舍入还会让残差失去正交、方向失去 $A$-共轭，最终出现比精确理论更慢的收敛或停滞。重新正交化、残差替换和预条件公理库预条件Preconditioning · Preconditioner用易应用的近似逆改变等价线性系统的尺度与 Krylov 几何，并计入构造、存储和每步应用成本。可以改变实践表现，但都必须作为额外算法与误差路径说明。

推论与应用 ​

椭圆 PDE 与有限元常产生大型稀疏 SPD 系统，CG 只需 SpMV、内积和向量更新，因而避免稠密因子。预条件的目标是重新塑造谱，使有效条件数下降；具体效果取决于预条件系统的定义和应用成本，不能只报告迭代次数减少。

可复现实验应同时画递推残差、定期重算的真实残差和已知参考下的前向或 $A$-范数误差，并记录 matvec 与内积次数。这样才能区分理论 Krylov 收敛、问题条件性和有限精度漂移。

参考资料

• Magnus R. Hestenes and Eduard Stiefel, “Methods of Conjugate Gradients for Solving Linear Systems,” Journal of Research of the National Bureau of Standards 49, 1952.
• Richard Barrett et al., Templates for the Solution of Linear Systems, 2nd ed., SIAM, 1994, Ch. 2.
• Lloyd N. Trefethen and David Bau III, Numerical Linear Algebra, SIAM, 1997, Lecture 38.
• Yousef Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., SIAM, 2003, Ch. 6.