Guass-Seidel迭代法数学原理

1. 问题描述

求解线性方程组：

$$A\mathbf{x} = \mathbf{b}$$

其中：
- $A = [a_{ij}]$ 是 $n \times n$ 系数矩阵
- $\mathbf{b} = [b_i]$ 是已知向量
- $\mathbf{x} = [x_i]$ 是待求解向量

具体到我们的问题：

$$A = \begin{bmatrix} 0.76 & -0.01 & -0.14 & -0.16 \\ -0.01 & 0.88 & -0.03 & 0.06 \\ -0.14 & -0.03 & 1.01 & -0.12 \\ -0.16 & 0.06 & -0.12 & 0.72 \end{bmatrix}, \quad \mathbf{b} = \begin{bmatrix} 0.68 \\ 1.18 \\ 0.12 \\ 0.74 \end{bmatrix}$$

2. 高斯-赛德尔迭代法的矩阵推导

2.1 矩阵分解

将矩阵 $A$ 分解为三个部分：

$$A = D - L - U$$

其中：
- $D$：$A$ 的对角线部分
- $L$：$A$ 的严格下三角部分（取负号）
- $U$：$A$ 的严格上三角部分（取负号）

具体形式：

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

$$L = -\begin{bmatrix} 0 & 0 & \cdots & 0 \\ a_{21} & 0 & \cdots & 0 \\ \vdots & \ddots & \ddots & \vdots \\ a_{n1} & \cdots & a_{n,n-1} & 0 \end{bmatrix}$$

$$U = -\begin{bmatrix} 0 & a_{12} & \cdots & a_{1n} \\ 0 & 0 & \ddots & \vdots \\ \vdots & \vdots & \ddots & a_{n-1,n} \\ 0 & 0 & \cdots & 0 \end{bmatrix}$$

2.2 迭代格式推导

原方程 $A\mathbf{x} = \mathbf{b}$ 可写为：

$$(D - L - U)\mathbf{x} = \mathbf{b}$$

移项得：

$$D\mathbf{x} = \mathbf{b} + L\mathbf{x} + U\mathbf{x}$$

高斯-赛德尔迭代法的核心思想是：在计算第 $k+1$ 次迭代时，使用已经更新的分量值。

因此，迭代格式为：

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

整理得：

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

最终得到矩阵形式的迭代公式：

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

3. 分量形式的迭代公式

3.1 通用公式

对于第 $k+1$ 次迭代的第 $i$ 个分量：

$$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)$$

其中：
- $i = 1, 2, \ldots, n$
- $a_{ii} \neq 0$（对角元素非零）

3.2 具体到我们的代码实现

在代码中，迭代公式体现为：

for i in range(n):
    indices1 = list(range(0, i))        # j = 0, 1, ..., i-1
    indices2 = list(range(i + 1, n))    # j = i+1, i+2, ..., n-1
    x_next[i] = (b[i] - np.sum(A[i, indices1] * x_next[indices1]) 
                  - np.sum(A[i, indices2] * x_last[indices2])) / A[i, i]

对应数学公式：

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

注意：由于Python索引从0开始，公式中的索引范围与数学表示略有不同。

4. 并行性

高斯-赛德尔迭代法不能并行计算的主要原因在于其迭代过程具有内在的顺序依赖性。

具体来说，在计算第 $k+1$ 次迭代的分量 $x_i^{(k+1)}$ 时，该方法立即使用已经更新过的前几个分量 $x_1^{(k+1)}, x_2^{(k+1)}, \ldots, x_{i-1}^{(k+1)}$，而不是像雅可比（Jacobi）迭代法那样全部使用上一次迭代的老值。这种“最新值优先”的策略提高了收敛速度，但也导致了计算必须按顺序进行：

• 计算 $x_2^{(k+1)}$ 需要用到刚更新的 $x_1^{(k+1)}$
• 计算 $x_3^{(k+1)}$ 需要用到已更新的 $x_1^{(k+1)}$ 和 $x_2^{(k+1)}$
• 以此类推

因此，每个分量的更新都依赖于前面分量在当前迭代中的新值，这种数据依赖关系使得各个分量无法同时独立计算，从而无法实现真正的并行化。

相比之下，雅可比迭代法在计算 $\mathbf{x}^{(k+1)}$ 时完全基于 $\mathbf{x}^{(k)}$，所有分量之间相互独立，适合并行计算。而高斯-赛德尔为了追求更快的收敛性，牺牲了并行性。

高斯-赛德尔迭代法由于在同一步迭代中前后分量之间存在强耦合与数据依赖，必须串行执行，因而不适合并行计算。这是其算法结构上的本质限制。