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
En utilisant l’inégalité triangulaire, on a
et donc
En particulier, en prenant \(k=0\) dans [eq24] et en appliquant la formule de récurrence [eq23] on obtient aussi l’inégalité
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
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)}\|\)
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
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
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
où \(P\) est la matrice de préconditionnement.