« 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 :
- si $f(m)=0$ $\left( m=\dfrac{a+b}{2} \right)$ alors $m$ est la racine de $f$ et le problème est terminé
- 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).