La dichotomie est une méthode pour encadrer une solution à une équation.
Par soucis de simplifier le problème, toutes les équations seront ramenées à la forme f(x) = 0.
Principe de la dichotomie
Avant tout, il faut s’assurer que la fonction est continue et strictement monotone (soit strictement croissante, soit strictement décroissante) sur un intervalle [a ; b], et que f(a) et f(b) n’ont pas le même signe (ce qui assure, d’après le corollaire du théorème des valeurs intermédiaires, l’existence d’une unique solution à l’équation sur l’intervalle considéré).
Considérons donc une fonction f continue et strictement monotone sur un intervalle [a;b]. La dichotomie consiste à:
- le milieu m de l’intervalle [a ; b] est calculé
- son image par la fonction f est ensuite calculée
- si f(a)×f(m) > 0 alors cela signifie que f(a) et f(m) ont le même signe; comme f est strictement monotone, cela signifie donc que la solution à l’équation f(x) = 0 n’est pas entre a et m. Dans ce cas, elle se trouve sur l’intervalle [m ; b]. On change donc d’intervalle et [a ; b] devient [m ; b]. On va alors au point 1 tant que l’amplitude de l’intervalle est supérieur au seuil que l’on se fixe (par exemple, 0,001).
- Dans le cas contraire, [a ; b] devient [a ; m] et on repart au point 1 tant que l’amplitude de l’intervalle est supérieure au seuil que l’on se fixe.
Un exemple pas à pas de la dichotomie
Prenons:$$f(x)=x^2-2.$$Plaçons-nous sur l’intervalle [0 ; 2] (donc a = 0 et b = 2). Voici un tableau des étapes des calculs (en prenant une marge de 0,1 pour finir plus vite):
| a | b | m | f(a) | f(b) | f(m) | amplitude |
|---|---|---|---|---|---|---|
| 0 | 2 | 1 | -2 | 2 | -1 | 2 |
| 1 | 2 | 1.5 | -1 | 2 | 0.25 | 1 |
| 1 | 1.5 | 1.25 | -1 | 0.25 | -0.4375 | 0.5 |
| 1.25 | 1.5 | 1.375 | -0.4375 | 0.25 | -0.109375 | 0.25 |
| 1.375 | 1.5 | 1.4375 | -0.109375 | 0.25 | 0.066406 | 0.125 |
| 1.375 | 1.4375 | 1.40625 | -0.109375 | 0.066406 | -0.02246 | 0.0625 |
D’après ce tableau, la solution de l’équation \(x^2-2=0\) qui se trouve dans [0 ; 2] est la valeur \(\alpha\) telle que \(1,375 < \alpha < 1,4375\). On obtient ainsi un encadrement de la solution à \(10^{-1}\) près.
Calcul de l’erreur
D’après le principe de la dichotomie, les intervalles successifs sont divisés en deux à chaque étape. Ainsi, le dernier intervalle (après n étapes) aura une amplitude égale à \(\displaystyle\frac{b-a}{2^n}\). Si \(\varepsilon\) représente l’amplitude maximale désirée, alors:$$\begin{align}\frac{b-a}{2^n} \leqslant \varepsilon & \iff \frac{2^n}{b-a} \geqslant \frac{1}{\varepsilon}\\&\iff 2^n \geqslant \frac{b-a}{\varepsilon}\\&\iff n \geqslant \log_2\left(\frac{b-a}{\varepsilon}\right)\end{align}$$On dit que la vitesse de convergence est linéaire car \(|x_{n+1} – \alpha| \leqslant k|x_n – \alpha|\).
Par exemple, si [a ; b] = [0 ; 2] comme précédemment, et si nous voulons un encadrement à \(\varepsilon=10^{-5}\) près, il faudra:$$n\geqslant\log_2\left(2\times10^{5}\right)\approx17,6$$soit au minimum 18 étapes pour avoir un tel encadrement.
Je ne suis pas là pour critiquer… mais quand-même… Oserais-je dire que la dichotomie est à la résolution d’équation ce que Facebook est aux réseaux sociaux (à savoir tout pourri) ?
La dichotomie en Python
On ne va pas se mentir (on est entre amis), je n’ai pas fait les calculs des nombres qui paraissent dans le tableau précédent à la main… car je ne suis pas non plus trop con… Je sais écrire une fonction Python qui le fait pour moi alors pourquoi me priver ? D’ailleurs, la voici:
def dichotomie(f,a,b,e):
delta = 1
while delta > e:
m = (a + b) / 2
delta = abs(b - a)
if f(m) == 0:
return m
elif f(a) * f(m) > 0:
a = m
else:
b = m
return a, b
print( dichotomie(lambda x: x*x - 2, 0, 2, 0.001) )Dans la fonction dichotomie, la variable delta représente l’amplitude de l’intervalle, donc |b – a|. Notez que très souvent, on a a < b, donc la valeur absolue n’est pas nécessaire, mais je la mets systématiquement par réflexe. Tant que cette amplitude est supérieure à celle donnée en argument (représentée par la variable e), on effectue les opérations:
- le milieu de l’intervalle [a ; b] est calculé → ligne 4
- l’amplitude (qui change à chaque fois) de l’intervalle est calculée → ligne 5
- on affiche les différentes valeurs (parce que l’on est très curieux) → ligne 6
- l’algorithme de dichotomie commence → lignes 7 à 12
Il est à noter aussi la syntaxe de la fonction sous la forme:
lambda x: <expression>
C’est un choix personnel… pour simplifier la saisie. Mais on aurait tout aussi bien pu écrire:
def dichotomie(a,b,e):
delta = 1
while delta > e:
m = (a + b) / 2
delta = abs(b - a)
if f(m) == 0:
return m
elif f(a) * f(m) > 0:
a = m
else:
b = m
return a, b
def f(x):
return x*x - 4
print( dichotomie(0, 9, 0.001) )(1.999786376953125, 2.00006103515625)
Notez alors que j’ai enlevé un argument à la fonction dichotomie (celui représentant la fonction f) et que j’ai écrit une autre fonction retournant l’image d’un nombre x. Ces deux syntaxes sont équivalentes.
Remarquez que l’on obtient pas exactement la valeur exacte (ici, 2). Ceci est dû à la représentation des nombres en Python.
Autres méthodes de résolution d’équations
Comme je l’ai suggéré précédemment, cette méthode n’est pas la plus efficace, mais elle a le mérite d’être simple à comprendre.
Une autre méthode, bien plus performante mais plus compliquée est la méthode de Newton.
Et n’oubliez pas que si vous avez des problèmes en mathématiques, je peux vous aider par webcam (cours ponctuels ou réguliers).