La méthode de dichotomie

La dichotomie (du grec « couper en deux ») figure dans les programmes de seconde et de terminale comme exemple d’algorithme, souvent écrit en Python. Elle donne une valeur approchée aussi précise qu’on le souhaite d’une solution qu’on ne sait pas calculer exactement. Le même principe sert à chercher un mot dans un dictionnaire ou une donnée dans une liste triée.

L’algorithme pas à pas

1. Partir d’un intervalle [a ; b] où f(a) et f(b) sont de signes contraires.
2. Calculer le milieu m = (a + b) / 2.
3. Si f(a) et f(m) sont de signes contraires (f(a) × f(m) < 0), la solution est dans [a ; m] : remplacer b par m.
4. Sinon, elle est dans [m ; b] : remplacer a par m.
5. Recommencer tant que b − a est supérieur à la précision voulue.
6. Renvoyer a et b : ils encadrent la solution.

Exemple : approcher √2

√2 est la solution positive de x² − 2 = 0. Avec f(x) = x² − 2 sur [1 ; 2] : f(1) = −1 < 0 et f(2) = 2 > 0.

Après 5 étapes : 1,406 < √2 < 1,438, intervalle d’amplitude 1/32 ≈ 0,031. La valeur exacte est √2 ≈ 1,41421 (voir racine carrée).

Combien d’étapes faut-il ?

À chaque étape, l’amplitude est divisée par 2. Après n étapes, partant d’un intervalle d’amplitude L, elle vaut L / 2ⁿ.

Environ 10 étapes de plus donnent 3 décimales de plus, puisque 2¹⁰ ≈ 10³.

L’algorithme en Python

On écrit une fonction dichotomie(a, b, precision) qui contient une boucle while b - a > precision:. Dans la boucle : m = (a + b) / 2, puis if f(a) * f(m) <= 0: b = m, sinon a = m. On renvoie a, b à la fin. La fonction f est définie au préalable, par exemple def f(x): return x**2 - 2. Voir débuter en Python.

Avantages et limites

• Avantages : très simple, fonctionne toujours si les hypothèses sont vérifiées, nombre d’étapes prévisible.
• Limites : il faut connaître au départ un intervalle avec changement de signe ; on ne trouve qu’une seule solution s’il y en a plusieurs ; la convergence est plus lente que d’autres méthodes (Newton, par exemple).
• Une racine double comme celle de (x − 1)² ne fait pas changer f de signe : la dichotomie ne la détecte pas.

Erreurs fréquentes

• Oublier de vérifier le changement de signe initial.
• Garder la mauvaise moitié en testant f(m) > 0 au lieu du produit f(a) × f(m) (cela ne marche que si f est croissante).
• Confondre le nombre d’étapes et la précision obtenue.
• Appliquer à une fonction non continue : 1/x change de signe sur [−1 ; 1] sans s’annuler.

Exercice corrigé

On cherche la solution de x³ + x − 1 = 0 sur [0 ; 1].

1. f(0) = −1 et f(1) = 1 : changement de signe, f continue, une solution existe.
2. m = 0,5 : f(0,5) = −0,375 < 0 → [0,5 ; 1].
3. m = 0,75 : f(0,75) ≈ 0,172 > 0 → [0,5 ; 0,75].
4. m = 0,625 : f(0,625) ≈ −0,131 < 0 → [0,625 ; 0,75].
5. Pour une précision de 0,01 depuis un intervalle de longueur 1 : 7 étapes. La solution vaut environ 0,682.

Questions fréquentes

À quoi sert la méthode de dichotomie ?

À obtenir une valeur approchée d’une solution d’équation qu’on ne sait pas résoudre exactement, avec une précision choisie à l’avance.

Quelle condition faut-il pour appliquer la dichotomie ?

La fonction doit être continue sur l’intervalle et prendre des valeurs de signes contraires aux deux bornes.

Combien d’étapes pour une précision de 10⁻³ ?

Avec un intervalle de départ de longueur 1, il faut 10 étapes, car 2¹⁰ = 1 024 > 1 000.

La dichotomie s’utilise-t-elle ailleurs qu’en maths ?

Oui : la recherche dichotomique dans une liste triée, en informatique, trouve un élément parmi un million en une vingtaine de comparaisons. Voir algorithme.