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:

    ““English! they are barbarians; they don’t believe in the great God.” I told him, “Excuse me, Sir. We do believe in God, and in Jesus Christ too.” “Um,” says he, “and in the Pope?” “No.” “And why?” This was a puzzling question in these circumstances.... I thought I would try a method of my own, and very gravely replied, “Because we are too far off.” A very new argument against the universal infallibility of the Pope.”
    —James Boswell (1740–1795)