Méthode du gradient conjugué

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 f: x \mapsto \frac{1}{2} (Ax,x) -(b,x) 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 \nabla f \left ( x \right) = Ax-b .

La méthode du gradient conjugué consiste donc à construire par récurrence une base de vecteurs de \mathbb{R}^n orthogonaux pour le produit scalaire \left (x , y \right ) \mapsto (Ax,y) , 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 \| x_N - x\| < \varepsilon (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


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Méthode du gradient conjugué de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • Methode du gradient conjugue — 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 symétrique et définie positive. Cette méthode est une méthode itérative. La… …   Wikipédia en Français

  • 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 symétrique et définie positive. Cette méthode est une méthode itérative. La méthode du gradient… …   Wikipédia en Français

  • Gradient conjugué — 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 symétrique et définie positive. Cette méthode est une méthode itérative. La… …   Wikipédia en Français

  • Methode du gradient biconjugue — Méthode du gradient biconjugué En mathématiques, plus spécifiquement en analyse numérique, la méthode du gradient biconjugué est un algorithme permettant de résoudre un système d équations linéaires Contrairement à la méthode du gradient conjugué …   Wikipédia en Français

  • Méthode Du Gradient Biconjugué — En mathématiques, plus spécifiquement en analyse numérique, la méthode du gradient biconjugué est un algorithme permettant de résoudre un système d équations linéaires Contrairement à la méthode du gradient conjugué, cet algorithme ne nécessite… …   Wikipédia en Français

  • Méthode du gradient biconjugué — En mathématiques, plus spécifiquement en analyse numérique, la méthode du gradient biconjugué est un algorithme permettant de résoudre un système d équations linéaires Contrairement à la méthode du gradient conjugué, cet algorithme ne nécessite… …   Wikipédia en Français

  • Méthode de résolution numérique — Analyse numérique Simulation numérique d un crash de véhicule L’analyse numérique est une discipline des mathématiques. Elle s’intéresse tant aux fondements théoriques qu’à la mise en pratique des méthodes permettant de résoudre, par des calculs… …   Wikipédia en Français

  • Méthode numérique — Analyse numérique Simulation numérique d un crash de véhicule L’analyse numérique est une discipline des mathématiques. Elle s’intéresse tant aux fondements théoriques qu’à la mise en pratique des méthodes permettant de résoudre, par des calculs… …   Wikipédia en Français

  • Algorithme du gradient — L algorithme du gradient désigne un algorithme d optimisation différentiable. Il est par conséquent destiné à minimiser une fonction réelle différentiable définie sur un espace euclidien (par exemple, , l espace des n uplets de nombres réels,… …   Wikipédia en Français

  • Descente De Gradient — Traduction à relire Gradient descent → …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”