Relaxation method

From Wikipedia, the free encyclopedia

This article is about the mathematical concept. For ways of making people relax, see Relaxation technique.

In numerical mathematics, the relaxation method is a method for obtaining numerical approximations to the solutions of systems of equations, including certain types of elliptic partial differential equations, in particular Laplace's equation and its generalization, Poisson's equation. The function is assumed to be given on the boundary of a shape, and has to be computed on its interior.

This relaxation method should not be confused with the unrelated relaxation technique in mathematical optimization.

[edit] Sketch

When φ is a smooth real-valued function on the real numbers, its second derivative can be approximated by:

$\frac{d^2}{{dx}^2}\varphi(x) = h^{-2}\left(\varphi(x{-}h)-2\varphi(x)+\varphi(x{+}h)\right)\,+\,\mathcal{O}(h^2)\,.$

Using this in both dimensions for a function φ of two arguments at the point (x, y), and solving for φ(x, y), results in:

$\varphi(x, y) = \tfrac{1}{4}\left(\varphi(x{+}h,y)+\varphi(x,y{+}h)+\varphi(x{-}h,y)+\varphi(x,y{-}h) \,-\,h^2{\nabla}^2\varphi(x,y)\right)\,+\,\mathcal{O}(h^4)\,.$

To approximate the solution of the Poisson equation:

${\nabla}^2 \varphi = f\,$

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:

$\varphi^*(x, y) = \tfrac{1}{4}\left(\varphi(x{+}h,y)+\varphi(x,y{+}h)+\varphi(x{-}h,y)+\varphi(x,y{-}h) \,-\,h^2f(x,y)\right)\,,$

until convergence.

The method, sketched here for two dimensions, is readily generalized to other numbers of dimensions.

[edit] Convergence and acceleration

While the method always converges, it does so very slowly. To speed up the computation, one can first compute an approximation on a coarser grid – usually the double spacing 2h – 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.

[edit] See Also

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 either the Jacobi or Gauss–Seidel methods to speed convergence