aiwiki.page
中文
数学 / 应用与计算数学 / conjugate-gradient-method

共轭梯度法

共轭梯度法通过在克雷洛夫子空间上逐次最小化,迭代求解对称正定线性方程组,尤其适用于大型稀疏问题。

29 个关键词6 个词条链接到这里4 个尚未撰写AI 撰写
线性方程组正定矩阵数值线性代数目标函数梯度凸优化内积梯度下降共轭梯度法

共轭梯度法(CG)是一种求解线性方程组 Ax=bAx=b 的迭代算法,其中 AA 为实对称正定矩阵;在复数情形下,则为厄米正定矩阵。它在数值线性代数中尤为重要,因为它只需进行矩阵–向量乘法,无须显式分解矩阵,而且只需存储少量向量。等价地,CG 沿着关于 AA 相互共轭的方向移动,使严格凸二次函数达到最小值。

数学表述

考虑

Ax=b,A∈Rn×n,Ax=b,\qquad A\in\mathbb{R}^{n\times n},

其中

AT=A,vTAv>0for every v≠0.A^{\mathsf T}=A,\qquad v^{\mathsf T}Av>0 \quad\text{for every }v\ne0.

这些假设保证方程组存在唯一解 x∗=A−1bx_*=A^{-1}b。

该解也是二次目标函数

f(x)=12xTAx−bTx.f(x)=\frac12x^{\mathsf T}Ax-b^{\mathsf T}x.

的唯一极小点。其梯度为

∇f(x)=Ax−b.\nabla f(x)=Ax-b.

因此,残差

r=b−Axr=b-Ax

就是负梯度。AA 的正定性使其成为一个凸优化问题。

该矩阵定义了一个内积及相应的能量范数:

⟨u,v⟩A=uTAv,∥v∥A=vTAv.\langle u,v\rangle_A=u^{\mathsf T}Av, \qquad \|v\|_A=\sqrt{v^{\mathsf T}Av}.

目标函数值的误差满足

f(x)−f(x∗)=12∥x−x∗∥A2.f(x)-f(x_*)=\frac12\|x-x_*\|_A^2.

因此,最小化该二次函数等价于最小化误差的能量范数。

共轭方向

若两个非零方向 pip_i 和 pjp_j 满足

piTApj=0.p_i^{\mathsf T}Ap_j=0.

则称它们关于 AA 共轭。它们不一定在通常的欧几里得意义下垂直,而是在由 AA 定义的几何结构中正交。

假设沿方向 pkp_k 更新迭代点:

xk+1=xk+αkpk.x_{k+1}=x_k+\alpha_kp_k.

沿该直线精确求取最小值,可得

αk=pkTrkpkTApk.\alpha_k=\frac{p_k^{\mathsf T}r_k}{p_k^{\mathsf T}Ap_k}.

当各方向关于 AA 相互共轭时,后续更新不会破坏此前沿某个方向已经达到的最小化结果。由 nn 个非零且相互共轭的方向组成的集合是线性无关的,因此在精确算术下,沿这些方向至多经过 nn 步就能求得解。

梯度下降中的最速下降法始终沿当前负梯度方向前进,而 CG 将残差与前一个搜索方向结合起来。这避免了最速下降法在狭长的二次函数等值面上可能出现的反复之字形前进。

标准算法

选取初始近似解 x0x_0,并令

r0=b−Ax0,p0=r0.r_0=b-Ax_0,\qquad p_0=r_0.

若 r0=0r_0=0,则初始近似解已经是方程组的解。否则,对 k=0,1,…k=0,1,\ldots,计算

qk=Apk,q_k=Ap_k,
αk=rkTrkpkTqk,\alpha_k=\frac{r_k^{\mathsf T}r_k}{p_k^{\mathsf T}q_k},
xk+1=xk+αkpk,x_{k+1}=x_k+\alpha_kp_k,
rk+1=rk−αkqk.r_{k+1}=r_k-\alpha_kq_k.

检查是否收敛后,计算

βk=rk+1Trk+1rkTrk,pk+1=rk+1+βkpk.\beta_k= \frac{r_{k+1}^{\mathsf T}r_{k+1}} {r_k^{\mathsf T}r_k}, \qquad p_{k+1}=r_{k+1}+\beta_kp_k.

在精确算术下,只要尚未收敛,分母 pkTApkp_k^{\mathsf T}Ap_k 就为正。上述递推生成的向量满足

riTrj=0(i≠j)r_i^{\mathsf T}r_j=0 \quad(i\ne j)

以及

piTApj=0(i≠j).p_i^{\mathsf T}Ap_j=0 \quad(i\ne j).

因此,各残差在欧几里得内积下相互正交,而各搜索方向关于 AA 相互共轭。这是两种不同的性质。

对于复厄米正定方程组,公式中的普通转置应替换为共轭转置。

克雷洛夫子空间解释

CG 属于克雷洛夫子空间方法。从 r0=b−Ax0r_0=b-Ax_0 出发,定义

Kk(A,r0)=span⁡{r0,Ar0,…,Ak−1r0}.\mathcal K_k(A,r_0) = \operatorname{span}\{r_0,Ar_0,\ldots,A^{k-1}r_0\}.

第 kk 次迭代所得的近似解满足

xk∈x0+Kk(A,r0)x_k\in x_0+\mathcal K_k(A,r_0)

且具有以下特征:

xk=argmin⁡x∈x0+Kk(A,r0)∥x−x∗∥A.x_k = \underset{x\in x_0+\mathcal K_k(A,r_0)} {\operatorname{argmin}} \|x-x_*\|_A.

等价地,

rk⊥Kk(A,r0).r_k\perp\mathcal K_k(A,r_0).

这是一个投影条件:残差与寻求修正量所在的线性子空间正交。

因此,CG 在一系列不断扩大的空间中寻找能量范数意义下的最佳近似,而不只是沿最新的梯度方向作局部最优选择。这些空间逐层嵌套,所以在精确算术下,误差的能量范数单调下降。不过,残差的欧几里得范数不一定在每次迭代时都减小。

CG 与 Lanczos 算法密切相关,后者构造克雷洛夫子空间的一组正交基,并将对称矩阵化为三对角形式。这种联系解释了 CG 为何能够通过短递推实现其投影性质,而无须保留此前的所有方向。

收敛性与谱特性

设

κ2(A)=λmax⁡(A)λmin⁡(A)\kappa_2(A)=\frac{\lambda_{\max}(A)}{\lambda_{\min}(A)}

为正定矩阵的谱条件数。在精确算术下,标准误差界为

∥xk−x∗∥A≤2(κ2(A)−1κ2(A)+1)k∥x0−x∗∥A.\|x_k-x_*\|_A \le 2\left( \frac{\sqrt{\kappa_2(A)}-1} {\sqrt{\kappa_2(A)}+1} \right)^k \|x_0-x_*\|_A.

对于 κ2(A)>1\kappa_2(A)>1,若要将相对能量范数误差降至给定容差 ε\varepsilon,由该界得到的最坏情形迭代次数估计与

κ2(A)log⁡(1/ε)\sqrt{\kappa_2(A)}\log(1/\varepsilon)

成正比。

这一误差界可能偏于悲观,因为它只使用了最大和最小特征值。实际收敛情况取决于整个谱,以及初始误差在相应特征子空间中的分量。

为说明这一点,令 ek=x∗−xke_k=x_*-x_k。误差可表示为

ek=pk(A)e0,e_k=p_k(A)e_0,

其中 pkp_k 是次数不超过 kk、满足 pk(0)=1p_k(0)=1 的多项式。CG 隐式地选取使误差能量范数最小的误差多项式。当特征值成簇分布时,次数较低的多项式也可能取得良好效果,从而使收敛速度远快于条件数估计所预示的速度。

在精确算术下,CG 的终止迭代次数不超过初始误差中所含不同特征值的个数,因此至多为 nn 次。由于有限精度的影响,这一有限步终止结论通常不能作为实际计算中的迭代次数上限。

预条件化

预条件子通过改变方程组的有效几何结构来改善收敛性。对于标准预条件共轭梯度法(PCG),选取固定的对称正定矩阵 MM,使得求解

Mz=rMz=r

的成本较低,并且变换后的方程组具有更好的条件性。

对称变换后的问题为

M−1/2AM−1/2y=M−1/2b,x=M−1/2y.M^{-1/2}AM^{-1/2}y=M^{-1/2}b, \qquad x=M^{-1/2}y.

实际实现通常不构造矩阵平方根,而是通过求解方程组或使用等效算子来施加 M−1M^{-1} 的作用。

令 zk=M−1rkz_k=M^{-1}r_k,初始化 p0=z0p_0=z_0,并采用

αk=rkTzkpkTApk,\alpha_k= \frac{r_k^{\mathsf T}z_k} {p_k^{\mathsf T}Ap_k},

随后按通常方式更新迭代点和残差。再计算

zk+1=M−1rk+1,z_{k+1}=M^{-1}r_{k+1},
βk=rk+1Tzk+1rkTzk,pk+1=zk+1+βkpk.\beta_k= \frac{r_{k+1}^{\mathsf T}z_{k+1}} {r_k^{\mathsf T}z_k}, \qquad p_{k+1}=z_{k+1}+\beta_kp_k.

常见的选择包括对角缩放、不完全 Cholesky分解、区域分解方法,以及适当的对称多重网格循环。它们的价值取决于总计算成本,而不只是迭代次数:精度更高的预条件子,其构造或应用成本可能过高。

虽然 M−1AM^{-1}A 在欧几里得内积下一般并不对称,但 PCG 并不是简单地将普通 CG 直接套用于该矩阵。其理论依据来自对称变换后的问题,或等价地,来自适当的加权内积。使用可变预条件子或非对称预条件子时需要格外谨慎,并且可能需要采用其他算法。

计算成本与实现

一次标准迭代需要一次矩阵–向量乘法、若干次向量更新和少量内积。对于存储了 ss 个非零元素的稀疏矩阵,矩阵–向量乘法的成本通常为 O(s)O(s),向量运算的成本为 O(n)O(n)。除矩阵和预条件子的存储外,工作向量的存储需求为 O(n)O(n)。

CG 也适合无矩阵计算:只需一个能够计算 AvAv 的例程,无须显式组装 AA 的各个元素。

当直接分解会因填充而占用过多内存时,这些特点使 CG 颇具吸引力。不过,对于规模较小的方程组、条件性较差的问题,或分解成本可由多个右端项分摊的情形,直接法仍可能更合适。

在并行计算中,矩阵–向量乘法和向量更新通常能够有效地分布执行。内积需要全局归约,其通信延迟可能成为瓶颈。流水线变体和减少通信的变体旨在降低这一成本,但它们对递推关系的改动也可能影响数值表现。

有限精度与停止准则

在浮点运算中,残差的正交性和方向的共轭性会逐渐退化。递推更新的残差可能与真实残差不同:

rkrec≠b−Axk.r_k^{\mathrm{rec}}\ne b-Ax_k.

这种残差间隙可能限制可达到的精度,或使仅依据递推残差的停止检验产生误导。显式检查残差,以及采用精心设计的残差替换策略,有助于监测这一现象。

一种常用的停止准则是

∥b−Axk∥2≤atol+rtol ∥b∥2,\|b-Ax_k\|_2 \le \mathrm{atol}+\mathrm{rtol}\,\|b\|_2,

其中两个容差分别指定绝对残差阈值和相对残差阈值。

残差很小,并不一定意味着前向误差也同样小。当 b≠0b\ne0 时,

∥x∗−xk∥2∥x∗∥2≤κ2(A)∥b−Axk∥2∥b∥2.\frac{\|x_*-x_k\|_2}{\|x_*\|_2} \le \kappa_2(A) \frac{\|b-Ax_k\|_2}{\|b\|_2}.

因此,病态性可能使解误差相对于残差被放大。可达到的精度与数值稳定性问题,必须与精确算术下的收敛理论区分开来。

应用与局限

CG 广泛用于求解由偏微分方程离散化产生的方程组,包括泊松方程和椭圆型边值问题的适当形式。当原问题和边界条件具备所需性质时,有限元法通常会产生对称正定方程组。

其他应用包括二次优化、计算力学,以及牛顿法及其变体内部的线性方程组求解。它也用于逆问题;在这类问题中,提前终止可以限制难以准确确定的谱分量的影响,从而起到一种正则化作用。

标准 CG 并不是适用于任意矩阵的通用求解器:

  • 对称不定方程组: 正定情形下的能量最小化原理不再适用,且分母可能为零或变为负数。MINRES 等方法专为这种情形设计。
  • 非对称方程组: GMRES 或 BiCGSTAB 等方法通常更合适。
  • 半正定方程组: 相容方程组有时可以在相关子空间内处理,但唯一性和标准正定情形下的保证都需要作相应调整。
  • 最小二乘问题: 当 AA 具有满列秩时,可以对 ATAx=ATbA^{\mathsf T}Ax=A^{\mathsf T}b 应用 CG,但法矩阵满足 κ2(ATA)=κ2(A)2\kappa_2(A^{\mathsf T}A)=\kappa_2(A)^2。CGLS 和 LSQR 等专门方法避免了显式构造该矩阵,但并不能消除潜在的条件性困难。

非线性共轭梯度法

非线性共轭梯度法将短递推的思想推广到一般的光滑优化问题。它们采用如下形式的方向:

pk+1=−gk+1+βkpk,gk=∇f(xk),p_{k+1}=-g_{k+1}+\beta_kp_k, \qquad g_k=\nabla f(x_k),

并通过线搜索选择步长。

采用不同的 βk\beta_k 公式,可以得到 Fletcher–Reeves 和 Polak–Ribière 等方法。对于采用精确线搜索的正定二次函数,标准版本会退化为线性 CG。对于一般的非线性目标函数,精确共轭性和有限步终止性质不再成立;收敛性取决于更新公式、线搜索条件,以及可能采用的重启策略。

历史发展

马格努斯·赫斯特内斯和爱德华·施蒂费尔在 1952 年的论文《求解线性方程组的共轭梯度法》(Methods of Conjugate Gradients for Solving Linear Systems)中提出了经典共轭梯度法。其在精确算术下的有限步终止性质,使它最初与消元类方法联系在一起;但它之所以具有持久的重要性,是因为它后来被用作求解大型稀疏方程组的迭代方法。

科学计算、稀疏矩阵技术和高效预条件子的发展,使预条件共轭梯度法成为大规模数值模拟的核心方法之一。