62
2 Equations non linéaires
seule fonction d’itération possible. Par exemple, pour résoudre l’équation
log(x) = γ, en posant f(x) = log(x) − γ, le choix (2.18) conduit à la
fonction d’itération
φ N (x) = x(1 − log(x) + γ).
Une autre méthode de point fixe peut être obtenue en ajoutant x
aux deux membres de l’équation f(x) = 0. La fonction d’itération associée est alors φ 1 (x) = x + log(x) − γ. On obtient une méthode encore
différente en choisissant la fonction d’itération φ 2 (x) = x log(x)/γ. Mais
toutes ces méthodes ne convergent pas. Par exemple, si γ = −2, les méthodes associées aux fonctions d’itération φ N et φ 2 sont toutes les deux
convergentes, alors que celle associée à φ 1 ne l’est pas puisque |φ
1 (x)| > 1
dans un voisinage du point fixe α.
2.4.1 Test d’arrêt des itérations de point fixe
En général, on interrompt des itérations de point fixe quand la valeur
absolue de la différence entre deux itérées successives est inférieure à une
tolérance donnée ε.
Comme α = φ(α) et x
(k+1) = φ(x
(k) ), on établit à l’aide du théorème
de la moyenne (voir Section 1.5.3),
α − x
(k+1) = φ(α) − φ(x
(k) ) = φ
(ξ
(k) ) (α − x
(k) ) avec ξ
(k)
∈ I α,x (k) ,
I α,x (k) étant l’intervalle d’extrémités α et x
(k) . En utilisant l’identité
α − x
(k) = (α − x
(k+1) ) + (x
(k+1)
− x
(k) ),
on en déduit que
α − x
(k) =
1
1 − φ (ξ (k) )
(x
(k+1)
− x
(k) ).
(2.24)
Par conséquent, si φ
(x) 0 dans un voisinage de α, la différence entre
deux itérées successives fournit un estimateur d’erreur satisfaisant. C’est
le cas des méthodes d’ordre 2, dont la méthode de Newton. Cette estimation devient d’autant moins bonne que φ
s’approche de 1.
Exemple 2.8 Calculons avec la méthode de Newton le zéro α = 1 de la fonction f (x) = (x − 1)
m−1 log(x) pour m = 11 et m = 21. Noter que ce zéro est de
multiplicité m. Dans ce cas, la méthode de Newton a une convergence d’ordre
1 ; de plus, il est possible de prouver (voir Exercice 2.15) que φ
N (α) = 1−1/m,
φN étant la fonction d’itération de la méthode vue comme un algorithme de
point fixe. Plus m est grand, plus se détériore la précision de l’estimation de
l’erreur par la différence entre deux itérées successives. Ceci est confirmé par
les résultats numériques de la Figure 2.10 sur laquelle on compare le comportement de l’erreur réelle et celui de l’erreur estimée pour m = 11 et m = 21.
La différence entre les deux quantités est plus grande quand m = 21.
2 Equations non linéaires
seule fonction d’itération possible. Par exemple, pour résoudre l’équation
log(x) = γ, en posant f(x) = log(x) − γ, le choix (2.18) conduit à la
fonction d’itération
φ N (x) = x(1 − log(x) + γ).
Une autre méthode de point fixe peut être obtenue en ajoutant x
aux deux membres de l’équation f(x) = 0. La fonction d’itération associée est alors φ 1 (x) = x + log(x) − γ. On obtient une méthode encore
différente en choisissant la fonction d’itération φ 2 (x) = x log(x)/γ. Mais
toutes ces méthodes ne convergent pas. Par exemple, si γ = −2, les méthodes associées aux fonctions d’itération φ N et φ 2 sont toutes les deux
convergentes, alors que celle associée à φ 1 ne l’est pas puisque |φ
1 (x)| > 1
dans un voisinage du point fixe α.
2.4.1 Test d’arrêt des itérations de point fixe
En général, on interrompt des itérations de point fixe quand la valeur
absolue de la différence entre deux itérées successives est inférieure à une
tolérance donnée ε.
Comme α = φ(α) et x
(k+1) = φ(x
(k) ), on établit à l’aide du théorème
de la moyenne (voir Section 1.5.3),
α − x
(k+1) = φ(α) − φ(x
(k) ) = φ
(ξ
(k) ) (α − x
(k) ) avec ξ
(k)
∈ I α,x (k) ,
I α,x (k) étant l’intervalle d’extrémités α et x
(k) . En utilisant l’identité
α − x
(k) = (α − x
(k+1) ) + (x
(k+1)
− x
(k) ),
on en déduit que
α − x
(k) =
1
1 − φ (ξ (k) )
(x
(k+1)
− x
(k) ).
(2.24)
Par conséquent, si φ
(x) 0 dans un voisinage de α, la différence entre
deux itérées successives fournit un estimateur d’erreur satisfaisant. C’est
le cas des méthodes d’ordre 2, dont la méthode de Newton. Cette estimation devient d’autant moins bonne que φ
s’approche de 1.
Exemple 2.8 Calculons avec la méthode de Newton le zéro α = 1 de la fonction f (x) = (x − 1)
m−1 log(x) pour m = 11 et m = 21. Noter que ce zéro est de
multiplicité m. Dans ce cas, la méthode de Newton a une convergence d’ordre
1 ; de plus, il est possible de prouver (voir Exercice 2.15) que φ
N (α) = 1−1/m,
φN étant la fonction d’itération de la méthode vue comme un algorithme de
point fixe. Plus m est grand, plus se détériore la précision de l’estimation de
l’erreur par la différence entre deux itérées successives. Ceci est confirmé par
les résultats numériques de la Figure 2.10 sur laquelle on compare le comportement de l’erreur réelle et celui de l’erreur estimée pour m = 11 et m = 21.
La différence entre les deux quantités est plus grande quand m = 21.