Knowledge base dedicated to Linux and applied mathematics.

Home > Mathematics > Linear Systems > **Preconditioned Conjugate Gradient Method**

All the versions of this article: [English] [français]

Solving linear systems resulting from the finite differences method or of the finite elements shows the limits of the conjugate gradient. Indeed, Spectral condition number of such matrices is too high. The technique of Preconditioned Conjugate Gradient Method consists in introducing a matrix C subsidiary.

We want to solve the following system:

where is a symmetric definite and positive matrix( and , for all non zero).

Let be the exact solution of this system.

It happens sometimes that the spectral condition number is too high (eigenvalues are not well distributed). Preconditionnement

consists in introducing regular matrix and solving the system:

such that the new spectral condition number is smaller for a judicious choice of the matrix .

Let be an intial vector, Preconditioned Gradient Method algorithm

is the following one:

For

EndFor

Jacobi Preconditioner consists in taking the diagonal of for the matrix , i.e.

Advantages of such preconditioner are the facility of its implementation and the low memory it needs.

But we can find other preconditioners such that resolution of the linear system is fastest, it is the case of the

SSOR Preconditioner.

We decompose the symmetric matrix like follows:

where is the strictly lower part of and is the diagonal of . SSOR Preconditioner consists

in taking

where is a relaxation parameter. A necessary and sufficient condition of the Preconditioned Gradient Method

algorithm is to fix the parameter in the interval .