Richardson (méthode de)

On cherche deux nombres qui satisfont simultanément deux équations. Au lieu de les trouver d’un coup, on part d’une estimation, on mesure l’écart restant dans chaque équation, puis on corrige cette estimation. La méthode de Richardson répète ce geste jusqu’à ce que l’écart devienne suffisamment petit.

Le réglage appelé paramètre de relaxation détermine la taille de chaque correction. Trop mal choisi, il peut ralentir les progrès ou faire diverger les estimations. Bien choisi, il réduit régulièrement l’erreur.

La méthode de Richardson résout de manière itérative un système linéaire dont la matrice est notée $AA$, le vecteur inconnu $xx$ et le second membre $bb$. À partir d’une estimation initiale, notée $x_{0}x\_0$, elle calcule le résidu, c’est-à-dire l’écart $b-A{x}_{k}b-Ax\_k$ laissé à l’étape numéro $kk$, puis ajoute une fraction de cet écart à l’estimation courante.

Le paramètre de relaxation est noté $\omega \backslash omega$. L’erreur est multipliée à chaque étape par la matrice d’itération $I-\omega AI-\backslash omega\; A$, où $II$ désigne la matrice identité. La suite converge depuis toute estimation initiale lorsque le rayon spectral de cette matrice, c’est-à-dire le plus grand module de ses valeurs propres, est strictement inférieur à 1.

Dans la version stationnaire, $\omega \backslash omega$ reste fixe. Dans une version dynamique, sa valeur change avec l’itération. Un choix optimal dépend du spectre de $AA$ et cherche à minimiser le rayon spectral, donc le facteur asymptotique de réduction de l’erreur.

On dispose de la matrice $AA$, du second membre $bb$, d’une estimation initiale $x_{0}x\_0$ et d’un paramètre de relaxation $\omega \backslash omega$. Pour chaque entier $k\ge 0k\backslash geq\; 0$, la règle est :

On s’arrête lorsque le résidu est assez petit pour la précision recherchée. Si $\rho (I-\omega A)<1\backslash rho\backslash left(I-\backslash omega\; A\backslash right)\backslash lt\; 1$, où $\rho \backslash rho$ désigne le rayon spectral, les estimations convergent vers la solution du système.

La méthode s’applique à un système linéaire $Ax=bAx=b$. Il faut pouvoir calculer le produit de la matrice $AA$ par un vecteur, choisir une estimation initiale et fixer, ou adapter, le paramètre de relaxation $\omega \backslash omega$. Lorsque $\omega \backslash omega$ est fixe, le critère vérifiable de convergence depuis toute estimation initiale est $\rho (I-\omega A)<1\backslash rho\backslash left(I-\backslash omega\; A\backslash right)\backslash lt\; 1$. Une version dynamique exige une analyse distincte de la suite des matrices d’itération.

Si ce rayon spectral vaut 1 ou le dépasse, la garantie disparaît : certaines composantes de l’erreur peuvent persister ou croître. Il faut alors changer $\omega \backslash omega$, employer une version dynamique convenablement réglée, ou choisir une autre méthode de résolution. Un petit résidu fournit le point d’arrêt pratique, mais sa tolérance doit correspondre à la précision attendue.

Résolvons un système à deux inconnues. La matrice est diagonale, avec 2 et 4 sur sa diagonale ; le second membre a pour coordonnées 2 et 8. On part du vecteur nul et on choisit le paramètre $\omega =1\mathrm{/}4\backslash omega=1/4$.

1. Le premier résidu est égal au second membre. La première correction donne $x_1=(1\mathrm{/}2,2)x\_1=\backslash left(1/2,2\backslash right)$.

2. Le nouveau résidu vaut $b-A{x}_1=(1,0)b-Ax\_1=\backslash left(1,0\backslash right)$. On obtient donc $x_2=(3\mathrm{/}4,2)x\_2=\backslash left(3/4,2\backslash right)$.

3. L’itération suivante donne $x_3=(7\mathrm{/}8,2)x\_3=\backslash left(7/8,2\backslash right)$. La seconde coordonnée est exacte dès la première étape ; l’erreur de la première est divisée par 2 à chaque correction.

La solution exacte est $x=(1,2)x=\backslash left(1,2\backslash right)$. Le contrôle consiste à multiplier : $Ax=(2,8)=bAx=\backslash left(2,8\backslash right)=b$. Ici, la matrice d’itération a pour valeurs propres $1\mathrm{/}21/2$ et 0 ; son rayon spectral vaut donc $1\mathrm{/}2<11/2\backslash lt\; 1$.

Pour un grand système, chaque étape demande surtout de calculer un produit matrice-vecteur et un résidu. Cette structure rend la méthode intéressante lorsque ce produit est peu coûteux et que l’on accepte une solution approchée.

On surveille le résidu après chaque correction. S’il diminue avec une régularité suffisante, on poursuit jusqu’à la tolérance fixée ; s’il stagne ou augmente, on revoit le paramètre de relaxation au lieu d’accumuler des itérations inutiles.

Un paramètre fixe convient lorsque le spectre est assez bien encadré pour garantir la convergence. Une version dynamique devient préférable lorsque l’on veut ajuster la taille des corrections au fil du calcul.

L’itération de Richardson et l’extrapolation de Richardson. La première corrige un vecteur à l’aide du résidu d’un système $Ax=bAx=b$. La seconde accélère une suite d’approximations en éliminant un terme d’erreur dominant. Un calcul qui combine des approximations obtenues avec plusieurs pas relève de l’extrapolation, pas de l’itération décrite dans cette fiche.

Paramètre stationnaire et paramètre dynamique. Ce ne sont pas deux noms pour un même réglage : dans le premier cas, $\omega \backslash omega$ garde la même valeur à toutes les étapes ; dans le second, il dépend de l’étape. Il suffit donc de vérifier si la taille de correction change au cours du calcul.

Seuil de convergence. La condition porte sur une inégalité stricte. Un rayon spectral égal à 1 n’est pas « presque convergent » au sens du critère : une composante de l’erreur peut ne pas décroître. Il faut modifier le paramètre ou la méthode.

Correction trop agressive. Augmenter $\omega \backslash omega$ n’accélère pas automatiquement le calcul. Si ce choix porte $\rho (I-\omega A)\backslash rho\backslash left(I-\backslash omega\; A\backslash right)$ à 1 ou au-delà, les résidus cessent de décroître régulièrement. Il faut choisir le paramètre à partir du spectre, et non de sa seule grandeur apparente.

Résidu et erreur. Le résidu mesure le défaut dans les équations ; il n’est pas, en général, le vecteur d’erreur lui-même. Pour éviter une conclusion trompeuse, le seuil d’arrêt doit être relié à la précision recherchée et au comportement de la matrice.

Le rayon spectral fournit le critère qui décide si l’erreur est contractée par la matrice d’itération.

La notion de valeur propre permet de comprendre comment chaque direction propre de l’erreur est amplifiée ou réduite à chaque étape.