GaussSeidel

The Gauss-Seidel method is an iterative technique for solving linear systems Ax = b. It updates the solution vector x by sequentially refining its components, using the latest available values as soon as they are computed. It is a refinement of the Jacobi method and is widely used for sparse systems arising from discretizations of partial differential equations.

Let A be decomposed as A = D + L + U, where D is the diagonal part, L is the strictly lower triangular part, and U is the strictly upper triangular part. The Gauss-Seidel update is x^{k+1} = (D+L)^{-1} (b - U x^{k}). Equivalently, the i-th component satisfies x_i^{k+1} = (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} ).

Convergence: If A is symmetric positive definite or strictly diagonally dominant, Gauss-Seidel converges for any initial guess. In general, convergence is not guaranteed; there exist matrices for which the method diverges. A common practical criterion is that the spectral radius of the Gauss-Seidel iteration matrix (D+L)^{-1} U be less than 1.

Computational aspects and applications: Each iteration requires solving a lower triangular system, typically by forward substitution, which makes the cost per iteration O(n^2) for dense A and favorable for sparse matrices. The method often converges faster than the Jacobi method and is commonly used in numerical linear algebra, especially for systems arising from discretized PDEs.

Relation to other methods and variants: Gauss-Seidel is a stationary iterative method and can be viewed as a special case of A = D+L+U splitting. A related technique is the successive over-relaxation (SOR) method, which introduces a relaxation parameter to accelerate convergence on suitable problems.