Le principe
On suppose f continue sur [a ; b] avec un changement de signe : d'après le théorème des valeurs intermédiaires, l'équation f(x) = 0 a une solution dans cet intervalle. À chaque étape, on calcule le milieu et on garde la moitié qui contient encore la racine :
Comme la largeur est divisée par deux à chaque tour, au bout de n étapes l'intervalle mesure (b − a) / 2ⁿ : la convergence est très rapide.
Le code Python
Exemple sur f(x) = x³ + x − 1, croissante et changeant de signe sur [0 ; 1]. La fonction renvoie une valeur approchée à e près :
def f(x):
return x**3 + x - 1
def dichotomie(e):
a = 0
b = 1
while b - a > e: # tant que l'intervalle est plus large que e
m = (a + b) / 2 # milieu
if f(m) <= 0: # la racine est à droite de m
a = m
else: # la racine est à gauche de m
b = m
return (a + b) / 2Les deux points qui rapportent les points au bac : la condition d'arrêt while b - a > e et le choix de la moitié selon le signe de f(m).
À toi de coder
Choisis l'exercice « Résoudre par dichotomie » dans l'atelier, complète la condition d'arrêt et le test, puis visualise a et b se rapprocher de la solution.
Questions fréquentes
Quel est le principe de la dichotomie ?
On part d'un intervalle [a ; b] sur lequel la fonction continue change de signe : il contient donc une solution de f(x) = 0. À chaque étape, on calcule le milieu m, on regarde le signe de f(m) et on garde la moitié qui contient encore la racine. L'intervalle est divisé par deux à chaque tour, donc on s'approche très vite de la solution.
Pourquoi la condition d'arrêt est while b - a > e ?
b − a est la largeur de l'intervalle. Tant qu'elle dépasse la précision e demandée, on continue à affiner. Dès qu'elle passe sous e, le milieu (a + b) / 2 est à moins de e de la vraie solution : on a une valeur approchée à e près.
Pourquoi f(m) <= 0 entraîne a = m ?
Si la fonction est croissante avec f(a) < 0 < f(b) et que f(m) <= 0, c'est qu'on est encore en dessous de la racine : elle se trouve à droite de m. On remonte donc la borne gauche en posant a = m. Si f change de sens de variation, on adapte le test au signe de f(a)·f(m).
Quelle hypothèse rend la dichotomie valable ?
La fonction doit être continue sur [a ; b] et y changer de signe (f(a) et f(b) de signes contraires). Le théorème des valeurs intermédiaires garantit alors l'existence d'une solution dans l'intervalle.
La dichotomie s'appuie sur le théorème des valeurs intermédiaires, et tous les autres algorithmes du bac sont dans l'atelier complet :