Conjugate Gradient Method - The Preconditioned Conjugate Gradient Method

The Preconditioned Conjugate Gradient Method

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 r_k+1 is sufficiently small then exit loop end if

end repeat

The result is x_k+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.