Préconditionneur

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En algèbre linéaire et en analyse numérique, un préconditionneur P d'une matrice A est une matrice telle que le conditionnement de P^{-1}A est plus petit que celui de A.

Description[modifier | modifier le code]

Le préconditionnement est surtout utilisé dans les méthodes itératives pour la résolution d'un système linéaire (méthode du gradient, méthode du gradient conjugué, ...).

Au lieu de résoudre,

Ax=b\,

on préfère résoudre

P^{-1}Ax=P^{-1}b\,

qui permet de diminuer considérablement le nombre d'itérations dans la méthode de résolution (itérative). On dit que le système est "mieux" conditionné.


Ici, nous avons écrit un préconditionneur à gauche. Nous pouvons aussi écrire un préconditionneur à droite. Dans ce cas, la résolution se fait en deux temps:

AP^{-1} z=b\, et x=P^{-1}z


Nous pouvons, dans la même idée, écrire un préconditionneur à droite et à gauche, c'est-à-dire :

P^{-1}_1AP^{-1}_2z=P^{-1}_1b\, avec x=P^{-1}_2z et A \approx P_1P_2

Exemples[modifier | modifier le code]

En général, on ne calcule pas explicitement P, mais on utilise des algorithmes pour trouver un inverse approché de A. Dans certaines méthodes numériques (intégrales de frontières avec décomposition multipôles, ...), on préfère définir le produit matrice-vecteur, ce qui permet de réduire le stockage de(s) matrice(s), donc certains types de préconditionneur seront préférés.

Préconditionneur de Jacobi

Il s'agit d'un des préconditionneurs les plus simples : la matrice P est choisie comme étant la diagonale de la matrice du système A.

P=\mathrm{diag}(A).

Il est intéressant dans le cas des matrices à diagonale dominante.

SPAI (Sparse Approximate Inverse)

Le préconditionneur T=P-1 est la matrice minimisant \| AT-I \|_F, où \| \cdot \|_F est la norme de Frobenius. Cela revient à résoudre des problèmes de moindres carrés pour chaque colonne de la matrice A.

Factorisation de Cholesky incomplète

Dans le cas où A est symétrique définie positive, on sait qu'elle admet une décomposition appelée factorisation de Cholesky A=LLT avec L une matrice triangulaire inférieure. Le préconditionneur de la factorisation de Cholesky incomplète pour A consiste à chercher une matrice K proche de L en un certain sens. Usuellement, on cherche K à partir de la factorisation de Cholesky mais en fixant à zéro les coefficients de K si le coefficient correspondant de A est nul.

Cette méthode est intéressante dans le cas des matrices A creuses, pour lesquelles la matrice correspondante K est aussi creuse que A.

Sources[modifier | modifier le code]