Résolution approchée d'une équation par dichotomie
Il arrive, en mathématiques, d'être confronté à une équation que l'on ne peut pas résoudre algébriquement. Il est alors possible d'utiliser un algorithme permettant de calculer une valeur approchée d'une solution de l'équation.
On considère dans cet exercice l'équation \((E)\) : \(f(x)=0\) :
-
supposons que l'on connaisse déjà un intervalle de recherche à cibler, l'intervalle \(\left[ \text{début}\,;\,\text{fin}\right]\) ;
-
supposons de plus que la fonction \(f\) est continue et strictement monotone sur cet intervalle.
Dans ce cas-là, nous pouvons utiliser l'algorithme de dichotomie.
Si \(C_f\) est la courbe représentative de \(f\), résoudre \((E)\) revient à déterminer l'abscisse d'un point d'intersection de \(C_f\) avec l'axe des abscisses.
Voici les trois premières étapes, dans le cas particulier représenté ci-dessus, du déroulement de cet algorithme :
- On calcule l'abscisse du milieu de l'intervalle de recherche ;
- On observe que \(f(\text{milieu})\) et \(f(\text{fin})\) sont de signes contraires ;
- On doit donc poursuivre la recherche sur l'intervalle \([\text{milieu}\,;\,\text{fin}]\) (sur la droite de l'intervalle de recherche comme illustré ci-dessous).
- On calcule à nouveau l'abscisse du milieu de l'intervalle de recherche ;
- On observe que \(f(\text{milieu})\) et \(f(\text{fin})\) sont de mêmes signes ;
- On doit donc poursuivre la recherche sur l'intervalle \([\text{début}\,;\,\text{milieu}]\) (sur la gauche de l'intervalle de recherche comme illustré ci-dessous).
- On calcule toujours l'abscisse du milieu de l'intervalle de recherche ;
- On observe que \(f(\text{milieu})\) et \(f(\text{fin})\) sont de signes contraires ;
- On doit donc poursuivre la recherche sur l'intervalle \([\text{milieu}\,;\,\text{fin}]\) (sur la droite de l'intervalle de recherche comme illustré ci-dessous).
👉 On continue le processus jusqu'à obtenir un encadrement de la solution d'amplitude désirée.
Valeurs de mêmes signes ?
On rappelle que les réels \(a\) et \(b\) distincts non nuls sont de même signe équivaut à : \(a \times b > 0\)
Si une solution exacte de l'équation n'a pas été trouvée (ce qui est le plus souvent le cas), on répète le principe de dichotomie en divisant par deux l'amplitude de l'intervalle de recherche à chaque étape, jusqu'à ce que son amplitude soit inférieure à une précision souhaitée.
Exprimé en français l'algorithme de dichotomie est donc le suivant (cliquer sur les + pour lire les explications en commentaires):
Fonction dichotomie(debut, fin, precision) : # (1)
Tant que fin - debut > precision :
milieu = (debut + fin) / 2
Si f(milieu) × f(fin) est strictement positif : # (2)
fin = milieu
Sinon si f(milieu) × f(fin) est strictement négatif : # (3)
debut = milieu
Sinon # (4)
Renvoyer (milieu, milieu) # (5)
Renvoyer (debut, fin)
- La fonction prend trois paramètres : le debut et la fin de l'intervalle de recherche ainsi que la précision.
milieuest strictement supérieur à la solution.milieuest strictement inférieur la solution.milieuest la solution. On renvoie l'intervalle [milieu,milieu]- L'instruction
Renvoyerprovoque la sortie de la fonction. C'est ici une sortie anticipée car la solution a été trouvée. Il est inutile de continuer à la chercher.
Nous allons utiliser cette méthode afin de déterminer une valeur approchée à \(10^{-6}\) près de l'équation :
Écrire le code de la fonction dichotomie qui prend en paramètres les nombres debut, fin et precision.
debut, fin délimitent l'intervalle de recherche et precision est la précision souhaitée.
Cette fonction renvoie un intervalle d'amplitude precision contenant la solution de l'équation étudiée.
assert ?
Le mot clé assert est utilisé en Python afin de vérifier que des propositions sont vraies.
Ainsi, l'instruction assert 3 + 5*7 == 38 permet de vérifier que l'expression 3 + 5*7 est bien évaluée à 38.
Si c'est le cas, le programme continue de se dérouler normalement. Dans le cas contraire, le programme est interrompu et une erreur est signalée.
# Tests (insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)