Gauss-Seidel方法

1. 引言

Gauss-Seidel 方法是求解线性方程组的一种经典迭代算法，由德国数学家高斯（Carl Friedrich Gauss）和塞德尔（Philipp Ludwig von Seidel）提出。该方法特别适用于求解大型稀疏线性方程组，在科学计算和工程应用中有着广泛的应用。

2. 基本原理

2.1 问题描述

考虑线性方程组：

$$Ax=b$$

其中 $A$ 是 $n\times n$ 的系数矩阵，$x$ 是未知向量，$b$ 是常数向量。

展开形式为：

$$\{\begin{array}{l}{a}_{11}{x}_1+a_{12}{x}_2+\cdots +a_{1n}{x}_n=b_1\\ a_{21}{x}_1+a_{22}{x}_2+\cdots +a_{2n}{x}_n=b_2\\ ⋮\\ a_{n1}{x}_1+a_{n2}{x}_2+\cdots +a_{nn}{x}_n=b_n\end{array}$$

2.2 迭代格式推导

Gauss-Seidel 方法的核心思想是：从第 $i$ 个方程中解出 $x_i$，在迭代过程中立即使用最新计算出的值。

步骤1：分离变量

从第 $i$ 个方程中分离出 $x_i$：

$$a_{ii}{x}_i=b_i-\sum _{j=1}^{i-1}{a}_{ij}{x}_j-\sum _{j=i+1}^n{a}_{ij}{x}_j$$

步骤2：构造迭代公式

假设我们已有第 $k$ 次迭代的近似解 $x^{(k)}$，则第 $k+1$ 次迭代为：

$$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_1^{(k+1)},x_2^{(k+1)},\dots ,x_{i-1}^{(k+1)}$ 使用的是最新计算的值
• 后面的 $x_{i+1}^{(k)},x_{i+2}^{(k)},\dots ,x_n^{(k)}$ 使用的是上一次迭代的值

实际计算中，常用以下准则判断迭代是否收敛：

1. 绝对误差： $\Vert x^{(k+1)}-x^{(k)}\Vert <ϵ$
2. 相对误差： $\frac{\Vert x^{(k+1)}-x^{(k)}\Vert }{\Vert x^{(k+1)}\Vert }<ϵ$
3. 残差： $\Vert A{x}^{(k)}-b\Vert <ϵ$

3. 算法实现

算法伪代码

// 等式：AX = b
// 输入：系数矩阵 A，常数向量 b，初始猜测 x⁽⁰⁾，容差 ε，最大迭代次数 max_iter
// 输出：近似解 x

k = 0
2. while k < max_iter:
3.     for i = 1 to n:
4.         sum1 = Σ(j=1 to i-1) a[i][j] * x[j]
5.         sum2 = Σ(j=i+1 to n) a[i][j] * x[j]
6.         x[i] = (b[i] - sum1 - sum2) / a[i][i]
8.     if ||x⁽ᵏ⁺¹⁾ - x⁽ᵏ⁾|| < ε:
9.         return x
10.    k = k + 1
11.
1.  return x（警告：未收敛）

为了研究算法的收敛速度，可以使用Octave绘制迭代次数和误差。例如：

A = [4, -1, 0, 0;
     -1, 4, -1, 0;
     0, -1, 4, -1;
     0, 0, -1, 3];
b = [15; 10; 10; 10];
x0 = zeros(4, 1);
tol = 1e-6;
maxIter = 100;
[x, iter] = GaussSeidel(A, b, x0, tol, maxIter);

横坐标为迭代次数，纵坐标为误差。