46
2 Equations non linéaires
I
(0)
I
(1)
I
(2)
I
(3)
a
(0)
x
(0)
x
(1) x
(2)
x
y
b
(0)
f
Figure 2.2. Quelques itérations de la méthode de dichotomie
2.2 Méthode de dichotomie (ou bisection)
Soit f une fonction continue sur [a, b] telle que f(a)f(b) < 0. Nécessairement f a au moins un zéro dans ]a, b[ (ce résultat est un cas particulier
du théorème des valeurs intermédiaires). Supposons pour simplifier qu’il
est unique et notons le α (dans le cas où il y a plusieurs zéros, on peut
localiser graphiquement, à l’aide de la commande fplot, un intervalle
qui n’en contient qu’un).
La méthode de dichotomie (aussi appelée méthode de bisection)
consiste à diviser en deux un intervalle donné, et à choisir le sousintervalle où f change de signe. Plus précisément, si on note I
(0) =]a, b[
et I
(k) le sous-intervalle retenu à l’étape k, on choisit le sous-intervalle
I
(k+1) de I
(k) pour lequel f a un signe différent à ses deux extrémités. En
répétant cette procédure, on est assuré que chaque I
(k) ainsi construit
contiendra α. La suite {x
(k)
} des milieux des intervalles I
(k) convergera
vers α puisque la longueur de ces intervalles tend vers zéro quand k tend
vers l’infini.
La méthode est initialisée en posant
a
(0) = a, b
(0) = b, I
(0) =]a
(0) , b
(0) [, x
(0) = (a
(0) + b
(0) )/2.
A chaque étape k ≥ 1, on choisit le sous-intervalle I
(k) =]a
(k) , b
(k) [ de
I
(k−1) =]a
(k−1) , b
(k−1) [ comme suit
étant donné x
(k−1) = (a
(k−1) + b
(k−1) )/2,
si f(x
(k−1) ) = 0,
alors α = x
(k−1)
et on s’arrête ;
sinon,