15 minutes de Python

Dichotomie : principe, justification et visualisation

Fondements mathématiques de la dichotomie : le théorème des valeurs intermédiaires

Soit \(f\) une fonction continue sur un segment \([a,b]\). Si \(f(a)\) et \(f(b)\) sont de signes opposés, c’est-à-dire si \[ f(a)f(b) < 0 \] alors, d’après le théorème des valeurs intermédiaires, il existe \(c\in\left]a,b\right[\) tel que \[ f(c)=0 \]

On sait donc avec certitude qu’une solution de l’équation \(f(x)=0\) se trouve dans l’intervalle \([a,b]\), mais on ne connaît pas sa position exacte. Le but de la méthode de dichotomie est de localiser de mieux en mieux cette solution.

Quelle valeur approchée pour un élément de \( [a,b] \) ?

Soit \(a<b\) et \[ m=\frac{a+b}{2} \] Alors on a \[ m-a=\frac{b-a}{2} \qquad\text{et}\qquad b-m=\frac{b-a}{2} \] Autrement dit, le milieu \(m\) est à égale distance de \(a\) et de \(b\), et cette distance vaut la moitié de la longueur de l’intervalle.

En particulier, si \(c\in[a,b]\), alors on a nécessairement \[ |m-c|\le \frac{b-a}{2} \] Le milieu \(m\) est donc une valeur approchée de \(c\) à \(\dfrac{b-a}{2}\) près.

Principe de la méthode

Puisqu’une solution \(c\) appartient à \([a,b]\), l’idée est de construire une suite de segments \([a_0,b_0] = [a,b] \), \([a_1,b_1]\), … de plus en plus petits, tous contenant \(c\), jusqu’à ce que la longueur du segment soit suffisamment faible pour obtenir la précision souhaitée.

On coupe donc le segment en deux \([a,b]\), puis on conserve le sous-segment sur lequel le changement de signe subsiste. On recommence alors le même procédé sur ce nouvel \([a,b]\).

À chaque itération, la longueur du segment est divisée par 2 donc, après \(n\) itérations, on obtient un intervalle de longueur \[ \frac{b_0-a_0}{2^n} \] Or \[ \lim_{n \to + \infty} \frac{b_0-a_0}{2^n} = 0 \] La longueur des segments tendant vers 0, il est donc certain qu’au bout d’un nombre fini d’itérations, l’intervalle sera assez petit pour fournir une approximation de la solution avec la précision imposée.

À l’étape \(k\), on calcule le milieu \[ m_k=\frac{a_k+b_k}{2} \] puis on s'intéresse au signe de \(f(m_k)\).

1. Si \(f(a_k)f(m_k)\le 0\), alors le changement de signe est sur \([a_k,m_k]\), donc on pose \[ a_{k+1}=a_k,\qquad b_{k+1}=m_k \]
2. Sinon, le changement de signe est sur \([m_k,b_k]\), donc on pose \[ a_{k+1}=m_k,\qquad b_{k+1}=b_k \]

Invariant important : à chaque étape, on conserve un intervalle \([a_k,b_k]\) tel que \(f(a_k)f(b_k)\le 0\). On est donc sûr que l’intervalle contient toujours au moins une solution.

Approximation : la longueur de l’intervalle est divisée par 2 à chaque étape : \[ b_k-a_k=\frac{b_0-a_0}{2^k} \] Donc \(a_k\) et \(b_k\) se rapprochent l’un de l’autre. Une approximation naturelle de la solution est le milieu \(\dfrac{a_k+b_k}{2}\).

Majorant de l'erreur : si on renvoie \(x_k=\dfrac{a_k+b_k}{2}\), alors la solution \(c\) vérifie \[ |x_k-c|\le \frac{b_k-a_k}{2}=\frac{b_0-a_0}{2^{k+1}} \]

Exemple guidé : visualiser la dichotomie

On cherche une solution de \[ x^3-2=0 \] sur \([1,2]\). On pose \(f(x)=x^3-2\).

On a \[ f(1)=-1,\qquad f(2)=6 \] donc \(f(1)f(2)<0\) : on peut appliquer la dichotomie.

On calcule successivement les milieux et on garde le sous-intervalle où le signe change. Au bout d’un certain nombre d’itérations, le milieu de l’intervalle obtenu fournit une approximation de \(\sqrt[3]{2}\).

L’animation suivante illustre les étapes de la dichotomie sur \(f(x)=x^3-2\).

5) Remarques pratiques pour programmer

• Il faut vérifier au départ que \(f(a)f(b)\le 0\) avant de lancer la boucle.
• On peut s’arrêter soit après un nombre d’itérations fixé, soit quand \(b-a\) devient plus petit qu’un seuil.
• Le résultat renvoyé est souvent le milieu \(\dfrac{a+b}{2}\), accompagné de l’intervalle final \([a,b]\).