Math-Linux.com

Knowledge base dedicated to Linux and applied mathematics.

Accueil > Mathématiques > Résolution de systèmes linéaires > La méthode du gradient conjugué préconditionné

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

Toutes les versions de cet article : [English] [français]

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\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 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-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 C la diagonale de A, 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 A comme suit :

A=L+D+L^{\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^{\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[.

Un message, un commentaire ?

comments powered by Disqus