Accueil > Mathématiques > Résolution de systèmes linéaires > La méthode du gradient conjugué

La méthode du gradient conjugué

mercredi 12 octobre 2005, par Nadir SOUALEM

Mots-clés: algorithme , descente , direction conjuguée , gradient conjugué , méthode , méthode itérative , résidu , résolution , système linéaire .

Toutes les versions de cet article : [English] [français]

Je vous présente ici la méthode du gradient conjugué. Cette méthode numérique permet de résoudre de grands systèmes linéaires dont la matrice est symétrique définie positive. Elle repose sur la recherche de directions successives permettant d’atteindre la solution exacte du système étudié.

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 !