IV – M´ ethodes it´ eratives pour la r´ esolution d’´ equations
103
On obtient ainsi une nouvelle approximation x 2 de a en calculant l’abscisse de
l’intersection de la s´ ecante avec l’axe Ox :
x 2 = x 1 −
f (x 1 )
τ 1
.
On va bien entendu it´ erer ce proc´ ed´ e ` a partir des nouvelles valeurs approch´ ees x 1
et x 2 , ce qui conduit `
a poser
τ p =
f (x p ) − f (x p−1 )
x p − x p−1
, x p+1 = x p −
f (x p )
τ p
.
La m´ ethode est donc tout `
a fait analogue `
a celle de Newton, ` a ceci pr` es que l’on
a remplac´ e la d´ eriv´ ee f
(x p ) par le taux d’accroissement τ p de f sur l’intervalle
[x p , x p−1 ]. On notera que l’algorithme it´ eratif ne peut d´ emarrer que si on dispose
d´ ej` a de deux valeurs approch´ ees x 0 , x 1 de a.
Inconv´ enient de la m´ ethode – Lorsque x p et x p−1 sont trop voisins, le calcul
de f (x p ) − f (x p−1 ) et x p − x p−1 donne lieu `
a un ph´ enom` ene de compensation et
donc `
a une perte de pr´ ecision sur le calcul de τ p . ´
Etudions l’erreur commise. La
formule de Taylor-Lagrange `
a l’ordre 2 au point x p donne
f (x p−1 ) − f (x p ) = (x p−1 − x p )f
(x p ) +
1
2
(x p−1 − x p )
2 f
(c),
τ p − f
(x p ) =
1
2
(x p−1 − x p )f
(c) = O(|x p − x p−1 |)
apr` es division de la premi` ere ligne par x p−1 − x p .
Supposons par ailleurs que le calcul des f (x i ) soit effectu´ e avec une erreur d’arrondi
de l’ordre de ε. Le calcul de τ p est alors affect´ e d’une erreur absolue de l’ordre de
ε
|xp−xp−1| . Il est inutile de continuer `
a calculer τ p d` es que cette erreur d´ epasse l’´ ecart
|τ p − f
(x p )|, ce qui a lieu si
ε
|xp−xp−1| > |x p − x p−1 | c’est-` a-dire |x p − x p−1 | <
√
ε.
Dans la pratique, si l’on dispose d’une pr´ ecision absolue ε = 10
−10 par exemple,
on arrˆ ete le calcul de τ p d` es que |x p − x p−1 | <
√
ε = 10
−5 ; on poursuit alors
les it´ erations avec τ p = τ p−1 jusqu’` a l’obtention de la convergence (c’est-` a-dire
|x p+1 − x p | < ε).
D’un point de vue th´ eorique, la convergence de la suite est assur´ ee par le r´ esultat
ci-dessous, qui donne simultan´ ement une estimation pr´ ecise pour |x p − a|.
Th´ eor` eme – On suppose f de classe C
2 et de d´ eriv´ ee f
= 0 sur l’intervalle
I = [a − r, a + r]. On introduit les quantit´ es M i , i = 1, 2, et les r´ eels K, h tels que
M i = max
x∈I
|f
(i) (x)|,
m i = min
x∈I
|f
(i) (x)|,
K =
M 2
2m 1
1 +
M 1
m 1
,
h= min
r,
1
K
.
Soit enfin (s p ) la suite de Fibonacci, d´ efinie par s p+1 = s p + s p−1 avec s 0 = s 1 = 1.
Alors quel que soit le choix des points initiaux x 0 , x 1 ∈ [a − h, a + h] distincts, on a
|x p − a| ≤
1
K
[K max(|x 0 − a|, |x 1 − a|)]
sp .
103
On obtient ainsi une nouvelle approximation x 2 de a en calculant l’abscisse de
l’intersection de la s´ ecante avec l’axe Ox :
x 2 = x 1 −
f (x 1 )
τ 1
.
On va bien entendu it´ erer ce proc´ ed´ e ` a partir des nouvelles valeurs approch´ ees x 1
et x 2 , ce qui conduit `
a poser
τ p =
f (x p ) − f (x p−1 )
x p − x p−1
, x p+1 = x p −
f (x p )
τ p
.
La m´ ethode est donc tout `
a fait analogue `
a celle de Newton, ` a ceci pr` es que l’on
a remplac´ e la d´ eriv´ ee f
(x p ) par le taux d’accroissement τ p de f sur l’intervalle
[x p , x p−1 ]. On notera que l’algorithme it´ eratif ne peut d´ emarrer que si on dispose
d´ ej` a de deux valeurs approch´ ees x 0 , x 1 de a.
Inconv´ enient de la m´ ethode – Lorsque x p et x p−1 sont trop voisins, le calcul
de f (x p ) − f (x p−1 ) et x p − x p−1 donne lieu `
a un ph´ enom` ene de compensation et
donc `
a une perte de pr´ ecision sur le calcul de τ p . ´
Etudions l’erreur commise. La
formule de Taylor-Lagrange `
a l’ordre 2 au point x p donne
f (x p−1 ) − f (x p ) = (x p−1 − x p )f
(x p ) +
1
2
(x p−1 − x p )
2 f
(c),
τ p − f
(x p ) =
1
2
(x p−1 − x p )f
(c) = O(|x p − x p−1 |)
apr` es division de la premi` ere ligne par x p−1 − x p .
Supposons par ailleurs que le calcul des f (x i ) soit effectu´ e avec une erreur d’arrondi
de l’ordre de ε. Le calcul de τ p est alors affect´ e d’une erreur absolue de l’ordre de
ε
|xp−xp−1| . Il est inutile de continuer `
a calculer τ p d` es que cette erreur d´ epasse l’´ ecart
|τ p − f
(x p )|, ce qui a lieu si
ε
|xp−xp−1| > |x p − x p−1 | c’est-` a-dire |x p − x p−1 | <
√
ε.
Dans la pratique, si l’on dispose d’une pr´ ecision absolue ε = 10
−10 par exemple,
on arrˆ ete le calcul de τ p d` es que |x p − x p−1 | <
√
ε = 10
−5 ; on poursuit alors
les it´ erations avec τ p = τ p−1 jusqu’` a l’obtention de la convergence (c’est-` a-dire
|x p+1 − x p | < ε).
D’un point de vue th´ eorique, la convergence de la suite est assur´ ee par le r´ esultat
ci-dessous, qui donne simultan´ ement une estimation pr´ ecise pour |x p − a|.
Th´ eor` eme – On suppose f de classe C
2 et de d´ eriv´ ee f
= 0 sur l’intervalle
I = [a − r, a + r]. On introduit les quantit´ es M i , i = 1, 2, et les r´ eels K, h tels que
M i = max
x∈I
|f
(i) (x)|,
m i = min
x∈I
|f
(i) (x)|,
K =
M 2
2m 1
1 +
M 1
m 1
,
h= min
r,
1
K
.
Soit enfin (s p ) la suite de Fibonacci, d´ efinie par s p+1 = s p + s p−1 avec s 0 = s 1 = 1.
Alors quel que soit le choix des points initiaux x 0 , x 1 ∈ [a − h, a + h] distincts, on a
|x p − a| ≤
1
K
[K max(|x 0 − a|, |x 1 − a|)]
sp .