52
2 Equations non linéaires
2.3.1 Tests d’arrêt pour les itérations de Newton
En théorie, une méthode de Newton convergente ne retourne le zéro α
qu’après une infinité d’itérations. En pratique, on recherche une approximation de α avec une certaine tolérance ε. Ainsi, on peut interrompre
la méthode à la première itération k min pour laquelle on a l’inégalité
suivante
|e
(kmin)
| = |α − x
(kmin)
| < ε.
Ceci est un test sur l’erreur. Malheureusement, comme l’erreur est ellemême inconnue, on doit la remplacer par un estimateur d’erreur, c’està-dire, une quantité qui peut être facilement calculée et grâce à laquelle
on peut estimer l’erreur réelle. A la fin du paragraphe 2.4, nous verrons
que la différence entre deux itérées successives fournit un estimateur
d’erreur correct pour la méthode de Newton. Cela signifie que l’on peut
interrompre les itérations à l’étape k min telle que
|x
(kmin)
− x
(kmin−1)
| < ε
(2.11)
Ceci est un test sur l’incrément.
Nous verrons au paragraphe 2.4.1 que le test sur l’incrément est satisfaisant quand α est un zéro simple de f. On pourrait utiliser alternativement un test sur le résidu à l’itération k, r
(k) = f(x
(k) ) (remarquer
que le résidu est nul quand x
(k) est un zéro de la fonction f).
Plus précisément, on pourrait arrêter les itérations à l’étape k min
pour laquelle
|r
(kmin)
| = |f(x
(kmin) )| < ε
(2.12)
Le test sur le résidu n’est satisfaisant que quand |f
(x)| | 1 dans un
voisinage I α du zéro α (voir Figure 2.5). Autrement, il a tendance à
surestimer l’erreur si |f
(x)| | 1 pour x ∈ I α et à la sous-estimer si
|f
(x)| | 1 (voir aussi l’Exercice 2.6).
Dans le Programme 2.2, nous implémentons la méthode de Newton
(2.7). Sa version modifiée s’obtient facilement en remplaçant f
par f
/m.
Les paramètres d’entrée fun et dfun sont des chaînes de caractères qui
définissent la fonction f et sa dérivée première, tandis que x0 est la
donnée initiale. On stoppe l’algorithme quand la valeur absolue de la
différence entre deux itérées successives est inférieure à une tolérance
fixée tol, ou quand le nombre d’itérations atteint la valeur nmax.
2 Equations non linéaires
2.3.1 Tests d’arrêt pour les itérations de Newton
En théorie, une méthode de Newton convergente ne retourne le zéro α
qu’après une infinité d’itérations. En pratique, on recherche une approximation de α avec une certaine tolérance ε. Ainsi, on peut interrompre
la méthode à la première itération k min pour laquelle on a l’inégalité
suivante
|e
(kmin)
| = |α − x
(kmin)
| < ε.
Ceci est un test sur l’erreur. Malheureusement, comme l’erreur est ellemême inconnue, on doit la remplacer par un estimateur d’erreur, c’està-dire, une quantité qui peut être facilement calculée et grâce à laquelle
on peut estimer l’erreur réelle. A la fin du paragraphe 2.4, nous verrons
que la différence entre deux itérées successives fournit un estimateur
d’erreur correct pour la méthode de Newton. Cela signifie que l’on peut
interrompre les itérations à l’étape k min telle que
|x
(kmin)
− x
(kmin−1)
| < ε
(2.11)
Ceci est un test sur l’incrément.
Nous verrons au paragraphe 2.4.1 que le test sur l’incrément est satisfaisant quand α est un zéro simple de f. On pourrait utiliser alternativement un test sur le résidu à l’itération k, r
(k) = f(x
(k) ) (remarquer
que le résidu est nul quand x
(k) est un zéro de la fonction f).
Plus précisément, on pourrait arrêter les itérations à l’étape k min
pour laquelle
|r
(kmin)
| = |f(x
(kmin) )| < ε
(2.12)
Le test sur le résidu n’est satisfaisant que quand |f
(x)| | 1 dans un
voisinage I α du zéro α (voir Figure 2.5). Autrement, il a tendance à
surestimer l’erreur si |f
(x)| | 1 pour x ∈ I α et à la sous-estimer si
|f
(x)| | 1 (voir aussi l’Exercice 2.6).
Dans le Programme 2.2, nous implémentons la méthode de Newton
(2.7). Sa version modifiée s’obtient facilement en remplaçant f
par f
/m.
Les paramètres d’entrée fun et dfun sont des chaînes de caractères qui
définissent la fonction f et sa dérivée première, tandis que x0 est la
donnée initiale. On stoppe l’algorithme quand la valeur absolue de la
différence entre deux itérées successives est inférieure à une tolérance
fixée tol, ou quand le nombre d’itérations atteint la valeur nmax.