专题进阶 · 数值算法推荐总顺序 · 第 121 / 148 课

用 A-共轭方向解决对称正定系统,区分残差、误差与收敛条件。

先学会这些,再进入本课 Cholesky 分解 梯度下降 矩阵乘法
还有 3 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 数值算法

共轭梯度Conjugate Gradient

利用共轭方向求对称正定系统,适合大规模稀疏矩阵,收敛受条件数影响。

建议 45 分钟 · 含手算、代码与三层练习

本课要建立的能力

用 A-共轭方向解决对称正定系统,区分残差、误差与收敛条件。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

大规模稀疏 Ax=b 不适合保存稠密三角因子。若 A 对称正定,能否只反复计算矩阵乘向量?

02一步步得到方法

线性系统也是二次型最小化

令 φ(x)=½xᵀAx−bᵀx,梯度为 Ax−b,最小点满足 Ax=b。残差 r=b−Ax 是负梯度。普通最速下降会在狭长等高线间来回摆动,共轭梯度选择互相 A-正交的方向 pᵢᵀApⱼ=0。

在方向 p 上精确最小化得到步长 α=(rᵀr)/(pᵀAp)。更新 x+=αp、r−=αAp,再用 β=(r_newᵀr_new)/(r_oldᵀr_old) 构造新方向 p=r_new+βp。

为何适合稀疏系统

核心只需要 Ap、向量加法和内积,可以用稀疏矩阵或隐式线性算子,无需形成逆矩阵。精确算术下至多 n 个独立共轭方向可解 n 维 SPD 系统。

浮点运算会损失正交性,不能承诺实际恰好 n 步收敛。收敛速度受条件数影响,预条件器用于改善问题几何;停止时检查残差范数,达到上限应报告未收敛。

共轭方向让旧进展不被破坏

对 SPD 系统,解 Ax=b 等价于最小化二次能量 ½xᵀAx−bᵀx。普通最速下降沿当前残差前进,CG 构造关于 A 内积互相共轭的方向,避免反复抵消先前方向上的优化。

精确算术下至多 n 步的结论并不表示浮点实现一定刚好 n 步达到任意精度。舍入会破坏共轭性,条件数影响速度,预条件通过改变几何改善收敛而不改变目标解。

03把一个小例子完全算清楚

A=diag(2,3),b=(2,3),x₀=(0,0)。

步骤计算与状态为什么这样做
初始r=p=(2,3),rᵀr=13负梯度
第一步Ap=(4,9),pᵀAp=35,α=13/35沿第一共轭方向
更新残差r=(18/35,−12/35)尚未为零
第二步修正方向后 x≈(1,1)精确算术下两步完成

窄屏可左右滑动表格,阅读完整计算与理由。

本课代码用稠密列表方便手算,算法结构本身只依赖矩阵向量乘。

04为什么这个方法成立

  1. SPD 保证 pᵀAp>0,沿每个非零方向有唯一最小点。
  2. 共轭方向使新方向优化不会破坏此前方向上的最优性。
  3. 精确算术中这些方向逐步扩展 Krylov 子空间,最终覆盖解;浮点时使用残差准则确认。

05把推导翻译成代码

Python · 可独立运行的教学实现

from math import sqrt
def conjugate_gradient(a,b,tol=1e-10,iterations=100):
    n = len(b)
    def dot(x,y): return sum(u*v for u,v in zip(x,y))
    def mv(x): return [dot(row,x) for row in a]
    x,r = [0.0]*n,list(map(float,b))
    p = r.copy(); rr = dot(r,r)
    target = tol*max(1.0,sqrt(dot(b,b)))
    for _ in range(iterations):
        if sqrt(rr) <= target: return x
        ap = mv(p); denominator = dot(p,ap)
        if denominator <= 0: raise ArithmeticError("SPD direction required")
        alpha = rr/denominator
        x = [u+alpha*v for u,v in zip(x,p)]
        r = [u-alpha*v for u,v in zip(r,ap)]
        new_rr = dot(r,r)
        beta = new_rr/rr
        p = [u+beta*v for u,v in zip(r,p)]
        rr = new_rr
    if sqrt(rr) <= target: return x
    raise RuntimeError("residual tolerance not reached")

逐个理解关键决定

p = [u+beta*v for u,v in zip(r,p)]
用新残差加旧方向的适当比例,不是每步重新用残差就结束。
target = tol*max(1.0
把停止阈值与右端尺度联系,明确绝对与相对容差的折中。

06时间、空间与实现范围

每轮一次矩阵向量乘:稠密 O(n²),稀疏可为 O(nnz(A)),总再乘迭代数 K。

除矩阵外只保留常数个 n 维向量,辅助空间 O(n)。本代码没有预条件器,SPD 由调用方保证,非正方向检查不能证明完整 SPD。

07改变条件,检查哪里会出错

残差小就保证解的相对误差同样小

病态 A 可放大残差到解误差,需考虑条件数。

任意非对称矩阵都用 CG

核心共轭与正性证明会失效,需选择适合结构的迭代法。

只因矩阵对称就使用 CG

经典保证还需要正定性;不定或非对称系统应选择适合的迭代法。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

b=0,x₀=0 需要迭代吗?

需要一点提示

初始残差。

查看解析与答案

不需要,直接返回零向量。

练习 2 · 边界与辨析

为什么不显式计算 A⁻¹?

需要一点提示

稀疏性与计算成本。

查看解析与答案

求逆可能产生稠密结果且昂贵,只需 Ap 就能推进迭代。

练习 3 · 变式与迁移

预条件器想改善什么?

需要一点提示

等高线几何与条件数。

查看解析与答案

将系统变成更易收敛的等价形式,减少迭代数,同时自身应用必须便宜并符合 SPD 条件。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Driscoll 与 Braun · Fundamentals of Numerical Computation

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。