Méthode du gradient conjugué

La méthode du gradient conjugué est une méthode itérative pour résoudre une équation $Ax=b$, avec $A$ une matrice symétrique définie positive, ou, de façon équivalente, pour trouver le minimum de la fonction $$f(x)=\langle Ax,x\rangle +\langle b,x\rangle.$$ Il s'agit d'une méthode de descente, c'est-à-dire que la suite construite $(x_k)$ est définie par son premier terme $x_0$ et une relation de récurrence $$x_{k+1}=x_k+\rho_k d_k$$ où $\rho_k$ est un pas, et $d_k$ est une direction de descente. La particularité de cette méthode est que les directions de descente $d_k$ sont construites de sorte que les gradients $\nabla f (x_k)$ soient tous orthogonaux deux à deux : $$\forall 0\leq k< j,\ \langle \nabla f(x_k),\nabla f(x_j)\rangle=0.$$ Pour la méthode du gradient à pas optimal, seuls deux gradients successifs sont orthogonaux. De plus, le choix de ces directions de descente et du pas $\rho_k$ font que $x_k$ réalise le minimum de $f$ sur l'espace affine $x_0+\textrm{vect}(\nabla f(x_0),\dots,\nabla f(x_{k-1}))$.

Ainsi, la méthode du gradient conjugué est une méthode exacte qui donne en un nombre fini d'itérations, inférieur ou égal à $n$, la valeur du minimum de $f$, ou la solution de $Ax=b$. Néanmoins, elle est presque toujours utilisée pour fournir une solution approchée, la convergence de $(x_k)$ vers sa limite étant en général rapide.

Les différents paramètres intervenant à chaque itération sont définis de la façon suivante : $$\rho_k=-\frac{\langle \nabla f (x_k), d_k)}{\langle d_k, A d_k\rangle}$$ $$\left\{ \begin{array}{rcl} \nabla f(x_0)&=&Ax_0-b\\ \nabla f(x_{k+1})&=&\nabla f(x_k)+\rho_k A d_k \end{array}\right.$$ $$ \left\{ \begin{array}{rcl} d_0&=&-\nabla f(x_0)\\ d_{k+1}&=&-\nabla f(x_{k+1})+ \frac{\langle \nabla f(x_{k+1}),\nabla f(x_{k+1})\rangle}{\langle \nabla f(x_k),\nabla f(x_k)\rangle}d_k. \end{array}\right.$$