L’algorithme comme « application numérique » autour des zéros d’une fonction

Les premières problématiques de la sous-ingénierie

On attend d’un algorithme d’approximation d’un zéro d’une fonction qu’il rende deux valeurs aussi proches que l’on veut, encadrant un réel annulant la fonction (effectivité), et éventuellement qu’il soit garanti qu’il n’existe pas de zéros en dehors de cet encadrement (unicité). Nous nous intéressons particulièrement à la dichotomie qui, dans notre contexte, peut être mise en place dès la Seconde.
Soient a et b deux réels et f une fonction continue et définie sur l’intervalle [a ; b], telle que f(a) et f(b) ne soient pas de même signe. Le processus de dichotomie va alors consister à découper l’intervalle [a ; b] en deux intervalles de « même » amplitude. Si la valeur médiane annule la fonction, l’algorithme termine, sinon on conserve l’intervalle tel que f n’a pas le même signe aux deux bornes. On recommence ensuite ce processus en découpant de même l’intervalle conservé, et ainsi de suite. On obtient alors soit un zéro, soit des intervalles emboîtés tels que f n’a pas le même signe aux deux bornes et dont les amplitudes forment une suite géométrique de raison 0,5. On considère que l’algorithme est effectif si les intervalles encadrent un zéro (fig. 116).
Figure 116 (Représentation graphique d’une fonction continue f sur [a ; b] avec f(a)×f(b)<0 Pour atteindre une précision , arbitrairement petite, il suffit d’itérer ce processus n fois, où n est le plus petit entier tel que ≤ . On peut démontrer que n est le plus petit entier naturel supérieur ou égal à log2 (| − |). Cependant, ce résultat n’est pas exploité avec les élèves. Toutefois, il permet de prévoir qu’avec des données couramment utilisées comme une différence a – b égale à 1 ou 2 et choisi jusqu’à 10− 10, le nombre d’itération est au maximum de 34.
Notons que la dichotomie n’appartient pas à la famille dite des méthodes du point fixe. Cette famille est abordée en Terminale, mais impose des conditions supplémentaires sur la fonction. Nous n’abordons pas cet aspect dans cette sous-ingénierie (b).
La première partie de la sous-ingénierie (b), à travers des études de fonctions particulières, vise à ce que les élèves mettent en évidence la définition sur un intervalle et la « continuité » sur cet intervalle initial comme des conditions suffisantes d’effectivité de l’algorithme. Nous visons aussi à ce que les élèves mettent en évidence la « monotonie » sur l’intervalle initial comme une condition suffisante d’unicité du zéro cherché. Ces problématiques renvoient respectivement à une version restreinte du TVI et de son corollaire, le « Théorème de la Bijection » (TDB), au sens vu en Terminale Scientifique (cf. ci-après). La seconde partie de cette sous-ingénierie vise à ce que les élèves reconnaissent les propriétés des suites des bornes des intervalles emboîtés, et utilisent ces propriétés pour construire une démonstration du TVI.
Afin d’aider à la compréhension de l’arrière-plan mathématique de cette sous-ingénierie, nous rappelons les contenus des deux théorèmes retenus : TVI et (TDB). Dans l’ingénierie, nous nous restreignons au cas k = 0 où le TVI est obtenu directement avec l’algorithme. La généralisation à k quelconque est un travail algébrique sans rapport avec notre problématique.

Arrière-plan mathématique et institutionnel

A ce stade de notre présentation des objectifs de la sous-ingénierie, nous tenons à rappeler quelques points théoriques autour du TVI et de la méthode de dichotomie. Nous considérons une fonction f définie d’une partie de R dans R. Le TVI fait intervenir des éléments issus de la Topologie : (I) la continuité de la fonction : si f est une fonction continue et définie à la limite l d’une suite convergente (Un) (resp. (Vn)) dont les éléments appartiennent à son ensemble de définition et tels que f(Un) < 0 pour tout n (resp. f(Vn)> 0) alors f(l)=0 ; (II) le fait que les connexes de R sont les intervalles, et que par conséquent l’intervalle de départ est un connexe (CN) ; en effet, si f est définie sur un connexe, cela garantit que si elle est définie en deux points a et b, elle est aussi définie en et si de plus f est continue cela garantit qu’elle est définie à la limite de toute suite convergente dont les éléments appartiennent à son ensemble de définition ; (III) la complétude de R qui peut s’exprimer avec les énoncés équivalents suivants : (a) « Toute partie majorée non vide admet une borne supérieure » ; (b) « Toutes les suites de Cauchy sont convergentes » ; (c) Le « Théorème de la convergence monotone » :
• Toute suite croissante majorée est convergente » ; (d) « Toutes les paires de suites adjacentes convergent vers une même limite ». La propriété (d) permet de montrer que les suites adjacentes formées des bornes inférieures (resp. supérieures) des intervalles emboîtés, si elles existent, convergent vers une limite commune. Les conditions de continuité et de connexité garantissent l’existence des suites, et le fait que leur limite commune est un zéro de la fonction.
Nous considérons chacun de ces éléments du point de vue de l’enseignement au lycée. En effet, pour (I), la continuité s’appuie sur la prise de conscience de la continuité en un point ou sur un intervalle de fonctions de référence et sur des règles algébriques de conservation ; une définition rigoureuse, et utile pour la démonstration du TVI serait : « pour toute suite (Un) d’éléments de l’ensemble de définition de f, convergeant vers un élément l de cet ensemble, la suite f(Un) converge vers f(l) » ; pour (II), la connexité n’est pas abordée en classe scientifique, par contre la notion d’intervalle est supposée connue et la propriété de la connexité de l’intervalle est implicite ; le TVI n’est considéré que sur des intervalles fermés bornés ; pour (III), conformément au programme seul l’énoncé (c) « Théorème de la convergence monotone » est connue des élèves de Terminale Scientifique. En revanche, les élèves n’ont aucune connaissance particulière sur les suites adjacentes. Par conséquent, la démonstration du TVI ne peut pas être une application directe du cours. Les élèves doivent étudier individuellement chacune des deux suites produites par la méthode de dichotomie et montrer leur convergence et l’égalité des limites.

Première partie de la sous-ingénierie « dichotomie continue »

Les objectifs et les attentes

Les objectifs

Comme nous l’avons dit, la première partie de la sous-ingénierie vise à ce que les élèves prennent connaissance de l’algorithme et mettent en évidence la définition sur un intervalle et la continuité sur cet intervalle ainsi que la monotonie comme des conditions suffisantes d’effectivité de l’algorithme de dichotomie.
Cette première partie s’adresse au trois niveaux, incluant la Terminale scientifique. En Seconde et en Première, elle va mettre en jeu la compréhension de la méthode de dichotomie
• continue » comme moyen d’obtenir une approximation d’un antécédent par une fonction donnée et de prendre conscience du « Théorème des Valeurs Intermédiaires » et des conditions nécessaires dans ce théorème. Le théorème n’est pas connu des élèves de Seconde et de Première Scientifique. En Terminale, le TVI est déjà connu des élèves et il s’agit plutôt de préparer une preuve de ce théorème (cf. la seconde partie de la sous-ingénierie).
Du fait que l’algorithme de dichotomie interagit fortement dans l’ingénierie avec des contenus mathématiques, elle va nous permettre d’étudier les interactions entre différents ETA et ETM relatifs au domaine de l’analyse.

Les attentes

Un travail sur l’algorithme de dichotomie va permettre aux élèves d’obtenir une suite d’intervalles emboités et à bornes rationnelles, avec des conditions de signe aux bornes des intervalles, jusqu’à une amplitude arbitrairement petite. L’étude du corps de boucle va permettre aux élèves de construire la suite des bornes et une condition d’arrêt faisant intervenir l’amplitude du dernier intervalle. En effet, afin de faire le lien avec la sous-ingénierie précédente sur le cas de la dichotomie « discrète », les élèves vont étudier les différences sur les conditions d’arrêt dans une structure de boucle. Nous attendons ainsi que les élèves prennent conscience que suivant que la situation soit « discrète » ou « continue », la condition d’arrêt va être ramenée à une égalité à un nombre donné ou à une comparaison à un nombre arbitraire.
Nous attendons aussi des élèves qu’ils puissent observer des cas où, bien que l’algorithme termine, il n’encadre pas un zéro, ou il n’en encadre qu’un seul alors qu’il en existe plusieurs. Cette première partie de la sous-ingénierie se place dans le prolongement de la sous-ingénierie « dichotomie discrète ». Au cours de cette partie sur la « dichotomie continue », les élèves sont à nouveau confrontés à des éléments de nature informatique comme la conception d’une structure pour l’algorithme et la mise en place de variables. Du fait que l’algorithme opère sur une fonction mathématique, il peut être intéressant que les élèves utilisent une fonctionnalité de l’environnement de programmation permettant le calcul de valeurs avec le formalisme fonctionnel (f(…)), faisant ainsi un lien entre fonctions mathématiques et fonctions informatiques.