Mathématice, intégration des Tice dans l'enseignement des mathématiques  
Sommaire > N°46 - septembre 2015 > La dichotomie : une résolution numérique de (...)

La dichotomie : une résolution numérique de l’équation f(x)=0
Moteur de recherche

« L’idée d’élaborer ce travail m’était venue après la lecture sur l’un des numéros de MathémaTICE d’un article où l’auteur présente des algorithmes qui traitent la résolution numérique de l’équation $f(x)=0$ de différentes méthodes : ça m’a plu et je m’en suis inspiré pour produire les quelques pages suivantes.
Il reste à signaler qu’en Tunisie, l’algorithmique est une matière à part, elle est enseignée par un prof qui a un profil autre que celui de l’enseignant des mathématiques.

On suppose que l’étude d’une fonction $f$ a permis de prouver l’existence d’une racine et de la localiser grossièrement dans un intervalle $]a,b[$. La dichotomie est l’une des méthodes qui permettent de déterminer une valeur approchée de cette racine avec une précision fixée au préalable.
Dans cet article, je propose un support théorique pour la dichotomie et des programmes écrits en Turbo-Pascal qui visent la recherche puis l’affichage

  • d’une valeur approchée de cette racine avec une précision fixée d’avance.
  • d’un intervalle d’encadrement de cette racine
  • le rang et les valeurs des termes des suites définies pour encadrer cette solution »

Support théorique

Conséquence du théorème des valeurs intermédiaires
« Si $f$ est une fonction continue sur $[a,b]$ et si $f(a).f(b) <0$, alors l’équation $f(x)=0$ a au moins une solution dans $]a,b[$ ; si de plus, $f$ est strictement monotone sur $[a,b]$, l’équation $f(x)=0$ a une unique solution dans $]a,b[$ ».

Étapes de la démarche (la dichotomie)
On démarre donc en ayant localisé la racine $\alpha$ entre $a$ et $b$ ($a < \alpha < b$) ; et on sait par exemple que sur cet intervalle, la fonction $f$ (continue) est strictement croissante.
On calcule alors le milieu $m$ de $a$ et $b$ $\left(m=\dfrac{a+b}{2}\right)$ puis son image par $f$ : $(f(m))$, et on la compare à 0.
Deux cas peuvent alors se produire :

Algorithme
On construit deux suites (an) et (bn) telles que : $a_0=a$, $b_0=b$ puis :

  1. si $f(m)=0$ $\left( m=\dfrac{a+b}{2} \right)$ alors $m$ est la racine de $f$ et le problème est terminé
  2. si $f(m)\neq 0$ alors
    • si $f\left( \dfrac{a_n+b_n}{2} \right)>0$ alors $\begin{cases} a_{n+1}=a_n \\ b_{n+1}=\frac{a_n+b_n}{2}\end{cases}$
    • si $f\left( \dfrac{a_n+b_n}{2} \right)<0$ alors $\begin{cases} a_{n+1}=\frac{a_n+b_n}{2} \\ b_{n+1}=b_n\end{cases}$

On montre alors que :
ces deux suites sont adjacentes et de limite commune $\alpha$ : la racine "visée" de l’équation $f(x)=0$ dans l’intervalle $]a,b[$.

Remarques
Remarque1 : Dans le cas où l’on tombe exactement sur la racine ($f(m)=0$ : pris en considération dans la première ligne du test ci-dessus) ; à partir de là, la suite $(b_n)$ devient stationnaire, égale à la racine $\alpha$ visée ; l’algorithme ne passe plus qu’alors dans la deuxième ligne, avec la suite $(a_n)$ qui, seule, continue à croître et se rapprocher de $\alpha$.

Remarque2 : Par construction, après $n$ itérations, on obtient $a_n < \alpha \leq b_n$ avec $b_n -a_n =\dfrac{b-a}{2^n}$. L’encadrement de la racine est donc d’amplitude : $\dfrac{b-a}{2^n}$. On peut donc faire tourner cet algorithme de construction, TANT QUE l’on n’obtient pas la précision souhaitée.

Remarque3 : Dans le cas où $f$ est strictement décroissante sur $[a,b]$, il suffit juste d’inverser dans le test, l’avancement des deux suites, ou bien, ce qui revient au même, d’inverser la condition du test.

Remarque4 : Pour avoir une valeur approchée de $\alpha$ à $\epsilon >0$ près à la $n$-ième itération, il suffit que $n$ vérifie : $\dfrac{b-a}{2^{n+1}} \leq \epsilon$

Ainsi on pourra calculer d’avance le nombre maximal $N$ d’itérations assurant la précision voulue. C’est la plus petite valeur de $n$ qui vérifie :
$\begin{eqnarray*} \frac{b-a}{2^{n+1}} \leq \varepsilon & \Longleftrightarrow & 2^{n+1} \geq \frac{b-a}{% \varepsilon } \\ & \Longleftrightarrow & n+1 \geq \frac{\ln \left( \frac{b-a}{\varepsilon }\right) }{\ln (2)} \\ & \Longleftrightarrow & n \geq \frac{\ln \left( \frac{b-a}{\varepsilon }\right) }{\ln (2)}-1 \end{eqnarray*}$

($\ln$ désigne la fonction logarithme népérien).

Exercice d’application

Soit la fonction $f$ définie sur $]0,+\infty[$ par : $f(x)=\ln x - x\ln x +x$.
On désigne par $(C_f)$ sa courbe représentative selon un repère orthonormé $(O,\overrightarrow{i},\overrightarrow{j})$.
1) Montrer que $(C_f)$ coupe l’axe des abscisses en deux points d’abscisses respectives $x_1$ et $x_2$ telles que : $0.4 < x_1 < 0.5$ et $3 < x_2 < 4$
2) Etablir un programme écrit en Turbo Pascal qui permettra de déterminer un encadrement d’amplitude $10^{-6}$ pour chacune de ces deux solutions.
3) Soit $N$ le rang des termes des suites $(a_n)$ et $(b_n)$ qui encadrement $x_2$ à $10^{-6}$ près.
a) Etablir un programme écrit en Turbo Pascal qui calcule et affiche $N$
b) Etablir un programme écrit en Turbo Pascal qui calcule et affiche $N$, $a_N$ et $b_N$
4) Soit $N’$ le rang des termes des suites $(a_n)$ et $(b_n)$ qui encadrement $x_1$ à $10^{-4}$ près. Proposer une version du programme établi en 3) qui permettra de calculer et afficher $N’$, $a_{N’}$ et $b_{N’}$.

(D’après sujet Bac Tunisien, Section Math, Session principale 2010)

Programme1 (Question 2) : intervalle d’encadrement)

  1. Program Encadrement_Solution;
  2. uses wincrt;
  3. var a,b,m:real;
  4. function f(x:real):real;
  5. begin
  6. f:=Ln(x)-x*Ln(x)+x;
  7. end;
  8. Begin
  9. write('Entrez la borne inférieure a : a= ');
  10. readln(a);
  11. write('Entrez la borne supérieure b : b= ');
  12. readln(b);
  13. repeat
  14. m:=(a+b)/2;
  15. if f(m)*f(a)<0 then b:=m else a:=m;
  16. until b-a<=1E-06;
  17. a:=a*1E+06;
  18. a:=Trunc(a);
  19. a:=a*1E-06;
  20. writeln('a= ',a);
  21. b:=b*1E+06;
  22. b:=Trunc(b);
  23. b:=b*1E-06;
  24. writeln('b= ',b);
  25. writeln(a,'<x2<',b)
  26. End.

Télécharger

Remarque :
Pour l’encadrement de chaque solution, entrer les bornes de l’intervalle de départ (Question 1) et dans l’avant-dernière ligne du programme, rectifier selon le cas : $x_1$ ou $x_2$.

Programme 2 (Question 3) a) Calcul et affichage du rang des termes)

  1. Program Rang_terme;
  2. uses wincrt;
  3. var N: integer;
  4. a, b, n, eps, y: real;
  5. function g(x:real):real;
  6. Begin
  7. g:= (Ln((b-a)/x)/Ln(2)) -1;
  8. end;
  9. Begin
  10. write ('Entrez a, a = ');
  11. readln(a);
  12. write ('Entrez b, b = ');
  13. readln(b);
  14. write ('Entrez eps, eps = ');
  15. readln(eps);
  16. y:= g(eps);
  17. N:= Trunc(y)+1;
  18. writeln (‘ N = ',N);
  19. End.

Télécharger

Programme 3 (Question 3) b) : calcul et affichage du rang et des valeurs des termes)

  1. Program Rang_Valeurs_termes;
  2. uses wincrt;
  3. var N, i: integer;
  4. a, b, eps, y, m: real;
  5. function g(x:real):real;
  6. Begin
  7. g:= (Ln((b-a)/x)/Ln(2)) -1;
  8. end;
  9. function f(x:real):real;
  10. begin
  11. f:=Ln(x)-x*Ln(x)+x;
  12. end;
  13. Begin
  14. write ('Entrez a, a = ');
  15. readln(a);
  16. write ('Entrez b, b = ');
  17. readln(b);
  18. write ('Entrez eps, eps = ');
  19. readln(eps);
  20. y:= g(eps);
  21. N:= Trunc(y)+1;
  22. For i:=0 to N do
  23. Begin
  24. m:=(a+b)/2;
  25. if f(m)*f(a)<0 then b:=m else a:=m;
  26. End;
  27. writeln('N= ',N );
  28. a:=a*1E+06;
  29. a:=Trunc(a);
  30. a:=a*1E-06;
  31. writeln('aN= ',a);
  32. b:=b*1E+06;
  33. b:=Trunc(b);
  34. b:=b*1E-06;
  35. writeln('bN= ',b);
  36. End.

Télécharger

Programme 4 (Question 4))

C’est à vous de jouer le jeu !

Conclusion

Par ce travail, j’ai voulu présenter au lecteur (qu’il soit enseignant ou élève de Terminale scientifique) un exemple de situation où l’interdisciplinarité peut beaucoup aider à assimiler les notions mises en jeu de différentes matières combinées : c’est le cas des mathématiques et l’informatique (et plus précisément, l’algorithmique) dans cet exemple.
Je tiens à signaler que les programmes que j’ai proposés ci-dessus peuvent être améliorés et enrichis par d’autres questions, telles que :

  • l’affichage des résultats de toutes les étapes de calcul,
  • la présentation de ces résultats sous forme d’un tableau,
  • la présentation de certaines parties sous forme de procédures à part

donc je ne prétends pas qu’ils sont des modèles à suivre, ils sont plutôt un support d’application de certaines notions d’algorithmie et d’illustration de certaines notions mathématiques.


Réagir à cet article
Vous souhaitez compléter cet article pour un numéro futur, réagir à son contenu, demander des précisions à l'auteur ou au comité de rédaction...
À lire aussi ici
MathémaTICE est un projet
en collaboration avec
Suivre la vie du site Flux RSS 2.0  |  Espace de rédaction  |  Nous contacter  |  Site réalisé avec: SPIP  |  N° ISSN 2109-9197