Gauss Seidal iterative method, Rate of Convergence

The Gauss-Seidel iterative method is one of the most common techniques for solving systems of linear equations iteratively. It’s particularly useful for symmetric and diagonally dominant matrices. The rate of convergence of the Gauss-Seidel method depends on the spectral radius of the iteration matrix.

Here’s how it works:

Initialization: Start with an initial guess for the solution vector, denoted by
Iterative Process: Update each component of the solution vector iteratively using the following formula:

$x_{i (k + 1)} = \frac{1}{a ^{ii}} (b_{i} - \sum_{j = 1 i - 1} a_{ij} x_{j (k + 1)} - \sum_{j = i + 1 n} a_{ij} x_{j (k)})$

where

$x_{i (k + 1)}$ represents the
$i -th component of the solution vector at the -th component of the solution vector at the (k + 1) -th iteration, a ij are the elements of the coefficient matrix A, b i are the elements of the constant vector b, and n is the size of the system.$
Convergence Criterion: Check for convergence by measuring the difference between successive approximations. Typically, the convergence criterion involves checking if the relative change in the solution vector falls below a specified tolerance level.

The rate of convergence of the Gauss-Seidel method depends on the spectral radius of the iteration matrix

$T = (D - L)^{-1} U$ , where

$D$ is the diagonal part of

$A$ , $L$ is the lower triangular part of

$A$ (excluding the diagonal), and

$U$ is the upper triangular part of

$A$ (excluding the diagonal).

If the spectral radius

$ρ (T)$ is less than 1, the method converges. The closer

$ρ (T)$ is to 0, the faster the convergence. However, if

$ρ (T)$ is close to 1, convergence can be slow.

To improve the rate of convergence:

Optimal Relaxation Parameter: You can use the Gauss-Seidel method with relaxation. Introducing a relaxation parameter (
Reduction of the Spectral Radius: Techniques like preconditioning or rearranging equations can reduce the spectral radius, thereby improving convergence.
Choosing a Good Initial Guess: A good initial guess can sometimes significantly reduce the number of iterations needed for convergence.
Problem-specific Modifications: Depending on the problem, certain modifications to the algorithm might improve convergence. For example, reordering equations or variables can sometimes improve the convergence rate.

By understanding the convergence properties and employing suitable techniques, you can optimize the Gauss-Seidel iterative method for efficient solution of linear systems.