La méthode du gradient conjugué préconditionné

La résolution de systèmes linéaires issus de la méthode des différences finies ou des éléments finis montre bien souvent les limites du gradient conjugué. En effet, le conditionnement de telles matrices est beaucoup trop élevé (valeurs propres mal réparties). La technique du préconditionnement consiste à introduire une matrice C subsidiaire.

Description du problème

Considérons le système suivant:

$Ax=b,$ où $A$ est une matrice de taille $n\times n$ symétrique définie positive ($A^{\mathrm{\top }}=A$ et $x^{\mathrm{\top }}Ax>0$, pour tout vecteur $x\in {\mathbf{R}}^n$ non nul).

Soit $x_{\star }$ la solution exacte de ce système.

Conditionnement

Il arrive parfois que le conditionnement $\kappa (A)$ de telles matrices soit beaucoup trop élevé (valeurs propres mal réparties). La technique du préconditionnement consiste à introduire une matrice $C\in {\mathcal{M}}_n(\mathbb{R})$ régulière et de résoudre le système:

$$C^{-1}(Ax)=C^{-1}b\iff Ax=b$$

tel que le nouveau conditionnement soit plus petit pour un choix judicieux de la matrice $C$.

Méthode du gradient conjugué préconditionné

Soit $x_0\in {\mathbb{R}}^n$ un vecteur initial quelconque, l’algorithme du gradient conjugué préconditionné est le suivant:

$$r_0=b-A{x}_0$$ $$z_0=C^{-1}{r}_0$$ $$d_0=z_0$$

Pour $k=0,1,2,\dots$

$${\alpha }_k=\frac{z_k^{\mathrm{\top }}{r}_k}{d_k^{\mathrm{\top }}A{d}_k}$$ $$x_{k+1}=x_k+{\alpha }_k{d}_k$$ $$r_{k+1}=r_k-{\alpha }_{k}A{d}_k$$ $$z_{k+1}=C^{-1}{r}_{k+1}$$ $${\beta }_{k+1}=\frac{z_{k+1}^{\mathrm{\top }}{r}_{k+1}}{z_k^{\mathrm{\top }}{r}_k}$$ $$d_{k+1}=z_{k+1}+{\beta }_{k+1}{d}_k$$

FinPour

Préconditionnement de Jacobi

Le préconditionnement de Jacobi consiste à  prendre pour matrice $C$ la diagonale de $A$, i.e.

$$C_{ij}=\{\begin{array}{cc}{A}_{ii}& \text{si }i=j,\\ 0& \text{sinon}.\end{array}$$

Les avantage d’un tel préconditionneur sont sans aucun doute la facilité de son implémentation et le peu d’espace mémoire qu’il occupe. D’un autre point de vue, on peut tout de màªme trouver des préconditionneurs apportant une plus grande amélioration de la résolution du système linéaire. C’est le cas du préconditionnement SSOR.

Préconditionnement SSOR(Symmetric Successive Over Relaxation)

On décompose la matrice symétrique $A$ comme suit:

$$A=L+D+L^{\mathrm{\top }}$$

où $L$ est la partie triangulaire à  diagonale nulle de la matrice $A$ et $D$ représente la diagonale de $A$. Le préconditionnement SSOR consiste à  prendre pour matrice

$$C=(\frac{D}{\omega }+L)\frac{\omega }{2-\omega }{D}^{-1}(\frac{D}{\omega }+L^{\mathrm{\top }})$$

où $\omega$ est appelé paramètre de relaxation. Une condition nécessaire et suffisante pour que la convergence du gradient conjugué préconditionné soit assuré est de fixer le paramètre $\omega$ dans l’intervalle $]0,2[$.