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

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.

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

Liens

• (fr) La méthode du gradient conjugué
• (en) Le gradient conjugué sans peine

Ce document provient de « M%C3%A9thode du gradient conjugu%C3%A9 ».