Conjugate Gradient Method - The Preconditioned Conjugate Gradient Method

The Preconditioned Conjugate Gradient Method

See also: Preconditioner

In most cases, preconditioning is necessary to ensure fast convergence of the conjugate gradient method. The preconditioned conjugate gradient method takes the following form:

repeat
if rk+1 is sufficiently small then exit loop end if
end repeat
The result is xk+1

The above formulation is equivalent to applying the conjugate gradient method without preconditioning to the system

where and .

The preconditioner matrix M has to be symmetric positive-definite and fixed, i.e., cannot change from iteration to iteration. If any of these assumptions on the preconditioner is violated, the behavior of the preconditioned conjugate gradient method may become unpredictable.

An example of a commonly used preconditioner is the incomplete Cholesky factorization.

Read more about this topic:  Conjugate Gradient Method

Famous quotes containing the word method:

    “I have a new method of poetry. All you got to do is look over your notebooks ... or lay down on a couch, and think of anything that comes into your head, especially the miseries.... Then arrange in lines of two, three or four words each, don’t bother about sentences, in sections of two, three or four lines each.”
    —Allen Ginsberg (b. 1926)