张叶安的小站

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
====== 第九章 迭代法 ======

===== 9.1 引言 =====

直接法经过有限步运算得到精确解（不计舍入误差），但对于大型稀疏矩阵，存储和计算量都很大。迭代法通过构造迭代格式，从一个初始猜测出发，逐步逼近精确解。

迭代法的优点：
  - 存储量小（只需存储非零元素）
  - 对大型稀疏矩阵效率高
  - 可以控制精度，适时终止

===== 9.2 迭代法的基本思想 =====

将 $Ax = b$ 改写为等价形式：
$$x = Bx + f$$

构造迭代格式：
$$x^{(k+1)} = Bx^{(k)} + f, \quad k = 0, 1, 2, \ldots$$

其中 $x^{(0)}$ 是初始猜测，$B$ 称为**迭代矩阵**。

===== 9.3 Jacobi迭代法 =====

==== 9.3.1 迭代格式 ====

设 $A = D - L - U$，其中：
  - $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迭代矩阵。

==== 9.3.2 分量形式 ====

对每个 $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}}$$

===== 9.4 Gauss-Seidel迭代法 =====

==== 9.4.1 迭代格式 ====

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迭代矩阵。

===== 9.5 逐次超松弛迭代法（SOR） =====

==== 9.5.1 松弛思想 ====

将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.5.2 松弛因子的选择 ====

  - $\omega = 1$：Gauss-Seidel迭代
  - $0 < \omega < 1$：低松弛（用于非正定系统）
  - $1 < \omega < 2$：超松弛（加速收敛）
  - $\omega \geq 2$ 或 $\omega \leq 0$：通常不收敛

===== 9.6 迭代法的收敛性 =====

==== 9.6.1 收敛的充分必要条件 ====

**定理 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.6.2 特殊矩阵的收敛性 ====

**定义 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$ 严格对角占优或不可约对角占优，则：
  - Jacobi迭代收敛
  - Gauss-Seidel迭代收敛

**定理 9.4** 若 $A$ 对称正定，则：
  - Gauss-Seidel迭代收敛
  - 当 $0 < \omega < 2$ 时SOR迭代收敛

**定理 9.5（SOR收敛的必要条件）** SOR迭代收敛的必要条件是 $0 < \omega < 2$。

===== 9.7 收敛速度 =====

==== 9.7.1 渐近收敛速度 ====

$$R(B) = -\ln \rho(B)$$

达到精度 $\varepsilon$ 所需的迭代次数：
$$k \geq \frac{-\ln \varepsilon}{R(B)}$$

==== 9.7.2 最优松弛因子 ====

对于某些特殊矩阵（如相容次序矩阵），有最优松弛因子：
$$\omega_{opt} = \frac{2}{1 + \sqrt{1 - \rho(B_J)^2}}$$

此时：
$$\rho(B_{\omega_{opt}}) = \omega_{opt} - 1$$

===== 9.8 典型例题 =====

**例题 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迭代：
  - $x_1^{(k+1)} = 0.72 + 0.1x_2^{(k)} + 0.2x_3^{(k)}$
  - $x_2^{(k+1)} = 0.83 + 0.1x_1^{(k)} + 0.2x_3^{(k)}$
  - $x_3^{(k+1)} = 0.84 + 0.2x_1^{(k)} + 0.2x_2^{(k)}$

迭代结果：
| $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迭代：
  - $x_1^{(k+1)} = 0.72 + 0.1x_2^{(k)} + 0.2x_3^{(k)}$
  - $x_2^{(k+1)} = 0.83 + 0.1x_1^{(k+1)} + 0.2x_3^{(k)}$
  - $x_3^{(k+1)} = 0.84 + 0.2x_1^{(k+1)} + 0.2x_2^{(k+1)}$

迭代结果：
| $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收敛更快）

===== 9.9 习题 =====

**基础练习**

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.