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为什么这个方法成立
- SPD 保证 pᵀAp>0,沿每个非零方向有唯一最小点。
- 共轭方向使新方向优化不会破坏此前方向上的最优性。
- 精确算术中这些方向逐步扩展 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从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
b=0,x₀=0 需要迭代吗?
需要一点提示
初始残差。
查看解析与答案
不需要,直接返回零向量。
为什么不显式计算 A⁻¹?
需要一点提示
稀疏性与计算成本。
查看解析与答案
求逆可能产生稠密结果且昂贵,只需 Ap 就能推进迭代。
预条件器想改善什么?
需要一点提示
等高线几何与条件数。
查看解析与答案
将系统变成更易收敛的等价形式,减少迭代数,同时自身应用必须便宜并符合 SPD 条件。
继续深入这个专题
本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。
Driscoll 与 Braun · Fundamentals of Numerical Computation