Comment encadrer une solution par la méthode de dichotomie ? | MetMat

Comment encadrer une solution par la méthode de dichotomie ?

En partant d'un intervalle $[a,b]$ où $f(a)$ et $f(b)$ sont de signes opposés, en évaluant $f$ au milieu $c = \dfrac{a+b}{2}$ , en choisissant le sous-intervalle qui contient la racine, et en répétant jusqu'à la précision souhaitée

Encadrer une racine $\alpha$ de $f$ à une précision donnée $\varepsilon > 0$ en appliquant l'algorithme de dichotomie.

L'objectif

Encadrer une racine $\alpha$ de $f$ à une précision donnée $\varepsilon > 0$ en appliquant l'algorithme de dichotomie.

Le principe

Si $f$ est continue sur $[a,b]$ avec $f(a)$ et $f(b)$ de signes opposés, il existe une racine dans $]a,b[$ ; en évaluant $f$ au milieu $c = \dfrac{a+b}{2}$ , on sélectionne un sous-intervalle de longueur $\dfrac{b-a}{2}$ contenant toujours la racine, et on répète jusqu'à obtenir la précision voulue.

La méthode

1
Partir d'un intervalle $[a_0, b_0]$ tel que $f(a_0)$ et $f(b_0)$ sont de signes strictement opposés (i.e. $f(a_0) \cdot f(b_0) < 0$ ). Noter la longueur initiale $b_0 - a_0$ .
2
Calculer le milieu $c = \dfrac{a + b}{2}$ et évaluer $f(c)$ . Trois cas : si $f(c) = 0$ , $c$ est la racine exacte ; si $f(a) \cdot f(c) < 0$ , la racine est dans $[a, c]$ , poser $b \leftarrow c$ ; sinon, la racine est dans $[c, b]$ , poser $a \leftarrow c$ .
3
Répéter l'étape 2 avec le nouvel intervalle. Après $n$ itérations, l'intervalle a une longueur $\dfrac{b_0 - a_0}{2^n}$ , ce qui donne une précision sur la racine de $\dfrac{b_0 - a_0}{2^n}$ .
4
S'arrêter lorsque la longueur de l'intervalle est inférieure à la précision souhaitée $\varepsilon$ (i.e. quand $\dfrac{b_0 - a_0}{2^n} < \varepsilon$ ), et donner l'encadrement $[a_n, b_n]$ ou la valeur approchée $\dfrac{a_n + b_n}{2}$ .

Pour comprendre, fais des exercices !

0/5 validés

Exercice d'exemple

Encadrer à $0{,}1$ près la solution de $x^3 + x - 1 = 0$ dans $[0, 1]$ par dichotomie.

Étape 1 —

Partir d'un intervalle

[a_0, b_0]

tel que

f(a_0)

f(b_0)

sont de signes strictement opposés (i.e.

f(a_0) \cdot f(b_0) < 0

). Noter la longueur initiale

b_0 - a_0

Soit $f(x) = x^3 + x - 1$ . $f(0) = -1 < 0$ et $f(1) = 1 > 0$ : on part de $[a_0, b_0] = [0, 1]$ , longueur $1$ .

Étape 2 —

Calculer le milieu

c = \dfrac{a + b}{2}

et évaluer

f(c)

. Trois cas : si

f(c) = 0

c

est la racine exacte ; si

f(a) \cdot f(c) < 0

, la racine est dans

[a, c]

, poser

b \leftarrow c

; sinon, la racine est dans

[c, b]

, poser

a \leftarrow c

Itération 1 : $c = \dfrac{0+1}{2} = 0{,}5$ . $f(0{,}5) = 0{,}125 + 0{,}5 - 1 = -0{,}375 < 0$ . $f(0{,}5) < 0$ et $f(1) > 0$ : on garde $[0{,}5, 1]$ .

Étape 3 —

Répéter l'étape 2 avec le nouvel intervalle. Après

n

itérations, l'intervalle a une longueur

\dfrac{b_0 - a_0}{2^n}

, ce qui donne une précision sur la racine de

\dfrac{b_0 - a_0}{2^n}

Itération 2 : $c = \dfrac{0{,}5+1}{2} = 0{,}75$ . $f(0{,}75) = 0{,}421875 + 0{,}75 - 1 = 0{,}171875 > 0$ . $f(0{,}5) < 0$ et $f(0{,}75) > 0$ : on garde $[0{,}5, 0{,}75]$ , longueur $0{,}25 > 0{,}1$ .

Étape 4 —

S'arrêter lorsque la longueur de l'intervalle est inférieure à la précision souhaitée

\varepsilon

(i.e. quand

\dfrac{b_0 - a_0}{2^n} < \varepsilon

), et donner l'encadrement

[a_n, b_n]

ou la valeur approchée

\dfrac{a_n + b_n}{2}

Itération 3 : $c = \dfrac{0{,}5+0{,}75}{2} = 0{,}625$ . $f(0{,}625) = 0{,}244 + 0{,}625 - 1 = -0{,}131 < 0$ . On garde $[0{,}625, 0{,}75]$ , longueur $0{,}125 > 0{,}1$ . Itération 4 : $c = 0{,}6875$ . $f(0{,}6875) \approx 0{,}325 + 0{,}6875 - 1 = 0{,}012 > 0$ . On garde $[0{,}625, 0{,}6875]$ , longueur $0{,}0625 < 0{,}1$ .

La racine est dans $[0{,}625, 0{,}6875]$ , donc la solution est approximativement $0{,}68$ à $0{,}1$ près.

Application guidée

Encadrer à $0{,}125$ près la solution de $e^x - 2 = 0$ dans $[0, 1]$ par dichotomie (effectuer 3 itérations).

Application autonome 1

Combien d'itérations de dichotomie sont nécessaires pour encadrer une racine à $10^{-3}$ près, en partant de l'intervalle $[0, 1]$ ?

Application autonome 2

Encadrer à $0{,}25$ près la racine de $f(x) = \cos x - x$ dans $[0, 1]$ par dichotomie (effectuer 2 itérations).

Application autonome 3

Encadrer à $0{,}125$ près la solution de $x^3 - x - 1 = 0$ dans $[1, 2]$ par dichotomie (effectuer $3$ itérations).

Crée ton compte gratuit pour accéder à la fiche et aux exercices

En partant d'un intervalle [a,b][a,b][a,b] où f(a)f(a)f(a) et f(b)f(b)f(b) sont de signes opposés, en évaluant fff au milieu c=a+b2c = \dfrac{a+b}{2}c=2a+b​, en choisissant le sous-intervalle qui contient la racine, et en répétant jusqu'à la précision souhaitée

Pour comprendre, fais des exercices !

En partant d'un intervalle $[a,b]$ où $f(a)$ et $f(b)$ sont de signes opposés, en évaluant $f$ au milieu $c = \dfrac{a+b}{2}$ , en choisissant le sous-intervalle qui contient la racine, et en répétant jusqu'à la précision souhaitée