Conjugate gradient method

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 !