w wyl123ly 的博客
MD

11-3-迭代方法与预条件

134 KB 2026.10.11 原文件

11-3-迭代方法与预条件

一句话概括

当 是 的稀疏矩阵(每行只有几个非零元)时,直接法的 LU / Cholesky 分解会制造出天文数字的填充(fill-in),内存与时间都不可接受;而迭代法每次只需要一次矩阵-向量乘法,存储与非零元个数成正比。

本篇讲清:Jacobi 迭代(,)、Gauss–Seidel 迭代(用最新算出的分量,收敛快一倍)、谱半径判据 、共轭梯度法(CG)(在 Krylov 子空间里找最优解,对称正定下 步收敛,速率取决于 而不是 )、预条件(把病态问题揉成良态问题,预告并承接 11-2-范数与条件数)、以及幂迭代法求主特征值与 Markov 稳态 / PageRank 的联系。


一、定义

1.1 为什么需要迭代法:稀疏性与填充

设 是 的矩阵。

存储的账:若 ,

  • 稠密存储: 个双精度数,每个 8 字节,共 字节 TB。不可行。
  • 稀疏存储(只存非零元与下标):若每行只有 5 个非零元,共 个数,约 40 MB(含下标约 80 MB)。完全可行。

计算的账与"填充"(fill-in):直接法 在消元过程中会在原本是零的位置产生非零元,这就是填充。二维网格上离散 Poisson 方程的例子最典型:

问题未知量 非零元带宽 带状 Cholesky 时间带状 Cholesky 存储是否可行()
1D 网格( 点)可行
2D 网格()时间 flops,存储 数 GB,勉强
3D 网格() 时存储 数 GB,不可行

关键结论:2D 与 3D 网格上,直接法的存储从 膨胀到 与 ,时间从 膨胀到 与 。 这就是"填充"的代价。

而迭代法(Jacobi、GS、CG)每次迭代只需要一次矩阵-向量乘法,成本 (非零元个数),存储也是 ——完全没有填充。代价是需要多轮迭代,且精度受条件数限制。

一句话记住分工

稠密小矩阵 直接法(LU / Cholesky);大型稀疏矩阵 迭代法(CG / GMRES)+ 预条件。

1.2 定常迭代的一般框架:矩阵分裂

定义 11.3.1(矩阵分裂 splitting) 把 写成

其中 非奇异且"容易求解"( 便宜)。由 得 ,于是构造迭代

即

称为迭代矩阵(iteration matrix)。不同的分裂给出不同的迭代法。

定义 11.3.2(残差与误差) 第 步的残差(residual)与误差(error)分别定义为

其中 是真解。两者由

联系(注意残差小不等于误差小,两者差一个 ,即差一个 因子,见 11-2-范数与条件数)。

误差的递推(这是全部收敛性分析的起点):

定义 11.3.3(定常迭代) 若 与 无关,则称该迭代为定常迭代(stationary iterative method)。Jacobi、Gauss–Seidel、SOR 都是定常的;共轭梯度不是(它的"迭代矩阵"每步都变)。

1.3 Jacobi 迭代

把 按对角、严格下三角、严格上三角拆开:

其中

取分裂 ,,得 ,写成逐分量形式:

迭代矩阵

特点:第 步的每个分量只依赖第 步的全部旧值,因此天然可并行(GPU 友好)。代价是需要同时保存 与 两份向量。

1.4 Gauss–Seidel 迭代

取分裂 ,,得 ,逐分量形式:

唯一的变化:求和 用的是本轮已经算出的新值 。

迭代矩阵

对比项Jacobi 迭代Gauss–Seidel 迭代
分裂
迭代矩阵
第 个分量用到的 全部是旧的 用新的, 用旧的
存储需要两份向量原地更新,一份向量
并行性完全可并行天然串行(可用红黑排序并行)
收敛速度慢快一倍(对 2-循环矩阵,)
收敛条件严格对角占优即可严格对角占优即可;对称正定必收敛
实现复杂度极简稍复杂(有数据依赖)
每步成本

为什么 Gauss–Seidel 常常更快? 直观解释:它每一步把"已知的最新信息"立刻用上,相当于在一轮扫描里推进了两倍的距离。对相容次序(consistently ordered)的矩阵(例如三对角、五点差分),有严格结论

所以 GS 的渐近收敛因子是 Jacobi 的平方,迭代次数约减半(后面的数值例子会精确验证这一点)。

SOR(successive over-relaxation,超松弛) 是 GS 的推广,引入松弛因子 :

退化为 GS。 是收敛的必要条件;对 2D Poisson 问题最优值为

本篇只作介绍,不深入展开。

1.5 收敛性的谱半径判据

定义 11.3.4(谱半径 spectral radius) 设 的(复)特征值为 ,

定理(收敛判据) 定常迭代 对任意初值 都收敛()当且仅当

证明与讨论见 §3.1。收敛时的渐近收敛速率为

即每步误差乘一个约等于 的因子。要达到相对误差 ,大致需要

步。这条式子把"谱半径"与"实用迭代次数"直接连起来: 时每步只赚 位十进制数字,要 8 位数字需要约 步; 时每步赚 位,只要 步。

1.6 Krylov 子空间与共轭梯度法

定义 11.3.5(Krylov 子空间) 给定 与初始残差 ,

定义 11.3.6(共轭梯度法 conjugate gradient, CG) 对对称正定(SPD)的 ,从任意 出发(常用 ),取 ,,然后循环:

关键观察:整个算法只用矩阵-向量乘法 ,不用分解、不用 的元素、不需要 显式存储(只要能算 即可,这叫 matrix-free)。每次迭代成本 。

定义 11.3.7(A-内积与 A-范数) 对 SPD 的 ,定义

这是合法的内积与范数(因为 正定)。CG 的核心性质:

  • 两两 -正交(共轭):()。
  • 在仿射空间 中最小化 -范数误差 。
  • 精确算术下 (至多 步精确收敛)。

1.7 预条件

定义 11.3.8(预条件子 preconditioner) 称为 的预条件子,若

  1. ("近似",使 );
  2. 容易求解( 有简单结构)。

左预条件:解 ,目标是 。

对称预条件(SPD 情形):要求 ,解

这样系数矩阵仍保持对称正定,CG 仍可使用——这就是预条件共轭梯度法(PCG)。

1.8 幂迭代法求主特征值

定义 11.3.9(幂迭代 power iteration) 设 有唯一模最大的特征值 ()。从任意 出发,

则 (主特征向量),并用 Rayleigh 商(6-5-二次型与标准形)估计特征值:

收敛速率是 (若 对称则 的误差按这个比值的平方衰减)。

若需要最小特征值或某个中间特征值,用反幂法:对 做幂迭代,会收敛到最靠近 的特征值对应的特征向量(这正是 QR 算法里"位移"的思想,也是 Google PageRank 求解的核心)。


二、几何直观

2.1 Jacobi / Gauss–Seidel = "轮流让每个方程被满足"

想象 个方程 个未知数。Jacobi 迭代做的事是:

固定其他所有未知量,只调 ,使第 个方程恰好成立。

即

几何图像: 维空间里,这相当于把当前点沿 轴方向垂直投影到第 张超平面上。一轮 Jacobi = 依次对 张超平面各做一次投影(但用的是同一批旧坐标,所以不是严格的序列投影);一轮 Gauss–Seidel = 依次做 次投影,每次都站在上一次投影的结果上(这是严格的"循环投影法",cyclic projection)。

循环投影为什么收敛? 因为超平面的交点是唯一的,而每次投影都让到交点的距离严格减小(除非已经在交点上)。收敛速度取决于超平面之间的夹角:夹角越接近正交,收敛越快;越接近平行(病态),收敛越慢。这就把§2.4 的条件数直觉接了上来。

2.2 收缩映射:误差像等比数列一样缩小

由 , 意味着每一步误差都按 的比例缩小。在二维情形,若 有两个实特征值 ,误差的几何轨迹是"两个方向各自按 缩小"的叠加——在相平面上是一条弯向原点的螺线(若为复特征值则是螺旋线)。

谱半径是"最慢的那个方向"的收缩率,这解释了为什么 才是判据,而不是 : 关心所有方向, 只关心最拖后腿的方向——而最终收敛速度由后者决定。

2.3 共轭梯度:为什么它比最速下降快得多

考虑二次函数

它的梯度是 ,所以解 等价于最小化 。 的等高线是中心在 的椭圆,椭圆的半轴比正是 ——条件数越大,椭圆越扁,像一个狭长的山谷。

  • 最速下降法(steepest descent):每步沿当前负梯度方向 走到谷底。问题是相邻两步的搜索方向正交(),在狭长山谷里这会导致"之字形(zig-zag)横跳":沿着山谷横向来回震荡,纵向推进极慢。收敛速率取决于 :

  • 共轭梯度法:改用一组两两 -正交(共轭)的方向 。-正交的几何含义是:沿 方向走完之后,误差在 方向的分量被彻底清除,而且以后任何一步都不会再把它带回来(因为后续方向与 共轭)。所以在狭长山谷里,CG 沿着"长轴"一次走到底,不需要来回横跳。

收敛速率(见 §3.7):

注意是 而不是 。 这是 CG 的全部价值所在: 时最速下降每步只缩小 (几乎不动),CG 每步缩小 ; 时 CG 仍有 ,而最速下降是 。

方法每步误差缩减因子 时达到 所需步数
最速下降
共轭梯度
Jacobi / GS,通常 与最速下降同量级或更差

预条件的几何图像:既然一切困难都来自椭圆太扁( 大),那就先做一个反向拉伸把椭圆揉圆。取 ,解 : 把 的椭圆"压回"接近圆形,使 。极端情形 时 ,,一步收敛——但那时解 和最原始的问题一样难,没有意义。预条件的艺术就在于在" 足够接近 "与" 足够容易求解"之间取平衡。

2.4 幂迭代:让主特征方向"胜出"

把 按特征向量展开 ,则

几何图像:每乘一次 ,非主方向都被按比例 "压扁"一点,反复相乘之后只剩主方向。归一化只是为了不让数值溢出。这就是"反复拉伸"的几何过程——与 Markov 链中概率分布反复乘以转移矩阵、最终收敛到稳态分布是同一件事(10-2-Markov矩阵与稳态)。


三、性质与定理

3.1 收敛的充要条件:谱半径小于 1

定理 11.3.1 定常迭代 对任意初值 收敛,当且仅当 。

证明:

() 设 。由 Jordan 标准形,存在可逆 使 , 是 Jordan 形,其对角块为 。则

的每个元素形如 。因为 ,而 是 的多项式,指数衰减必然战胜多项式增长,故 ,从而 。

又由 得 ,即 。

() 设迭代对任意初值收敛。取 为 的某个特征向量,特征值 ,则 。要它趋于 必须 。对所有特征值成立即得 。

适用条件: 保证的是渐近收敛;它不告诉你收敛有多快(那是 的大小决定的),也不排除前几步误差短暂增大。此外它只适用于定常迭代——CG 的"迭代矩阵"每步变化,不能用这个判据。

推论 11.3.1(实用充分条件) 若存在某个诱导矩阵范数使 ,则迭代收敛。

证明:(见定理 11.3.2),故 蕴涵 。

注意:这是充分不必要条件。存在 但所有常见诱导范数都 的矩阵,此时迭代仍收敛,只是收敛速度需要一个"预热期"才显现。

3.2 谱半径不超过任何诱导范数

定理 11.3.2 对任意诱导矩阵范数,。

证明:设 ,。则

两边除以 得 ,对所有特征值取最大即得。

适用条件:必须是诱导范数。Frobenius 范数不是诱导范数, 仍成立(因为 Frobenius 范数控制所有元素),但用它做判据会过于保守(11-2-范数与条件数)。

3.3 严格对角占优 ⟹ Jacobi 与 Gauss–Seidel 都收敛

定义 11.3.10(严格对角占优) 若对每个 ,

则称 是严格对角占优(strictly diagonally dominant)的。

定理 11.3.3 若 严格对角占优,则 Jacobi 迭代与 Gauss–Seidel 迭代都收敛。

证明(Jacobi 部分):由 ,其元素为

所以第 行的绝对值之和为

(严格对角占优的定义正是这个不等式)。于是 ,由推论 11.3.1,Jacobi 收敛。

证明(Gauss–Seidel 部分):这一步不能用 Jacobi 那套 的写法—— 不是对称矩阵,其特征值可以是复数。标准做法是 Young 的反证法:把 的特征方程写成 ,即

取 ,则

若 ,则 ,上式给出 ,矛盾。故 。

适用条件:充分不必要。存在非对角占优但收敛的矩阵(例如某些对称正定矩阵),也存在对角占优但收敛很慢的矩阵(对角占优只保证 ,不保证 小)。

这条定理的实用价值:差分法离散椭圆型偏微分方程得到的矩阵通常天然对角占优,所以 Jacobi / GS 在这些问题上一定收敛——开箱即用。

3.4 对称正定 ⟹ Gauss–Seidel 一定收敛

定理 11.3.4 若 对称正定,则 Gauss–Seidel 迭代收敛,即 。

证明(完整的能量论证):设 是 的特征向量,特征值 :。由 得

两边左乘 :

现在利用 对称: 且 。对标量 取转置不变:

于是

因为 正定,;因为 的对角元 (正定的必要条件),。代入 :

分母 分子 ,所以 ,即

对每个特征值成立,故 。

适用条件:只对 Gauss–Seidel 成立。Jacobi 没有这个保证——见下一个定理。

3.5 对称正定 ⟹ Jacobi 收敛?不一定!

定理 11.3.5 设 对称正定。则 当且仅当 也正定。

证明: 是 的特征值, 是对应特征向量:

左乘 :。由于 都正定, 即 。

另一方面, 相似于对称正定矩阵 ,所以它的特征值 全为正实数, 全为实数。于是

对一切特征向量成立,即 正定。

适用条件: 必须对称正定(否则 可能为负,整个论证失效)。

反例(对称正定但 Jacobi 发散):

它的特征值是 与 (二重),全部为正,故 对称正定(,条件数很小!)。

此时 , 的特征值是 与 ,有负特征值,故不正定。于是由定理 11.3.5,Jacobi 发散。直接计算: 的特征值是 与 ,

而由定理 11.3.4,Gauss–Seidel 仍然收敛,实测

这个反例的教学价值

"矩阵对称正定"绝不蕴含"Jacobi 收敛"。 严格对角占优才蕴含 Jacobi 收敛(定理 11.3.3)——而上面这个 恰好不是对角占优的()。这条反例正是易错点第 1 条"未检查收敛条件就迭代"的活证据。

3.6 共轭梯度:A-正交性与最优性

定理 11.3.6(CG 的基本性质) 设 对称正定, 任意。按定义 11.3.6 生成 。则对 :

(a) (-正交 / 共轭);

(b) (残差两两正交);

(c) ;

(d) 在仿射空间 中唯一最小化 。

证明思路:(a)(b)(c) 用归纳法——假设 已共轭,验证 与所有旧方向共轭(需要 的特定取法)。(d) 是 (a)(b) 的直接推论:把误差写成 ,用 -正交性计算 ,对每个 求导置零即得 的唯一最优值,而 CG 的 恰好就是它。

适用条件: 必须对称正定。 对称但不定(有负特征值)时 不是范数,"最小化"无意义,CG 可能崩溃或除零。非对称矩阵请改用 GMRES / BiCGSTAB / QMR。

推论 11.3.6.1(有限终止性) 精确算术下 (至多 步)。

证明:由 (c), 的维数最多 。当 时 已经是整个空间, 在整个空间里最小化 -范数误差,只能是 。

推论 11.3.6.2(提前终止) 若 只落在 的少数几个特征方向张成的子空间里(例如对称问题的 只用到了若干对称模式),CG 会在远少于 步内精确收敛。后面的数值实验里 、 时 CG 只用 15 步,就是这个原因。

3.7 CG 的收敛速率: 的威力

定理 11.3.7 设 对称正定,。则

证明思路:由定理 11.3.6(d),,其中 是满足 的 次多项式(因为 与 正交,)。于是

再把 Chebyshev 多项式 代入 ,用 在区间外的增长估计即得。

适用条件与局限:

  • 这是最坏情形界,实际收敛通常快得多(尤其当特征值成簇分布时)。
  • 它忽略了有限终止性:界永远不会在 时给出 ,而实际 CG 在 精确收敛。
  • 只对对称正定成立。非对称矩阵没有这样的简洁界。
  • 而不是 是 CG 相对最速下降的根本优势,也是预条件的目标:只要把 降低 100 倍, 就降低 10 倍,迭代次数也降低 10 倍。

3.8 预条件降低条件数

定理 11.3.8 设 非奇异, 非奇异。则

证明:对乘积用条件数的次乘性 (P5)(11-2-范数与条件数)。

适用条件:这只是上界,说明"随便选一个 不保证有效"——若 选得差( 很大), 可能比 还大,迭代反而变慢。这正是易错点第 3 条"预条件矩阵选取不当导致更慢"的来源。

选择 的四条实用原则:

  1. 必须容易求逆:解 的成本必须远低于解原问题。对角、三角、带状、多重网格的一步都是候选。
  2. 要"抓大放小":优先匹配 的大特征值与"强耦合"部分,而不是精确匹配小的细节。
  3. 优先保证对称性:SPD 情形下若 不是 SPD,CG 的整套理论失效。用 形式或对称的对角 / 不完全 Cholesky。
  4. 实测迭代次数:不要理论推导,直接跑 20 步看残差下降率。选错 是最常见的性能陷阱。
预条件方法 的取法求逆成本典型迭代次数降低适用场景
对角(Jacobi)预条件 倍通用第一步;消除量纲失衡
块对角 = 块对角部分 倍多物理场耦合、分块结构
不完全 Cholesky(IC), 与 同稀疏结构 前代回代 倍SPD 稀疏矩阵的行业标准
不完全 LU(ILU)同 IC 倍非对称矩阵(配 GMRES)
多重网格(multigrid)在多个网格尺度上做光滑与限制可做到与 无关椭圆型偏微分方程(最优方法)
稀疏近似逆(SPAI)直接逼近 是稀疏乘法 倍并行环境

多重网格为什么"最优"

迭代法(Jacobi/GS)擅长消除高频误差,对低频(光滑)误差几乎无能为力——而低频误差恰好可以在更粗的网格上被"看成"高频。多重网格在粗细网格之间来回转移,让所有频率的误差都以 的因子下降,于是迭代次数与网格规模无关( 增大也不影响)。这是 11 章里唯一能彻底摆脱 依赖的技术,也是求解亿级未知量 PDE 的标准武器。

3.9 幂迭代与 Markov 稳态

定理 11.3.9(幂迭代的收敛速率) 设 可对角化,,且 在 方向的分量 。则

证明思路:由 ,归一化后非主项的系数按 衰减。

适用条件:(严格占优;若 则可能不收敛或只在子空间内旋转),且 (否则主方向根本没被"激发")。若 为负,迭代会在 之间震荡。

与 Markov 链 / PageRank 的联系:设 是随机矩阵(列和为 ,)。由 Perron–Frobenius 定理(10-2-Markov矩阵与稳态), 是最大特征值,对应的特征向量 就是稳态分布。求稳态分布正是对 做幂迭代:

(而且因为 ,不需要归一化也不会溢出——这是幂迭代最"友好"的情形。)

PageRank 的做法完全一致,只是把原始的链接矩阵 换成 Google 矩阵

这个"阻尼(damping)"的作用正是把 压小:原本 的 可能接近 (收敛极慢),加上 之后( 是所有特征向量的公共分量,不影响主特征向量)

于是每步误差至少缩小 ,约 次幂迭代即可收敛。这正是用 控制收敛速率的教科书级应用。


四、计算方法与步骤

4.1 Jacobi 迭代的步骤

  1. 检查 对所有 (若某个 ,先做行列置换)。
  2. 初始化 (常用 ),算 。
  3. 循环:
  4. 用旧的 一次性算出全部新分量(向量化):

  1. ,更新残差。
  2. 检查相对残差 或达到 maxit,否则继续。
  3. 输出 、迭代次数、最终相对残差。

4.2 Gauss–Seidel 迭代的步骤

  1. 同样先检查对角元非零。
  2. 循环:
  3. 对 依次执行

注意这是原地更新: 时括号里用的是刚更新的值。

  1. 检查相对残差与迭代上限。
  2. 输出结果。

不要把 GS 写成 Jacobi

用 numpy 的向量写法很容易写出

```python

x = (b - U @ x - L @ x + D * x) / D # 这是 Jacobi,不是 Gauss-Seidel!

```

因为右边的 x 全都是旧值。Gauss–Seidel 必须逐分量原地更新(或者用 for i in range(n) 显式循环)。这是实现 GS 时最常见的 bug。

4.3 共轭梯度法的步骤(伪代码)

输入:SPD 矩阵 (或一个能算 的函数)、、初值 、容差 。

实现要点:

  1. 每步只保留 四个向量, 额外存储。
  2. 用 时,也可以用数值更稳的 递推;若 因舍入变得极小,直接重启()。
  3. 停止准则用相对残差 ,不要用绝对残差。
  4. 若矩阵病态,加预条件(PCG):把 换成 ,并把内积换成 内积。

4.4 稀疏矩阵的正确存储

  1. 绝对不要用 np.zeros((N, N)) 存 的稀疏矩阵。
  2. 用 scipy.sparse(需要 pip install scipy):
  • csr_matrix / csc_matrix:通用压缩稀疏行 / 列,适合矩阵-向量乘法。
  • scipy.sparse.diags / eye / kron:直接构造带状、张量积矩阵。
  • scipy.sparse.linalg.cg / gmres:内置 Krylov 迭代求解器(支持预条件子 M)。
  • scipy.sparse.linalg.LinearOperator:matrix-free——只提供 matvec 函数即可,连矩阵都不用存。
  1. 稀疏矩阵绝不要做 A.T @ A 或 np.linalg.inv——那会瞬间变成稠密。

4.5 停止准则与"迭代次数 ≠ 精度"

  1. 用相对量:(或除以 )。
  2. 设上限 maxit:迭代法可能不收敛,必须防止死循环。
  3. 理解残差与误差的差别:残差小只说明向后误差小。真实的解误差还乘了一个 (11-2-范数与条件数)。
  4. 不要把 tol 设得比 还小:到了那个量级,继续迭代只是追噪声,残差可能反而停滞或震荡。

五、数值例子:同一个对称正定系统上三种方法的对比

取

第 1 步:精确解与基本量

,

对称正定(,)。特征值:

第 2 步:Jacobi 迭代(手算)

从 出发:

与真解的最大偏差
0
1
2
3
4
5
6

迭代矩阵与谱半径:

第 3 步:Gauss–Seidel 迭代(手算)

(注意 用的是本轮刚算出的 。)

与真解的最大偏差
0
1
2
3
4
5——
6————

迭代矩阵:

验证定理:

第 4 步:共轭梯度法(手算,两步收敛)

是对称正定 矩阵,由推论 11.3.6.1,CG 应在恰好 2 步内精确收敛。逐步验证:

初始化:,,,。

第 1 步:

核验:, ✓

第 2 步:

精确等于真解 ! 两步收敛(),与推论 11.3.6.1 完全一致。

第 5 步:三种方法的误差对比表

迭代步 Jacobi 误差Gauss–Seidel 误差CG 误差
0
1
2(精确)
3
4
5
6
每步缩减因子——

读表要点:

  1. GS 每步的缩减因子 恰好是 Jacobi 的平方,印证 :GS 的迭代次数约为 Jacobi 的一半。
  2. CG 在第 2 步就精确收敛——这不是"收敛快一点",而是质变:Krylov 方法具有有限终止性, 维问题至多 步。
  3. CG 第 1 步的误差()比 Jacobi 第 3 步()还大,说明 CG 的优势来自"A-范数意义下的最优",不是每一步的 -范数误差都单调下降。

五之补一、知识点补强:迭代矩阵、收敛条件与预条件的直觉

为什么要单独补这一节

§一~§四 给了框架、公式与算法,但自学者最容易在三个地方卡住:

1. "迭代矩阵"到底长什么样?为什么说 CG 没有迭代矩阵,却仍然能谈"收敛速度"?

2. 对角占优为什么能保证收敛?§3.3 的 Gauss–Seidel 证明用的是 Young 的反证法,绕;下面给一个可以直接算出收敛因子的初等证明。

3. CG 比最速下降快,快的到底是什么?下面会指出一个反直觉的事实:两者的迭代点落在同一个 Krylov 空间里,差别在"怎么选系数"。

最后把"预条件"从口号变成一张可操作的决策表。

补 3.1 四种方法的迭代矩阵与收敛条件(总表)

把 按 拆开( 对角、 严格下三角、 严格上三角),则

方法分裂 迭代矩阵 收敛条件每步成本并行性
Jacobi;充分:严格对角占优;SPD 不够(需 正定)完全并行
Gauss–Seidel;充分:严格对角占优;SPD 必收敛串行(红黑排序可并行)
SOR() 是必要条件;SPD 时 也充分串行
CG——(非定常)没有固定的 必须对称正定只有矩阵乘法可并行

为什么 CG 没有迭代矩阵? 因为迭代矩阵的前提是" 固定"(定常迭代)。CG 的"有效算子"每步都变:它是在仿射空间 上做正交投影,第 步用的方向 依赖前面所有步。所以 CG 的收敛性不能写成 ,而要写成多项式逼近的形式(§3.7):

这张表最重要的一列是"收敛条件"

三种定常迭代的判据都是 ,但"什么条件能保证 "完全不同:

- Jacobi:严格对角占优 ✅;对称正定 ❌(反例见 §3.5);

- Gauss–Seidel:严格对角占优 ✅;对称正定 ✅(定理 11.3.4);

- SOR: 是必要条件( 越界必发散);SPD 时它也是充分条件。

实操建议:拿到矩阵先算(或估);算不动就先跑 20 步看残差是升还是降。

补 3.2 严格对角占优 收敛:一个能算出收敛因子的初等证明

§3.3 里 Gauss–Seidel 的证明用的是 Young 的反证法(假设 导出矛盾),优点是普适,缺点是不给收敛因子。下面这个证明更初等,而且直接给出每步误差缩小的倍数。

记号:,其中 。

(1)Jacobi 的情形(回顾)

由 立刻得到收敛,且收敛因子就是 。

(2)Gauss–Seidel 的情形(本节的主角)

从 出发,写出第 行:

把对角项单独留在左边:

取绝对值并用三角不等式(注意右边第一项用的是新误差、第二项用的是旧误差):

(因为 且 。)

关键一步:取 使 (最大分量所在的行),则左边就是 。移项:

严格对角占优保证 ,于是可以除过去:

这就证明了 ,从而 ,并且得到了每步误差缩小的倍数 。

(3)"去掉严格两字"会怎样(这是最容易错的地方)

矩阵严格对角占优?上面的界
是
()否(中间行 ,弱对角占优)(判据失效)
(SPD)否(发散)

读表三条:

  1. 第一行是"严格对角占优"的标准情形:两个范数界都 ,证得干净,而且 与实测的 同量级(界不紧但可用)。
  2. 第二行是 1D Poisson 矩阵——它只是弱对角占优,所以 ,范数判据给不出结论;但 、 说明它其实收敛得很好。这证明范数判据是充分不必要的。
  3. 第三行是 §3.5 的 SPD 反例: 而 ——再次说明"谱半径才是判据,范数只是充分条件"(定理 11.3.2:,反过来不成立)。

补 3.3 CG 为什么比最速下降快:同一个 Krylov 空间,不同的取系数方式

这是本篇最值得写清楚的一节,因为网上最常见的解释是错的。常见说法是"最速下降只在梯度方向上走,CG 在 Krylov 空间里走"——这句话不准确。

事实:两者的迭代点落在同一个空间里。

(第一个包含关系来自递推 :每一步都把新的残差 加进张成集合,而 ,归纳可得 。所以最速下降的迭代点也在 Krylov 空间里,只是它落在其中一个特定的方向组合上。)

真正的差别在"怎么选系数":

对比项最速下降(SD)共轭梯度(CG)
每步做什么沿当前残差方向做一维最优(贪心):在整个 上做全局最优:
搜索方向,两两 -正交(共轭)
相邻方向的关系(正交)(共轭)
误差的多项式形式, 由贪心系数决定, 在所有 的 次多项式中最优
收敛速率
有限终止没有保证 步内精确收敛(精确算术)

几何直觉(为什么"正交"会之字形,而"共轭"不会):

二次函数 的等高线是中心在 的椭圆,半轴比为 。 大时椭圆极扁,像一个狭长的山谷。

  • SD 的方向正交:沿 走到谷底,则 ,于是下一步必然横着穿过山谷;而扁山谷里"横向"方向的长度尺度差异巨大,结果就是来回之字形(zig-zag),纵向推进极慢。
  • CG 的方向 -正交:沿 走完之后,误差在 方向的分量被彻底清空,而且以后任何一步都不会再把它带回来(因为后续方向都与 共轭)。所以在扁山谷里,CG 可以沿"长轴"一次走到底,不必回头。

为什么 而不是 ? 因为 CG 的误差界是"在 上做多项式 min-max"(§3.7 的证明思路),而 Chebyshev 多项式在区间外的增长是指数的——指数上的因子正好是 而不是 (Chebyshev 的变量变换 引入了这个平方根)。这是"多项式最优"相对"贪心一维最优"的定量红利。

补 3.4 预条件:把椭圆揉圆,以及什么时候揉不动

预条件的目标只有一个:把 压小。三种形式:

形式解的系统适用注意
左预条件通用(配 GMRES 等) 不对称,CG 用不了
右预条件,通用同样破坏对称性
对称(分裂)预条件()SPD + CG(PCG)必须用这种才能保住 SPD

""到底近似什么? 不是近似元素,而是近似特征值谱——尤其要把 的大特征值匹配住(大特征值对应椭圆的短轴方向,也是误差放大最厉害的方向)。所以预条件的设计原则是"抓大放小":优先消除强耦合、大量级的部分,细节留着让 CG 处理。

常见预条件子与"什么时候没用":

预条件子有效场景无效场景(务必知道)
对角(Jacobi)对角元量级相差大(量纲混杂、尺度失衡)对角元全相等而病态来自非对角耦合,如 1D Poisson():预条件就是恒等变换
块对角 / 块三角块结构多物理场、分块稀疏块本身病态
不完全 Cholesky 与 同稀疏结构SPD 稀疏矩阵的行业标准填充过多时分解成本高
不完全 LU(ILU)非对称(配 GMRES)——
多重网格(一次 V-cycle)多尺度光滑椭圆 PDE,可做到迭代次数与 无关非椭圆问题(对流主导、不定)
稀疏近似逆(SPAI)直接逼近 并行环境构造成本

两条实践铁律

1. 判断预条件是否有效只看一件事:迭代步数有没有下降。 由定理 11.3.8,——如果 自己病态,预条件后的系统可能更难解。

2. 不要用 (那是"完美预条件",但求解 与原问题一样难,等于什么也没做)。scipy 文档说"M should approximate the inverse of A",意思是" 扮演近似 的角色",你要传的是那个容易求逆的 。

预条件之后 CG 的速率怎么变? 把 换成 。降低条件数 倍 迭代次数降低 倍(因为速率含 )。这条"平方根法则"是评估预条件收益的快捷算法(例题 6 的实验里, 从 降到 ,约 倍,步数从 降到 ,约 倍——与 同量级但更保守,因为还需考虑谱分布)。

补 3.5 停止准则:截断误差与舍入误差的平衡点

迭代法的误差有两部分(11-1-数值稳定性与LU §1.3):截断误差(还差多少步才到真解)与舍入误差(每步累积的 级噪声)。前者随步数下降,后者随步数上升,于是存在一个最优停止点:

把 tol 设得比 还小是纯浪费:残差会在那个量级附近停滞甚至随机游走(不是单调下降)。例如 时,——想让残差降到 是徒劳的,此时应该做的是换预条件降低 ,而不是加大 maxit。


五之补二、新增例题(六道)

题目 1(手算数字题):在 Poisson 系统上手算 Jacobi 与 Gauss–Seidel 的前三步

取

(1) 求精确解 。

(2) 从 出发,手算 Jacobi 与 Gauss–Seidel 各前三步,用精确分数表示,并给出每步的最大误差。

(3) 写出 与 ,求它们的谱半径,验证 。

(4) 计算 的 -范数、-范数、Frobenius 范数与 2-范数,解释"用范数判收敛"在这里会发生什么。

第 1 步:精确解

方程组是

由对称性令 ,:第一式给 ,第二式给 。两式相加得 ,代回得 。所以

(与公式 在 、 时的结果一致:,。)

第 2 步:Jacobi 迭代公式与前三步(手算,精确分数)

Jacobi 的逐分量公式是 ,本题具体为

(注意每一行右边全部是旧值。)

第 1 步:,

第 2 步:用 ,

第 3 步:用 ,

第 3 步:Gauss–Seidel 的迭代公式与前三步

GS 的公式是

( 用刚算出的 , 用刚算出的 ——这就是"GS 与 Jacobi 唯一的区别"。)

第 1 步:

第 2 步(用 ):

第 3 步:

第 4 步:两个方法的误差表

最大误差指 。

Jacobi Jacobi Jacobi Jacobi 最大误差GS GS GS GS 最大误差
0
1
2
3

读表要点:

  1. GS 的误差是精确的等比数列:,每步缩小 ——这正是 (下面算出)。
  2. Jacobi 的误差比值在前几步还不稳定:,比值是 ,慢慢逼近 。渐近收敛率要跑若干步才显现(这就是为什么"跑 20 步看趋势"是实用建议)。
  3. 第 1 步时 GS 的误差()比 Jacobi()小,但 GS 的 已经跑到 ——GS"抢跑"了,这也解释了它为什么通常更快。

第 5 步:迭代矩阵与谱半径

Jacobi:

特征方程:。按第一行展开:

所以特征值是 ,

Gauss–Seidel:先算 。,下三角矩阵的逆可以用前代逐列求出:

(验证: 的第一列 乘以这个矩阵的第一列 得 ;第二列为 ✓。)

先别急着读对角元——这里有一个非常容易踩的坑。 的第一列全是 ,看起来"像个三角矩阵",于是有人直接读对角元 并宣布 。这是错的:对角线下方的元素并不只有第 1 列, 位置上的 ,所以 不是三角矩阵,"特征值 = 对角元"的捷径不适用。(另一个独立的反驳:题目 1 第 4 步实测 GS 的误差每步缩小 而不是 ,所以 一定是 。)

老老实实算特征多项式。展开 ,按第一行(或第一列)展开,只剩一个非零项:

括号里 。

所以

这个坑值得单独记一句:判断"能不能直接读对角元"要检查对角线下方(或上方)的所有元素,而不是只看第一列。 的 就在对角线下方,因此它不是三角矩阵。这是本题最值得记住的一个陷阱(它也解释了为什么"一眼看谱半径"在小矩阵上很危险,必须真算特征多项式或交给 np.linalg.eigvals)。

验证定理:

第 6 步: 的四个范数——范数判据的"范数依赖性"

  • -范数(最大行和):行和分别是 ,故 。
  • 1-范数(最大列和):列和分别是 ,故 。
  • Frobenius:四个非零元素都是 ,故 。
  • 2-范数: 对称,所以 。

这张表说明了两件事:

  1. 推论 11.3.1( 收敛)对范数敏感:用 -范数、-范数或 Frobenius 范数判断,得到的是恰好等于 ——判据给不出结论(需要严格小于 );换成 2-范数才得到 ,判据成立。
  2. 但迭代明明收敛():这再次印证"谱半径才是充要判据,范数只是充分条件"。而且顺带说明" 对称时 "是一条很实用的捷径。

题目 2(手算数字题):在同一个系统上手算共轭梯度法的三步(精确收敛)

仍取题目 1 的 (),但右端项换成

从 出发,手算 CG 的全部中间量(),验证:

(1) 第 3 步得到精确解;

(2) 两两 -正交;

(3) 残差 两两正交。

第 1 步:为什么换右端项

若取 ,由对称性 只落在 的两个特征方向张成的子空间里( 的三个特征向量中, 为偶数的那个与 正交),由推论 11.3.6.2,CG 会在少于 步内收敛。要演示" 步精确收敛",就取一个把三个特征方向全部激发的 ,例如 。

第 2 步:初始化

第 3 步:第 1 轮迭代()

核验:, ✓

第 4 步:第 2 轮迭代()

第 5 步:第 3 轮迭代()——精确收敛

残差为零 就是精确解。 直接验证:

第 6 步:验证两条正交性

-正交(共轭),即 ():

残差正交:

第 7 步:本例题的三条结论

  1. CG 在 步内精确收敛(定理 11.3.6 的推论 11.3.6.1),而且每一步的残差范数都严格下降()——这在" 远大于条件数要求"的一般情形下并不成立(CG 的残差范数一般不单调,见 §七 代码示例 (3))。
  2. 三个方向 构成了 -内积下的一组正交基:这正是 3-4-线性无关基与维数 里"基与正交化"的思想在非标准内积 下的版本——CG 实际上是在一边生成 Krylov 向量、一边对它们做 -内积的 Gram–Schmidt 正交化(这就是它和 4-4-标准正交基与Gram-Schmidt 的深层联系)。
  3. 都是精确的分数:CG 的每一步只用到内积与矩阵-向量乘法,没有任何"魔法参数"。

题目 3(手算数字题):用谱半径估算迭代次数,并手算 SOR 的最优松弛因子

取 的 1D Poisson 矩阵 ,,要求相对残差降到 。

(1) 写出 、 的公式并手算数值。

(2) 用 估算 Jacobi 与 GS 各自需要的步数,与实测( 与 )对照。

(3) 手算 SOR 的最优松弛因子 与对应的 ,估算步数,并说明它比 GS 快多少倍。

(4) 与 CG 的 步对比,说明" 相对 (或 )的优势"。

第 1 步:两个谱半径的公式与数值

1D Poisson 矩阵(三对角 Toeplitz)的特征值有显式公式(证明见本篇练习 4):

Jacobi 的迭代矩阵是 ,特征值为 ,于是

由相容次序理论(§1.4 的 ):

(也可以用特征值直接算: 的特征值是 。)

第 2 步:估算步数并与实测对照

每一步能赚到的十进制位数是 :

估算与实测只差不到 ——因为这里的迭代已经跑了几千步,渐近率完全生效。这验证了 §1.5 那条公式的实用性:只要知道 ,不用真的跑程序就能估出迭代次数。

第 3 步:SOR 的最优松弛因子(手算)

对 2D Poisson 类问题(更一般地:对相容次序的矩阵),最优松弛因子的公式是

代入 :

SOR 的谱半径(当 时)有一个漂亮的关系:

对照表:

方法每步赚的十进制位数估算步数实测步数(tol )相对 GS 的加速
Jacobi
Gauss–Seidel(基准)
SOR()
CG——( 速率)(用 的界)

三个读数:

  1. SOR 的威力来自""这个量: 时 ,而 ——每步赚的位数提高了约 倍,步数降到 。这就是为什么 1970 年代 SOR 是 PDE 求解的主力。
  2. SOR 的实测步数()比渐近估算()多 :因为渐近率只在若干步之后才生效,前几十步的收敛因子还没到位。估算公式给的是量级,不是精确值。
  3. CG 只用了 步,远少于估算界给出的 步(界 是最坏情形,且完全没考虑" 只激发了 个特征方向"这个事实,见题目 5)。

第 4 步:为什么 CG 能这么离谱地快

  • 定常迭代的速率由 决定,而 的速度是 ()—— 翻倍,步数变 4 倍( 步)。
  • CG 的速率由 决定,而 ,—— 翻倍,步数变 2 倍( 步)。
  • 本例 :Jacobi 量级(),CG ()。量级上的差别,不是常数因子上的差别。

题目 4(证明题):严格对角占优 Jacobi 与 Gauss–Seidel 收敛(带显式收敛因子)

设 严格对角占优。证明

(1) ,从而 ;

(2) ,其中

从而 ;

(3) 举出弱对角占优(允许等号)时这个证明失效的例子,并说明此时迭代仍可能收敛。

第 1 步:(1) Jacobi 部分

由 ,其第 行的绝对值之和是

(对角元 。)取最大:

最后一个严格不等号正是严格对角占优的定义。由定理 11.3.2()得 ,再由定理 11.3.1 得 Jacobi 收敛。

第 2 步:(2) Gauss–Seidel 部分(误差递推 + 取最大分量)

GS 的误差递推是 。写出第 行:

移项把对角元单独留下:

记 ,用三角不等式与 :

取 使 (这样的 一定存在),则上面这个不等式变成

把第一项移到左边:

由严格对角占优,,所以括号为正,可以除过去:

注意这个 依赖于 (每一步最大分量所在的指标可能不同),所以要对所有 取最坏:

于是 ,且由 与 (只要 )的比较可推出必有 ,从而 ,GS 收敛。

第 3 步:(3) 去掉"严格"会发生什么

取 ()。第 2 行:,,相等,所以它只是弱对角占优。代入 :

也就是说,上述证明只能给出 ,给不出收敛结论(需要 才能断言误差严格下降)。

但迭代其实收敛得很好:由题目 1,、,实测(代码见题目 6) 也远小于 。

这说明:

命题是否成立
严格对角占优 Jacobi / GS 收敛✅(上面证了)
收敛 严格对角占优❌(三对角 Poisson 是反例:弱对角占优却收敛得很好)
弱对角占优 收敛❌(例如 :弱对角占优,但 奇异, 的 ,迭代不收敛)
的某个范数 发散❌(题目 1 里 的 /F 范数都 ,但 ,收敛)

"严格"两个字不能省的理由

严格对角占优的作用是在上式的除法中保证分母严格大于分子()。一旦允许等号, 可能等于 (三对角 Poisson 的中间行就是如此),证明立刻失效——不是"结论错了",而是"这个证明方法不够强"。要证弱对角占优 + 不可约 + 对角元非零(这类矩阵叫不可约对角占优)也收敛,需要更强的工具(如 Perron–Frobenius 理论,10-2-Markov矩阵与稳态)。


题目 5(证明题):若 只有 个互异特征值,则 CG 至多 步精确收敛;并解释最速下降为什么没有这个性质

设 对称正定, 的互异特征值为 ()。证明:

(1) 对任意初值 ,CG 在至多 步内给出精确解(精确算术下);

(2) 最速下降法没有这个性质(构造一个例子);

(3) 用这条结论解释:为什么 1D Poisson 矩阵取 时, 阶问题的 CG 只需 步(而不是 步)。

第 1 步:(1) 的证明(多项式视角)

由定理 11.3.6(d),CG 的第 步误差 满足

(理由: 与 中所有向量 -正交,等价于 与 正交,而"与这些向量正交 + 次数 + "恰好刻画了这族多项式。)并且

现在构造一个次数恰为 、在零点取值为 、在 的所有特征值处取值为 的多项式:

对称正定 可正交对角化 ,特征值全部落在 中,于是

(每个 都是某个 。)因此

(第一个等号是 CG 的最优性:CG 的 在所有候选多项式里最好,所以它的误差不超过我们手写的这个 的误差。)于是 ,即 。

第 2 步:(2) 为什么最速下降没有这条性质

最速下降的误差也能写成 ,但 不是 min-max 最优的,而是由每一步的贪心步长决定的:

即 被强制因式分解成已有因子再乘一个线性因子。这个约束使得"取 "(那个能让误差变零的多项式)通常不是贪心过程能产生出来的。

反例(一个 的极端情形):取

只有 个互异特征值,CG 保证 2 步收敛(事实上与题目 2 同理)。而最速下降:

总位移只有 量级,而真解是 ——最速下降在"之长字形"里反复横跳, 分量的推进速度是每步 ,需要 步才能收敛。(这正是 的含义。)

第 3 步:(3) 为什么 时 CG 只要 步

1D Poisson 矩阵 的特征向量是

在这组基下的系数为

对偶数 ,这个和恰好为 (因为序列关于区间中点反对称:, 为偶数时相邻项相消)。所以 只落在奇数 的特征方向上,激活的特征方向只有 个。

于是由第 1 步的结论(把 理解为"实际被激活的互异特征值个数"):

实测验证(,tol ):

1020304060
的非零特征系数个数
CG 实测步数

逐行完全相等——这条理论不是"上界",在这个例子里就是精确步数。

第 4 步:这条结论的三重意义

  1. 它是"CG 是直接法还是迭代法"这个问题的答案: 步有限终止让 CG 在理论上像直接法,但 步的成本是 ,对 2D 网格与带状直接法同阶;CG 的真正价值在于实际需要的步数远少于 (本例 ,病态时 )。
  2. 它解释了"谱成簇"为什么对 CG 有利:如果 的特征值只聚成 簇(),CG 会在约 步内收敛。这正是预条件的设计目标——不是把每个特征值都搬到 附近,而是把谱"挤成少数几簇"。
  3. 它是 Krylov 子空间维数的直接推论: 的维数不超过 所激活的特征方向个数(3-4-线性无关基与维数 里"维数 = 基的个数"在这里的体现)。"Krylov 子空间什么时候长满整个空间"决定了迭代法什么时候变成直接法。

题目 6(numpy 数值实验):同一个 SPD 系统上五种方法的收敛步数对比

用一段 numpy 代码完成五组实验:(1) 手算例题(题目 1、2)的精确分数验证;(2) 同一个 SPD 系统上 Jacobi / Gauss–Seidel / SOR / CG 的收敛步数表(含解析估算与实测的对照);(3) 最速下降 vs CG;(4) 对角预条件的两种命运(有效 / 无效);(5) 激活的特征方向数与 CG 步数的精确吻合。要求只用 numpy,输出与下面一致。

第 1 步:代码

import numpy as np
from fractions import Fraction as F

def poisson_1d(n):
    return 2.0 * np.eye(n) - np.eye(n, k=1) - np.eye(n, k=-1)

# ================= (1) 3x3 hand example: Jacobi / Gauss-Seidel =================
A3 = poisson_1d(3)
b3 = np.ones(3)
print("A3 =\n", A3, "\nb3 =", b3, "  x* =", np.linalg.solve(A3, b3))

def jacobi_frac(A, b, steps):
    n = len(b)
    A = [[F(int(A[i][j])) for j in range(n)] for i in range(n)]
    b = [F(int(v)) for v in b]
    x = [F(0)] * n
    hist = [x[:]]
    for _ in range(steps):
        x = [ (b[i] - sum(A[i][j] * x[j] for j in range(n) if j != i)) / A[i][i] for i in range(n)]
        hist.append(x[:])
    return hist

def gs_frac(A, b, steps):
    n = len(b)
    A = [[F(int(A[i][j])) for j in range(n)] for i in range(n)]
    b = [F(int(v)) for v in b]
    x = [F(0)] * n
    hist = [x[:]]
    for _ in range(steps):
        for i in range(n):
            x[i] = (b[i] - sum(A[i][j] * x[j] for j in range(n) if j != i)) / A[i][i]
        hist.append(x[:])
    return hist

xs = [F(3, 2), F(2), F(3, 2)]
for name, hist in (("Jacobi", jacobi_frac(A3, b3, 3)), ("Gauss-Seidel", gs_frac(A3, b3, 3))):
    print("-- %s (exact rationals) --" % name)
    for k, xk in enumerate(hist):
        err = max(abs(xk[i] - xs[i]) for i in range(3))
        print("  k=%d  x = [%s]  max|err| = %s = %.6f"
              % (k, ", ".join(str(v) for v in xk), err, float(err)))

D = np.diag(np.diag(A3)); L = np.tril(A3, -1); U = np.triu(A3, 1)
GJ = -np.linalg.solve(D, L + U)
GGS = -np.linalg.solve(D + L, U)
print("G_J =\n", GJ, "\n  eig =", np.linalg.eigvals(GJ), " rho = %.6f  1/sqrt(2) = %.6f"
      % (max(abs(np.linalg.eigvals(GJ))), 1 / np.sqrt(2)))
print("  norms of G_J: 1:%.4f inf:%.4f F:%.4f 2:%.4f"
      % (np.linalg.norm(GJ, 1), np.linalg.norm(GJ, np.inf), np.linalg.norm(GJ, 'fro'), np.linalg.norm(GJ, 2)))
print("G_GS =\n", GGS, "\n  eig =", np.linalg.eigvals(GGS), " rho = %.6f  rho_J^2 = %.6f"
      % (max(abs(np.linalg.eigvals(GGS))), max(abs(np.linalg.eigvals(GJ)))**2))
print("  ||G_GS||_inf = %.6f   cond_2(A3) = %.6f (3+2sqrt2 = %.6f)"
      % (np.linalg.norm(GGS, np.inf), np.linalg.cond(A3), 3 + 2 * np.sqrt(2)))

# ================= (2) CG in exact rationals on the same 3x3 =================
A3i = [[F(int(A3[i][j])) for j in range(3)] for i in range(3)]
x = [F(0)] * 3
r = [F(1), F(0), F(0)]
p = r[:]
rho = sum(v * v for v in r)
for k in range(3):
    q = [sum(A3i[i][j] * p[j] for j in range(3)) for i in range(3)]
    pq = sum(p[i] * q[i] for i in range(3))
    alpha = rho / pq
    x = [x[i] + alpha * p[i] for i in range(3)]
    r = [r[i] - alpha * q[i] for i in range(3)]
    print("k=%d: q=[%s] p^Tq=%s alpha=%s x=[%s] r=[%s]"
          % (k, ", ".join(str(v) for v in q), pq, alpha, ", ".join(str(v) for v in x),
             ", ".join(str(v) for v in r)))
    rho_new = sum(v * v for v in r)
    if k < 2:
        beta = rho_new / rho
        p = [r[i] + beta * p[i] for i in range(3)]
        print("      rho_new=%s beta=%s p=[%s]" % (rho_new, beta, ", ".join(str(v) for v in p)))
    rho = rho_new

# ================= (3) step counts on the same SPD system =================
n = 30
A = poisson_1d(n)
b = np.ones(n)
nrmb = np.linalg.norm(b)

def jacobi(A, b, tol, maxit=200000):
    Dg = np.diag(A); R = A - np.diag(Dg)
    x = np.zeros_like(b)
    for k in range(maxit):
        x = (b - R @ x) / Dg
        if np.linalg.norm(b - A @ x) / nrmb < tol:
            return k + 1
    return maxit

def gauss_seidel(A, b, tol, maxit=200000):
    n = b.size; x = np.zeros(n)
    for k in range(maxit):
        for i in range(n):
            x[i] = (b[i] - A[i, :] @ x + A[i, i] * x[i]) / A[i, i]
        if np.linalg.norm(b - A @ x) / nrmb < tol:
            return k + 1
    return maxit

def sor(A, b, omega, tol, maxit=200000):
    n = b.size; x = np.zeros(n)
    for k in range(maxit):
        for i in range(n):
            x[i] = (1 - omega) * x[i] + omega * (b[i] - A[i, :] @ x + A[i, i] * x[i]) / A[i, i]
        if np.linalg.norm(b - A @ x) / nrmb < tol:
            return k + 1
    return maxit

def cg(A, b, tol, M=None, maxit=100000):
    x = np.zeros_like(b)
    r = b - A @ x
    z = r if M is None else r / M
    p = z.copy(); rho = r @ z
    for k in range(maxit):
        q = A @ p
        alpha = rho / (p @ q)
        x = x + alpha * p
        r = r - alpha * q
        if np.linalg.norm(r) / nrmb < tol:
            return k + 1
        z = r if M is None else r / M
        rho_new = r @ z
        p = z + (rho_new / rho) * p
        rho = rho_new
    return maxit

rho_J = np.cos(np.pi / (n + 1))
omega_opt = 2 / (1 + np.sqrt(1 - rho_J ** 2))
print("\nn = %d Poisson, b = ones, tol = 1e-8" % n)
print("rho_J = %.6f  rho_GS = %.6f (= rho_J^2)  omega_opt = %.6f  rho_SOR = %.6f"
      % (rho_J, rho_J**2, omega_opt, omega_opt - 1))
print("%8s %10s %10s %10s %10s" % ("tol", "Jacobi", "GS", "SOR(w_opt)", "CG"))
for tol in (1e-2, 1e-4, 1e-6, 1e-8):
    print("%8.0e %10d %10d %10d %10d"
          % (tol, jacobi(A, b, tol), gauss_seidel(A, b, tol), sor(A, b, omega_opt, tol), cg(A, b, tol)))
print("CG with diagonal preconditioner:", cg(A, b, 1e-8, M=np.diag(A)), "steps (D = 2I, useless here)")
print("asymptotic estimate  k = d / (-log10 rho):  Jacobi %.1f  GS %.1f  SOR %.1f"
      % (8 / -np.log10(rho_J), 8 / -np.log10(rho_J**2), 8 / -np.log10(omega_opt - 1)))
print("cond_2(A) = %.4f   sqrt(cond) = %.4f" % (np.linalg.cond(A), np.sqrt(np.linalg.cond(A))))

# how many eigenmodes of b are excited -> exact CG step count
w, V = np.linalg.eigh(A)
coef = np.abs(V.T @ b)
print("nonzero eigen-coefficients of b: %d (out of %d)  -> CG steps = %d"
      % (int((coef > 1e-10 * coef.max()).sum()), n, cg(A, b, 1e-10)))

# ================= (4) steepest descent vs CG =================
rng = np.random.default_rng(2026)
nn = 100
Q, _ = np.linalg.qr(rng.standard_normal((nn, nn)))
As = (Q * np.logspace(0, -2, nn)) @ Q.T
As = (As + As.T) / 2
bs = As @ np.ones(nn)
nbs = np.linalg.norm(bs)

def steepest_descent(A, b, tol, maxit=2000000):
    x = np.zeros_like(b)
    r = b - A @ x
    for k in range(maxit):
        Ar = A @ r
        alpha = (r @ r) / (r @ Ar)
        x = x + alpha * r
        r = r - alpha * Ar
        if np.linalg.norm(r) / nbs < tol:
            return k + 1
    return maxit

print("\nsteepest descent vs CG, cond_2(A) = %.4f" % np.linalg.cond(As))
print("%10s %18s %10s" % ("tol", "steepest descent", "CG"))
for tol in (1e-2, 1e-4, 1e-6):
    print("%10.0e %18d %10d" % (tol, steepest_descent(As, bs, tol), cg(As, bs, tol)))

# ================= (5) diagonal preconditioning =================
nn = 40
S = np.diag(np.logspace(0, 3, nn))
Asc = S @ poisson_1d(nn) @ S
bsc = Asc @ np.ones(nn)
nb2 = np.linalg.norm(bsc)

def cg2(A, b, tol, M=None, maxit=200000):
    x = np.zeros_like(b)
    r = b - A @ x
    z = r if M is None else r / M
    p = z.copy(); rho = r @ z
    for k in range(maxit):
        q = A @ p
        alpha = rho / (p @ q)
        x = x + alpha * p
        r = r - alpha * q
        if np.linalg.norm(r) / nb2 < tol:
            return k + 1
        z = r if M is None else r / M
        rho_new = r @ z
        p = z + (rho_new / rho) * p
        rho = rho_new
    return maxit

Dsc = np.diag(Asc)
print("\nbadly scaled SPD: cond_2(A) = %.4e   cond_2(D^-1 A) = %.4e"
      % (np.linalg.cond(Asc), np.linalg.cond(Asc / Dsc[:, None])))
print("CG steps = %d   PCG (diagonal) steps = %d" % (cg2(Asc, bsc, 1e-8), cg2(Asc, bsc, 1e-8, M=Dsc)))

第 2 步:实测输出

A3 =
 [[ 2. -1.  0.]
 [-1.  2. -1.]
 [ 0. -1.  2.]]
b3 = [1. 1. 1.]   x* = [1.5 2.  1.5]
-- Jacobi (exact rationals) --
  k=0  x = [0, 0, 0]  max|err| = 2 = 2.000000
  k=1  x = [1/2, 1/2, 1/2]  max|err| = 3/2 = 1.500000
  k=2  x = [3/4, 1, 3/4]  max|err| = 1 = 1.000000
  k=3  x = [1, 5/4, 1]  max|err| = 3/4 = 0.750000
-- Gauss-Seidel (exact rationals) --
  k=0  x = [0, 0, 0]  max|err| = 2 = 2.000000
  k=1  x = [1/2, 3/4, 7/8]  max|err| = 5/4 = 1.250000
  k=2  x = [7/8, 11/8, 19/16]  max|err| = 5/8 = 0.625000
  k=3  x = [19/16, 27/16, 43/32]  max|err| = 5/16 = 0.312500
G_J =
 [[-0.   0.5 -0. ]
 [ 0.5 -0.   0.5]
 [-0.   0.5 -0. ]]
  eig = [-7.07106781e-01  4.88975180e-17  7.07106781e-01]  rho = 0.707107  1/sqrt(2) = 0.707107
  norms of G_J: 1:1.0000 inf:1.0000 F:1.0000 2:0.7071
G_GS =
 [[-0.     0.5   -0.   ]
 [-0.     0.25   0.5  ]
 [-0.     0.125  0.25 ]]
  eig = [-0.00000000e+00  5.00000000e-01  5.55111512e-17]  rho = 0.500000  rho_J^2 = 0.500000
  ||G_GS||_inf = 0.750000   cond_2(A3) = 5.828427 (3+2sqrt2 = 5.828427)
k=0: q=[2, -1, 0] p^Tq=2 alpha=1/2 x=[1/2, 0, 0] r=[0, 1/2, 0]
      rho_new=1/4 beta=1/4 p=[1/4, 1/2, 0]
k=1: q=[0, 3/4, -1/2] p^Tq=3/8 alpha=2/3 x=[2/3, 1/3, 0] r=[0, 0, 1/3]
      rho_new=1/9 beta=4/9 p=[1/9, 2/9, 1/3]
k=2: q=[0, 0, 4/9] p^Tq=4/27 alpha=3/4 x=[3/4, 1/2, 1/4] r=[0, 0, 0]

n = 30 Poisson, b = ones, tol = 1e-8
rho_J = 0.994869  rho_GS = 0.989765 (= rho_J^2)  omega_opt = 1.816253  rho_SOR = 0.816253
     tol     Jacobi         GS SOR(w_opt)         CG
   1e-02        878        441         41         15
   1e-04       1774        888         66         15
   1e-06       2669       1336         91         15
   1e-08       3564       1783        115         15
CG with diagonal preconditioner: 15 steps (D = 2I, useless here)
asymptotic estimate  k = d / (-log10 rho):  Jacobi 3581.1  GS 1790.5  SOR 90.7
cond_2(A) = 388.8121   sqrt(cond) = 19.7183
nonzero eigen-coefficients of b: 15 (out of 30)  -> CG steps = 15

steepest descent vs CG, cond_2(A) = 100.0000
       tol   steepest descent         CG
     1e-02                 29         11
     1e-04                191         30
     1e-06                395         48

badly scaled SPD: cond_2(A) = 1.7451e+07   cond_2(D^-1 A) = 6.2878e+03
CG steps = 186   PCG (diagonal) steps = 40

第 3 步:从输出里读出的六条结论

  1. 手算与程序逐位吻合:Jacobi 三步 、GS 三步 ,误差 (Jacobi)与 (GS)。
  2. 迭代矩阵与谱半径: 的特征值 、 的特征值 , ✓。注意 的 -范数、-范数、Frobenius 范数全部等于 (判据失效),而 2-范数 (因为 对称,)。
  3. CG 三步精确收敛: 全部是精确分数,。这就是" 步有限终止"的具体样子。
  4. 同一个系统的五方法对照():Jacobi 、GS 、SOR() 、CG 、PCG(对角)。解析估算 与实际只差 (定常法)到 (SOR)。
  5. 特征方向数决定 CG 步数: 只激活 个(偶数 的系数为 )特征方向,CG 恰好 步收敛。理论与实测精确吻合。
  6. 预条件的两种命运:在对角元全相等的 1D Poisson 上,对角预条件是恒等变换( 步,毫无帮助);在量纲失衡的 ( 对角、 跨 量级)上, 从 降到 ,步数从 降到 (快 倍)。"预条件有没有用"完全取决于病态的来源是不是对角的。

复现时注意三件事

1. GS 必须逐分量原地更新:把 x[i] = ... A[i, :] @ x ... 写成向量化的 x = (b - U@x - L@x + D*x)/D 就退化成 Jacobi 了(数值上会得到与 Jacobi 相同的步数,答案却"看起来也对",因为两者收敛到同一个解)。

2. Jacobi / GS 的实测步数依赖 tol 与初值:本实验固定 、相对残差判据。换初值会改变常数因子,但不改变量级。

3. CG 的残差范数一般不单调:本实验中 只激活 个方向,残差下降很"干净";在随机右端项下会看到残差先升后降(§七 代码示例 (3) 的现象)。


六、应用

  1. 偏微分方程数值解(最大宗):有限差分 / 有限元离散 Poisson 方程、热传导、弹性力学,得到的矩阵稀疏、对称正定,标准路径是 CG + 不完全 Cholesky 预条件或多重网格。三维问题规模可达 未知量。
  2. 计算流体力学(CFD):Navier–Stokes 离散后矩阵非对称,用 GMRES / BiCGSTAB + ILU 预条件。
  3. PageRank 与网络分析:对阻尼后的 Google 矩阵做幂迭代, 保证快速收敛(10-2-Markov矩阵与稳态)。
  4. 图像处理:去噪、去模糊、图像修复(inpainting)都归结为大型稀疏线性系统或最小二乘,用 CG / LSQR 求解。
  5. 机器学习与优化:Newton-CG、信赖域方法内部都用 CG 解 Newton 方程 (Hessian 太大,不显式存储,用 Hessian-vector product 实现 matrix-free)。
  6. 电路与网络分析:大规模电阻网络、输电网潮流计算中,迭代法是直接法内存爆掉时的唯一出路。
  7. 特征值问题:结构振动模态、量子化学(Lanczos / Arnoldi)、谱聚类(求图的 Fiedler 向量)都建立在幂迭代与 Krylov 子空间方法之上。
  8. 推荐系统与矩阵补全:交替最小二乘(ALS)内部的每一步子问题都是大型稀疏最小二乘,用 CG 或 LSQR 求解。

七、可运行代码示例

依赖

第 (1)(2)(3)(4) 段只用 numpy。第 (5) 段用到 scipy.sparse,已在代码块前注明 pip install scipy。

(1) 手写 Jacobi / Gauss–Seidel / CG,并与 np.linalg.solve 对比

本段定义三个迭代函数,后面第 (2)(3) 段会复用它们,请先运行本段。

import numpy as np

def poisson_1d(n):
    """一维 Poisson 矩阵 T_n = tridiag(-1, 2, -1):对称、正定、严格对角占优。"""
    return 2.0 * np.eye(n) - np.eye(n, k=1) - np.eye(n, k=-1)

def jacobi(A, b, x0=None, tol=1e-10, maxit=100000):
    """Jacobi 迭代:x_new = (b - offdiag(A) x) / diag(A)"""
    n = b.size
    D = np.diag(A)
    if np.any(D == 0):
        raise ValueError("对角元有 0,Jacobi 迭代无法启动")
    R = A - np.diag(D)                 # 非对角部分
    x = np.zeros(n) if x0 is None else x0.astype(float).copy()
    nb = np.linalg.norm(b)
    for k in range(maxit):
        x = (b - R @ x) / D            # 只用旧值,完全向量化
        rr = np.linalg.norm(b - A @ x) / nb
        if rr < tol:
            return x, k + 1, rr
    return x, maxit, rr

def gauss_seidel(A, b, x0=None, tol=1e-10, maxit=100000):
    """Gauss-Seidel 迭代:逐分量原地更新,j<i 用新值,j>i 用旧值。"""
    A = np.asarray(A, float)
    b = np.asarray(b, float)
    n = b.size
    x = np.zeros(n) if x0 is None else x0.astype(float).copy()
    nb = np.linalg.norm(b)
    for k in range(maxit):
        for i in range(n):
            # A[i,:] @ x 用的是"当前"的 x(前半已更新,后半还是旧值)
            x[i] = (b[i] - A[i, :] @ x + A[i, i] * x[i]) / A[i, i]
        rr = np.linalg.norm(b - A @ x) / nb
        if rr < tol:
            return x, k + 1, rr
    return x, maxit, rr

def cg(A, b, x0=None, tol=1e-10, maxit=None):
    """共轭梯度法(要求 A 对称正定)。"""
    n = b.size
    maxit = 10 * n if maxit is None else maxit
    x = np.zeros(n) if x0 is None else x0.astype(float).copy()
    r = b - A @ x
    p = r.copy()
    rho = r @ r
    nb = np.linalg.norm(b)
    hist = []
    for k in range(maxit):
        q = A @ p                      # 每步唯一的一次矩阵-向量乘法
        pq = p @ q
        if pq <= 0:
            raise ValueError("p^T A p <= 0:A 不是对称正定的")
        alpha = rho / pq
        x = x + alpha * p
        r = r - alpha * q
        rr = np.linalg.norm(r) / nb
        hist.append(rr)
        if rr < tol:
            return x, k + 1, rr, hist
        rho_new = r @ r
        p = r + (rho_new / rho) * p
        rho = rho_new
    return x, maxit, rr, hist

# ---------------- 2x2 手算例题的程序验证 ----------------
A2 = np.array([[4.0, -1.0], [-1.0, 3.0]])
b2 = np.array([1.0, 2.0])
x_true = np.linalg.solve(A2, b2)
print("真解 =", x_true, "  应为 [5/11, 9/11] =", np.array([5/11, 9/11]))
print("kappa_2(A) =", np.linalg.cond(A2))

for name, fn in (("Jacobi", jacobi), ("Gauss-Seidel", gauss_seidel)):
    print("\n--- %s ---" % name)
    for k in (2, 4, 6):
        # 用 maxit=k 只跑 k 步,看误差
        xk, _, _ = fn(A2, b2, tol=0.0, maxit=k)
        print("  k=%d  x=%s  误差(inf)=%.6e" % (k, np.round(xk, 6), np.abs(xk - x_true).max()))

print("\n--- CG ---")
for k in (1, 2):
    xk, _, _, _ = cg(A2, b2, tol=0.0, maxit=k)
    print("  k=%d  x=%s  误差(inf)=%.6e" % (k, np.round(xk, 10), np.abs(xk - x_true).max()))

(2) 迭代次数对比:Jacobi vs Gauss–Seidel vs CG

import numpy as np
# 接续第 (1) 段:沿用其中定义的 jacobi / gauss_seidel / cg 与 poisson_1d

def spectral_radius_jacobi(A):
    D = np.diag(A)
    G = np.eye(A.shape[0]) - A / D[:, None]
    return np.abs(np.linalg.eigvals(G)).max()

def spectral_radius_gs(A):
    G = -np.linalg.solve(np.tril(A), np.triu(A, 1))
    return np.abs(np.linalg.eigvals(G)).max()

print("%5s %10s %10s %10s %8s %8s %8s" %
      ("n", "cond", "rho_J", "rho_GS", "Jac", "GS", "CG"))
for n in (10, 20, 30, 50):
    A = poisson_1d(n)
    b = np.ones(n)
    _, kj, _ = jacobi(A, b, tol=1e-8, maxit=200000)
    _, kg, _ = gauss_seidel(A, b, tol=1e-8, maxit=200000)
    _, kc, _, _ = cg(A, b, tol=1e-8)
    rJ, rG = spectral_radius_jacobi(A), spectral_radius_gs(A)
    print("%5d %10.2f %10.6f %10.6f %8d %8d %8d" % (n, np.linalg.cond(A), rJ, rG, kj, kg, kc))
# 预期:rho_GS ≈ rho_J^2,GS 迭代次数约为 Jacobi 的一半,CG 只需 O(n/2) 步(b 对称)

(3) CG 的残差不是单调下降的(一个容易误解的现象)

import numpy as np

def poisson_1d(n):
    return 2.0 * np.eye(n) - np.eye(n, k=1) - np.eye(n, k=-1)

n = 30
A = poisson_1d(n)
b = np.ones(n)
x_true = np.linalg.solve(A, b)
x = np.zeros(n)
r = b - A @ x
p = r.copy()
rho = r @ r
nb = np.linalg.norm(b)

print("CG 的相对残差 ||r_k||/||b||(前 12 步):")
print("  初始相对残差 = %.4f" % (np.linalg.norm(r) / nb))
for k in range(12):
    q = A @ p
    alpha = rho / (p @ q)
    x = x + alpha * p
    r = r - alpha * q
    print("  k=%2d  rel_res = %.4e   ||e_k||_2 = %.4e"
          % (k, np.linalg.norm(r) / nb, np.linalg.norm(x - x_true)))
    rho_new = r @ r
    p = r + (rho_new / rho) * p
    rho = rho_new
print("注意:第 0 步的相对残差从 1 跳到 3.74 —— CG 最小化的是 A-范数误差,")
print("      残差的 2-范数并不保证单调下降,看到上升不要以为算法坏了。")

(4) 幂迭代法求主特征值 ── 与 Markov 稳态的同一件事

import numpy as np

# 一个 3 状态 Markov 链的转移矩阵(列和为 1,列随机;注意不是双随机的)
P = np.array([[0.8, 0.3, 0.0],
              [0.2, 0.5, 0.4],
              [0.0, 0.2, 0.6]])
print("列和 =", P.sum(axis=0), " <- 应为 [1,1,1]")
print("行和 =", P.sum(axis=1), " <- 不等于 1,说明稳态分布不是均匀分布")

def power_iteration(M, x0=None, tol=1e-14, maxit=10000):
    n = M.shape[0]
    x = np.ones(n) / n if x0 is None else x0 / np.linalg.norm(x0)
    lam_old = 0.0
    for k in range(maxit):
        y = M @ x
        x = y / np.linalg.norm(y)
        lam = x @ (M @ x)                       # Rayleigh 商
        if abs(lam - lam_old) < tol:
            return x, lam, k + 1
        lam_old = lam
    return x, lam, maxit

v, lam, it = power_iteration(P)                # 列随机的 Markov 矩阵:稳态满足 P x = x
print("\n幂迭代:主特征值 lambda_1 = %.12f(应为 1),用了 %d 步" % (lam, it))
print("主特征向量(稳态分布) =", v / v.sum())

# 与 numpy 直接求特征值对照
w, V = np.linalg.eig(P)
i = int(np.argmax(w.real))
stationary = (V[:, i] / V[:, i].sum()).real
print("numpy eig 给出的稳态分布  =", stationary)
print("两种方法之差 = %.3e" % np.linalg.norm(v / v.sum() - stationary))

# 次主特征值决定收敛速率
mods = np.sort(np.abs(w))[::-1]
print("\n次主特征值之比 |lambda_2|/|lambda_1| = %.4f  -> 每步误差缩减这个比例" % (mods[1] / mods[0]))

(5) 稀疏矩阵为什么必须用稀疏存储(本示例需要 scipy:pip install scipy)

import numpy as np
from scipy.sparse import diags
from scipy.sparse.linalg import cg as sp_cg

# ---- 存储对比:一百万个未知量 ----
n_big = 1_000_000
print("稠密存储 %d x %d = %.1f TB(不可行)" % (n_big, n_big, n_big * n_big * 8 / 1024**4))
main_big = 2.0 * np.ones(n_big)
off_big = -1.0 * np.ones(n_big - 1)
A_big = diags([off_big, main_big, off_big], [-1, 0, 1], format="csr")
print("稀疏存储:非零元 %d 个,占用 %.1f MB"
      % (A_big.nnz, (A_big.data.nbytes + A_big.indices.nbytes + A_big.indptr.nbytes) / 1024**2))
y = A_big @ np.ones(n_big)                       # 一次矩阵-向量乘法,O(nnz)
print("A @ ones 的前 3 个分量 =", y[:3], "(边界为 1,内部为 0)")

# ---- 在同类问题上真正求解(规模取小一点以便观察收敛) ----
n = 1000
main = 2.0 * np.ones(n)
off = -1.0 * np.ones(n - 1)
A = diags([off, main, off], [-1, 0, 1], format="csr")
b = np.ones(n)
x, info = sp_cg(A, b, rtol=1e-8, maxiter=5000)
print("\nn=%d:scipy.sparse.linalg.cg 退出码 info = %d(0 表示达到 rtol)" % (n, info))
print("相对残差 = %.3e" % (np.linalg.norm(b - A @ x) / np.linalg.norm(b)))
x_true = np.arange(1, n + 1) * (n + 1 - np.arange(1, n + 1)) / 2.0   # T_n^{-1} 1 的解析解
print("与解析解 x_i = i(n+1-i)/2 的最大偏差 = %.3e" % np.abs(x - x_true).max())
print("提示:无预条件时 1D Poisson 的 CG 需要 O(n) 步;")
print("      真正的大规模计算必须加不完全 Cholesky 或多重网格预条件。")

八、易错点

四个高频错误

1. 未检查收敛条件就迭代。 Jacobi / Gauss–Seidel 不是无条件收敛的。判据是 ,实用充分条件是严格对角占优(此时两者都收敛)。特别提醒:

- "对称正定"只保证 Gauss–Seidel 收敛,不保证 Jacobi 收敛。 反例: 对称正定(),但 ,Jacobi 发散(§3.5)。

- CG 要求对称正定。非对称矩阵必须改用 GMRES / BiCGSTAB,否则可能立刻崩溃(代码里 p @ (A @ p) <= 0 就是信号)。

- 实操建议:跑迭代之前先算一次 (小矩阵直接 eigvals)或先跑 20 步看残差是升是降,别等到 10000 步之后才发现不收敛。

2. 把"迭代次数"与"精度"混淆。 迭代次数不是精度指标。真实的解误差满足

所以残差降到 不等于解准确到 :若 ,实际只有 。反过来,把 tol 设得比 还小是浪费时间——继续迭代只是在追舍入噪声,残差会停滞甚至在 附近随机游走。正确的停止准则是

3. 预条件矩阵选取不当导致更慢。 预条件不是"加了就一定快"。由定理 11.3.8, —— 若 本身病态(例如对角元量级相差 倍却直接取 ), 可能比 还大。判断标准只有一个:实测迭代次数。选 之后跑 20 步,如果残差下降速率不如无预条件,就换一个。

4. 稀疏矩阵误用稠密存储。 把 的稀疏矩阵写成 np.zeros((n,n)) 会直接吃掉 8 TB 内存。更隐蔽的错误包括:

- 用稠密写法做稀疏运算:A.T @ A(瞬间变稠密,非零元从 变成 );

- 用 np.linalg.inv / np.linalg.cholesky 处理稀疏矩阵;

- 对稀疏矩阵逐元素循环(Python 循环比稀疏 BLAS 慢几百倍);

- 忘记 scipy.sparse 的矩阵-向量乘法要用 A @ x(csr_matrix 支持)或用 LinearOperator 做 matrix-free。

补充两个实现层面的坑:

  • 把 Gauss–Seidel 写成了 Jacobi。 用 numpy 向量化时,x = (b - U @ x - L @ x + D * x) / D 右边的 x 全是旧值——那还是 Jacobi。GS 必须逐分量原地更新(见 §4.2 的伪代码与代码示例)。
  • CG 的残差范数不是单调下降的。 CG 最小化的是 -范数误差 ,而 完全可能先升后降(代码示例 (3) 里第一步相对残差从 跳到 )。看到残差上升不要慌,也不要据此判断"CG 坏了"。

九、练习题

练习 1(基础) 设

(1) 写出 Jacobi 与 Gauss–Seidel 的逐分量迭代公式。

(2) 从 出发,手算两种方法各 3 步,并给出每步与真解的最大偏差。

(3) 分别求 、 与它们的谱半径,验证 。

(4) 是否严格对角占优? 是否对称正定?这两个结论能否保证 (1) 中的两种迭代都收敛?

练习 2(基础) 判断正误并说明理由:

(1) 若 对称正定,则 Jacobi 迭代一定收敛。

(2) 若 严格对角占优,则 Jacobi 与 Gauss–Seidel 都收敛。

(3) 迭代法的迭代次数越多,解的精度一定越高。

(4) 共轭梯度法在精确算术下最多 步收敛,所以它是"直接法"。

(5) 预条件一定能让迭代法更快。

练习 3(进阶) 设 (本篇 §3.5 的反例)。

(1) 求 的全部特征值,验证 对称正定,并求 。

(2) 求 与 的谱半径,验证 Jacobi 发散而 Gauss–Seidel 收敛。

(3) 取 ,从 出发,用程序跑 Jacobi 与 Gauss–Seidel 各 30 步,记录并对比相对残差 ,画出(或打印)两条曲线。

(4) 说明为什么"对称正定"这个条件对 Gauss–Seidel 足够,对 Jacobi 不够。

练习 4(进阶) 对 (1D Poisson 矩阵):

(1) 证明 的特征值为 ,,并求 。

(2) 证明 与 。

(3) 由此说明:要达到固定的相对精度,Jacobi 与 GS 的迭代次数是 ,而 CG 是 。(提示:CG 的速率因子是 ,而 。)

练习 5(思考) 设 对称正定,考虑预条件 (对角预条件)。

(1) 证明 与对称正定矩阵 相似,因此 的特征值全为正实数。

(2) 证明 ,并说明对角预条件为什么能消除"量纲失衡"造成的病态。

(3) 举一个例子说明:若 的对角元量级相差极大,对角预条件效果显著;但若 对角元相同而病态来自非对角耦合(例如 1D Poisson 矩阵,),则对角预条件几乎是恒等变换、毫无帮助。这个例子说明了预条件设计的什么原则?


十、常见问题 FAQ

Q1:既然 CG 最多 步就收敛,为什么不直接跑 步当直接法用?

两个原因。(a)精度:CG 理论上的有限终止性依赖精确算术。在浮点下,收敛所需的步数通常在 量级(通常远小于 ),但若强行跑到 步,后期的搜索方向会因舍入而失去共轭性,残差反而停滞甚至上升。(b)成本: 步 CG 的成本是 。对 2D 网格()这是 ,与带状直接法同阶——没有任何优势。CG 的价值在于实际上只需要远少于 步就能达到工程精度,尤其是在有预条件的时候。

Q2:什么时候该用直接法,什么时候该用迭代法?

判断顺序:

  1. 矩阵稠密且 :直接法(LU / Cholesky)。稳定、可预测、一次分解可复用多个右端项。
  2. 矩阵稀疏、有多个右端项:直接法仍可能更好(分解一次,回代 每次)。
  3. 矩阵稀疏且很大()或来自 2D/3D PDE 离散:迭代法(CG / GMRES)+ 预条件。
  4. 矩阵只以"能算 "的形式存在(matrix-free):只能迭代法。
  5. 需要高精度(接近机器精度):直接法更可靠;迭代法在 大时很难把残差压到 。

经验法则:先试直接法,若内存或时间不可接受(通常因为填充)再换迭代法。

Q3:scipy.sparse.linalg.cg 的 M 参数到底怎么用?为什么文档说 M 应该近似 的逆?

scipy 的约定是:M 是预条件子,cg 每次迭代会解一次 (数学上是左预条件 )。所以你要传的 M 是那个"容易求逆、且近似 "的矩阵——不是 本身。文档之所以说"should approximate the inverse of A",是因为从效果上看, 扮演的是"近似 "的角色。最简单的用法:M = scipy.sparse.linalg.spilu(A).solve(不完全 LU)或 M = scipy.sparse.diags(1.0 / A.diagonal())(对角预条件,传的是逆对角)。判断是否有效,只看迭代次数有没有下降。

Q4:幂迭代法为什么和 PageRank 是同一件事?

三个层次上它们是同一件事:(a)算法相同: 就是幂迭代,只不过因为 所以不需要归一化(不会溢出)。(b)数学对象相同:稳态分布 就是 的模最大特征值对应的特征向量(10-2-Markov矩阵与稳态)。(c)收敛速率相同:都由 决定,这正是 PageRank 引入阻尼因子 的目的——把 压到不超过 ,从而保证 步内收敛。工程上 PageRank 还会用" dangling node 处理"与稀疏矩阵乘法把单步成本压到 ,但数学内核就是幂迭代。


本篇小结

一、核心结论(十二句话)

  1. 分工原则:稠密小矩阵()用直接法(LU / Cholesky);大型稀疏矩阵(,来自 2D/3D 网格)必须用迭代法。原因是填充:2D 网格上带状 Cholesky 的存储从 涨到 、时间涨到 ;3D 更糟。迭代法每步只要一次矩阵-向量乘法,成本 ,没有任何填充。
  2. 定常迭代的统一框架:把 分裂成 ,迭代就是 ,即 ,;误差满足 。这就是全部收敛性分析的起点。
  3. 收敛的充要条件是 (谱半径),(某个诱导范数)只是充分条件。 恒成立,反之不成立——存在 但所有常见范数都 的矩阵(本篇 的 /F 范数都恰好 ,而 )。
  4. 迭代次数的估算公式:( = 想达到的十进制位数)。( 的 Poisson)时每步只赚 位,要 8 位数字就得 3581 步——实测 3564 步,误差不到 。
  5. 三种定常方法的迭代矩阵与充分条件:(严格对角占优 ✅,对称正定 ❌);(严格对角占优 ✅,对称正定 ✅);( 是必要条件,SPD 时也充分)。对相容次序的矩阵有 ,所以 GS 的迭代次数约为 Jacobi 的一半。
  6. 严格对角占优 的显式收敛因子:,且 ,。"严格"两字不能省:弱对角占优时 可能 ,判据失效(但迭代仍可能收敛,例如三对角 Poisson 矩阵)。
  7. 共轭梯度法:要求 对称正定;每步只需一次矩阵-向量乘法;方向 两两 -正交; 在 上最小化 -范数误差;精确算术下 步精确收敛,而且实际步数 所激活的互异特征方向数( 时 Poisson 矩阵只激活 个方向,实测步数恰好 )。
  8. CG 的速率取决于 :,而最速下降是 。 时要达到 ,最速下降约 步,CG 约 步。这就是"降低条件数 100 倍 迭代次数降低 10 倍"的平方根法则。
  9. CG 比最速下降快的真正原因(最常见的误解在这里):两者的迭代点落在同一个 Krylov 空间 里。差别在系数的选法——最速下降做的是逐步贪心的一维最优(相邻方向正交 在扁椭圆里之字形横跳),CG 做的是整个子空间上的全局最优(方向共轭 沿长轴一次走到底)。数学上表现为"多项式 是否 min-max 最优"。
  10. 预条件:找一个 且 易解(对角、三角、多重网格一步)的算子,解 ,目标是 。SPD 情形必须用对称形式 才能保住 CG(PCG)。判断标准只有一条:实测迭代步数。 由定理 11.3.8,—— 选得差会让问题更难。
  11. 对角预条件只治"对角失衡":在量纲混杂的矩阵上( 从 降到 )步数从 186 降到 40;在 1D Poisson 上()它就是恒等变换,15 步还是 15 步,毫无帮助。"病在哪就预条件哪"是设计预条件的第一原则。
  12. 停止准则要平衡两类误差:截断误差随步数下降,舍入误差随步数累积,所以 。把 tol 设得比 更小是纯浪费(残差会停滞甚至随机游走);正确的做法是换更好的预条件把 降下来。

二、易混概念对照表

容易混淆的一对区别要点一句话判别
残差 vs 误差 二者差一个 ,即差一个 因子残差 + 实际误差
迭代次数 vs 精度次数不是精度指标;精度受 与舍入限制想更准先降 ,而不是加 maxit
Jacobi vs Gauss–Seidel唯一区别:GS 的 项用本轮新值向量化写法 x = (b-U@x-L@x+D*x)/D 是 Jacobi,不是 GS
vs 前者是充要判据,后者只是充分条件(且依赖范数选择)范数 不等于发散,去算 eigvals
严格对角占优 vs 弱对角占优严格 Jacobi/GS 都收敛;弱则没有任何保证三对角 Poisson 只是"弱",却收敛得很好
"SPD 收敛"对 GS 成立;对 Jacobi 不成立(需 正定)反例 : 发散
CG 的" 步有限终止" vs 实际步数前者是精确算术下的最坏保证;实际常远小于 ( 或"激活方向数")能跑 步当直接法吗?不能——成本 没有优势
最速下降 vs CG迭代点同在一个 Krylov 空间;差别在"贪心一维最优" vs "全局 -范数最优"方向正交 ⟹ 之字形;方向共轭 ⟹ 一次走到底
迭代矩阵(定常) vs Krylov 框架(非定常)CG 没有固定的 ,不能用 判据非对称问题要 GMRES/BiCGSTAB,不是"把 CG 硬套上去"
预条件的 vs 传的 必须容易求逆且近似 ; 等于没做scipy 文档的"approximate the inverse of A"说的是 的角色
左预条件 vs 对称预条件左预条件破坏对称性(CG 不能用);SPD 要用 PCG 里 必须 SPD
对角预条件"有效" vs "无效"有效:对角元量级失衡;无效:对角元全相等(如 Poisson 的 )先看 A.diagonal() 的量级跨度
稀疏存储 vs 稠密存储稀疏用 csr_matrix/diags/LinearOperator;稠密写法会吃掉 TB 级内存稀疏矩阵上做 A.T@A 或 inv = 自杀
幂迭代的 vs 收敛速率由 决定,PageRank 的阻尼就是为了压低它 每步至少缩小

三、动手清单(学完这一篇应该能独立完成)

  1. 对一个小矩阵写出 、,用特征多项式手算 ,并判断收敛性。
  2. 手算 Jacobi 与 GS 的前三步(用分数),验证 GS 每步误差缩小 。
  3. 用 估算迭代次数,并与程序实测对照。
  4. 手算 SOR 的最优 与 ,说明它相对 GS 的加速比。
  5. 手算一次 CG 的全部中间量(),验证 -正交性与有限终止。
  6. 判断一个具体问题该用哪种预条件(提示:先看病态来自对角失衡还是非对角耦合)。

这一篇与后面几篇的接口

- 谱半径与 Jordan 形的代数基础在 6-2-矩阵的对角化:定常迭代收敛性证明()用的正是"Jordan 块的幂按 衰减",可对角化时更简单()。

- Gauss–Seidel 的几何图像(循环投影到超平面)在 4-2-投影与投影矩阵 里有完整的投影矩阵理论:一轮 GS 就是依次向 个超平面做投影,收敛速度取决于超平面之间的夹角。

- Krylov 子空间的维数由 3-4-线性无关基与维数 提供语言:CG 的有限终止性就是" 的维数最多 ,到 时已长满整个空间";而" 只激活 个特征方向"则是"子空间维数提前饱和"。

- -内积 是 1-2-长度与点积 里内积公理的非标准例子(只有 正定它才是内积),CG 的正交性都是在这个内积下说的。

- 稀疏矩阵从哪里来:10-1-图与网络 里图的关联矩阵、Laplacian 矩阵都是稀疏的,消元顺序(填充)与图的排序密切相关;红黑排序让 GS 可并行也是图着色问题。

- 预条件与协方差结构:在统计与机器学习里(12-2-协方差矩阵),协方差矩阵的条件数决定迭代求解的难度,"标准化 + 白化"本质就是对角预条件。


相关笔记

  • 11-1-数值稳定性与LU:迭代法的每一步都会累积舍入误差,理解"向后误差"才能正确设置停止准则。
  • 11-2-范数与条件数:迭代次数与误差放大都由 决定;预条件的目标就是把 降下来;CG 的速率取决于 。
  • 10-2-Markov矩阵与稳态:幂迭代求稳态分布、Perron–Frobenius 定理与 PageRank 阻尼因子的完整背景。
  • 6-4-对称矩阵与正定矩阵:CG 与 Cholesky 都要求对称正定;正定的等价条件与判定方法。
  • 6-5-二次型与标准形:Rayleigh 商是幂迭代估计特征值与 CG 证明 的共同工具。
  • 7-1-SVD的构造与几何意义:Krylov 子空间、奇异值与条件数的几何图像。
  • 附录-矩阵分解总览:直接法(LU / Cholesky / QR)与迭代法(Krylov)的定位对比。
  • 6-2-矩阵的对角化:谱半径、Jordan 形与 的代数依据。本篇定理 11.3.1( 收敛)的证明就建立在"Jordan 块的幂按 衰减"之上; 可对角化时证明可以简化成 。
  • 4-2-投影与投影矩阵:投影矩阵 的理论。Gauss–Seidel 的几何解释是"依次向 张超平面做投影",收敛速度取决于超平面之间的夹角;而一轮 Jacobi 相当于"用同一批旧坐标同时投影"。
  • 3-4-线性无关基与维数:维数与基的语言。CG 的有限终止性(推论 11.3.6.1)本质上是" 的维数 ,到 时已长满 ";" 只激活 个特征方向"则是子空间维数提前饱和。
  • 1-2-长度与点积:内积公理。CG 用的 -内积 是标准内积的推广(只有 正定它才满足内积公理),-正交与普通的正交在这里是同一套语言换了内积。
  • 10-1-图与网络:稀疏矩阵的来源与图的排序。图的关联矩阵、Laplacian 矩阵天然稀疏,消元产生的"填充"与图的顶点排序直接相关(这正是 11-1-数值稳定性与LU 提到稀疏 LU 要重排的原因);红黑排序让 Gauss–Seidel 可并行则是图着色问题。
  • 12-2-协方差矩阵:协方差矩阵的对称正定性与条件数。统计与机器学习里的迭代求解(如交替最小二乘、高斯过程)都要求解大型 SPD 系统,而"特征标准化 / 白化"本质上就是对角预条件。

参考来源

  • MIT OpenCourseWare 18.335J Introduction to Numerical Methods(Steven G. Johnson):稀疏矩阵迭代法、Krylov 子空间方法、预条件与多重网格 —— https://ocw.mit.edu/courses/18-335j-introduction-to-numerical-methods-spring-2019/
  • MIT OpenCourseWare 18.06 Linear Algebra(Gilbert Strang):迭代法与 Krylov 方法的课堂视角、特征值与稳态分布 —— https://ocw.mit.edu/courses/18-06-linear-algebra-spring-2010/
  • SciPy 官方文档 scipy.sparse.linalg.cg(CG 要求 对称正定、收敛判据 norm(b - A @ x) <= max(rtol*norm(b), atol)、 为预条件子且"应近似 的逆"、"有效预条件可显著改善收敛速率") —— https://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.linalg.cg.html
  • numpy 官方文档 numpy.linalg.cholesky(对称正定矩阵的 分解,先解 再解 ) —— https://numpy.org/doc/stable/reference/generated/numpy.linalg.cholesky.html
  • numpy 官方文档 numpy.linalg.solve(作为对比用的"真值"求解器,LAPACK _gesv) —— https://numpy.org/doc/stable/reference/generated/numpy.linalg.solve.html
  • 教材(文字来源):Gilbert Strang, Introduction to Linear Algebra, 5th ed., Wellesley–Cambridge Press, 2016, §11.3–11.4(迭代法与 Krylov 方法);Gene H. Golub & Charles F. Van Loan, Matrix Computations, 4th ed., Johns Hopkins University Press, 2013, 第 10 章(定常迭代法)、第 11 章(Krylov 子空间方法);Yousef Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., SIAM, 2003(预条件技术与多重网格);David M. Young, Iterative Solution of Large Linear Systems, Academic Press, 1971(SOR 与 的相容次序理论);Lloyd N. Trefethen & David Bau, Numerical Linear Algebra, SIAM, 1997, Lecture 32–40(CG 与预条件)