Preconditioner

From Wikipedia, the free encyclopedia

You have new messages (last change).

In linear algebra and numerical analysis, a preconditioner P of a matrix A is a matrix such that P−1A has a smaller condition number than A. A preconditioner as defined here is also known as a left preconditioner; there are also right preconditioners, but they are not discussed in this article.

Preconditioners are useful when using an iterative method to solve a large, sparse linear system

Ax = b\,

for x. Solving the preconditioned system

P^{-1}Ax = P^{-1}b,\,

is equivalent to solving the original system. However, the preconditioned system has a smaller condition number; it is better conditioned. The number of iterations used to solve the system increases with the condition number so by reducing the number of needed iterations (if the cost — computing time — of applying P-1 is small), a gain in efficiency is achieved.

The matrix P−1A is almost never explicitly formed. In using an iterative method, only the action of applying P−1 to a given vector need be computed.

The desired effect in a applying a preconditioner is to make the quadratic form of P − 1A be nearly spherical[1]

Contents

[edit] Examples

[edit] Jacobi preconditioner

The Jacobi preconditioner is the diagonal of the matrix. That is,

P_{ij} = A_{ii}\delta_{ij} = \begin{cases}A_{ii} & i=j \\ 0 &\mbox{otherwise}\end{cases}

and so

P^{-1}_{ij} = \frac{\delta_{ij}}{A_{ii}}.

[edit] SSOR

The SSOR (Symmetric Successive Over Relaxation) preconditioner factors A as follows:

A = L + D + LT

where L is the lower part of A and D the diagonal part of A. SSOR then takes P to be

P=\left(\frac{D}{\omega}+L\right)\frac{\omega}{2-\omega}D^{-1}\left(\frac{D}{\omega}+L^{\top}\right)

where ω is a "relaxation parameter" between 0 and 2, exclusive.

[edit] See also

[edit] External links

Retrieved from "http://en.wikipedia.org../../../p/r/e/Preconditioner.html"
In other languages