定常线性迭代法

形式陈述 ​

考虑非奇异线性系统公理库线性方程组System of linear equations可写为矩阵方程 Ax=b 的有限个一次方程系统。 $Ax=b$。选取容易求解且非奇异的 $M$，把

$$A=M-N$$

写成矩阵分裂，并定义

$$x_{k+1}=M^{-1}N{x}_k+M^{-1}b=G{x}_k+c.$$

实现不应显式形成 $M^{-1}$，而是每步解 $M{z}_k=r_k$，再令

$$r_k=b-A{x}_k,x_{k+1}=x_k+z_k.$$

对应的精确残差递推为

$$r_{k+1}=(I-A{M}^{-1})r_k.$$

该式用于分析；实现仍通过求解 $M{z}_k=r_k$ 和矩阵—向量乘法更新，不能为了写出递推而显式形成 $M^{-1}$。

若 $x_{\ast }=A^{-1}b$、$e_k=x_k-x_{\ast }$，精确算术中

$$e_{k+1}=G{e}_k,G=M^{-1}N.$$

因此从任意初值收敛到 $x_{\ast }$ 当且仅当迭代矩阵的谱半径公理库特征值与特征向量Eigenvalue and eigenvector满足 Tv=λv 且 v 非零的标量 λ 与向量 v。满足 $\rho (G)<1$。谱半径不等于任意指定的矩阵范数公理库矩阵范数与诱导算子范数Matrix norm · Induced matrix norm · Operator norm of a matrix用诱导范数和常用可计算矩阵范数度量线性映射的放大能力，并区分算子范数、Frobenius 范数与谱半径。；若某个相容范数有 $\Vert G\Vert <1$，它是方便的充分条件，而不是必要条件。

按 $A=D+L+U$ 分成对角、严格下三角和严格上三角部分，Jacobi 取

$$M_J=D,N_J=-(L+U),$$

即

$$x_{k+1}=D^{-1}(b-(L+U)x_k).$$

它要求所有对角元非零，并允许各分量主要使用旧迭代值并行更新。Gauss–Seidel 取

$$M_{GS}=D+L,N_{GS}=-U,$$

每步通过一次下三角求解立即使用本轮新分量。SOR 引入松弛参数 $\omega$：

$$M_{\omega }=\frac{1}{\omega }D+L,N_{\omega }=(\frac{1}{\omega }-1)D-U.$$

$\omega =1$ 恢复 Gauss–Seidel；最优 $\omega$ 依赖矩阵谱和排序，不能作为跨问题常数。

一次 Jacobi 或 Gauss–Seidel sweep 对稀疏矩阵通常需要 $O(\mathrm{nnz}(A))$ 工作，存储由矩阵和少量向量主导；Gauss–Seidel 的三角依赖会限制并行度。输入应包括 $A,b,x_0$、分裂或方法、容差和迭代上限；输出应包括 $x_k$、真实残差、迭代次数和退出状态。

停止条件可采用

$$\Vert b-A{x}_k\Vert \le \mathrm{atol}+\mathrm{rtol}\Vert b\Vert ,$$

并同时检测非有限值、发散、最大迭代数和残差停滞。相邻迭代差只能在已知收缩因子时转换成误差界；递推或增量残差还应定期由 $b-A{x}_k$ 重算，以免舍入漂移伪造收敛。

直觉 ​

矩阵分裂把难解的 $A$ 拆成一个每步容易处理的骨架 $M$，再把遗漏耦合 $N$ 当作根据当前解反复修正的反馈。Jacobi 同时更新全部坐标，Gauss–Seidel 沿顺序立即传播新信息，SOR 则调节每次修正迈得多远。

固定反馈矩阵 $G$ 决定误差轨道。$\rho (G)<1$ 表示每个特征模式最终衰减；当谱半径接近 $1$ 时，误差虽然收敛，却会保留很久。对角占优和正定性之所以有用，是因为它们在特定分裂下推出谱半径条件，而不是替代这个条件本身。

例子与边界 ​

一维 Poisson 的 $n\times n$ 三对角矩阵

$$A=\mathrm{tridiag}(-1,2,-1)$$

严格正定。按自然排序，Jacobi 迭代矩阵满足

$$\rho (G_J)=\cos \frac{\pi }{n+1},$$

Gauss–Seidel 则有

$$\rho (G_{GS})={\cos }^2\frac{\pi }{n+1}.$$

例如 $n=4$ 时，两者约为 $0.809$ 与 $0.655$；Gauss–Seidel 的渐近衰减更快，但更新依赖也更强。随着 $n$ 增大，两者谱半径都逼近 $1$，说明网格加密会让朴素定常迭代越来越慢。

非零对角元只让 Jacobi 公式可写，不保证收敛。取

$$A=\left(\begin{array}{cc}1& 2\\ 2& 1\end{array}\right),$$

Jacobi 迭代矩阵为

$$G_J=\left(\begin{array}{cc}0& -2\\ -2& 0\end{array}\right),$$

其谱半径为 $2$，一般初值下误差发散。严格行对角占优可保证 Jacobi 与 Gauss–Seidel 收敛；Hermitian 正定保证 Gauss–Seidel 收敛，并使 $0<\omega <2$ 的 SOR 收敛，但正定本身不能无条件保证普通 Jacobi。

即使 $\rho (G)<1$，非正规 $G$ 也可能先出现暂态增长，再进入渐近衰减。只观察头几步残差或只引用谱半径，未必能描述有限迭代预算内的行为；实际历史仍应保存并按问题尺度解释。

推论与应用 ​

定常迭代提供矩阵分裂、残差修正与谱收敛的基础语言。Krylov 方法公理库Krylov 子空间Krylov subspace · Arnoldi iteration · Lanczos iteration从初始向量反复施加矩阵，生成只依赖矩阵—向量乘法的递增子空间及其 Arnoldi、Lanczos 正交基。不再固定使用同一个多项式反馈，而是在逐渐扩大的子空间中选择更合适的残差多项式；许多预条件器则重新使用一次容易求解的 $M$。

方法报告应给分裂、变量排序、谱半径估计或充分条件、每步成本和残差历史。把“Gauss–Seidel 通常更快”或“对角占优所以稳定”写成无上下文结论，会掩盖矩阵结构、排序、并行成本和有限精度停滞。

参考资料

• Richard Barrett et al., Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, 2nd ed., SIAM, 1994, Ch. 2.
• Yousef Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., SIAM, 2003, Ch. 4.
• Gene H. Golub and Charles F. Van Loan, Matrix Computations, 4th ed., Johns Hopkins University Press, 2013, §11.2.