Gauss-Seidel Method

Large linear systems appear frequently in scientific computing, engineering simulations, and optimization problems. Direct methods become expensive for large matrices, while iterative methods offer better scalability and lower memory usage. The Gauss–Seidel method is a simple yet effective iterative technique that exploits matrix structure to accelerate convergence compared to basic fixed-point iterations.

Introduction

The Gauss-Seidel method is an iterative algorithm for solving a system of linear equations of the form $A\mathbf{x}=\mathbf{b}$. It updates each variable sequentially using the most recent values available, which often results in faster convergence than the Jacobi method. The method is particularly effective for diagonally dominant or symmetric positive definite matrices and is commonly used as a baseline solver or as a smoother in multigrid methods.

We solve the linear system:

$$\begin{cases} 4x_1 - x_2 + x_3 = 7 \\\\ -2x_1 + 6x_2 + x_3 = 9 \\\\ x_1 + x_2 + 5x_3 = -6 \end{cases}$$

Rearranged Equations

$$x_1 = \frac{7 + x_2 - x_3}{4}$$

$$x_2 = \frac{9 + 2x_1 - x_3}{6}$$

$$x_3 = \frac{-6 - x_1 - x_2}{5}$$

Gauss–Seidel Iteration Formula

Using the latest available values:

$$x_1^{(k+1)} = \frac{7 + x_2^{(k)} - x_3^{(k)}}{4}$$

$$x_2^{(k+1)} = \frac{9 + 2x_1^{(k+1)} - x_3^{(k)}}{6}$$

$$x_3^{(k+1)} = \frac{-6 - x_1^{(k+1)} - x_2^{(k+1)}}{5}$$

Initial Guess

$$\mathbf{x}^{(0)} = (0,0,0)$$

First Iteration

$$x_1^{(1)} = \frac{7}{4} = 1.75$$

$$x_2^{(1)} = \frac{9 + 2(1.75)}{6} = 2.083333$$

$$x_3^{(1)} = \frac{-6 - 1.75 - 2.083333}{5} = -1.966667$$

$$\mathbf{x}^{(1)} \approx (1.75,\;2.083333,\;-1.966667)$$

Stopping Criterion

$$\left\lVert \mathbf{x}^{(k+1)} - \mathbf{x}^{(k)} \right\rVert_\infty < \varepsilon$$

with

$$\left\lVert \mathbf{v} \right\rVert_\infty = \max_i |v_i|$$