Algorithme de dichotomie pour résoudre une équation

I. Problématique

L'objectif est de trouver une solution approchée de l'équation $x^3 - 7 = 0$ en utilisant la méthode de la dichotomie. Cette méthode consiste à diviser un intervalle en deux à chaque étape et à déterminer dans quel sous-intervalle la solution se trouve, jusqu'à ce que l'écart entre les bornes de l'intervalle soit suffisamment petit.

II. Principe de la méthode de dichotomie

Nous savons que l'équation à résoudre est $x^3 - 7 = 0$.

Cette équation admet une solution dans l'intervalle $[1, 2]$ puisque $f(1) = 1^3 - 7 = -6\lt 0$ et $f(2) = 2^3 - 7 = +1\gt 0$, et la fonction $f(x) = x^3 - 7$ est continue (on peut tracer sa courbe sans lever le crayon). On va alors chercher à localiser la racine dans cet intervalle.

III. Algorithme

La méthode de dichotomie est implémentée par un algorithme qui fonctionne selon les étapes suivantes :

Initialisation :

On fixe un intervalle de départ, ici $[a = 1, b = 2]$.

Itération :

Tant que la différence entre $b$ et $a$ est plus grande que la tolérance (notée approx), on effectue les étapes suivantes :

Calculer le point médian $x = \frac{a + b}{2}$.

Si $f(x) < 0$, alors la solution est dans l'intervalle $[x, b]$ et on met à jour $a = x$.

Sinon, la solution est dans l'intervalle $[a, x]$ et on met à jour $b = x$.

Condition d'arrêt :

La boucle s'arrête lorsque l'écart entre les bornes de l'intervalle est inférieur à une valeur de tolérance donnée, ce qui signifie que la solution approchée est suffisamment précise.

Résultat :

L'algorithme renvoie les valeurs de $a$ et $b$, qui encadrent la solution approchée.

Détail des notations :

$a$ et $b$ : Les bornes de l'intervalle de recherche.

$x$ : Le point médian de l'intervalle.

$f(x)$ : La fonction à résoudre, ici $f(x) = x^3 - 7$.

approx : La tolérance, définie comme le critère d'arrêt de l'algorithme.

IV. Algorithme en langage naturel

V. Algorithme en Python

VI. Calcul avec une tolérance de 0.001

Prenons une tolérance de $0.001$ et appliquons l'algorithme de dichotomie.

Itération 1 :

$a = 1$, $b = 2$

$x = \frac{1 + 2}{2} = 1.5$

$f(1.5) = (1.5)^3 - 7 = -2.375$

Comme $f(1.5) < 0$, on met à jour $a = 1.5$.

Itération 2 :

$a = 1.5$, $b = 2$

$x = \frac{1.5 + 2}{2} = 1.75$

$f(1.75) = (1.75)^3 - 7 = -0.421875$

Comme $f(1.75) < 0$, on met à jour $a = 1.75$.

Itération 3 :

$a = 1.75$, $b = 2$

$x = \frac{1.75 + 2}{2} = 1.875$

$f(1.875) = (1.875)^3 - 7 = 0.296875$

Comme $f(1.875) > 0$, on met à jour $b = 1.875$.

Itération 4 :

$a = 1.75$, $b = 1.875$

$x = \frac{1.75 + 1.875}{2} = 1.8125$

$f(1.8125) = (1.8125)^3 - 7 = -0.060546875$

Comme $f(1.8125) < 0$, on met à jour $a = 1.8125$.

Itération 5 :

$a = 1.8125$, $b = 1.875$

$x = \frac{1.8125 + 1.875}{2} = 1.84375$

$f(1.84375) = (1.84375)^3 - 7 = 0.1185302734375$

Comme $f(1.84375) > 0$, on met à jour $b = 1.84375$.

Les itérations se poursuivront ainsi jusqu'à ce que l'écart entre $b$ et $a$ soit inférieur à $0.001$, donnant une solution approchée pour la racine de l'équation $x^3 - 7 = 0$.

VII. Conclusion

L'algorithme de dichotomie permet de trouver la solution approchée de l'équation $x^3 - 7 = 0$ en réduisant l'intervalle de manière systématique. Par exemple, après plusieurs itérations, la solution approchée peut être $x \approx 1.913$.