Un algorithme itératif pour résoudre de grands systèmes linéaires symétriques définis positifs Ax = b et pour minimiser des fonctions quadratiques en générant des directions de recherche A-conjuguées qui convergent vers la solution exacte en au plus n étapes en arithmétique exacte.

Principe

Construire des directions de recherche conjuguées par rapport à la matrice système A de sorte que les corrections le long des directions successives éliminent les composantes orthogonales de l'erreur ; utiliser des récurrences courtes pour mettre à jour la solution, le résidu et la direction sans stocker une base de Krylov complète.

Démonstration

Résoudre une équation de Poisson discrétisée sur une grille : représenter l'opérateur de Laplace par une matrice creuse SPD A et appliquer le gradient conjugué pour réduire itérativement la norme d'énergie de l'erreur jusqu'à atteindre les tolérances sur le résidu ou l'énergie, en utilisant un préconditionneur pour accélérer la convergence.

Mauvaise application

Appliquer le gradient conjugué non modifié à des matrices non symétriques ou indéfinies (sans recourir à GMRES ou MINRES) ou utiliser de mauvais préconditionneurs, ce qui peut provoquer stagnation, rupture ou lenteur de convergence.

Conséquence

Pour des problèmes creux SPD de grande taille, le GC offre des résolutions itératives économes en mémoire avec une convergence rapide quand les valeurs propres sont regroupées ou quand de bons préconditionneurs sont disponibles ; en arithmétique exacte, il garantit l'arrêt en nombre fini d'étapes et en pratique une approximation rapide.

Inversion

Les méthodes directes comme la factorisation de Cholesky calculent des solutions exactes via une décomposition matricielle, évitant l'itération mais au prix d'un coût mémoire et de factorisation plus élevé pour des systèmes creux très grands comparé au GC.

Limite

Destiné aux systèmes symétriques définis positifs ou aux minimisations quadratiques équivalentes ; il exclut les problèmes non symétriques, fortement indéfinis ou sévèrement mal conditionnés sauf s'il est adapté par préconditionnement, réorthogonalisation ou remplacement par des méthodes de Krylov plus générales.

Tension sémantique

Tension entre GC et d'autres méthodes de Krylov (GMRES, BiCGStab) concernant la symétrie et le stockage : le GC est optimal pour les systèmes SPD avec stockage minimal et récurrences courtes, tandis que d'autres méthodes acceptent la non symétrie au prix d'un stockage ou d'une complexité accrue.

Synthèse

Le gradient conjugué transforme la résolution linéaire en une suite de minimisations unidimensionnelles le long de directions A-conjuguées, offrant une utilisation mémoire efficace et une convergence rapide pour les systèmes creux SPD ; ses performances pratiques dépendent fortement de la distribution spectrale et du préconditionnement.