全部文章

数值计算

从 Poisson 方程到最优松弛因子:Jacobi、Gauss-Seidel 与 SOR 的理论和 GPU 实验

从一维 Poisson 方程的离散化出发,解释 Jacobi、Gauss-Seidel 和 SOR 的收敛原理,推导一致排序矩阵的特征值关系与最优松弛因子,并结合 NumPy、PyTorch 和两张 GPU 的实验分析性能。

摘要 我们经常听到“Gauss-Seidel 比 Jacobi 快”“SOR 调大松弛因子就能加速”,但这些判断究竟依赖什么条件?本文从线性方程组的矩阵分裂讲起,以一维 Poisson 方程为主线,推导 Jacobi 和 Gauss-Seidel 的谱半径关系,以及 SOR 的最优松弛因子。随后,使用 NumPy 与 PyTorch 的手写求解器验证收敛理论,并比较 Tesla T10 与 RTX 4090 上的执行性能。最有代表性的结果是:对于 n=20n=20 的一维 Poisson 测试问题,在相同的 10−1010^{-10} 相对残差阈值下,Jacobi 需要 1971 轮,Gauss-Seidel 需要 763 轮,而取理论最优 ω≈1.74058\omega\approx1.74058 的 SOR 只需要 80 轮。

1. 为什么要研究迭代法?

考虑线性方程组

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

一种解法是利用 LU、Cholesky 等分解进行直接求解。对于一般稠密矩阵,分解的计算成本通常为 O(n3)O(n^3)。另一种思路是从初始猜测 x(0)x^{(0)} 出发,不断进行低成本修正,让 x(k)x^{(k)} 接近精确解 x∗x^*。

迭代法的关键不是“每轮算得少”这么简单:一轮有多便宜、需要多少轮、能否并行,三者共同决定实际速度。Jacobi、Gauss-Seidel(以下简称 GS)与逐次超松弛法 SOR,恰好展示了这三者之间的取舍。

本文使用四个手写求解接口(NumPy / PyTorch 各实现 Jacobi 与 GS/SOR),并以 np.linalg.solve、torch.linalg.solve 作为精度和时间的参考。参考求解器允许调用库函数,手写迭代内核不调用直接求解库;用于分析谱半径的代码另行使用特征值计算。

2. 从矩阵分裂理解 Jacobi 与 Gauss-Seidel

2.1 Jacobi:所有分量使用上一轮的值

设 aii≠0a_{ii}\ne0。将第 ii 个方程对 xix_i 求解,得到

xi(k+1)=1aii(bi−∑j≠iaijxj(k)).x_i^{(k+1)}=\frac{1}{a_{ii}}\left(b_i-\sum_{j\ne i}a_{ij}x_j^{(k)}\right).

Jacobi 的特点是:本轮计算的每个 xi(k+1)x_i^{(k+1)} 都只依赖旧向量 x(k)x^{(k)},因此所有分量可以并行更新。

把矩阵分解为

A=D+L+U,A=D+L+U,

其中 DD 为对角部分,LL、UU 分别为严格下三角和严格上三角部分。下文始终采用这个带原始符号的约定,避免与有些教材写作 A=D−L−UA=D-L-U 的记法混淆。

Jacobi 的矩阵形式为

x(k+1)=D−1(b−(L+U)x(k)),x^{(k+1)}=D^{-1}\bigl(b-(L+U)x^{(k)}\bigr),

对应迭代矩阵

TJ=−D−1(L+U).\boxed{T_J=-D^{-1}(L+U)}.

2.2 Gauss-Seidel:立即使用已经更新的分量

GS 按照变量顺序更新:在计算第 ii 个分量时,前面的分量已经是本轮的新值。因此

xi(k+1)=1aii(bi−∑j<iaijxj(k+1)−∑j>iaijxj(k)).x_i^{(k+1)}=\frac{1}{a_{ii}} \left(b_i-\sum_{j<i}a_{ij}x_j^{(k+1)}-\sum_{j>i}a_{ij}x_j^{(k)}\right).

写成矩阵形式,得到

(D+L)x(k+1)=b−Ux(k),(D+L)x^{(k+1)}=b-Ux^{(k)}, TGS=−(D+L)−1U.\boxed{T_{GS}=-(D+L)^{-1}U}.

与 Jacobi 相比,GS 利用了更“新”的信息,却引入了前后分量的依赖。这对 CPU 上的顺序计算通常有利,对大规模 GPU 并行则未必如此。

2.3 统一为残差修正

定义第 kk 轮的残差 r(k)=b−Ax(k)r^{(k)}=b-Ax^{(k)}。三种方法都可以写成

x(k+1)=x(k)+M−1r(k).\boxed{x^{(k+1)}=x^{(k)}+M^{-1}r^{(k)}}.

不同方法只需选取不同的易求解矩阵 MM:

方法MM迭代矩阵 T=I−M−1AT=I-M^{-1}A
JacobiDD−D−1(L+U)-D^{-1}(L+U)
Gauss-SeidelD+LD+L−(D+L)−1U-(D+L)^{-1}U
SORD/ω+LD/\omega+L(D+ωL)−1[(1−ω)D−ωU](D+\omega L)^{-1}\bigl[(1-\omega)D-\omega U\bigr]

注意:这里的 M−1rM^{-1}r 是数学写法,程序里不应该显式构造逆矩阵;对角矩阵用逐元素除法,下三角矩阵用前代或三角求解。

3. 迭代什么时候收敛?谱半径为什么重要?

设 x∗x^* 满足 Ax∗=bAx^*=b,误差 e(k)=x(k)−x∗e^{(k)}=x^{(k)}-x^*。对任意定常迭代 x(k+1)=Tx(k)+cx^{(k+1)}=Tx^{(k)}+c,都有

e(k+1)=Te(k),e(k)=Tke(0).e^{(k+1)}=Te^{(k)},\qquad e^{(k)}=T^k e^{(0)}.

因此,对于所有初值都收敛到唯一解的充要条件是

ρ(T)=max⁡λ∈σ(T)∣λ∣<1.\boxed{\rho(T)=\max_{\lambda\in\sigma(T)}|\lambda|<1}.

直观地说,每个特征方向上的误差会按照相应特征值的幂缩放。若存在模大于 11 的特征值,就可以构造一个沿该方向放大的初始误差;若所有特征值的模都小于 11,则 Tk→0T^k\to0。

较小的谱半径通常对应较快的渐近收敛,但有限轮迭代的表现还受到初始误差在各特征方向上的投影、迭代矩阵的非正规性和停止准则的影响。因此“谱半径平方”不意味着在每个具体算例中迭代次数严格减半。

常见的充分条件包括:严格行对角占优时 Jacobi 与 GS 都收敛;当 AA 对称正定时,GS 收敛,SOR 在 0<ω<20<\omega<2 收敛,但普通 Jacobi 未必收敛。

4. 为什么 Poisson 矩阵是研究迭代法的好例子?

4.1 从微分方程到三对角矩阵

研究一维 Dirichlet 边值问题

−u′′(s)=f(s),0<s<1,u(0)=u(1)=0.-u''(s)=f(s),\quad 0<s<1,\qquad u(0)=u(1)=0.

取 nn 个内部网格点 si=ihs_i=ih,h=1/(n+1)h=1/(n+1)。用中心差分代替二阶导数:

−u′′(si)≈−ui−1+2ui−ui+1h2.-u''(s_i)\approx\frac{-u_{i-1}+2u_i-u_{i+1}}{h^2}.

因此得到

1h2[2−1−12−1⋱⋱⋱−12][u1u2⋮un]=[f1f2⋮fn].\frac1{h^2}\begin{bmatrix} 2&-1&&\\ -1&2&-1&\\ &\ddots&\ddots&\ddots\\ &&-1&2 \end{bmatrix} \begin{bmatrix}u_1\\u_2\\\vdots\\u_n\end{bmatrix} =\begin{bmatrix}f_1\\f_2\\\vdots\\f_n\end{bmatrix}.

若把 h−2h^{-2} 吸收到右端,得到实验中使用的无量纲矩阵

An=2I−diag⁡(1,1)−diag⁡(1,−1).\boxed{A_n=2I-\operatorname{diag}(\mathbf1,1)-\operatorname{diag}(\mathbf1,-1)}.

这是对称正定矩阵。令 v0=vn+1=0v_0=v_{n+1}=0,则

vTAnv=∑i=0n(vi+1−vi)2>0(v≠0).v^\mathsf T A_nv=\sum_{i=0}^{n}(v_{i+1}-v_i)^2>0\qquad(v\ne0).

它还有一个特别适合做理论分析的特点:各行只与相邻的网格点耦合。

4.2 用正弦特征向量求出 Jacobi 的全部特征值

对该矩阵,D=2ID=2I,因而

TJ=I−12An.T_J=I-\frac12A_n.

考虑向量

vj(m)=sin⁡(jmπn+1),j=1,…,n.v_j^{(m)}=\sin\left(\frac{jm\pi}{n+1}\right), \qquad j=1,\ldots,n.

利用三角恒等式

sin⁡((j−1)θ)+sin⁡((j+1)θ)=2cos⁡θsin⁡(jθ),\sin((j-1)\theta)+\sin((j+1)\theta)=2\cos\theta\sin(j\theta),

可以直接验证 v(m)v^{(m)} 是 TJT_J 的特征向量,对应特征值

μm=cos⁡(mπn+1),m=1,…,n.\boxed{\mu_m=\cos\left(\frac{m\pi}{n+1}\right),\quad m=1,\ldots,n}.

于是

ρ(TJ)=cos⁡(πn+1).\boxed{\rho(T_J)=\cos\left(\frac{\pi}{n+1}\right)}.

当 nn 很大时,令 h=1/(n+1)h=1/(n+1),有 cos⁡(πh)=1−12π2h2+O(h4)\cos(\pi h)=1-\frac12\pi^2h^2+O(h^4)。谱半径非常接近 11,说明低频误差衰减很慢。这正是 Poisson 类方程让简单定常迭代陷入大量循环的原因之一。

5. 从 Gauss-Seidel 到 SOR:为什么松弛会有效?

5.1 SOR 并不是简单地在最终结果上做加权平均

先计算当前分量的 GS 建议值 x~i\widetilde{x}_i,再将这一步乘以 ω\omega:

xi(k+1)=(1−ω)xi(k)+ωx~i.\boxed{x_i^{(k+1)}=(1-\omega)x_i^{(k)}+\omega\widetilde{x}_i}.

注意 x~i\widetilde{x}_i 用的是本轮已经更新的 x1,…,xi−1x_1,\ldots,x_{i-1}。这意味着每个分量被依次松弛,而不是在全部分量计算完后统一插值。

  • ω=1\omega=1:标准 GS;
  • 0<ω<10<\omega<1:欠松弛,减小每步幅度;
  • 1<ω<21<\omega<2:超松弛,在该分量的 GS 建议值方向上走得更远。

在 A=D+L+UA=D+L+U 的符号约定下,SOR 等价于

(D+ωL)x(k+1)=ωb+((1−ω)D−ωU)x(k),(D+\omega L)x^{(k+1)}= \omega b+\bigl((1-\omega)D-\omega U\bigr)x^{(k)},

所以

Tω=(D+ωL)−1((1−ω)D−ωU).\boxed{T_\omega=(D+\omega L)^{-1}\bigl((1-\omega)D-\omega U\bigr)}.

5.2 一个几何解释:对称正定系统上的坐标下降

对于对称正定矩阵,解 Ax=bAx=b 等价于最小化严格凸的二次函数

Φ(x)=12xTAx−bTx.\Phi(x)=\frac12x^\mathsf T Ax-b^\mathsf T x.

若只沿第 ii 个坐标方向移动,令 gi=(Ax−b)ig_i=(Ax-b)_i,则

Φ(x+tei)−Φ(x)=tgi+12aiit2.\Phi(x+t e_i)-\Phi(x)=tg_i+\frac12a_{ii}t^2.

GS 选取沿该方向的精确最小点 t∗=−gi/aiit_*=-g_i/a_{ii};SOR 则取 t=ωt∗t=\omega t_*。代入得到

ΔΦ=−ω(2−ω)2aiigi2.\boxed{\Delta\Phi=-\frac{\omega(2-\omega)}{2a_{ii}}g_i^2}.

由于对称正定矩阵满足 aii>0a_{ii}>0,只要 0<ω<20<\omega<2,每次非平凡的分量更新都能使 Φ\Phi 下降。这解释了为什么超松弛的“越过当前坐标最优点”不一定造成整体发散:只要还在适当的范围内,二次函数依然下降。

但是,这还不能证明 ω>1\omega>1 一定比 ω=1\omega=1 快。对于给定矩阵,哪一个 ω\omega 真正最快,需要继续研究迭代矩阵的谱。

5.3 为什么 0<ω<20<\omega<2 是必要范围,而不总是充分条件?

因为 D+ωLD+\omega L、(1−ω)D−ωU(1-\omega)D-\omega U 都是三角矩阵,

det⁡(Tω)=det⁡((1−ω)D−ωU)det⁡(D+ωL)=(1−ω)n.\det(T_\omega)=\frac{\det((1-\omega)D-\omega U)}{\det(D+\omega L)}=(1-\omega)^n.

特征值的乘积等于行列式,所以

ρ(Tω)n≥∣det⁡Tω∣=∣1−ω∣n,\rho(T_\omega)^n\ge|\det T_\omega|=|1-\omega|^n,

即

ρ(Tω)≥∣1−ω∣.\boxed{\rho(T_\omega)\ge|1-\omega|}.

SOR 若收敛,必有 ∣1−ω∣<1|1-\omega|<1,即 0<ω<20<\omega<2。这个条件对一般矩阵只是必要条件;对对称正定矩阵,它才同时成为标准 SOR 的充分条件。

6. 关键证明:从一致排序到最优 ω

下面沿着“Poisson 矩阵 → 一致排序 → 特征方程 → 最优松弛因子”的路线完成证明。关键并不在于记住公式,而在于理解为什么 SOR 的两个非对角系数,可以通过一个 λ\sqrt\lambda 的变量替换,转化为 Jacobi 的谱问题。

6.1 什么叫“一致排序”?

在这里考虑更具体、足以覆盖一维 Poisson 矩阵的性质。对任意非零复数 α\alpha,定义

C(α)=αD−1L+α−1D−1U.C(\alpha)=\alpha D^{-1}L+\alpha^{-1}D^{-1}U.

如果 C(α)C(\alpha) 的特征值集合不随 α\alpha 改变,就具有我们所需的一致排序谱不变性。这在经典一致排序理论中是重要性质;本文只证明一维三对角矩阵的情形,不将其宣称为所有稀疏矩阵的通性。

对于一维 Poisson 矩阵,构造可逆对角矩阵

S(α)=diag⁡(1,α−1,α−2,…,α−(n−1)).S(\alpha)=\operatorname{diag}(1,\alpha^{-1},\alpha^{-2},\ldots,\alpha^{-(n-1)}).

由于 D−1LD^{-1}L 只有下方第一条副对角线、D−1UD^{-1}U 只有上方第一条副对角线,直接逐项检查可得

C(α)=S(α)−1C(1)S(α).\boxed{C(\alpha)=S(\alpha)^{-1}C(1)S(\alpha)}.

这是一个相似变换,因而各个 C(α)C(\alpha) 具有完全相同的特征值。而 TJ=−C(1)T_J=-C(1),所以若 μ\mu 是 Jacobi 的特征值,−μ-\mu 就是任意 C(α)C(\alpha) 的特征值。

这个相似性是后续证明的核心。它让一个表面上依赖 α\alpha 的复杂矩阵变成一个已经理解的 Jacobi 矩阵。

6.2 写出 SOR 的特征方程

令 λ≠0\lambda\ne0 为 TωT_\omega 的特征值。由

det⁡(λI−Tω)=0\det(\lambda I-T_\omega)=0

乘上非奇异的 D+ωLD+\omega L,可得等价条件

det⁡((λ+ω−1)D+λωL+ωU)=0.\det\bigl((\lambda+\omega-1)D+\lambda\omega L+\omega U\bigr)=0.

再左乘 D−1D^{-1},忽略非零的 det⁡D\det D 因子,得到

det⁡[(λ+ω−1)I+λωD−1L+ωD−1U]=0.\det\Bigl[(\lambda+\omega-1)I+\lambda\omega D^{-1}L+\omega D^{-1}U\Bigr]=0.

问题出现了:这里 LL 的系数为 λω\lambda\omega,UU 的系数为 ω\omega,看起来不像 Jacobi 的 D−1(L+U)D^{-1}(L+U)。应该怎样把它们配成 C(α)C(\alpha)?

6.3 为什么偏偏构造 C(λ)C(\sqrt\lambda)?

设想找到两个数 q,αq,\alpha,使

q C(α)=qαD−1L+qα−1D−1Uq\,C(\alpha)=q\alpha D^{-1}L+q\alpha^{-1}D^{-1}U

恰好等于上式中的非对角部分。只需比较系数:

qα=λω,qα−1=ω.q\alpha=\lambda\omega,\qquad q\alpha^{-1}=\omega.

两式相除,立即得到 α2=λ\alpha^2=\lambda;因此可以取

α=λ,q=ωλ.\boxed{\alpha=\sqrt\lambda,\qquad q=\omega\sqrt\lambda}.

原来 λ\sqrt\lambda 并不是凭空猜出来的,而是由两个系数的配比强制决定的。于是特征行列式变为

det⁡[(λ+ω−1)I+ωλ C(λ)]=0.\det\bigl[(\lambda+\omega-1)I+\omega\sqrt\lambda\,C(\sqrt\lambda)\bigr]=0.

利用刚才证明的谱不变性,C(λ)C(\sqrt\lambda) 的特征值就是 −μ-\mu,其中 μ∈σ(TJ)\mu\in\sigma(T_J)。行列式为零意味着对某个这样的 μ\mu,有

λ+ω−1−ωλ μ=0.\lambda+\omega-1-\omega\sqrt\lambda\,\mu=0.

两边平方,得到 Young–SOR 经典的特征值关系

(λ+ω−1)2=ω2λμ2.\boxed{(\lambda+\omega-1)^2=\omega^2\lambda\mu^2}.

这里 λ\lambda 是 SOR 的非零特征值,μ\mu 是 Jacobi 的特征值。平方关系对于求谱半径足够,但处理完整特征值重数时还需考虑 λ=0\lambda=0 等特殊情形。

6.4 令 ω=1\omega=1:为什么 GS 的谱半径恰好是 Jacobi 的平方?

当 ω=1\omega=1,SOR 退化为 GS,特征值关系变成

λ2=λμ2.\lambda^2=\lambda\mu^2.

对非零的 λ\lambda,有 λ=μ2\lambda=\mu^2。因此对于这种一致排序的 Poisson 矩阵,

ρ(TGS)=ρ(TJ)2.\boxed{\rho(T_{GS})=\rho(T_J)^2}.

注意这个等式不是对任意矩阵都成立。本文实验中还有一个 GS 发散而 Jacobi 收敛的反例,恰好提醒我们不能脱离矩阵结构套用这个关系。

6.5 从特征方程推导最优松弛因子

记 ρ=ρ(TJ)\rho=\rho(T_J),在本节 Poisson 情形有 0<ρ<10<\rho<1,且 Jacobi 特征值都是实数。令 t=λt=\sqrt\lambda,特征值方程可写为

t2−ωμt+(ω−1)=0.\boxed{t^2-\omega\mu t+(\omega-1)=0}.

它的判别式是

Δ(μ,ω)=ω2μ2−4(ω−1).\Delta(\mu,\omega)=\omega^2\mu^2-4(\omega-1).

当 ω\omega 从 11 开始增加时,控制最慢收敛的 ∣μ∣=ρ|\mu|=\rho 对应的主导实根不断缩小;但继续增大 ω\omega,两个 tt 根会成为共轭复数。对 Δ<0\Delta<0 的情形,两根乘积为 ω−1\omega-1,故其模均为 ω−1\sqrt{\omega-1},对应 ∣λ∣=ω−1|\lambda|=\omega-1。

因此,最优位置恰好是主导根由实数转为共轭复数的临界点:

ω2ρ2−4(ω−1)=0.\omega^2\rho^2-4(\omega-1)=0.

解二次方程,选取位于 (1,2)(1,2) 内的根,便得到

ωopt=21+1−ρ(TJ)2.\boxed{\omega_{\mathrm{opt}}=\frac{2}{1+\sqrt{1-\rho(T_J)^2}}}.

与此同时,该最优点满足

ρ(Tωopt)=ωopt−1.\boxed{\rho(T_{\omega_{\mathrm{opt}}})=\omega_{\mathrm{opt}}-1}.

从另一角度看,第 5.3 节已经证明 ρ(Tω)≥∣ω−1∣\rho(T_\omega)\ge|\omega-1|:当 ω\omega 超过临界点时,这个不可突破的下界反而随 ω\omega 增大。于是最优值出现在“主导收敛因子下降”和“下界开始主导”之间的交接处。

适用条件非常重要:这一经典公式适用于本文的一维 Poisson 矩阵,以及满足相应一致排序、实 Jacobi 谱等假设的经典问题;它不是任意可逆矩阵、任意 SPD 矩阵的通用最优参数公式。对其他矩阵,往往需要另行估计或搜索 ω\omega。

6.6 Poisson 矩阵的闭式解与渐近意义

我们已经得到

ρ(TJ)=cos⁡(πn+1).\rho(T_J)=\cos\left(\frac\pi{n+1}\right).

因此 1−ρ(TJ)2=sin⁡(π/(n+1))\sqrt{1-\rho(T_J)^2}=\sin\bigl(\pi/(n+1)\bigr),从而

ωopt=21+sin⁡(πn+1).\boxed{\omega_{\mathrm{opt}}=\frac{2}{1+\sin\left(\frac\pi{n+1}\right)}}.

当 n→∞n\to\infty,令 h=1/(n+1)h=1/(n+1),则

ρ(TJ)=1−O(h2),ρ(TGS)=1−O(h2),ρ(Tωopt)=1−O(h).\rho(T_J)=1-O(h^2),\qquad \rho(T_{GS})=1-O(h^2),\qquad \rho(T_{\omega_{\mathrm{opt}}})=1-O(h).

在渐近误差衰减意义下,达到固定比例的误差下降所需的扫描轮数,Jacobi/GS 量级为 O(h−2)O(h^{-2}),最优 SOR 则为 O(h−1)O(h^{-1})。所以 SOR 的价值远不止“比 GS 少几轮”,而是对这类网格问题改善了随网格加密而增长的迭代次数量级。

7. 核心实现:只保留值得分析的代码

原项目包含完整的测试框架、结果类、异常处理、NumPy 与 PyTorch 两套接口。这里仅展示与数学理论、实现复杂度和 GPU 性能最相关的片段。

7.1 Jacobi:避免把矩阵向量乘法写成矩阵乘矩阵

# 核心更新,省略参数检查和停止条件
d = np.diag(A)
for k in range(max_iter):
    dx = (b - A @ x) / d
    x = x + dx

最初容易写出 D_inv @ (D - A) @ x。NumPy 从左到右计算,前两个 n×nn\times n 矩阵相乘,导致每轮出现不必要的 O(n3)O(n^3) 运算。改写成 A @ x 后,更新本身只需一个 O(n2)O(n^2) 的稠密矩阵向量乘法。

需要指出,当前提供的 mt.py 在 stop_criterion='residual' 时,还会在更新后执行一次 b - A @ x 来检查残差,因此它在该模式下实际每轮进行了两次矩阵向量乘法,并非完整循环只做一次。若希望进一步优化,可让相邻轮次复用已经算出的残差,或按一定间隔检查收敛。

7.2 GS/SOR:按顺序更新,同一代码处理 ω=1\omega=1 和 ω≠1\omega\ne1

w_over_d = omega / np.diag(A)
for k in range(max_iter):
    for j in range(len(b)):
        x[j] += w_over_d[j] * (b[j] - A[j] @ x)

这里的 x 原地更新:计算第 j 行时,前面的分量已经改变,这正是 GS/SOR 与 Jacobi 的本质区别。代码与公式等价;当 omega=1 时就是标准 GS。

7.3 PyTorch:将逐分量循环转为下三角求解

在 GPU 上为每个分量单独发起 PyTorch 运算会带来大量小内核调用。代码采用统一残差更新,只把 M−1rM^{-1}r 的计算方式按方法区分:

# Jacobi
inv_d = 1.0 / torch.diagonal(A)
dx = r * inv_d

# GS / SOR
D = torch.diagonal(A)
M = torch.tril(A, diagonal=-1) + torch.diag(D / omega)
dx = torch.linalg.solve_triangular(
    M, r.unsqueeze(1), upper=False
).squeeze(1)

# 统一更新
x.add_(dx)
torch.addmv(b, A, x, alpha=-1.0, out=r)  # r = b - A @ x

这段代码展示的是算法核心,省略了真实实现中的收敛检测、状态冻结及 CUDA Graph 管理。真实代码使用 torch.where 在 GPU 上冻结已经收敛的迭代状态,并每隔若干轮才把误差同步到 CPU。

对于稠密矩阵,两种方法每轮都包含 O(n2)O(n^2) 级别的数值运算。但 Jacobi 的逐元素计算和矩阵向量乘法具有更好的并行性;下三角求解存在前代依赖,即使 GPU 算力很强,也不一定能够像矩阵乘法那样高效展开。

8. 实验设计与环境

实验原始数据来自两台 GPU 机器,统一采用双精度浮点数(float64)、相对残差阈值 10−1010^{-10}、最多 10000 轮。每种方法先预热,再测量 3 次并取最短时间;GPU 测试在计时区间两端执行同步。

机器GPUPyTorch 版本
ATesla T102.7.1+cu118
BNVIDIA GeForce RTX 40902.5.1+cu121

原记录未保存 CPU 型号、BLAS 后端和线程数,因此跨机器的 NumPy 差异只能作为观察,不能直接归因于 GPU。

测试中包括:可手算的 2×22\times2 系统、随机生成的严格对角占优矩阵、n=20n=20 的 Poisson 矩阵、SPD 但 Jacobi 发散的反例,以及 Jacobi 收敛而 GS 发散的反例。随机矩阵和目标解由固定种子生成,右端取 b=Axtrueb=Ax_{\mathrm{true}},以便直接检查解的误差。

需要区分两类结果:第 9 节的 Jacobi/GS 与 GPU 性能数据为原报告已有结果;第 10 节的 SOR 扫描是本次基于同一份 mt.py 和同一 Poisson 用例新增的本地 NumPy 复核。新增 SOR 测试没有声称在两张 GPU 上重新跑过。

9. 原始实验结果:理论能预测收敛,但不能代替计时

9.1 正确性及迭代次数

原报告在两台机器上分别完成了 28/28 项通过测试。对收敛的算例,NumPy 与 PyTorch 解向量的逐元素最大差值不超过约 7×10−157\times10^{-15};各实现的迭代轮数一致。表中的“发散”是测试框架在预设容差、轮数限制和数值异常检查下的实际判定。

测试用例nnρ(TJ)\rho(T_J)ρ(TGS)\rho(T_{GS})Jacobi 轮数GS 轮数
tiny_2x220.2890.0831910
diag_dominant_n50500.1730.065139
poisson1d_n20200.9890.9781971763
spd_jacobi_diverges31.8000.854602(发散)132
gs_diverges30.0002.0003503(发散)
diag_dominant_n5005000.0530.01987
diag_dominant_n20002000未计算未计算76

这里有两件事值得特别注意。

第一,SPD 并不保证 Jacobi 收敛:spd_jacobi_diverges 的 Jacobi 谱半径为 1.81.8,GS 却只有 0.8540.854。第二,“GS 总比 Jacobi 好”也不成立:gs_diverges 恰好反过来,Jacobi 的谱半径为 00,GS 为 22。Poisson 的 ρ(TGS)=ρ(TJ)2\rho(T_{GS})=\rho(T_J)^2 必须放在相应的矩阵结构条件下理解。

Poisson 测试中,ρ(TJ)≈0.98883\rho(T_J)\approx0.98883,ρ(TGS)≈0.97779\rho(T_{GS})\approx0.97779,确实符合平方关系。实测轮数为 1971 与 763,而非恰好 2:1;这是因为实验依据有限轮下的相对残差停止,并非只追踪一个主导特征向量的渐近误差。

9.2 RTX 4090:小问题上的 GPU 固定开销

以下均为原报告记录的毫秒值;J 表示 Jacobi,GS 表示 Gauss-Seidel。

用例NumPy JNumPy GSTorch JTorch GSnp.solvetorch.solve
tiny_2x20.190.1327.027.90.020.16
diag_dominant_n500.161.0428.331.50.090.18
poisson1d_n2013.028.766.557.80.030.14
spd_jacobi_diverges3.401.0934.429.90.020.14
gs_diverges0.044.051.3537.10.010.12
diag_dominant_n5000.346.381.521.816.841.86

在这里,n=500n=500 的 Torch GS 比 NumPy GS 快,但 Torch Jacobi 的 1.52 ms 仍慢于 NumPy Jacobi 的 0.34 ms。因此“GPU 到 n≥500n\ge500 就全面领先”不是从这组数据能够得到的结论。

为什么不少 Torch 迭代用例都需要约 27–37 ms?原实现采用“前 8 轮尚未停止就录制 CUDA Graph”的策略;这些用例包含每次求解时重新录图的成本。对于报告所使用的 PyTorch 2.5.1,torch.cuda.graph 的上下文入口在源码中确实调用了 torch.cuda.synchronize()、gc.collect() 和 torch.cuda.empty_cache()。不过,从计时现象只能判断固定开销显著,不能把全部毫秒差精确归因于其中某一个调用。

9.3 Tesla T10:大规模、快速收敛矩阵上的表现

用例NumPy JNumPy GSTorch JTorch GSnp.solvetorch.solve
tiny_2x20.150.1229.431.80.040.17
diag_dominant_n500.160.8929.935.00.060.53
poisson1d_n2012.326.178.771.90.040.28
spd_jacobi_diverges3.731.1741.434.10.030.19
gs_diverges0.074.182.6844.80.030.17
diag_dominant_n5001.5814.13.122.863.904.48
diag_dominant_n20001.5568.63.215.8345.745.3

n=2000n=2000 的严格对角占优稠密矩阵只需要 6–7 轮收敛。在 Tesla T10 的这组测试里,Torch Jacobi 为 3.21 ms,Torch 直接法为 45.3 ms;但 NumPy Jacobi 甚至只需 1.55 ms。这同时说明两个问题:快速收敛时迭代法可能显著超过直接法;把迭代法搬到 GPU,本身不保证比成熟的 CPU 矩阵向量运算更快。

原始 Markdown 的 RTX 4090、n=2000n=2000 结果仅以未能恢复的嵌入图表示,没有可核实的具体数值,因此本文不重建这组计时或引用其倍数。

9.4 残差小,不代表解的误差同样小

实验中 Poisson 算例的 GS 相对残差约为 9.9×10−119.9\times10^{-11},与库函数参考解的相对误差仍约为 1.25×10−81.25\times10^{-8}。设 r=b−Axr=b-Ax、e=x−x∗e=x-x^*,则 Ae=−rAe=-r,于是

∥e∥2∥x∗∥2≤κ2(A)∥r∥2∥b∥2,\frac{\|e\|_2}{\|x^*\|_2}\le \kappa_2(A)\frac{\|r\|_2}{\|b\|_2},

其中 κ2(A)=∥A∥2∥A−1∥2\kappa_2(A)=\|A\|_2\|A^{-1}\|_2。本例 κ2(A)≈178\kappa_2(A)\approx178,足以解释为什么小残差不能保证同样数量级的前向误差。这个界是误差控制的上界,而非对每次实验的精确等式。

10. 新增复核实验:最优 SOR 到底快多少?

将原始 mt.py 生成的 poisson1d_n20 系统保持不变,使用 gauss_seidel_numpy(..., omega=...) 扫描不同 ω\omega;所有设置沿用 tol=10−10\texttt{tol}=10^{-10}、float64、最多 10000 轮。原文件测试时仅调用默认 ω=1\omega=1,以下是本次新增的验证结果。

对于 n=20n=20,根据第 6 节公式,

ρ(TJ)=cos⁡(π/21)≈0.9888308262,\rho(T_J)=\cos(\pi/21)\approx0.9888308262, ωopt=21+sin⁡(π/21)≈1.7405800107,\boxed{\omega_{\mathrm{opt}}=\frac2{1+\sin(\pi/21)}\approx1.7405800107}, ρ(Tωopt)≈0.7405800107.\rho(T_{\omega_{\mathrm{opt}}})\approx0.7405800107.
方法 / 参数实际迭代轮数说明
Jacobi1971原始实验基线
GS,ω=1\omega=1763原始实验基线;新增复核一致
SOR,ω=1.30\omega=1.30409已有明显加速
SOR,ω=1.50\omega=1.50249继续改善
SOR,ω=1.65\omega=1.65148接近最优区域
SOR,ω=1.74058\omega=1.7405880理论最优参数
SOR,ω=1.75\omega=1.7580离散停止轮数与理论最优并列
SOR,ω=1.80\omega=1.80103超过最优后开始变慢
SOR,ω=1.90\omega=1.90222更大的松弛因子并不更快

按这次测试的停止准则,最优 SOR 的迭代轮数约为 GS 的 1/9.54、Jacobi 的 1/24.64。这并不是对任何右端、任何容差都保证的固定加速比;它是该矩阵、初值和实验停止准则下的测量结果。注意最小谱半径对应的是渐近收敛因子,因此在“整数轮数”这一离散指标上,附近几个 ω\omega 可能出现并列甚至轻微不同的最优值。

Poisson n=20 上的 SOR 理论谱半径与 omega 的关系

图 1:根据一致排序特征值关系计算的 ρ(Tω)\rho(T_\omega)。曲线最低点出现在 ω≈1.74058\omega\approx1.74058;ω\omega 太接近 22 时,谱半径重新逼近 11。

Poisson n=20 上的 SOR 实测迭代次数与 omega 的关系

图 2:调用原始 NumPy SOR 求解器新增复核所得的迭代轮数。图 1 优化的是谱半径,图 2 测的是达到指定残差阈值所需的轮数,两者关联紧密但并不完全相同。

11. 对 GPU 性能的进一步理解

这一轮实验最重要的工程收获,是认识到数学上的收敛速度与计算设备上的吞吐能力属于两套不同指标。

  • 小系统:大部分时间消耗于 Python 调用、主机与设备同步、图录制等固定开销。即使只有十几轮,GPU 求解器也可能耗时数十毫秒。
  • 稠密 Jacobi:主要依赖矩阵向量乘法,算术强度低,矩阵足够大时容易受到显存带宽影响。固定开销没有充分摊薄时,高端 GPU 仍可能输给 CPU。
  • GS/SOR:减少迭代轮数很有价值,但每轮需要下三角求解,计算存在顺序依赖,因此它们比 Jacobi 更难直接映射到大规模 GPU 并行执行。
  • 稀疏 Poisson 系统:实际网格离散得到的是稀疏矩阵,当前使用稠密张量作对比只是实验上的便利。将来应使用 CSR 等稀疏存储,并比较稀疏 Jacobi、红黑排序 GS/SOR,甚至共轭梯度和多重网格方法。

如果重新做正式性能基准,应将初始化、CUDA Graph 录制和图重放分别计时,并记录 CPU、BLAS、GPU、驱动、PyTorch 与线程配置。对于高频重复求解且矩阵形状固定的场景,可考虑复用图;对于只需数轮就收敛的系统,不应轻易在每次求解时重新录制大块 CUDA Graph。

本报告原先也讨论了 P100/V100 与 RTX 4090 的 FP64 性能差异。仅凭理论峰值参数,不能确定这段特定 PyTorch 代码换卡后的实际加速,因此这里不再把未经同条件测试的跨卡推断当作实验结论。

12. 总结:从现象走向理论,再回到实验

这次实验最终回答了三个相互关联的问题。

第一,为什么 GS 经常比 Jacobi 快? 它在一轮内部复用了新值;对于本文的一维 Poisson 矩阵,一致排序性质进一步给出严格的 ρ(TGS)=ρ(TJ)2\rho(T_{GS})=\rho(T_J)^2。但这一等式不适用于任意矩阵,甚至可以存在 Jacobi 收敛而 GS 发散的情况。

第二,为什么 SOR 能更快? 在 SPD 系统上,SOR 的分量更新可被理解为带有超松弛的坐标下降;当 0<ω<20<\omega<2 时,每步仍使相应二次目标下降。更重要的是,在适当的一致排序结构下,松弛因子改变了迭代矩阵的谱。由 λ\lambda、μ\mu 的特征值关系可以推导出一个最优 ω\omega,它让 Poisson 问题的渐近收敛因子从 1−O(h2)1-O(h^2) 改善到 1−O(h)1-O(h)。本例中实际轮数从 GS 的 763 降到 80。

第三,为什么 GPU 不一定更快? 迭代次数、每轮计算量和并行能力必须同时考虑。少轮数、可并行、可复用图的任务适合 GPU;小系统或包含较多顺序依赖的任务,可能受到启动、同步和三角求解的限制。

后续值得扩展的方向是:二维 Poisson 与网格规模扫描、稀疏格式、红黑排序 SOR、不同停止准则、CUDA Graph 复用,以及与共轭梯度和多重网格的对照实验。这样才能把一次迭代法实验继续推进为更完整的数值线性代数求解器研究。


参考资料与复现说明

  1. Oxford Research Software Engineering, Jacobi and Relaxation Methods:矩阵分裂、残差修正与 Poisson 离散示例。
  2. Cornell CS 6210, Matrix Computations — Iterative Methods:定常迭代、GPU 并行性、Poisson 谱及 SOR 分析。
  3. Elmar Klausmeier, Theorem of Stein and Rosenberg:一致排序矩阵的 Young–SOR 特征值关系与最优松弛因子。
  4. PyTorch v2.5.1 torch/cuda/graphs.py 源码:CUDA Graph 上下文的初始化行为。
  5. PyTorch CUDA semantics:CUDA Graph 的使用限制和同步行为。
  6. G. H. Golub & C. F. Van Loan, Matrix Computations;R. S. Varga, Matrix Iterative Analysis:经典矩阵迭代分析参考书目。

原始材料:Jacobi 与 Gauss-Seidel 迭代法实验报告.md 和 mt.py(2026-11-20 提供)。本文中的两台 GPU 计时来自原始报告;SOR 参数扫描与配图为根据 mt.py 新增的本地验证。代码片段经过删减以突出原理,不构成可独立执行的完整脚本。本文未对原报告中的 GPU 测量进行重新跑分。

  • 数值分析
  • 线性代数
  • Poisson
  • Jacobi
  • Gauss-Seidel
  • SOR
  • PyTorch
  • CUDA

继续阅读

拆解三份高阶 Skill:如何把“提示词”写成可落地的工程方法论?