- Méthode du gradient conjugué
-
En analyse numérique, la méthode du gradient conjugué est un algorithme pour résoudre des systèmes d'équations linéaires dont la matrice est définie positive (et par conséquent symétrique). Cette méthode, imaginée en 1950 simultanément par Cornelius Lanczos et Magnus Hestenes, est une méthode itérative qui converge en fait en un nombre fini d'itérations (au plus égal à la dimension du système linéaire). Toutefois, son grand intérêt pratique du point de vue du temps de calcul vient de ce qu’une initialisation astucieuse (dite « préconditionnement ») permet d'aboutir en seulement quelques passages à une estimation très proche de la solution exacte, et c'est pourquoi en pratique on se borne à un nombre d'itérations bien inférieur au nombre d'inconnues.
La méthode du gradient biconjugué fournit une généralisation pour les matrices non symétriques.
Sommaire
Principe
L'objectif est de minimiser la fonction où A est une matrice carrée symétrique définie positive de taille n.
Le calcul montre qu'une solution du problème est la solution du système Ax = b : en effet , on a .
La méthode du gradient conjugué consiste donc à construire par récurrence une base de vecteurs de orthogonaux pour le produit scalaire , et exprimer le vecteur solution dans cette base.
Pour amorcer la récurrence, il faut bien partir d’une estimation initiale x0 du vecteur x recherché ; et le nombre d'itérations N nécessaire pour que (où ε est un nombre positif arbitrairement proche de zéro) dépend naturellement du x0 choisi. On peut dire que « tous les coups sont permis » pour obtenir une estimation initiale accélérant la convergence ; malheureusement, les méthodes de « préconditionnement » à la fois sûres et générales (c'est-à-dire efficaces pour toutes sortes de matrices symétriques positives) pour former un x0 correct sont aussi elles-mêmes coûteuses en temps de calcul! En pratique, l'intuition physique, guidée par la nature physique du problème à résoudre, suggère parfois une initialisation efficace : ces idées ont donné lieu depuis plus de trente ans à une littérature spécialisée abondante.
Implémentation
Un exemple d'implémentation pour Octave:
function [x] = conjgrad(A,b,x0) r = b - A*x0; w = -r; z = A*w; a = (r'*w)/(w'*z); x = x0 + a*w; B = 0; for i = 1:size(A)(1); r = r - a*z; if( r < 1e-10 ) break; endif B = (r'*z)/(w'*z); w = -r + B*w; z = A*w; a = (r'*w)/(w'*z); x = x + a*w; end endfunction
Solveur
- M1CG1 - A solver of symmetric linear systems by conjugate gradient iterations, using/building a BFGS/ℓ-BFGS preconditioner. Écrit en Fortran-77. Le solveur a l'intérêt d'offrir la possibilité de construire un préconditionneur BFGS ou ℓ-BFGS (en), qui pourra être utile pour la résolution d'un système linéaire avec une matrice proche et un second membre différent.
Bibliographie
- Philippe Ciarlet, Introduction à l’analyse numérique matricielle et à l’optimisation, Masson, coll. « Math. Appl. pour la Maîtrise », 1985 (réimpr. 2001) (ISBN 2-225-68893-1)
- Dianne P. O'Leary (dir.), Linear and nonlinear Conjugate gradient-related Methods, AMS-SIAM, 1996, « Conjugate gradient and related KMP algorithms : the Beginnings »
Liens
Catégorie :- Analyse numérique matricielle
Wikimedia Foundation. 2010.