Principe de la dichotomie et application avec Python
La dichotomie (prononcer dikotomi) est une notion mathématique dont le principe est assez simple à comprendre. Manuellement, elle peut être longue à mettre en œuvre mais une fois programmée elle devient parfaitement opérationnelle.
Cette page s’inscrit dans le programme de maths de spécialité de terminale, ou plutôt dans ses prolongements possibles.
Le principe
Vous connaissez l’expression d’une fonction \(f\) et vous souhaitez résoudre l’équation \(f(x) = 0.\) Cette louable intention peut vous conduire, par le calcul, à une ou des solutions exactes (lorsqu’il y en a, bien entendu). Mais bien souvent, le calcul ne permet pas de répondre. Il peut être très compliqué ou même impossible. Le but est alors de trouver une valeur approchée ou un intervalle très fin qui contient la solution.
En terminale, on utilise le corollaire du théorème des valeurs intermédiaires. Celui-ci permet d’affirmer qu’une solution existe dans un intervalle donné sous certaines conditions, d’ailleurs assez évidentes. La valeur approchée est trouvée à l’aide de la calculatrice.
Supposons que vous souhaitez un encadrement très fin de la solution et que l’algorithme de la calculatrice ne soit pas suffisamment précis pour vous le fournir. Vous devez alors programmer le calcul. Mais évidemment, vous devez d’abord connaître le principe de la dichotomie.
En premier lieu, il vous faut connaître un intervalle fini dans lequel la solution se trouve. Comme il peut être très grand, cette étape n’a rien de très compliqué.
Divisez cet intervalle en deux sous-parties égales. Retenez celle dans laquelle se situe la solution et éliminez l’autre. Répétez l’opération dans le sous-intervalle qui contient la solution et ainsi de suite jusqu’à ce que l’intervalle obtenu soit suffisamment petit.
Exemple
Soit la fonction \(f\) définie sur \(\mathbb{R}\) par \(f(x) = x^5 - 2x^2 + 5.\) Déterminons une valeur approchée de \(f(x) = 0.\)
La calculatrice graphique nous montre que la solution se trouve dans l’intervalle \([-2\, ;-1].\) La fonction \(f\) est continue et strictement croissante sur cet intervalle.
\(f(-2) = -35\) et \(f(-1) = 2\)
Séparons l’intervalle en deux, donc calculons \(f(-1,5) ≈ -7,09.\)
Nous en déduisons facilement que la solution de l’équation se trouve entre -1,5 et -1 puisque sur \([-2\, ;-1,5]\) toutes les solutions sont négatives.
Partageons à nouveau en deux parties égales l’intervalle qu’il nous reste. La valeur moyenne est -1,25. Un calcul nous amène à \(f(-1,25) ≈ -1,18.\)
Il s’ensuit que la valeur de \(x\) pour laquelle \(f(x) = 0\) se trouve entre \(f(-1,25)\) et \(f(-1).\)
Après quelques itérations, nous constatons que la solution est d’environ -1,174933.
Programmation en Python
Programmons cet exemple. Il n’est pas difficile de l’étendre à d’autres fonctions.
Nous cherchons un intervalle relativement fin dans lequel \(f(x) = 0.\)
a = float(input('début intervalle : '))
b = float(input('fin intervalle : '))
i = int(input('nombre de décimales : '))
def f(x):
return x**5 - 2 * x**2 + 5
if f(a) * f(b) > 0:
print('pas de solution si la fonction est continue et monotone')
else:
while b - a > 10**-(i):
m = (b + a)/2
if f(m) * f(a) > 0:
a = m
else:
b = m
print(a,b,m)
if f(a) * f(m) < 0:
print('Solution entre ', a , 'et', m)
else:
print('Solution entre ', m , 'et', b)
Cet algorithme repose sur un principe simple : si deux nombres sont de même signe, leur produit est positif. Par conséquent, si l’on pose \(m\) comme milieu du segment \([a\, ;b],\) avec \(a\) et \(b\) de signes contraires, il est simple de situer \(f(0).\) Si \(f(a) × f(m)\) est positif, alors \(f(0)\) se situe entre \(f(m)\) et \(f(b)\) et inversement si le produit est négatif.
Précisons que ce programme n’est pas tout à fait satisfaisant au niveau des arrondis et qu’un petit travail doit être réalisé par l’opérateur à partir des outputs.
Précisons également qu’à des fins didactiques une sortie est affichée à chaque itération (un print est inclus dans la boucle). D’ailleurs, voici ce que l’on obtient pour une précision de \(10^{-3}.\)
Input :
début intervalle : -2
fin intervalle : -1
nombre de décimales : 3
Output :
-1.5 -1.0 -1.5
-1.25 -1.0 -1.25
-1.25 -1.125 -1.125
-1.1875 -1.125 -1.1875
-1.1875 -1.15625 -1.15625
-1.1875 -1.171875 -1.171875
-1.1796875 -1.171875 -1.1796875
-1.17578125 -1.171875 -1.17578125
-1.17578125 -1.173828125 -1.173828125
-1.17578125 -1.1748046875 -1.1748046875
Solution entre -1.17578125 et -1.1748046875
Ce nombre de trois décimales a été choisi à dessein pour mettre le doigt sur le problème des arrondis. Cette sortie nous permet d’affirmer que la solution se trouve entre -1,176 et -1,175 avec un arrondi à la troisième décimale. En l’occurrence, la réponse est -1,175. Mais en fait, elle ne se trouve pas dans cet intervalle puisqu’elle est environ égale à -1,174933.