Relaxation (iterative method)

Relaxation methods are iterative methods in numerical mathematics for solving systems of equations, including nonlinear systems. They were developed for large sparse linear systems that arise when differential equations are discretized by finite differences, and they are also used for linear least-squares problems and for systems of linear inequalities such as those in linear programming. They matter most for the linear systems that model elliptic partial differential equations such as Laplace's equation and Poisson's equation, where values are fixed on the boundary of a domain and the solution is computed on its interior. On a grid, the method starts from the boundary values and arbitrary interior values and repeatedly replaces each interior value by an average of its neighbours, adjusted for the source term, until the values converge. Because this resembles repeated local smoothing, the process is often called smoothing. Convergence is usually slower than competing methods, yet relaxation theory supplies good preconditioners, and multigrid methods can accelerate it. The Jacobi method, the Gauss-Seidel method and successive over-relaxation are well known examples. It should not be confused with relaxation in mathematical optimization, which replaces a hard problem by a simpler one.