Home > Mathematics > Linear Systems > Conjugate gradient method

Conjugate gradient method

Saturday 19 August 2006, by Nadir SOUALEM

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 $n\times n$ symmetric and positive definite matrix ( $A^\top =A$ and $x^\top Ax>0$ , for all $x\in \mathbf{R}^n$ non-zero).
Let $x_\star$ 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 $\mathbf{R}^n$ :
$\langle u,v \rangle_A = u^\top A v.$
Two elements $u,v\in \mathbf{R}^n$ are -conjuguate if:

$u^\top A v = 0$

Conjugate Gradient Method consists in building a vectorial sequence $(p_k)_{k\in\mathbf{N}^*}$ of -conjugate vectors . Consequently, the sequence $p_1,p_2,\ldots,p_n$ form a basis of $\mathbf{R}^n$ . The exact solution $x_\star$ can be expanded like follows:

$x_\star = \alpha_1 p_1 + \cdots + \alpha_n p_n$

where $\alpha_k = \frac{p_k^\top b}{p_k^\top A p_k},k=1,\ldots,n.$

Construction of Conjugate directions

The exact solution $x_\star$ is also the unique one minimizer of the functionnal
$J(x) = \frac12 x^\top A x - b^\top x, \quad x\in\mathbf{R}^n$
We have clearly $\nabla J(x) = A x - b, \quad x\in\mathbf{R}^n$
so

$\nabla J(x_\star)=0_{\mathbf{R}^n}$

We define the residual vector of the linear system
$r_k = b - Ax_k=-\nabla J(x_k)$

is the direction of the gradient of the functional in .

The new direction of descent $p_{k+1}$ is the same as its -conjugaison with , we have then:

$p_{k+1} = r_k - \frac{p_k^\top A r_k}{p_k^\top A p_k} p_k$

It is the choice of the coefficient $\frac{p_k^\top A r_k}{p_k^\top A p_k}$ wich allows the -conjugaison of the directions . If you want you can calculate $(Ap_{k+1},p_k)$ , it is zero !

Conjugate Gradient Algorirthm

We calculate the residual for any vector . We fix .

For $k=1,2,\ldots$

$p_1=r_{0}$

Else

$\beta_{k-1}= \frac{r_{k-1}^\top r_{k-1}}{r_{k-2}^\top r_{k-2}}$

$p_k=r_{k-1} + \beta_{k-1}p_{k-1}$

EndIf

$\alpha_k=\frac{r_{k-1}^\top r_{k-1}}{p_k^\top q_k}$

$x_k=x_{k-1}+\alpha_k p_k$

$r_k=r_{k-1}-\alpha_k q_k$

Forum posts

1. Conjugate gradient method, 16 April, 19:39, by Ortos

The humanity has made a great breakthrough in exploring the planet, the space and the waters in the last couple of centuries. That was a case of a talent to see such a degree of thinkings. People would surely use certain amount of reasonable ideas given here in professional custom compare and contrast essay for students. Feeling high to find one more clever person.

Any message or comments?

Forum registration required

You must be registered before participating in this forum. Please enter your personal identifier . If you have not yet registered, you must register.

Connection | register | password forgotten?

If you want to help Math-Linux.com project , Send your contributions to our team. Thanks !!!

Links