直接法经过有限步运算得到精确解（不计舍入误差），但对于大型稀疏矩阵，存储和计算量都很大。迭代法通过构造迭代格式，从一个初始猜测出发，逐步逼近精确解。
迭代法的优点：
将 $Ax = b$ 改写为等价形式： $$x = Bx + f$$
构造迭代格式： $$x^{(k+1)} = Bx^{(k)} + f, \quad k = 0, 1, 2, \ldots$$
其中 $x^{(0)}$ 是初始猜测，$B$ 称为迭代矩阵。
设 $A = D - L - U$，其中：
将第 $i$ 个方程解出 $x_i$： $$x_i = \frac{1}{a_{ii}}\left(b_i - \sum_{j \neq i} a_{ij} x_j\right), \quad i = 1, 2, \ldots, n$$
Jacobi迭代格式： $$x_i^{(k+1)} = \frac{1}{a_{ii}}\left(b_i - \sum_{j=1}^{i-1} a_{ij} x_j^{(k)} - \sum_{j=i+1}^{n} a_{ij} x_j^{(k)}\right)$$
或写成矩阵形式： $$x^{(k+1)} = D^{-1}(L + U)x^{(k)} + D^{-1}b = B_J x^{(k)} + f_J$$
其中 $B_J = D^{-1}(L + U) = I - D^{-1}A$ 是Jacobi迭代矩阵。
对每个 $i = 1, \ldots, n$： $$x_i^{(k+1)} = \frac{b_i - \sum_{j=1}^{n} a_{ij} x_j^{(k)} + a_{ii} x_i^{(k)}}{a_{ii}}$$
Jacobi迭代中，计算 $x_i^{(k+1)}$ 时，$x_1^{(k+1)}, \ldots, x_{i-1}^{(k+1)}$ 已经算出，可以立即使用：
Gauss-Seidel迭代格式： $$x_i^{(k+1)} = \frac{1}{a_{ii}}\left(b_i - \sum_{j=1}^{i-1} a_{ij} x_j^{(k+1)} - \sum_{j=i+1}^{n} a_{ij} x_j^{(k)}\right)$$
矩阵形式： $$x^{(k+1)} = (D - L)^{-1}Ux^{(k)} + (D - L)^{-1}b = B_G x^{(k)} + f_G$$
其中 $B_G = (D - L)^{-1}U$ 是Gauss-Seidel迭代矩阵。
将Gauss-Seidel迭代的修正量乘以一个因子 $\omega$（松弛因子）：
SOR迭代格式： $$x_i^{(k+1)} = x_i^{(k)} + \frac{\omega}{a_{ii}}\left(b_i - \sum_{j=1}^{i-1} a_{ij} x_j^{(k+1)} - \sum_{j=i}^{n} a_{ij} x_j^{(k)}\right)$$
或写成： $$x_i^{(k+1)} = (1-\omega)x_i^{(k)} + \frac{\omega}{a_{ii}}\left(b_i - \sum_{j=1}^{i-1} a_{ij} x_j^{(k+1)} - \sum_{j=i+1}^{n} a_{ij} x_j^{(k)}\right)$$
矩阵形式： $$x^{(k+1)} = (D - \omega L)^{-1}[(1-\omega)D + \omega U]x^{(k)} + \omega(D - \omega L)^{-1}b = B_\omega x^{(k)} + f_\omega$$
定理 9.1 迭代法 $x^{(k+1)} = Bx^{(k)} + f$ 对任意初值 $x^{(0)}$ 收敛的充分必要条件是迭代矩阵的谱半径 $\rho(B) < 1$。
谱半径：$\rho(B) = \max_{1 \leq i \leq n} |\lambda_i|$，其中 $\lambda_i$ 是 $B$ 的特征值。
定理 9.2（充分条件） 若 $\|B\| < 1$，则迭代法收敛，且有误差估计： $$\|x^{(k)} - x^*\| \leq \frac{\|B\|^k}{1-\|B\|} \|x^{(1)} - x^{(0)}\|$$ $$\|x^{(k)} - x^*\| \leq \frac{\|B\|}{1-\|B\|} \|x^{(k)} - x^{(k-1)}\|$$
定义 9.1（严格对角占优） 若 $|a_{ii}| > \sum_{j \neq i} |a_{ij}|$ 对所有 $i$ 成立，则称 $A$ 严格对角占优。
定义 9.2（不可约对角占优） 若 $A$ 不可约（不能通过行列重排化为分块上三角）且 $|a_{ii}| \geq \sum_{j \neq i} |a_{ij}|$，至少有一个严格不等式成立，则称 $A$ 不可约对角占优。
定理 9.3 若 $A$ 严格对角占优或不可约对角占优，则：
定理 9.4 若 $A$ 对称正定，则：
定理 9.5（SOR收敛的必要条件） SOR迭代收敛的必要条件是 $0 < \omega < 2$。
$$R(B) = -\ln \rho(B)$$
达到精度 $\varepsilon$ 所需的迭代次数： $$k \geq \frac{-\ln \varepsilon}{R(B)}$$
对于某些特殊矩阵（如相容次序矩阵），有最优松弛因子： $$\omega_{opt} = \frac{2}{1 + \sqrt{1 - \rho(B_J)^2}}$$
此时： $$\rho(B_{\omega_{opt}}) = \omega_{opt} - 1$$
例题 9.1 用Jacobi和Gauss-Seidel迭代解：
$$\begin{cases}
10x_1 - x_2 - 2x_3 = 7.2
-x_1 + 10x_2 - 2x_3 = 8.3
-x_1 - x_2 + 5x_3 = 4.2
\end{cases}$$
初值 $x^{(0)} = (0, 0, 0)^T$，进行3次迭代。
解：
Jacobi迭代：
迭代结果：
| $k$ | $x_1$ | $x_2$ | $x_3$ |
| —– | ——- | ——- | ——- |
| 0 | 0 | 0 | 0 |
| 1 | 0.72 | 0.83 | 0.84 |
| 2 | 0.971 | 1.07 | 1.15 |
| 3 | 1.057 | 1.157 | 1.248 |
Gauss-Seidel迭代：
迭代结果：
| $k$ | $x_1$ | $x_2$ | $x_3$ |
| —– | ——- | ——- | ——- |
| 0 | 0 | 0 | 0 |
| 1 | 0.72 | 0.902 | 1.1644 |
| 2 | 1.04308 | 1.16719 | 1.28205 |
| 3 | 1.09313 | 1.19572 | 1.29777 |
（精确解约为 $(1.1, 1.2, 1.3)^T$，可见G-S收敛更快）
基础练习
1. 对 $A = \begin{bmatrix} 4 & 1 & 1
1 & 4 & 1
1 & 1 & 4 \end{bmatrix}$，写出Jacobi和Gauss-Seidel迭代矩阵。
2. 证明：若 $A$ 严格对角占优，则Jacobi迭代收敛。
3. 用Jacobi迭代解：$\begin{cases} 5x_1 + 2x_2 + x_3 = 8
2x_1 + 8x_2 + 3x_3 = 13
x_1 + 3x_2 + 6x_3 = 10 \end{cases}$，初值取 $x^{(0)} = 0$，迭代3次。
进阶练习
4. 证明SOR方法收敛的必要条件是 $0 < \omega < 2$。
5. 设 $A$ 对称正定，证明 $\rho(B_G) \leq \rho(B_J) < 1$，即Gauss-Seidel收敛比Jacobi快。
6. 设 $B$ 是Jacobi迭代矩阵，证明SOR迭代矩阵的特征值 $\lambda$ 满足：
$$(\lambda + \omega - 1)^2 = \lambda \omega^2 \mu^2$$ 其中 $\mu$ 是 $B$ 的特征值。
编程实践
7. 编写Jacobi、Gauss-Seidel和SOR迭代程序，比较收敛速度。
8. 实现稀疏矩阵的迭代求解，测试大型对角占优矩阵。
1. 李庆扬等. 数值分析（第5版）. 清华大学出版社, 2008. 2. Saad Y. Iterative Methods for Sparse Linear Systems (2nd ed.). SIAM, 2003.