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

Description du problème

Considérons le système suivant :

où

est une matrice de taille $n\timesn$ symétrique définie positive ( $A^\top =A$ et $x^\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\Leftrightarrow Ax=b$

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

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-Ax_{0}$

$z_{0}={C}^{-1}r_{0}$

$d_{0}=z_{0}$

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

$\alpha_k={{z_{k}^{\top}r_{k}}\over{{ d}_k^{\top}Ad_k}}$

$x_{k+1}=x_{k}+\alpha_kd_k$

$r_{k+1}=r_{k}-\alpha_kAd_k$

$z_{k+1}={C}^{-1}r_{k+1}$

$\beta_{k+1}={{z_{k+1}^{\top}r_{k+1} } \over { z_{k}^{\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 la diagonale de , i.e.

$C_{ij}= \left\{ \begin{array}{cc} A_{ii} & \textrm{si }i=j ,\\ 0 &\textrm{sinon}. \end{array} \right.$

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 comme suit :

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

où

est la partie triangulaire à diagonale nulle de la matrice

représente la diagonale de

. Le préconditionnement SSOR consiste à prendre pour matrice

$C=(\frac{D}{\omega}+L)\frac{\omega}{2-\omega}D^{-1}(\frac{D}{\omega}+L^{\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

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

Mots-clés:

Description du problème

Conditionnement

Méthode du gradient conjugué préconditionné

Préconditionnement de Jacobi

Préconditionnement SSOR(Symmetric Successive Over Relaxation)

Rubriques

Dans la même rubrique

Mots-clés