Stationary and Relaxation Methods

Stationary iterative methods solve a linear system by splitting the matrix and repeatedly applying a fixed update rule; the classical Jacobi, Gauss-Seidel, and successive over-relaxation schemes are the foundational examples.

Definition

A stationary iterative method is one whose update applies the same iteration matrix at every step, derived from a splitting of the coefficient matrix into an easily invertible part and a remainder; convergence is governed by the spectral radius of the resulting iteration matrix.

Scope

This topic covers the matrix-splitting framework, the Jacobi and Gauss-Seidel iterations, successive over-relaxation and the choice of optimal relaxation parameter, the spectral-radius criterion for convergence, and the role these simple iterations play today as smoothers within multigrid and as preconditioners.

Core questions

• How does splitting the matrix yield a fixed-point iteration for the linear system?
• How do the Jacobi and Gauss-Seidel methods differ, and why is Gauss-Seidel usually faster?
• How does over-relaxation accelerate convergence, and how is the optimal parameter chosen?
• Under what conditions on the matrix do these iterations converge?

Key theories

Matrix splitting and the spectral radius criterion

Writing the matrix as an easily invertible part minus a remainder defines a stationary iteration whose error is multiplied by an iteration matrix each step; the iteration converges for every starting guess if and only if the spectral radius of that iteration matrix is less than one.

Successive over-relaxation

By overshooting the Gauss-Seidel correction with a relaxation factor, successive over-relaxation can greatly reduce the spectral radius; for certain structured matrices an optimal relaxation parameter is known analytically and yields a dramatic speed-up.

Mechanisms

The Jacobi method updates every unknown simultaneously using only values from the previous sweep, equivalent to splitting off the diagonal. Gauss-Seidel uses the most recently updated values within the same sweep, splitting off the lower-triangular part, which typically converges faster. Successive over-relaxation forms a weighted average of the old value and the Gauss-Seidel update governed by a relaxation parameter; choosing this parameter larger than one accelerates convergence for suitable matrices. Convergence for all three is guaranteed for classes such as strictly diagonally dominant or symmetric positive-definite matrices, and is quantified by the spectral radius of the iteration matrix.

Clinical relevance

Although usually too slow to be competitive standalone solvers for large systems, stationary methods remain important as the smoothers at the heart of multigrid, as simple preconditioners for Krylov methods, and as easily parallelizable building blocks; Gauss-Seidel and weighted Jacobi in particular are ubiquitous inside modern multilevel solvers.

History

The Jacobi and Gauss-Seidel iterations date to the nineteenth century, while successive over-relaxation and its rigorous convergence theory were developed by David Young and Richard Varga in the 1950s; though later eclipsed by Krylov and multigrid methods as primary solvers, these iterations were revived as essential components of multilevel and preconditioned schemes.

Key figures

• Carl Friedrich Gauss
• Philipp Ludwig von Seidel
• David M. Young
• Richard S. Varga

Seminal works

• saad2003
• varga2000

Frequently asked questions

Why is Gauss-Seidel usually faster than Jacobi?

Gauss-Seidel immediately uses updated values within the same sweep, so information propagates faster through the unknowns, typically halving the number of iterations compared with Jacobi, which uses only values from the previous sweep.

If these methods are slow, why are they still studied?

They are excellent smoothers and simple preconditioners. Inside multigrid, a few Gauss-Seidel or weighted-Jacobi sweeps efficiently remove oscillatory error, which is exactly the role multigrid needs, so these classical iterations live on as components of fast modern solvers.