Introduction :
Dans cette fiche, nous allons voir comment programmer en Python un algorithme qui permet de donner un encadrement, avec une précision donnée, de la solution d’une équation de la forme , où est une fonction strictement monotone et continue sur un intervalle ( et réels tels que ).
Pour cela, nous allons utiliser une méthode dite de dichotomie.
Méthode de dichotomie (fonction strictement croissante)
Méthode de dichotomie (fonction strictement croissante)
Principe
Principe
Nous considérons une fonction continue et strictement croissante sur un intervalle ( et deux réels tels que ), avec et . Il existe donc un unique réel tel que : .
- Nous cherchons à encadrer , avec une précision donnée, c’est-à-dire que nous cherchons un intervalle de longueur inférieure ou égale à auquel appartient .
Voici le principe de la dichotomie :
- On calcule le milieu de l’intervalle :
- On calcule l’image de par .
- Si , alors on a la solution : .
- Si (c’est-à-dire du même signe que ), alors n’appartient pas à , appartient donc à .
- Si (c’est-à-dire du même signe que ), alors appartient à .
- On répète, si besoin, le processus à partir du point 1 avec l’intervalle ou .
- On arrête dès que la longueur de l’intervalle est inférieure ou égale à la précision trouvée.
Exemple
Exemple
Nous considérons la fonction définie sur par :
Comme fonction polynôme, est continue sur .
Nous admettons en outre que est strictement croissante sur l’intervalle , avec :
En appliquant le corollaire du théorème des valeurs intermédiaires, nous pouvons donc dire que l’équation admet une unique solution sur l’intervalle .
À notre niveau, nous ne savons pas résoudre une telle équation. Nous utilisons la méthode de dichotomie pour donner un encadrement du résultat, avec la précision .
Première boucle
- , nous calculons donc le milieu de :
- Nous calculons :
est donc strictement supérieur à , la solution appartient à l’intervalle .
- , nous répétons donc le processus avec l’intervalle .
Deuxième boucle
- Nous calculons le milieu de :
- Nous calculons :
est donc strictement inférieur à , la solution appartient à l’intervalle .
- , nous répétons donc le processus avec l’intervalle .
Troisième boucle
- Nous calculons le milieu de :
- Nous calculons et obtenons :
est donc strictement inférieur à , la solution appartient à l’intervalle .
- , nous répétons donc le processus avec l’intervalle .
Quatrième boucle
- Nous calculons le milieu de :
- Nous calculons et obtenons :
est donc strictement supérieur à , la solution appartient à l’intervalle .
- , nous sortons donc de la boucle, l’intervalle obtenu nous convient.
Encadrement obtenu
Nous obtenons ainsi, avec une précision de :
Algorithme pour une fonction strictement croissante
Algorithme pour une fonction strictement croissante
Nous venons de le voir, la méthode de dichotomie nous fait parcourir à plusieurs reprises une boucle, nous pouvons donc programmer un algorithme qui nous renvoie l’intervalle recherché.
- Nous allons le faire à partir de la fonction définie dans la première partie :
Nous travaillerons sur un intervalle tel que est strictement croissante sur et où et .
Nous considérons en outre que la précision demandée est strictement inférieure à la longueur de l’intervalle (si était supérieure ou égale à , alors nous aurions déjà la réponse et un algorithme serait inutile…).
En toute rigueur, pour ne pas risquer d’avoir une erreur dans notre programme, nous devrions le faire, comme nous devrions vérifier que le entré est bien strictement inférieur au entré ; nous ne le faisons pas ici pour ne pas alourdir l’algorithme, mais vous pouvez bien sûr le faire de votre côté !
- Commençons tout simplement par programmer en Python la fonction .
- Elle prend pour paramètre un réel et qui renverra l’image de ce réel par la fonction .
- Nous définissons la fonction Python , où est la borne inférieure, la borne supérieure et la précision voulue :
- Nous précisons l’instruction de la boucle : nous voulons qu’elle s’exécute tant que la longueur de l’intervalle est strictement supérieure à la précision donnée :
- Nous calculons le milieu de :
- Nous considérons le cas où l’image de par est nulle.
- est alors la solution recherchée, nous sortons de la boucle avec l’instruction .
- Nous considérons maintenant le cas où l’image de par est strictement négative.
- La solution recherchée appartient alors à l’intervalle .
- Nous assignons donc à la valeur de .
- Le cas restant est celui où l’image de par est strictement positive.
- La solution recherchée appartient alors à l’intervalle .
- Nous assignons donc à la valeur de .
La boucle est maintenant exécutée.
- Les différentes variables contiennent donc les valeurs qui nous intéressent.
- Considérons à nouveau le cas particulier où nous avons obtenu une image de par nulle.
Rappelons que nous sommes partis du principe que la précision demandée était strictement inférieure à la longueur de l’intervalle entré en paramètre, soit : . - La boucle est au moins exécutée une fois et la variable est bien définie.
- Dans ce cas, nous demandons à notre programme d’afficher qu’il a trouvé la solution exacte et de la donner.
- Nous considérons enfin les autres cas.
- Nous demandons alors au programme d’afficher l’intervalle recherché.
- contient sa borne inférieure.
- contient sa borne supérieure.
- Sa longueur est bien inférieure ou égale à .
- L’algorithme est terminé :
Reprenons l’exemple de la première partie, où nous partions de l’intervalle
Nous entrons donc la commande
- La fonction affichera en retour :
.[1.375 ; 1.4375] \purple{\text{[1.375\ ;\, 1.4375]}}
Il s’agit bien du résultat que nous avons trouvé.
Vous pouvez bien sûr donner une valeur (positive) inférieure à
- Si vous travaillez avec une fonction différente, qui est continue et strictement croissante sur un intervalle, il suffit de modifier en conséquence la fonction
; la fonctionf \purple{\text{f}} reste bien sûr valable.dichocroiss \purple{\text{dicho\textunderscore croiss}} - Si, plus généralement, on cherche à encadrer la solution d’une équation du type «
», avecf ( x ) = k f(x)=k réel quelconque, on peut se ramener à ce que nous venons de voir en posant la fonctionk k : l’équationg : x ↦ f ( x ) − k g:x\mapsto f(x)-k sera alors équivalente àf ( x ) = k f(x)=k . (Il faudra évidemment montrer auparavant que l’équationg ( x ) = 0 g(x)=0 admet une unique solution sur l’intervalle considéré.)f ( x ) = k f(x)=k
Exercice : fonction strictement décroissante
Exercice : fonction strictement décroissante
Écrire une fonction Python
- Les modifications sont minimes par rapport à l’algorithme pour une fonction strictement croissante…
Considérons encore la fonction
Par le corollaire du TVI, l’équation
- Si vous exécutez l’algorithme que vous venez d’écrire en entrant
et si vous n’avez pas commis d’erreur, vous obtiendrez en retour :dichodecroiss(-1,0,0.1) \purple{\text{dicho\textunderscore decroiss(-1,0,0.1)}} .[-0.25 ; -0.1875] \purple{\text{[-0.25\ ;\, -0.1875]}}
Vous pouvez aussi étudier de manière complète la fonction
- En vous servant des deux algorithmes, vous donnerez alors un encadrement avec une précision inférieure ou égale à
de ces1 0 − 3 10^{-3} solutions.3 3