Méthode du gradient conjugué

Un article de Wikipédia, l'encyclopédie libre.

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 biconjugué fournit une généralisation pour les matrices non symétriques.

[modifier] 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.

[modifier] 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

[modifier] Liens