Les critères de convergence

1. Un test d’arrêt basé sur l’incrément

D’après la rélation de récurrence sur l’érreur \(\mathbf{e}^{(k+1)}=B\mathbf{e}^{(k)}\), on a

\[\| \mathbf{e}^{(k+1)}\| \leq \| B\| \| \mathbf{e}^{(k)}\| \label{rec1}\]

En utilisant l’inégalité triangulaire, on a

\[\|\mathbf{e}^{(k+1)}\|\leq \|B \|(\|\mathbf{e}^{(k+1)}\|+\|\mathbf{x}^{(k+1)}-\mathbf{x}^{(k)}\|)\]

et donc

\[\|\mathbf{x}-\mathbf{x}^{(k+1)}\|\leq \frac{\|B\|}{1-\|B\|}\|\mathbf{x}^{(k+1)}-\mathbf{x}^{(k)}\| \label{rec2}\]

En particulier, en prenant \(k=0\) dans [eq24] et en appliquant la formule de récurrence [eq23] on obtient aussi l’inégalité

\[\|\mathbf{x}-\mathbf{x}^{(k+1)} \|\leq \frac{\|B\|^{k+1}}{1-\|B\|}\|\mathbf{x}^{(1)}-\mathbf{x}^{(0)}\|\]

qu’on peut utiliser pour estimer le nombre d’itérations nécessaire à satisfaire la condition \(\| \mathbf{e}^{(k+1)}\|\leq \varepsilon\), pour une tolérance \(\varepsilon\) donnée.

En pratique, on peut estimer \(\| B\|\) comme suit: puisque

\[\mathbf{x}^{(k+1)}-\mathbf{x}^{(k)}=-(\mathbf{x}-\mathbf{x}^{(k+1)})+(\mathbf{x}-\mathbf{x}^{(k)})= B(\mathbf{x}^{(k)}-\mathbf{x}^{(k-1)})\]

la quantité \(\| B\|\) est minorée par \(c=\delta_{k+1}/ \delta_k\), où \(\delta_{k+1}=\|\mathbf{x}^{(k+1)}-\mathbf{x}^{(k)}\|\). En remplaçant \(\| B\|\) par \(c\), le membre de droite de [eq24] suggère d’utiliser l’indicateur suivant pour \(\| \mathbf{e}^{(k+1)}\|\)

\[\varepsilon^{(k+1)}=\frac{\delta^2_{k+1}}{\delta_k-\delta_{k+1}}\]

Donc on peut s’arreter lorsque \(\varepsilon^{(k+1)}<\delta\), avec \(\delta\) une tolérance fixée.

2. Un test d’arrêt basé sur le résidu

Un autre critère d’arrêt consiste à tester si \(\| \mathbf{r}^{(k)}\| \leq \varepsilon\), \(\varepsilon\) étant une tolérance fixée. Comme

\[\| \mathbf{x}-\mathbf{x}^{(k)}\| = \| A^{-1}\mathbf{b}-\mathbf{x}^{(k)}\| = \| A^{-1}\mathbf{r}^{(k)}\| \leq \| A^{-1}\| \varepsilon\]

on doit prendre \(\varepsilon \leq \delta / \| A^{-1}\|\) pour que l’erreur soit inférieur à \(\delta\). Il est en général plus judicieux de considérer un résidu normalisé : on interrompt alors les inérations qunad \(\| \mathbf{r}^{(k)}\| / \| \mathbf{r}^{(0)}\| \leq \varepsilon\) ou bien quand \(\|\mathbf{r}^{(k)}\|/ \| b\| \leq \varepsilon\) (ce qui correspond au choix \(x^{(0)}=0\)). Dans ce dernier cas, le test d’arrêt fournit le contrôle suivant de l’erreur rélative

\[\label{eq:err_rel} \frac{\| \mathbf{x}-\mathbf{x}^{(k)}\|}{\|\mathbf{x}\|}\leq \frac{\|A^{-1}\|\|\mathbf{r}^{(k)}\|}{\|\mathbf{x}\| }\leq K(A)\frac{\|\mathbf{r}^{(k)}\|}{\|\mathbf{b}\|} \leq \varepsilon K(A).\]

Dans le cas des méthodes préconditionnées, le résidu est rémplacé par le résidu préconditionné. Le critère précédent devient alors

\[\frac{\| P^{-1}\mathbf{r}^{(k)}\| }{\| P^{-1}\mathbf{r}^{(0)}\| }\leq \varepsilon,\]

où \(P\) est la matrice de préconditionnement.