Gradient conjugué (méthode du)

Imaginez un point qui cherche le fond d’une cuvette elliptique. Suivre chaque fois la pente la plus forte peut faire zigzaguer d’un bord à l’autre. Le gradient conjugué choisit au contraire des directions qui ne défont pas le progrès déjà accompli.

Pour résoudre un grand système linéaire, la méthode part d’une estimation, mesure l’erreur restante, puis corrige cette estimation. Les directions successives sont accordées à la matrice du système. Dans un calcul exact à n inconnues, n corrections au plus suffisent ; souvent, une précision utile est atteinte avant.

La méthode du gradient conjugué résout un système linéaire dont la matrice A est symétrique définie positive. Le vecteur b est le second membre et le vecteur x est l’inconnue. Résoudre ce système revient aussi à minimiser la fonction quadratique $q(x)=\frac{1}{2}{x}^{T}Ax-b^{T}xq(x)=\backslash frac\{1\}\{2\}x^\{T\}Ax-b^\{T\}x$, qui possède alors un unique minimum.

À partir d’une estimation x₀, l’algorithme forme le résidu r₀, qui mesure le défaut dans l’équation, puis une première direction p₀. Les directions p_i et p_j sont dites A-conjuguées lorsque $p_i^{T}A{p}_j=0p\_i^\{T\}Ap\_j=0$ pour deux indices distincts i et j. Chaque pas minimise la fonction quadratique le long de la direction courante, tandis que la conjugaison préserve les minimisations précédentes.

En arithmétique exacte, les directions explorent au plus n dimensions indépendantes pour n inconnues, d’où une solution en au plus n itérations. Sur ordinateur, les arrondis peuvent altérer cette propriété : on arrête plutôt le calcul lorsque la norme du résidu est assez petite. La variante dite gradient conjugué non linéaire reprend l’idée de directions successives pour minimiser une fonction régulière, mais elle n’est pas le même algorithme que la résolution linéaire décrite ici.

Soient A une matrice symétrique définie positive, b le second membre et x₀ une estimation initiale. Le résidu initial et la première direction sont définis par r₀ = b − Ax₀ et p₀ = r₀. Si r₀ est nul, x₀ est déjà la solution. Sinon, tant que la norme du résidu reste strictement supérieure à la tolérance choisie, appliquer :

Le vecteur x obtenu à l’arrêt est la solution exacte si le résidu est nul, ou une approximation contrôlée par le critère d’arrêt sinon.

La version linéaire s’applique à un système carré Ax = b. La matrice A doit être symétrique, donc identique à sa transposée, et définie positive : pour tout vecteur non nul v, le nombre $v^{T}Avv^\{T\}Av$ est strictement positif. Ainsi, $p_k^{T}A{p}_{k}p\_k^\{T\}Ap\_k$ est positif si p_k est non nul, et $r_k^T{r}_{k}r\_k^\{T\}r\_k$ l’est si r_k est non nul. Si le résidu initial est nul, l’estimation est déjà la solution et aucune itération n’est effectuée. Ces conditions assurent aussi l’unicité de la solution. Il faut enfin pouvoir calculer le produit d’un vecteur par A à chaque itération.

Un contre-cas simple est la matrice diagonale ayant 1 et −1 sur sa diagonale : elle est symétrique, mais pas définie positive. Pour le vecteur porté par la seconde coordonnée, la quantité $v^{T}Avv^\{T\}Av$ est négative. Les garanties du gradient conjugué disparaissent alors ; il faut choisir une méthode adaptée à cette autre structure.

On résout un système à deux inconnues. La matrice A, le second membre b et l’estimation initiale x₀ sont :

1. Le résidu et la direction initiaux valent r₀ = p₀ = (1, 2). Le premier coefficient est α₀ = 1/4. On obtient x₁ = (1/4, 1/2), puis r₁ = (−1/2, 1/4).

2. Le coefficient suivant vaut β₀ = 1/16. La nouvelle direction est p₁ = (−7/16, 3/8). Le contrôle de conjugaison donne exactement $p_0^{T}A{p}_1=0p\_0^\{T\}Ap\_1=0$.

3. Avec α₁ = 4/11, la seconde correction conduit à x₂ = (1/11, 7/11). Le résidu r₂ est nul : l’algorithme s’arrête après deux itérations.

La trajectoire des deux corrections rend visible le changement de direction imposé par la conjugaison. Pour vérifier le résultat, on remplace x dans le système : 4/11 + 7/11 = 1 et 1/11 + 21/11 = 2.

Pour un grand système creux, on conserve seulement les coefficients non nuls et l’on calcule surtout des produits matrice-vecteur. Le gradient conjugué est pertinent lorsque la matrice est symétrique définie positive et qu’une factorisation directe demanderait trop de mémoire.

On suit la norme du résidu au fil des itérations. Si elle devient assez petite relativement au second membre, l’approximation est acceptée ; si elle stagne, on examine le conditionnement et l’effet des arrondis. Un préconditionnement peut transformer le système en un problème équivalent plus favorable.

Pour minimiser une fonction régulière qui n’est pas quadratique, on peut employer une variante non linéaire. Son choix de pas et sa mise à jour des directions demandent des règles propres ; on ne réutilise pas sans vérification la procédure du système linéaire.

Le gradient classique choisit à chaque étape la direction du résidu, donc la pente locale la plus forte. Le gradient conjugué combine le nouveau résidu avec la direction précédente afin d’obtenir des directions A-conjuguées. Sur une cuvette quadratique allongée, le premier peut zigzaguer tandis que le second préserve les progrès déjà réalisés.

Le gradient conjugué non linéaire peut s’appliquer à certains problèmes de minimisation suffisamment différentiables, sous des hypothèses et avec une recherche linéaire adaptées. La version linéaire vise Ax = b avec A symétrique définie positive. Pour une fonction non quadratique, cette variante est une méthode possible parmi d’autres, et ses formules de pas ne se réduisent pas nécessairement à celles données ici.

La borne de n itérations pour n inconnues suppose une arithmétique exacte. En calcul flottant, les arrondis font perdre progressivement l’orthogonalité des résidus et la conjugaison des directions. Un résidu non nul après n étapes n’est donc pas une contradiction ; on contrôle sa norme et l’on poursuit ou redémarre selon le niveau de précision recherché.

Une matrice très mal conditionnée peut produire une convergence lente bien qu’elle soit symétrique définie positive. Le symptôme est une baisse irrégulière ou trop faible du résidu. Un préconditionneur approprié cherche à resserrer la répartition des valeurs propres sans changer la solution du système.

Si le résidu initial est déjà nul, l’estimation x₀ est la solution et aucune division ne doit être effectuée. À l’inverse, si la matrice n’est pas définie positive, un dénominateur peut ne plus être strictement positif : la procédure et sa garantie ne s’appliquent plus.

La fiche Symétrique positive (matrice) approfondit la propriété qui garantit ici l’existence d’un unique minimum quadratique et la positivité des pas.

La fiche produit scalaire éclaire l’orthogonalité généralisée qui se cache derrière la conjugaison des directions par la matrice A.