Home > Mathematics > Linear Systems > **Conjugate gradient method**

# Conjugate gradient method

Saturday 19 August 2006, by

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

I will study here the Conjugate Gradient Method. This numerical method allows you to solve linear systems whose matrix is symmetric and positive definite. The search for successive directions makes possible to reach the exact solution of the linear system.

### Problem

We want to solve the following linear system:

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

Let be the exact solution of this linear system.

### Conjugate directions

As the matrix is symmetric and positive definite, we can define the following scalar product on :

Two elements are -conjuguate if:

Conjugate Gradient Method consists in building a vectorial sequence of -conjugate vectors . Consequently, the sequence form a basis of . The exact solution can be expanded like follows:

where

### Construction of Conjugate directions

The exact solution is also the unique one minimizer of the functionnal

We have clearly

so

We define the residual vector of the linear system

is the direction of the gradient of the functional in .

The new direction of descent is the same as its -conjugaison with , we have then:

It is the choice of the coefficient wich allows the -conjugaison of the directions . If you want you can calculate , it is zero !

### Conjugate Gradient Algorirthm

We calculate the residual for any vector . We fix .

For

If

Else

EndIf