Préconditionneur

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,

${\displaystyle Ax=b\,}$

on préfère résoudre

${\displaystyle 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:

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

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

${\displaystyle P_{1}^{-1}AP_{2}^{-1}z=P_{1}^{-1}b\,}$ avec ${\displaystyle x=P_{2}^{-1}z}$ et ${\displaystyle A\approx P_{1}P_{2}}$

En général, on ne calcule pas explicitement ${\displaystyle P}$, mais on utilise des algorithmes pour trouver un inverse approché de ${\displaystyle 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.

${\displaystyle 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 ${\displaystyle \|AT-I\|_{F}}$, où ${\displaystyle \|\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=LL^T 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.

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « preconditioner » (voir la liste des auteurs).

• Portail des mathématiques