迭代法：Jacobi 与 Gauss-Seidel

1. 定义与一般形式

Jacobi和Gauss-Seidel方法是求解线性方程组 $Ax=b$ 的经典迭代技术。其核心思想是将矩阵 $A$ 分解为 $A = M - N$，其中 $M$ 是一个容易求逆的矩阵。

由此，方程 $Ax=b$ 可以转化为 $(M-N)x=b$，进而得到迭代的一般形式：

$$Mx^{(k+1)} = Nx^{(k)} + b $$

$$x^{(k+1)} = M^{-1}Nx^{(k)} + M^{-1}b $$

记迭代矩阵 $B = M^{-1}N$，常数向量 $f = M^{-1}b$，则一般形式为：

$$x^{(k+1)} = Bx^{(k)} + f $$

2. 使用的先决条件

为了保证迭代过程能够顺利进行，必须满足以下基本条件：

  • 对角元素非零：对于矩阵 $A$ 的所有对角元素 $a_{ii}$，必须有 $a_{ii} \neq 0$。这是因为两种方法都需要用对角元素作为分母。

3. 收敛条件

迭代法是否收敛，即迭代序列 $\{x^{(k)}\}$ 是否收敛于真实解 $x^*$，取决于迭代矩阵 $B$ 的性质。

  • 充分必要条件：
    迭代法收敛的充分必要条件是迭代矩阵 $B$ 的谱半径 $\rho(B) < 1$。谱半径定义为矩阵特征值的最大绝对值，即 $\rho(B) = \max_i |\lambda_i|$。

  • 充分不必要条件（更容易判断）：

    1. 严格对角占优：如果矩阵 $A$ 是严格对角占优的，即对于每一行，对角元素的绝对值大于该行其他元素绝对值之和：

      $$|a_{ii}| > \sum_{j \neq i} |a_{ij}|, \quad \forall i=1, \dots, n $$

      则Jacobi和Gauss-Seidel迭代法都收敛。
    2. 对称正定：如果矩阵 $A$ 是对称正定矩阵，则Gauss-Seidel迭代法收敛。

  • 必要条件：
    如果迭代法收敛，那么必然有 $\rho(B) < 1$。这是收敛的最低要求。

收敛性对比

条件 Jacobi Gauss-Seidel
严格对角占优 收敛 收敛
对称正定 不一定收敛 收敛
谱半径小于1 收敛 收敛

4. Jacobi 迭代

4.1 定义

Jacobi迭代法的思想是，在第 $k+1$ 次迭代中，计算 $x_i^{(k+1)}$ 时，所有分量都使用第 $k$ 次的迭代结果 $x^{(k)}$。

我们将矩阵 $A$ 分解为 $A = D - L - U$，其中：

$$D = \begin{pmatrix} a_{11} & 0 & \cdots & 0 \\ 0 & a_{22} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & a_{nn} \end{pmatrix} $$

$$L = \begin{pmatrix} 0 & 0 & \cdots & 0 \\ -a_{21} & 0 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ -a_{n1} & -a_{n2} & \cdots & 0 \end{pmatrix}, \quad U = \begin{pmatrix} 0 & -a_{12} & \cdots & -a_{1n} \\ 0 & 0 & \cdots & -a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 0 \end{pmatrix} $$

4.2 迭代算法

将分解代入 $Ax=b$：

$$(D-L-U)x = b \implies Dx = (L+U)x + b $$

由此得到Jacobi迭代的矩阵形式：

$$x^{(k+1)} = D^{-1}(L+U)x^{(k)} + D^{-1}b $$

其分量形式为：

$$x_i^{(k+1)} = \frac{1}{a_{ii}} \left( b_i - \sum_{j \neq i} a_{ij}x_j^{(k)} \right), \quad i=1, \dots, n $$

4.3 一般形式

  • 迭代矩阵：$B_J = D^{-1}(L+U)$
  • 常数向量：$f_J = D^{-1}b$

5. Gauss-Seidel 迭代

5.1 定义

Gauss-Seidel迭代法是对Jacobi迭代的改进。在计算 $x_i^{(k+1)}$ 时，它会立即使用在同一次迭代中已经计算出的新分量 $x_1^{(k+1)}, \dots, x_{i-1}^{(k+1)}$。

5.2 迭代算法

基于同样的分解 $A = D-L-U$，我们将方程整理为：

$$(D-L)x = Ux + b $$

由此得到Gauss-Seidel迭代的矩阵形式：

$$x^{(k+1)} = (D-L)^{-1}Ux^{(k)} + (D-L)^{-1}b $$

其分量形式为：

$$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), \quad i=1, \dots, n $$

5.3 一般形式

  • 迭代矩阵：$B_{GS} = (D-L)^{-1}U$
  • 常数向量：$f_{GS} = (D-L)^{-1}b$

6. 总结与比较

特性 Jacobi 迭代 Gauss-Seidel 迭代
核心思想 所有分量均使用上一轮的旧值 总是使用当前可用的最新值
收敛速度 通常较慢 通常比Jacobi快
并行性 非常好，所有分量可同时计算 较差，分量计算有串行依赖
实现 简单，需要存储两份向量（新旧） 略复杂，可原地更新（节省空间）

在实际应用中，如果收敛，Gauss-Seidel通常是更好的选择。然而，Jacobi的并行特性使其在大规模并行计算中仍有应用价值。这两种方法也为更高级的迭代法（如SOR法）奠定了基础。