In
numerical mathematics, relaxation methods are
iterative method
In computational mathematics, an iterative method is a Algorithm, mathematical procedure that uses an initial value to generate a sequence of improving approximate solutions for a class of problems, in which the ''i''-th approximation (called an " ...
s for solving
systems of equations, including nonlinear systems.
Relaxation methods were developed for solving large
sparse linear systems, which arose as
finite-difference discretization
In applied mathematics, discretization is the process of transferring continuous functions, models, variables, and equations into discrete counterparts. This process is usually carried out as a first step toward making them suitable for numeri ...
s of
differential equations.
They are also used for the solution of linear equations for
linear least-squares problems
and also for systems of linear inequalities, such as those arising in
linear programming
Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements and objective are represented by linear function#As a polynomia ...
.
They have also been developed for solving nonlinear systems of equations.
Relaxation methods are important especially in the solution of linear systems used to model
elliptic partial differential equations, such as
Laplace's equation
In mathematics and physics, Laplace's equation is a second-order partial differential equation named after Pierre-Simon Laplace, who first studied its properties in 1786. This is often written as
\nabla^2\! f = 0 or \Delta f = 0,
where \Delt ...
and its generalization,
Poisson's equation. These equations describe
boundary-value problems, in which the solution-function's values are specified on boundary of a domain; the problem is to compute a solution also on its interior. Relaxation methods are used to solve the linear equations resulting from a discretization of the differential equation, for example by finite differences.
[ Richard S. Varga 2002 ''Matrix Iterative Analysis'', Second ed. (of 1962 Prentice Hall edition), Springer-Verlag.][ David M. Young, Jr. ''Iterative Solution of Large Linear Systems'', Academic Press, 1971. (reprinted by Dover, 2003)][Abraham Berman, Robert J. Plemmons, ''Nonnegative Matrices in the Mathematical Sciences'', 1994, SIAM. .]
Iterative relaxation of solutions is commonly dubbed
smoothing because with certain equations, such as
Laplace's equation
In mathematics and physics, Laplace's equation is a second-order partial differential equation named after Pierre-Simon Laplace, who first studied its properties in 1786. This is often written as
\nabla^2\! f = 0 or \Delta f = 0,
where \Delt ...
, it resembles repeated application of a local smoothing filter to the solution vector. These are not to be confused with
relaxation methods in
mathematical optimization
Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criteria, from some set of available alternatives. It is generally divided into two subfiel ...
, which
approximate
An approximation is anything that is intentionally similar but not exactly equal to something else.
Etymology and usage
The word ''approximation'' is derived from Latin ''approximatus'', from ''proximus'' meaning ''very near'' and the prefix ...
a difficult problem by a simpler problem whose "relaxed" solution provides information about the solution of the original problem.
Model problem of potential theory
When φ is a smooth
real-valued function
In mathematics, a real-valued function is a function whose values are real numbers. In other words, it is a function that assigns a real number to each member of its domain.
Real-valued functions of a real variable (commonly called ''real ...
on the real numbers, its
second derivative
In calculus, the second derivative, or the second-order derivative, of a function is the derivative of the derivative of . Informally, the second derivative can be phrased as "the rate of change of the rate of change"; for example, the secon ...
can be approximated by:
:
Using this in both dimensions for a function φ of two arguments at the point (''x'', ''y''), and solving for φ(''x'', ''y''), results in:
:
To approximate the solution of the Poisson equation:
:
numerically on a two-dimensional grid with grid spacing ''h'', the relaxation method assigns the given values of function φ to the grid points near the boundary and arbitrary values to the interior grid points, and then repeatedly performs the assignment
φ := φ* on the interior points, where φ* is defined by:
:
until convergence.
The method
is easily generalized to other numbers of dimensions.
Convergence and acceleration
While the method converges under general conditions, it typically makes slower progress than competing methods. Nonetheless, the study of relaxation methods remains a core part of
linear algebra
Linear algebra is the branch of mathematics concerning linear equations such as
:a_1x_1+\cdots +a_nx_n=b,
linear maps such as
:(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n,
and their representations in vector spaces and through matrix (mathemat ...
, because the transformations of relaxation theory provide excellent
preconditioners for new methods. Indeed, the choice of preconditioner is often more important than the choice of iterative method.
[ Yousef Saad, ]
Iterative Methods for Sparse Linear Systems
', 1st edition, PWS, 1996.
Multigrid methods may be used to accelerate the methods. One can first compute an approximation on a coarser grid – usually the double spacing 2''h'' – and use that solution with
interpolated values for the other grid points as the initial assignment. This can then also be done recursively for the coarser computation.
[William L. Briggs, Van Emden Henson, and Steve F. McCormick (2000), ]
A Multigrid Tutorial
'' (2nd ed.), Philadelphia: Society for Industrial and Applied Mathematics, .
See also
* In linear systems, the two main classes of relaxation methods are
stationary iterative methods, and the more general
Krylov subspace methods.
* The
Jacobi method is a simple relaxation method.
* The
Gauss–Seidel method is an improvement upon the Jacobi method.
*
Successive over-relaxation can be applied to either of the Jacobi and Gauss–Seidel methods to speed convergence.
*
Multigrid methods
Notes
References
* Abraham Berman, Robert J. Plemmons, ''Nonnegative Matrices in the Mathematical Sciences'', 1994, SIAM. .
*
*
*
Yousef Saad,
Iterative Methods for Sparse Linear Systems', 1st edition, PWS, 1996.
*
Richard S. Varga 2002 ''Matrix Iterative Analysis'', Second ed. (of 1962 Prentice Hall edition), Springer-Verlag.
*
David M. Young, Jr. ''Iterative Solution of Large Linear Systems'', Academic Press, 1971. (reprinted by Dover, 2003)
Further reading
* Southwell, R.V. (1940) ''Relaxation Methods in Engineering Science''. Oxford University Press, Oxford.
* Southwell, R.V. (1946) ''Relaxation Methods in Theoretical Physics''. Oxford University Press, Oxford.
*
*
*
* P. Grivet, P.W. Hawkes, A.Septier (1972). ''Electron Optics, 2nd edition''. Pergamon Press. .
* D. W. O. Heddle (2000). ''Electrostatic Lens Systems, 2nd edition''. CRC Press. .
* Erwin Kasper (2001). ''Advances in Imaging and Electron Physics, Vol. 116, Numerical Field Calculation for Charged Particle Optics''. Academic Press. {{ISBN, 978-0-12-014758-8.
Iterative methods
Numerical linear algebra