6.2 Une approche g´ eom´ etrique de la d´ etermination des racines
215
En partant de I 0 = [a, b], la m´ ethode de dichotomie produit une suite de
sous-intervalles I k = [a
(k) , b
(k) ], k ≥ 0, avec I k ⊂ I k−1 , k ≥ 1, et tels que
f(a
(k) )f(b
(k) ) < 0. Plus pr´ ecis´ ement, on pose a
(0) = a, b
(0) = b et x
(0) =
(a
(0) + b
(0) )/2 ; alors, pour k ≥ 0 :
on pose a
(k+1) = a
(k) , b
(k+1) = x
(k) si f(x
(k) )f(a
(k) ) < 0;
ou a
(k+1) = x
(k) , b
(k+1) = b
(k)
si f(x
(k) )f(b
(k) ) < 0;
et x
(k+1) = (a
(k+1) + b
(k+1) )/2.
x (1)
x
y
f (x)
a
b
α
I 1
I 0
x (0)
0
5
10
15
20
25
30
10
−12
10
−10
10
−8
10
−6
10
−4
10
−2
10
0
Fig. 6.1. Les deux premiers pas de la m´ ethode de dichotomie (` a gauche). Historique
de la convergence pour l’Exemple 6.3 (` a droite) ; le nombre d’it´ erations est report´ e
sur l’axe des x et l’erreur absolue sur l’axe des y
Les it´ erations s’ach` event ` a la m-` eme ´ etape quand |x
(m)
− α| ≤ |I m | ≤ ε,
o` u ε est une tol´ erance fix´ ee et |I m | d´ esigne la longueur de I m . Consid´ erons
` a pr´ esent la vitesse de convergence de la m´ ethode de dichotomie. Remarquer
que |I 0 | = b − a, et que
|I k | = |I 0 |/2
k = (b − a)/2
k ,
k ≥ 0.
(6.8)
En notant e
(k) = x
(k)
− α l’erreur absolue ` a l’´ etape k, on d´ eduit de (6.8) que
|e
(k)
| < |I k |/2 = (b − a)/2
k+1 , ce qui implique lim k→∞ |e
(k)
| = 0.
La m´ ethode de dichotomie est donc globalement convergente. De plus, pour
avoir |x
(m)
− α| ≤ ε, on doit prendre
m ≥ log 2
b − a
ε
− 1 =
log((b − a)/ε)
log(2)
− 1
log((b − a)/ε)
0.6931
− 1. (6.9)
En particulier, pour am´ eliorer d’un ordre de grandeur la pr´ ecision de l’approximation de la racine (i.e. pour avoir |x
(k)
− α| = |x
(j)
− α|/10), on doit
effectuer k − j = log 2 (10) 3.32 dichotomies. Cet algorithme converge donc
` a coup sˆ ur mais lentement. De plus, notons que la m´ ethode de dichotomie
215
En partant de I 0 = [a, b], la m´ ethode de dichotomie produit une suite de
sous-intervalles I k = [a
(k) , b
(k) ], k ≥ 0, avec I k ⊂ I k−1 , k ≥ 1, et tels que
f(a
(k) )f(b
(k) ) < 0. Plus pr´ ecis´ ement, on pose a
(0) = a, b
(0) = b et x
(0) =
(a
(0) + b
(0) )/2 ; alors, pour k ≥ 0 :
on pose a
(k+1) = a
(k) , b
(k+1) = x
(k) si f(x
(k) )f(a
(k) ) < 0;
ou a
(k+1) = x
(k) , b
(k+1) = b
(k)
si f(x
(k) )f(b
(k) ) < 0;
et x
(k+1) = (a
(k+1) + b
(k+1) )/2.
x (1)
x
y
f (x)
a
b
α
I 1
I 0
x (0)
0
5
10
15
20
25
30
10
−12
10
−10
10
−8
10
−6
10
−4
10
−2
10
0
Fig. 6.1. Les deux premiers pas de la m´ ethode de dichotomie (` a gauche). Historique
de la convergence pour l’Exemple 6.3 (` a droite) ; le nombre d’it´ erations est report´ e
sur l’axe des x et l’erreur absolue sur l’axe des y
Les it´ erations s’ach` event ` a la m-` eme ´ etape quand |x
(m)
− α| ≤ |I m | ≤ ε,
o` u ε est une tol´ erance fix´ ee et |I m | d´ esigne la longueur de I m . Consid´ erons
` a pr´ esent la vitesse de convergence de la m´ ethode de dichotomie. Remarquer
que |I 0 | = b − a, et que
|I k | = |I 0 |/2
k = (b − a)/2
k ,
k ≥ 0.
(6.8)
En notant e
(k) = x
(k)
− α l’erreur absolue ` a l’´ etape k, on d´ eduit de (6.8) que
|e
(k)
| < |I k |/2 = (b − a)/2
k+1 , ce qui implique lim k→∞ |e
(k)
| = 0.
La m´ ethode de dichotomie est donc globalement convergente. De plus, pour
avoir |x
(m)
− α| ≤ ε, on doit prendre
m ≥ log 2
b − a
ε
− 1 =
log((b − a)/ε)
log(2)
− 1
log((b − a)/ε)
0.6931
− 1. (6.9)
En particulier, pour am´ eliorer d’un ordre de grandeur la pr´ ecision de l’approximation de la racine (i.e. pour avoir |x
(k)
− α| = |x
(j)
− α|/10), on doit
effectuer k − j = log 2 (10) 3.32 dichotomies. Cet algorithme converge donc
` a coup sˆ ur mais lentement. De plus, notons que la m´ ethode de dichotomie