Préconditionneur

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

Description

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, on a écrit un préconditionneur à gauche^[1]. On peut 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}$

On peut, dans la même idée, écrire un préconditionneur à droite et à gauche, ou split preconditioner^[2], 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}}$

Exemples

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éconditionneurs simples

Ces préconditionneurs simples sont très utilisés pour leur intérêt pratique, car simples à calculer et efficaces pour des matrices creuses.

Dans la suite, on décompose A en trois matrices : A = D +L+U, avec D sa diagonale, L, une matrice triangulaire inférieure stricte et U, une matrice triangulaire supérieure stricte.

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=D.}$

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

Préconditionneur de Gauss-Seidel

La matrice P est choisie comme étant la partie inférieure de la matrice :.

${\displaystyle P=D+L.}$

SOR (Successive over-relaxation)

${\displaystyle P=\omega (D+\omega L),\omega >1.}$

SSOR (Symmetric successive over-relaxation)

${\displaystyle P={\frac {1}{\omega (2-\omega )}}(D+\omega L)D^{-1}(D+\omega U),\omega >1.}$

Inverses approchés

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.

Factorisations incomplètes

Les préconditionneurs reposant sur des factorisations incomplètes utilisent les résultats sur les décomposition de matrices en produit de matrices aux formes ou propriétés particulières. Ces matrices n'étant pas forcément aussi creuses et leur calcul pouvant être lui-même assez lourd, il est plus simple de chercher des approximations "aussi creuses" que A, et d'utiliser ces approximations comme préconditionneurs.

Cette méthode est intéressante dans le cas des matrices A creuses, pour lesquelles les matrices recherches seront aussi creuse que A : pour ${\displaystyle A=(A_{i,j})}$, pour une décomposition ${\displaystyle A=BC}$, on va imposer :

${\displaystyle \forall i,j,A_{i,j}=0\Longrightarrow B_{i,j}=0,C_{i,j}=0.}$

Factorisation LU incomplète

Pour une matrice A, on utilise la décomposition LU A = LU avec L une matrice triangulaire inférieure et U une matrice triangulaire supérieure dont tous les coefficients diagonaux sont égaux à 1. Le préconditionneur de la factorisation LU incomplète (ILU) pour A consiste à chercher deux matrices proches de L et U^[3],[4].

On désigne également cette factorisation par ILU(0), les factorisations ILU(k) reposent sur la décomposition LU de A^k+1.

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.

Sources

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

1. (en) Massimiliano Ferronato, « Review Article: Preconditioning for Sparse Linear Systems at the Dawn of the 21st Century: History, Current Developments, and Future Perspectives », International Scholarly Research Notices, vol. 2012,‎ octobre 2012, p. 49 (DOI 10.5402/2012/127647, lire en ligne)
2. John W. Pearson et Jennifer Pestana, « Preconditioners for Krylov subspace methods: An overview », Topical Issue Applied and Numerical Linear Algebra – Part II, GAMM-Mitteilungen, vol. 43, n^o 4,‎ novembre 2020 (DOI 10.1002/gamm.202000015)
3. (en) « Preconditioners based on Incomplete LU Factorization Technique »
4. (en) J. A. Meijerink et H. A. van der Vorst, « An Iterative Solution Method for Linear Systems of Which the Coefficient Matrix is a Symmetric M-Matrix », Mathematics of Computation, vol. 31, n^o 137,‎ janvier 1977, p. 148-162 (lire en ligne)

• Portail des mathématiques