高斯—赛德尔迭代法

高斯—赛德尔迭代法（Gauss–Seidel iteration）按指定顺序逐个解线性方程，并立刻使用本轮已经更新的分量。它与 Jacobi 的区别是新旧信息的使用次序，因而迭代矩阵、并行方式及收敛速度都不同。改变未知量的排列，也可能改变实际表现。

一轮中立即使用新值

对 $4x+y=1$、$2x+3y=2$，先更新 $x$，再使用新值更新 $y$： $$x^{k+1}=\frac{1-y^k}{4},y^{k+1}=\frac{2-2x^{k+1}}{3}.$$ 从零开始，第一轮为 $(1/4,1/2)$，第二轮为 $(1/8,7/12)$，第三轮为 $(5/48,43/72)$。代入首式到次式，还能消去 $x$ 得到 $$y^{k+1}=\frac{1}{2}+\frac{1}{6}{y}^k.$$ 固定点为 $3/5$，所以 $y^{k+1}-3/5=(y^k-3/5)/6$，每轮该分量误差缩小为六分之一。对应 $x_{\ast }=1/10$。这个速度是本例的精确结论，不能据此宣称 GS 对所有矩阵都比 Jacobi 快。

从同一零初值开始；本例GS顺序使用新值后收敛更快。图中误差以精确解(0.1,0.6)核对，纵轴为十进制对数。

三角分裂与谱条件

写 $A=D+L+U$，对角元非零。使用新下三角分量和旧上三角分量给出 $$(D+L)x^{k+1}=b-U{x}^k,B_{GS}=-(D+L{)}^{-1}U.$$ 实际每轮是前代入，不需要形成逆矩阵。若 $A$ 可逆，误差满足 $e^{k+1}=B_{GS}{e}^k$；从所有初值收敛的充要条件仍为 $\rho (B_{GS})<1$。严格行对角占优和对称正定分别是常见充分条件，但证明路径不同。

按更新顺序证明收缩

定义 Sassenfeld 数 $${\beta }_i=\frac{\sum _{j<i}|A_{ij}|{\beta }_j+\sum _{j>i}|A_{ij}|}{|A_{ii}|},q=\underset{i}{max}{\beta }_i.$$ 若 $q<1$，就可直接证明全轮最大范数收缩。设旧误差最大值为 $E$。首分量只读取旧的其他分量，所以新误差不超过 ${\beta }_{1}E$。假设此前各新分量都不超过相应 ${\beta }_{j}E$，第 $i$ 行给出 $$|e_i^{new}|\le \frac{\sum _{j<i}|A_{ij}|{\beta }_{j}E+\sum _{j>i}|A_{ij}|E}{|A_{ii}|}={\beta }_{i}E.$$ 归纳到最后一行即得 $\Vert e^{new}{\Vert }_{\mathrm{\infty }}\le qE$，因此重复迭代几何收敛。严格行对角占优时，逐项归纳也给 ${\beta }_i<1$，所以它包含在这个充分条件内。

主例 ${\beta }_1=1/4$、${\beta }_2=1/6$，可取 $q=1/4$。它控制两个分量的全轮最大误差，因而比只看 $y$ 的六分之一略保守。收缩证明也指出了顺序的作用：更换行列排列后，需要重新计算这些系数。

对称正定问题的能量解释

当 $A$ 对称正定时，GS 相当于逐坐标最小化 $\varphi (x)=x^{T}Ax/2-b^{T}x$。其他坐标固定后，对第 $i$ 坐标求导为 $(Ax-b{)}_i$，令其为零就得到 GS 更新。一次坐标位移 ${\delta }_i$ 使能量下降 $A_{ii}{\delta }_i^2/2$。

能量有下界，因此所有坐标位移的平方和有限，位移趋零；正定性使能量的有界水平集紧，迭代有聚点。沿收敛子列及一整轮趋零的坐标位移，各行的坐标极小条件在极限上都成立，得到 $Ax=b$。唯一性迫使所有聚点相同，故迭代收敛。这给出不依赖严格对角占优的另一份证明，但不适用于任意非对称矩阵。

有解变式取对角系统 $2x=2,5y=10$，一轮得到 $(1,2)$。反例取 $x+2y=3,2x+y=3$，仍从零开始：一轮为 $(3,-3)$，下一轮为 $(9,-15)$，并不收敛。方程有唯一解与某个迭代分裂收敛，是两件不同的事。

可运行的顺序更新

代码限定严格行对角占优的有限矩阵，保证所述收敛条件。返回近似和轮数，不修改原矩阵或右端；每轮新建旧状态快照，使“新下三角、旧上三角”一目了然。稠密每轮 $O(n^2)$ 时间和 $O(n)$ 向量存储，稀疏时可按非零元计算。

Python 3

import math


def gauss_seidel(A, b, tol=1e-12, maxiter=1000):
    A, b = [list(map(float, row)) for row in A], list(map(float, b)); n = len(b)
    if not n or len(A) != n or any(len(row) != n for row in A):
        raise ValueError("square matrix matching b required")
    if not all(math.isfinite(v) for row in A for v in row) or not all(math.isfinite(v) for v in b):
        raise ValueError("finite data required")
    if any(abs(A[i][i]) <= sum(abs(A[i][j]) for j in range(n) if j != i) for i in range(n)):
        raise ValueError("this interface requires strict row diagonal dominance")
    if not math.isfinite(tol) or tol <= 0 or not isinstance(maxiter, int) or maxiter < 0:
        raise ValueError("positive tolerance and nonnegative integer limit required")
    x = [0.0]*n; target = tol*max(1.0, max(map(abs, b)))
    for k in range(maxiter+1):
        residual = [b[i]-sum(a*v for a, v in zip(A[i], x)) for i in range(n)]
        if max(map(abs, residual)) <= target:
            return x, k
        if k == maxiter:
            break
        old = x[:]
        for i in range(n):
            lower = sum(A[i][j]*x[j] for j in range(i))
            upper = sum(A[i][j]*old[j] for j in range(i+1, n))
            x[i] = (b[i]-lower-upper)/A[i][i]
            if not math.isfinite(x[i]):
                raise ArithmeticError("nonfinite sequential iterate")
    raise RuntimeError("true residual did not reach tolerance")


print(gauss_seidel([[4, 1], [2, 3]], [1, 2]))  # near ([0.1, 0.6], iteration count)

多色 GS 可将互不直接耦合的未知量分组并行，块 GS 则每次解一组变量；二者改变更新单元和顺序。它们常用于多重网格法平滑和预条件，仍需与具体矩阵结构配合。