La méthode du gradient conjugué

Description du problème

Considérons le système suivant :

où

est une matrice de taille $n\times n$ symétrique définie positive ( $A^\top =A$ et $x^\top Ax>0$ , pour tout vecteur $x\in \mathbf{R}^n$ non nul). Soit $x_\star$ la solution exacte de ce système.

Directions conjuguées

Comme la matrice est symétrique définie positive, on peut définir le produit scalaire suivant sur $\mathbf{R}^n$ : $\langle u,v \rangle_A = u^\top A v.$ Deux éléments $u,v\in \mathbf{R}^n$ sont dit -conjugués si :

$u^\top A v = 0$

La méthode du gradient conjugué consiste à construire une suite $(p_k)_{k\in\mathbf{N}^*}$ de vecteurs -conjugués. Dès lors, la suite $p_1,p_2,\ldots,p_n$ forme une base de $\mathbf{R}^n$ . La solution exacte $x_\star$ peut donc se décomposer comme suit :

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

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

Construction des directions conjuguées

La solution exacte $x_\star$ peut-être également vu comme l’unique minimisant de la fonctionnelle $J(x) = \frac12 x^\top A x - b^\top x, \quad x\in\mathbf{R}^n$ On a donc clairement $\nabla J(x) = A x - b, \quad x\in\mathbf{R}^n$ d’où

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

On définit le résidu du système d’équation comme suit $r_k = b - Ax_k=-\nabla J(x_k)$

représente donc la direction du gradient de la fonctionnelle en (à un signe près).

La nouvelle direction de descente $p_{k+1}$ suit donc celle du résidu modulo, sa -conjugaison avec , on a alors :

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

C’est le choix du coefficient $\frac{p_k^\top A r_k}{p_k^\top A p_k}$ qui assure la -conjugaison des directions . Pour vous en assurez calculer $(Ap_{k+1},p_k)$ , cette quantité est nulle !