2.4.2–2.4.4 Jacobi、Gauss–Seidel 与 SOR

对应教材 2.4.2–2.4.4、定理 2.10–2.21、例 6–11、习题 15–24；对应老师第 5 讲 §四–§五、第 6 讲 §二–§八。 三种方法都是分裂 $A=N-P$ 的特例：拆法即名字。

2.4.2 Jacobi 迭代

取 $A=L+D+U$（$L$ 严格下三角、$D$ 对角、$U$ 严格上三角），$N=D$、$P=-(L+U)$，则 $$G_J=-D^{-1}(L+U), \qquad x_i^{(k+1)}=\frac{1}{a_{ii}}\left(b_i-\sum_{j\ne i}a_{ij}x_j^{(k)}\right).$$ Jacobi 用上一步的全部旧值，可并行；每步一次矩阵-向量乘（或按行算）。

定理 2.10：Jacobi 迭代收敛的充要条件是 $\rho(G_J)\lt1$。

定理 2.11：若 $\lVert G_J\rVert\lt1$（某种范数），则 Jacobi 迭代收敛。

引理 2.1：若 $A$ 是主对角线按行（或按列）严格占优阵，即 $$|a_{ii}|\gt\sum_{j\ne i}|a_{ij}|\quad(\forall i),$$ 则 $A$ 非奇异。

证明要点：反设 $A\boldsymbol x=0$ 有 $\boldsymbol x\ne0$，取 $|x_k|=\max_i|x_i|\gt0$，由第 $k$ 个方程 $$|a_{kk}||x_k|=\left|\sum_{j\ne k}a_{kj}x_j\right|\le\sum_{j\ne k}|a_{kj}||x_k| \lt|a_{kk}||x_k|,$$ 矛盾。$\blacksquare$

定理 2.12：若 $A$ 按行（或按列）严格对角占优，则 Jacobi 迭代收敛。

证明要点：由引理 2.1，$D$ 可逆；反设 $\rho(G_J)\ge1$，取特征值 $\mu$、$|\mu|\ge1$，则 $\det(\mu I-G_J)=0$。把 $\mu I-G_J$ 写成 $\mu D^{-1}[D+\mu^{-1}(L+U)]$，其行列式为零意味着 $D+\mu^{-1}(L+U)$ 奇异；但 $|\mu^{-1}|\le1$ 使该矩阵仍严格对角占优，矛盾。$\blacksquare$

例 6（教材 2.4.2，Jacobi 收敛）：方程组 $$\begin{cases} 10x_1-2x_2-2x_3=1,\ -2x_1+10x_2-x_3=0.5,\ -x_1-2x_2+3x_3=1. \end{cases}$$ 系数矩阵严格对角占优，$\lVert G_J\rVert_1=13/15\lt1$，故 Jacobi 收敛。取 $x^{(0)}=0$，迭代到 $\lVert x^{(k)}-x^{(k-1)}\rVert_\infty\le10^{-5}$：

解约 $(0.231087,0.147055,0.508393)^{\mathrm T}$。

例 7（教材 2.4.2，Jacobi 发散）：方程组 $$\begin{cases} 2x_1-x_2+x_3=1,\ x_1+x_2+x_3=1,\ x_1+x_2-2x_3=1. \end{cases}$$ $G_J$ 的特征值为 $0,\pm\mathrm i\sqrt{1.25}$，$\rho(G_J)=\sqrt{1.25}\gt1$，故 Jacobi 发散。注意：发散不是“算错了”，而是迭代矩阵的谱半径超界。

例 8（教材 2.4.2，Jacobi 收敛）：方程组 $$\begin{cases} 10x_1+2x_2+5x_4=2,\ x_1+9x_2+2x_3-4x_4=0,\ 3x_1-4x_2+8x_3=1,\ x_1+2x_2-x_3+6x_4=8. \end{cases}$$ 系数矩阵严格对角占优，故 Jacobi 收敛；本题只问“是否收敛”，不必列迭代表。

2.4.3 Gauss–Seidel 迭代

取 $N=L+D$、$P=-U$，则 $$G_{GS}=-(L+D)^{-1}U, \qquad x_i^{(k+1)}=\frac{1}{a_{ii}}\left(b_i-\sum_{j\lt i}a_{ij}x_j^{(k+1)}-\sum_{j\gt i}a_{ij}x_j^{(k)}\right).$$ 与 Jacobi 的唯一差别：本轮已算出的新分量立刻投入使用。形式上是隐式的，实际按 $i=1,\dots,n$ 一行一行显式计算。

定理 2.13：GS 迭代收敛的充要条件是 $\rho(G_{GS})\lt1$。

定理 2.14：若 $\lVert G_{GS}\rVert\lt1$（某种范数），则 GS 迭代收敛。

定理 2.15：若 $A$ 按行（或按列）严格对角占优，则 GS 迭代收敛。

定理 2.16：若 $A$ 对称正定，则 GS 迭代收敛。

证明要点（2.15）：与定理 2.12 同构，把 $G_J$ 换成 $G_{GS}$；关键是 $L+D$ 仍严格对角占优，反证时 $\mu I-G_{GS}$ 的剩余因子仍严格对角占优。（2.16） 用 $A$ 的对称正定性构造能量内积，证明 $\rho(G_{GS})\lt1$；教材给出完整证明。

例 9（教材 2.4.3，GS 收敛）：仍取例 6 的方程组 $$\begin{cases} 10x_1-2x_2-2x_3=1,\ -2x_1+10x_2-x_3=0.5,\ -x_1-2x_2+3x_3=1. \end{cases}$$ GS 迭代矩阵 $G_{GS}=-(D+L)^{-1}U$，$\lVert G_{GS}\rVert_1=150/300\lt1$，故收敛。取 $x^{(0)}=0$：

9 次迭代即达到 $10^{-5}$，比 Jacobi 的 15 次快。

例 10（教材 2.4.3，GS 收敛而 Jacobi 发散）：对例 7 的方程组，$G_{GS}$ 的特征值为 $0,-0.5,-0.5$，$\rho(G_{GS})=0.5\lt1$，故 GS 收敛——尽管 Jacobi 发散（例 7）。这说明“GS 一定比 Jacobi 好/坏”都不对，必须看具体矩阵。

2.4.4 逐次超松弛（SOR）

把 GS 的增量乘上松弛因子 $\omega$： $$x_i^{(k+1)}=(1-\omega)x_i^{(k)} +\frac{\omega}{a_{ii}}\left(b_i-\sum_{j\lt i}a_{ij}x_j^{(k+1)}-\sum_{j\gt i}a_{ij}x_j^{(k)}\right).$$ 矩阵形式：$N=L+\omega^{-1}D$、$P=(\omega^{-1}-1)D-U$， $$G_S=N^{-1}P.$$ $\omega=1$ 退化为 GS；$0\lt\omega\lt1$ 为低松弛，$1\lt\omega\lt2$ 为超松弛。

定理 2.17：SOR 收敛的充要条件是 $\rho(G_S)\lt1$。

定理 2.18：若 $\lVert G_S\rVert\lt1$，则 SOR 收敛。

定理 2.19（必要条件）：SOR 收敛 $\Rightarrow 0\lt\omega\lt2$。

证明要点：$\det G_S=(1-\omega)^n$，故特征值之积为 $(1-\omega)^n$；若收敛，所有 $|\lambda_i|\lt1$，于是 $|1-\omega|\lt1$，即 $0\lt\omega\lt2$。$\blacksquare$

定理 2.20（充分条件①）：若 $A$ 按行（或按列）严格对角占优，且 $0\lt\omega\le1$，则 SOR 收敛。

证明要点：反设 $\rho(G_S)\ge1$，取 $|\mu|\ge1$、$\det(\mu I-G_S)=0$；把 $\mu I-G_S$ 化为 $L+cD+\mu^{-1}U$，证明 $|c|\ge1$，于是“对角放大、其余缩小”，该矩阵仍严格对角占优，矛盾。完整证明见第 6 讲。$\blacksquare$

定理 2.21（Ostrowski）：若 $A$ 对称正定，则 $0\lt\omega\lt2$ 时 SOR 收敛；$\omega\notin(0,2)$ 时发散。

例 11（教材 2.4.4，SOR）：用 $\omega=1.25$ 求解 $$\begin{cases} 4x_1+3x_2=16,\ 3x_1+4x_2-x_3=20,\ -x_2+4x_3=-12. \end{cases}$$ 系数矩阵 $A$ 对称正定，故由 Ostrowski 定理，$0\lt\omega\lt2$ 时 SOR 收敛。取 $x^{(0)}=0$，迭代到 $\lVert x^{(k)}-x^{(k-1)}\rVert_\infty\lt0.00005$：

解约 $(1.50001,3.33333,-2.16667)^{\mathrm T}$。同样精度 GS（$\omega=1$）需 22 次；合适 $\omega$ 能加速，但最优 $\omega$ 通常不知道，实际靠试算。

2.4.5 三种方法的对比

选择顺序：先看结构（三对角/稀疏/对角占优/对称正定），再选方法；不要一上来就 SOR。对大规模稀疏问题，现代做法是 Krylov 方法 + 预条件（补充篇/后续课程），但经典迭代仍是理解分裂与谱半径的入口。

2.4.6 习题（教材习题 15–24）