Gauss-Seidel Iteration Method for Solving Linear Systems | 高斯-赛德尔迭代法求解线性方程组

📚 Gauss-Seidel Iteration Method for Solving Linear Systems | 高斯-赛德尔迭代法求解线性方程组

The Gauss-Seidel iteration method is a classical iterative technique for solving a system of linear equations Ax = b. It is particularly useful for large, sparse systems where direct methods such as Gaussian elimination are computationally expensive. The method updates each unknown sequentially, using the most recently computed values, which often leads to faster convergence than the Jacobi method.

高斯-赛德尔迭代法是一种经典的求解线性方程组 Ax = b 的迭代技术。它特别适用于大型稀疏方程组，此时高斯消元等直接方法计算成本过高。该方法按顺序逐个更新未知量，并使用最新计算出的值，因此通常比雅可比方法收敛更快。

---

1. Problem Setup | 问题设定

Consider a linear system of n equations in n unknowns:

考虑一个包含 n 个未知数、n 个方程的线性方程组：

a₁₁x₁ + a₁₂x₂ + ⋯ + a_1nx_n = b₁
a₂₁x₁ + a₂₂x₂ + ⋯ + a_2nx_n = b₂
vdots
a_n1x₁ + a_n2x₂ + ⋯ + a_nnx_n = b_n

The goal is to find the vector x = (x₁, x₂, …, x_n)^T that satisfies the system, assuming a unique solution exists.

目标是找到满足方程组的向量 x = (x₁, x₂, …, x_n)^T，并假设解存在且唯一。

---

2. Iterative Idea | 迭代思想

Instead of solving the system directly, iterative methods generate a sequence of approximate solutions x⁽⁰⁾, x⁽¹⁾, x⁽²⁾, … that converge to the true solution. Each iteration refines the previous approximation using a splitting of the coefficient matrix A.

迭代方法不直接求解方程组，而是生成一系列近似解 x⁽⁰⁾, x⁽¹⁾, x⁽²⁾, …，它们逐步收敛到精确解。每一次迭代都利用系数矩阵 A 的分解来改进上一次的近似值。

For the Gauss-Seidel method, we split A into a lower triangular part L_*, a diagonal part D, and a strictly upper triangular part U_*:

对于高斯-赛德尔方法，我们将 A 分解为一个下三角部分 L_*、一个对角部分 D 和一个严格上三角部分 U_*：

A = L_* + D + U_*

where L_* contains entries below the diagonal, D contains the diagonal entries, and U_* contains entries above the diagonal.

其中 L_* 包含对角线以下的元素，D 包含对角线元素，U_* 包含对角线以上的元素。

---

3. Derivation of the Update Formula | 更新公式的推导

From the i-th equation:

由第 i 个方程出发：

a_i1x₁ + a_i2x₂ + ⋯ + a_inx_n = b_i

We solve for x_i, assuming the other components are known:

我们解出 x_i，并假设其余分量已知：

x_i = ¹⁄_aii ( b_i - ∑_j=1^i-1 a_ijx_j - ∑_j=i+1ⁿ a_ijx_j )

In the Gauss-Seidel iteration, the latest available values are used: for j < i, we use the values from the current iteration x_j^(k+1); for j > i, we use values from the previous iteration x_j^(k).

在高斯-赛德尔迭代中，我们使用最新的可用值：对于 j < i，使用当前迭代的值 x_j^(k+1)；对于 j > i，使用上一迭代的值 x_j^(k)。

---

4. Algorithm Steps | 算法步骤

Given an initial guess x⁽⁰⁾, repeat the following for k = 0, 1, 2, … until convergence:

给定初始猜测 x⁽⁰⁾，对 k = 0, 1, 2, … 重复以下步骤直到收敛：

• For i = 1, 2, …, n:
  对 i = 1, 2, …, n：
• Compute
  计算
  

  x_i^(k+1) = ¹⁄_aii ( b_i - ∑_j=1^i-1 a_ijx_j^(k+1) - ∑_j=i+1ⁿ a_ijx_j^(k) )

• Update the solution vector immediately after each component is computed.
  每计算出一个分量后立即更新解向量。

The process continues until the difference between successive iterates is smaller than a given tolerance ε.

该过程持续进行，直到相邻两次迭代的差小于给定的容差 ε。

---

5. Matrix Formulation | 矩阵形式

The Gauss-Seidel iteration can be written in matrix form. Using the splitting A = L_* + D + U_*, the update is:

高斯-赛德尔迭代可以用矩阵形式写成。利用分解 A = L_* + D + U_*，更新式为：

(L_* + D)x^(k+1) = b - U_* x^(k)

Thus the iteration matrix is:

因此迭代矩阵为：

x^(k+1) = (L_* + D)^-1 (b - U_* x^(k))

Equivalently, x^(k+1) = (L_* + D)^-1b + B_GS x^(k), where B_GS = -(L_* + D)^-1 U_*.

等价地，x^(k+1) = (L_* + D)^-1b + B_GS x^(k)，其中 B_GS = -(L_* + D)^-1 U_*。

---

6. Worked Example | 算例演示

Solve the following system using Gauss-Seidel iteration:

使用高斯-赛德尔迭代法求解以下方程组：

10x₁ + 2x₂ + x₃ = 14
2x₁ + 10x₂ + 3x₃ = 19
x₁ + 3x₂ + 10x₃ = 23

From each equation, we isolate the diagonal variable:

从每个方程中分离出对角线变量：

x₁ = 110(14 - 2x₂ - x₃)
x₂ = 110(19 - 2x₁ - 3x₃)
x₃ = 110(23 - x₁ - 3x₂)

Starting with initial guess x⁽⁰⁾ = (0, 0, 0)^T:

从初始猜测 x⁽⁰⁾ = (0, 0, 0)^T 开始：

• Iteration 1:
  第1次迭代：
• x₁⁽¹⁾ = 110(14) = 1.4
• x₂⁽¹⁾ = 110(19 - 2(1.4) - 0) = 1.62
• x₃⁽¹⁾ = 110(23 - 1.4 - 3(1.62)) = 1.674

Continue iterating until the values stabilize. The exact solution is x = (1, 1, 2)^T.

继续迭代直到数值稳定。精确解为 x = (1, 1, 2)^T。

---

广告 / Sponsored

7. Convergence Criteria | 收敛条件

A sufficient condition for convergence of the Gauss-Seidel method is that the coefficient matrix A is strictly diagonally dominant:

高斯-赛德尔方法收敛的一个充分条件是系数矩阵 A 严格对角占优：

|a_ii| > ∑_{j ≠ i} |a_ij| for all i

Another sufficient condition is that A is symmetric positive definite.

另一个充分条件是 A 对称正定。

More generally, convergence depends on the spectral radius of the iteration matrix B_GS. If ρ(B_GS) < 1, the iteration converges for any initial guess.

更一般地，收敛性取决于迭代矩阵 B_GS 的谱半径。如果 ρ(B_GS) < 1，则迭代对任意初始猜测都收敛。

---

8. Comparison with Jacobi Method | 与雅可比方法的比较

In the Jacobi method, all components are updated simultaneously using only values from the previous iteration:

在雅可比方法中，所有分量同时更新，且仅使用上一迭代的值：

x_i^(k+1) = ¹⁄_aii ( b_i - ∑_{j ≠ i} a_ijx_j^(k) )

The Gauss-Seidel method uses updated components immediately. This often accelerates convergence, especially when the matrix is diagonally dominant or positive definite.

高斯-赛德尔方法则立即使用已更新的分量。这通常会加速收敛，尤其是当矩阵对角占优或正定时。

However, Gauss-Seidel is inherently sequential and cannot be parallelized as easily as Jacobi.

然而，高斯-赛德尔本质上是顺序执行的，不像雅可比方法那样容易并行化。

---

9. Advantages and Disadvantages | 优点与缺点

Advantages:

优点：

• Simple to implement and requires less memory than direct methods.
  实现简单，比直接方法占用内存少。
• Often converges faster than Jacobi for many practical problems.
  在许多实际问题中通常比雅可比收敛更快。
• Preserves the sparsity of the matrix A.
  保持矩阵 A 的稀疏性。

Disadvantages:

缺点：

• Convergence is not guaranteed for arbitrary matrices.
  对任意矩阵不保证收敛。
• Sequential updates limit parallel implementation.
  顺序更新限制了并行实现。
• Convergence can be slow for ill-conditioned systems.
  对于病态方程组收敛可能很慢。

---

10. Applications in IB Mathematics | 在IB数学中的应用

In IB Mathematics, numerical methods are often introduced in the context of solving systems of equations that arise in real-world modelling. Gauss-Seidel iteration is particularly relevant in:

在IB数学中，数值方法常结合现实建模中产生的方程组求解来介绍。高斯-赛德尔迭代在以下情境中尤其相关：

• Modelling electrical circuits (network analysis).
  电路建模（网络分析）。
• Predicting equilibrium prices in economics.
  经济学中的均衡价格预测。
• Solving steady-state temperature distributions.
  求解稳态温度分布。
• Optimization and approximation problems.
  优化与近似问题。

Students should be able to perform several iterations manually and use technology to compute more extensive approximations.

学生应能手动进行几次迭代，并使用技术工具计算更精确的近似解。

---

11. Tips for Exam Questions | 考试答题技巧

When solving Gauss-Seidel questions in an exam:

在考试中解答高斯-赛德尔问题时：

• Always write down the iteration formula explicitly.
  务必明确写出迭代公式。
• Use a table to record each iteration clearly.
  使用表格清晰记录每次迭代。
• Check whether the matrix is diagonally dominant before concluding convergence.
  在判断收敛前先检查矩阵是否对角占优。
• Carry enough decimal places to avoid premature rounding errors.
  保留足够的小数位数以避免过早舍入误差。
• Stop only when the required accuracy is achieved.
  只有在达到所需精度时才停止迭代。

Iteration k	x1(k)	x2(k)	x3(k)
0	0	0	0
1	1.4	1.62	1.674

---

12. Summary | 总结

The Gauss-Seidel method is a powerful iterative tool for solving linear systems, especially when the coefficient matrix is large and sparse. Its sequential nature gives it a convergence advantage over Jacobi, provided the matrix satisfies certain conditions. Understanding its formulation, convergence criteria, and practical implementation is essential for IB Mathematics students.

高斯-赛德尔方法是求解线性方程组的强大迭代工具，尤其适用于大型稀疏系数矩阵。其顺序更新特性使它在满足一定条件时比雅可比方法更具收敛优势。理解其公式、收敛条件和实际应用，对IB数学学生来说至关重要。

Published by TutorHao | Mathematics Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）