Terminale > Mathématiques > Algorithmique et programmation > Algorithmes

ALGORITHMES

Accède gratuitement à cette vidéo pendant 7 jours

Profite de ce cours et de tout le programme de ta classe avec l'essai gratuit de 7 jours !

Démarrer l'essai gratuit

Dichotomie

Permalien

Télécharger la fiche de cours Les téléchargements sont réservés uniquements aux abonnés

Dichotomie

 

L'algorithme de dichotomie est une succession d'opérations permettant de donner un encadrement de la solution de l'équation $f(x) = 0$. 

On cherche à savoir pour quelles valeurs une fonction $f$ s'annule, en raisonnant en tâtonnant. On choisit de manière arbitraire deux nombres $a$ et $b$ tels que $f(a) < 0$ et $f(b) > 0$.

La fonction est d'abord négative puis positive : elle passe donc par 0. 

 

On se place ensuite au milieu de l'intervalle, c'est à dire $\dfrac{a + b}{2}$ puis on calcule l'image par la fonction $f$ de ce nouveau point que l'on compare à 0. 

Ici, $f\left ( \dfrac{a + b}{2} \right ) > 0$.

On en déduit alors que la fonction s'annule dans l'intervalle $\left [a; \dfrac{a + b}{2} \right ]$. 

 

On prend donc pour nouvelle valeur de $b$ la valeur du milieu $\dfrac{a + b}{2}$ et on conserve la même valeur pour $a$.

Puis on recommence le même procédé : on considère le milieu de l'intervalle puis on calcule l'image par la fonction $f$ de ce nouveau point.

Ici, l'image est négative, on se place donc sur la deuxième moitié de l'intervalle : le nombre $a$ change cette fois ci pour devenir $\dfrac{a + b}{2}$.

7ac708496c7e7ee48986e28836110fc0ac260e29.png

 

On réitère ce procédé autant de fois qu'on le souhaite pour approcher la solution à la précision désirée.

On peut alors réaliser un tableau résumant les différentes étapes de calcul de cet algorithme comprenant les valeurs de $a, b, \dfrac{a + b}{2}$ et le signe de leur image par la fonction $f$.

Etape 1 2
$a$ 1 1
$b$ 2 1,5
$\dfrac{a + b}{2}$ 1,5 1,25
$f(a)$ $-$ $-$
$f(b)$ $+$ $+$
$f\left ( \dfrac{a + b}{2} \right )$ $+$ $-$

 

On se propose de commenter l'algorithme ci-dessous.

91056e0f2ee13317bc547092205afbc9972238d7.png

 

On indique dans un premier temps les variables utilisées dans l'algorithme.

L'entrée correspond aux valeurs que l'utilisateur doit rentrer.

$N$ correspond au nombre d'itérations de l'algorithme, c'est à dire le nombre de fois où l'on va chercher le milieu de l'intervalle et calculer son image par la fonction $f$ et étudier son signe. 

Le traitement correspond à l'algorithme. $k$ compte le nombre d'itérations en cours, $m$ correspond au milieu de l'intervalle d'étude. 

Enfin, on affiche les bornes de l'intervalle final qui donne un encadrement de la solution $f(x) = 0$.