Qu'est-ce que la méthode de dichotomie ?
La méthode de dichotomie est l'une des techniques les plus anciennes et les plus fiables pour trouver une racine d'une fonction continue \(f(x)\) — c'est-à-dire une valeur \(x\) telle que \(f(x) = 0\). Le principe consiste à partir d'un intervalle \([a, b]\) sur lequel la fonction change de signe, puis à couper cet intervalle en deux de façon répétée en conservant la moitié qui encadre toujours la racine. Comme le changement de signe est préservé à chaque étape, la méthode est garantie de converger tant que \(f\) est continue et que \(f(a)\) et \(f(b)\) sont de signes opposés. Ce calculateur fonctionne avec n'importe quelle fonction réelle sans dimension et utilise les radians pour la trigonométrie.
Comment utiliser ce calculateur
Saisissez votre fonction dans le champ f(x) en utilisant x comme variable (par exemple x-cos(x), x^2-2 ou exp(x)-3). Définissez la borne inférieure a et la borne supérieure b de manière que la racine se situe entre les deux — le produit \(f(a)\cdot f(b)\) doit être inférieur ou égal à zéro. Choisissez un nombre maximal d'itérations n ainsi que le nombre de chiffres à afficher. L'outil renvoie la racine approchée, la valeur de la fonction en ce point (qui doit être proche de zéro) et le nombre d'itérations réellement nécessaires.
La formule
À chaque étape, l'estimation correspond au milieu de l'intervalle
$$x_n = \frac{a_n + b_n}{2}$$Si \(|f(x_n)|\) est inférieur à la tolérance, \(x_n\) est retenu. Sinon, l'algorithme conserve la moitié qui présente encore un changement de signe : si \(f(a_n)\cdot f(x_n) > 0\), la racine se trouve à droite (on pose \(a = x_n\)), sinon elle se trouve à gauche (on pose \(b = x_n\)). La largeur de l'intervalle diminue selon \(\frac{b-a}{2^n}\) : la convergence est donc linéaire — on gagne environ un chiffre binaire correct par étape.
Exemple résolu
Pour \(f(x) = x - \cos(x)\) sur \([-10, 10]\) : \(f(-10) \approx -10{,}84\) (négatif) et \(f(10) \approx 10{,}84\) (positif), la racine est donc bien encadrée. Les divisions successives par moitié convergent vers \(x \approx 0{,}7390851332151607\), le célèbre nombre de Dottie pour lequel \(x = \cos x\), avec une valeur de \(f(x)\) pratiquement nulle.
Comment effectuer la méthode de la bisection à la main
La méthode de la bisection trouve une racine de \(f(x)=0\) en divisant répétitivement par deux un intervalle qui contient une racine. Elle repose sur le théorème des valeurs intermédiaires : si \(f\) est continue sur \([a,b]\) et \(f(a)\) et \(f(b)\) ont des signes opposés, une racine doit se trouver entre eux.
- Vérifier l'encadrement. Confirmer que \(f(a)\cdot f(b)<0\). Si le produit est positif, l'intervalle ne contient pas nécessairement une racine — choisissez un \([a,b]\) différent.
- Calculer le point milieu. \(m=\dfrac{a+b}{2}\).
- Évaluer la fonction. Trouver \(f(m)\). Si \(f(m)=0\) (ou est dans la tolérance), \(m\) est la racine et vous arrêtez.
- Remplacer une extrémité par signe. Si \(f(a)\cdot f(m)<0\), la racine est dans \([a,m]\), donc définir \(b\leftarrow m\). Sinon, la racine est dans \([m,b]\), donc définir \(a\leftarrow m\).
- Répéter les étapes 2–4 jusqu'à \(|b-a|<\text{tol}\) ou \(|f(m)|<\text{tol}\), ou jusqu'à atteindre le nombre maximal d'itérations.
Exemple : \(f(x)=x^{3}-x-2\) sur \([1,2]\). Vérification : \(f(1)=-2\), \(f(2)=4\), produit \(<0\) — l'encadrement est valide.
| Itér | a | b | m=(a+b)/2 | f(m) | Nouvel intervalle |
|---|---|---|---|---|---|
| 1 | 1.0000 | 2.0000 | 1.5000 | −0.125 | [1.5, 2] |
| 2 | 1.5000 | 2.0000 | 1.7500 | 1.6094 | [1.5, 1.75] |
| 3 | 1.5000 | 1.7500 | 1.6250 | 0.6660 | [1.5, 1.625] |
| 4 | 1.5000 | 1.6250 | 1.5625 | 0.2522 | [1.5, 1.5625] |
| 5 | 1.5000 | 1.5625 | 1.5313 | 0.0591 | [1.5, 1.5313] |
| 6 | 1.5000 | 1.5313 | 1.5156 | −0.0340 | [1.5156, 1.5313] |
Après plus d'itérations, l'intervalle se resserre autour de la vraie racine 1.521380, qui est également l'unique racine réelle du polynôme \(x^{3}-x-2=0\) trouvée par un 1.521380 solveur direct.
Itérations par rapport à la tolérance et à la largeur de l'encadrement
Chaque étape de bisection divise l'intervalle par deux, donc après \(n\) itérations la largeur de l'encadrement est \((b-a)/2^{\,n}\). Pour atteindre une tolérance \(\text{tol}\) sur la localisation de la racine, vous avez besoin d'environ
$$n \approx \log_2\!\left(\frac{b-a}{\text{tol}}\right).$$Le nombre d'itérations croît seulement avec le logarithme de la précision, donc même les tolérances très strictes nécessitent relativement peu d'étapes. Le tableau montre le nombre d'itérations arrondi vers le haut pour plusieurs combinaisons.
| Largeur initiale \(b-a\) | Tolérance cible | \(\log_2((b-a)/\text{tol})\) | Itérations nécessaires |
|---|---|---|---|
| 1 | \(10^{-3}\) | 9.97 | 10 |
| 1 | \(10^{-6}\) | 19.93 | 20 |
| 1 | \(10^{-10}\) | 33.22 | 34 |
| 10 | \(10^{-6}\) | 23.25 | 24 |
| 20 | \(10^{-6}\) | 24.25 | 25 |
| 100 | \(10^{-8}\) | 33.22 | 34 |
| 0.5 | \(10^{-12}\) | 38.86 | 39 |
Par exemple, un encadrement de largeur 20 affiné à \(10^{-6}\) nécessite \(\lceil\log_2(20/10^{-6})\rceil=\lceil 24.25\rceil=\) 25 itérations, et un encadrement de largeur 1 à \(10^{-10}\) nécessite \(\lceil 33.22\rceil=\) 34. Diviser par deux la largeur initiale économise exactement une itération ; augmenter la précision au carré (une décimale supplémentaire) coûte environ 3.3 itérations.
Termes clés
- Racine. Une valeur \(x^{*}\) où la fonction est zéro, \(f(x^{*})=0\) ; également appelée un zéro ou une solution de l'équation.
- Encadrement / intervalle \([a,b]\). Une paire d'extrémités supposées enfermer une racine. Pour la bisection, elle doit satisfaire la condition de changement de signe.
- Changement de signe. La condition \(f(a)\cdot f(b)<0\), ce qui signifie \(f\) prend des signes opposés aux extrémités. Pour une \(f\) continue, cela garantit au moins une racine entre elles (théorème des valeurs intermédiaires).
- Point milieu. Le centre de l'intervalle actuel, \(m=(a+b)/2\) ; chaque étape teste ce point et écarte la moitié qui ne peut pas contenir la racine.
- Tolérance. La cible de précision qui arrête l'itération, appliquée soit à la largeur de l'intervalle \(|b-a|\), soit au résidu \(|f(m)|\).
- Convergence (linéaire). La bisection converge linéairement : l'erreur est à peu près divisée par deux à chaque étape (erreur \(\le (b-a)/2^{n}\)), donnant un progrès régulier mais non accélérateur — environ un chiffre binaire exact supplémentaire par itération.
- Itération. Un cycle complet de calcul du point milieu, évaluation de la fonction et mise à jour d'une extrémité. Le nombre d'itérations est plafonné par le réglage du nombre maximal d'itérations.
FAQ
Pourquoi est-ce que j'obtiens une erreur « pas de changement de signe » ? La dichotomie exige que \(f(a)\) et \(f(b)\) soient de signes opposés. Ajustez a et b jusqu'à ce qu'ils encadrent la racine.
Peut-elle trouver plusieurs racines ? Non — elle renvoie une seule racine à l'intérieur de l'intervalle et ne peut pas détecter les racines où la courbe se contente de toucher l'axe sans le traverser.
Pourquoi est-elle plus lente que la méthode de Newton ? La dichotomie converge de façon linéaire, en gagnant environ un chiffre binaire par étape, tandis que Newton converge de façon quadratique. La dichotomie sert souvent à obtenir un point de départ sûr que des méthodes plus rapides viennent ensuite affiner.
