定常线性迭代法 | Codeboy's Blog

形式陈述

考虑非奇异线性系统 $Ax=b$ 。选取容易求解且非奇异的 $M$ ，把

A=M-N

写成矩阵分裂，并定义一个待按序列收敛判定的迭代序列

x_{k+1}=M^{-1}Nx_k+M^{-1}b =Gx_k+c.

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

r_k=b-Ax_k,\qquad x_{k+1}=x_k+z_k.

对应的精确残差递推为

r_{k+1}=(I-AM^{-1})r_k.

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

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

e_{k+1}=Ge_k,\qquad G=M^{-1}N.

因此从任意初值收敛到 $x_*$ 当且仅当迭代矩阵的谱半径满足 $\rho(G)<1$ 。谱半径不等于任意指定的矩阵范数；若某个相容范数有 $\|G\|<1$ ，它是方便的充分条件，而不是必要条件。

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

M_J=D,\qquad N_J=-(L+U),

即

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

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

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

每步通过一次下三角求解立即使用本轮新分量。SOR 引入非零松弛参数 $\omega$ （并仍要求 $M_\omega$ 非奇异）：

M_\omega=\frac1\omega D+L,\qquad N_\omega=\left(\frac1\omega-1\right)D-U.

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

采用逐行稀疏表示时，若实际保存 $s$ 个条目（包括显式零和重复坐标），一次 Jacobi 或 Gauss–Seidel sweep 需要 $O(n+s)$ 工作，其中 $n$ 项计入完整向量的处理，存储由矩阵和少量向量主导；Gauss–Seidel 的三角依赖会限制并行度。输入应包括 $A,b,x_0$ 、分裂或方法、容差和迭代上限；输出应包括 $x_k$ 、真实残差、迭代次数和退出状态。

停止条件可采用

\|b-Ax_k\| \le \mathrm{atol}+\mathrm{rtol}\,\|b\|,

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

直觉

固定矩阵分裂依次计算残差、解出校正并重复逼近线性系统固定点 — 定常迭代的残差校正回环

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

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

例子与边界

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

A=\operatorname{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=\begin{pmatrix}1&2\\2&1\end{pmatrix},

Jacobi 迭代矩阵为

G_J=\begin{pmatrix}0&-2\\-2&0\end{pmatrix},

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

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

推论与应用

迭代是否应停止由残差、误差估计与停止准则连接：残差 rk=b−Axk 可直接计算，但只有结合 A^{-1} 或条件数的控制才能把它转成误差界。固定迭代次数与小残差都不是普适的前向精度证书。

定常迭代提供矩阵分裂、残差修正与谱收敛的基础语言。Krylov 方法不再固定使用同一个多项式反馈，而是在逐渐扩大的子空间中选择更合适的残差多项式；许多预条件器则重新使用一次容易求解的 $M$ 。

多重网格平滑性质把谱分析进一步按频段拆开：一维 Poisson 上的加权 Jacobi 可以快速压低高频误差，而低频因子仍接近一。因此一个单独求解时很慢的定常迭代，仍能与粗空间校正互补。

方法报告应给分裂、变量排序、谱半径估计或充分条件、每步成本和残差历史。把“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.

形式陈述 ​

反向链接

形式陈述