Mathématiques · Licence 1 · 14 min de lecture
Approcher une solution : dichotomie et méthode de Newton
Localisation d'une solution par le théorème des valeurs intermédiaires ; algorithme de dichotomie, division par deux de l'amplitude à chaque étape, nombre d'étapes nécessaire pour atteindre une précision donnée et erreur commise en prenant le milieu ; méthode de Newton comme suite construite par les tangentes successives, hypothèses de fonctionnement et comparaison des deux vitesses de convergence.
Chapitre du programme : Analyse
Bloc 1 sur 7 · Comprendre
Comprendre : localiser, puis resserrer
Beaucoup d'équations n'ont pas de solution « en formule ». possède une expression par radicaux, mais une approximation certifiée peut être plus pratique : le théorème des valeurs intermédiaires vous dit qu'une solution existe, il ne vous dit pas laquelle. Ce chapitre répond à une question que le lycée laissait ouverte : comment obtenir cette solution avec la précision que l'on veut, et comment savoir qu'on l'a.
Localiser. Soit continue sur avec . Le théorème des valeurs intermédiaires garantit une solution de . Si de plus est strictement monotone sur l'intervalle, cette solution est unique : c'est le cas dès que la dérivée garde un signe strict, comme pour , dont la dérivée est toujours strictement positive. On a et : la solution est dans . L'intervalle a une amplitude de ; c'est le point de départ.
Dichotomie. On coupe l'intervalle en deux par son milieu , on calcule le signe de , et on garde la moitié sur laquelle change encore de signe. Si , on a trouvé une racine et on peut arrêter. Sinon chaque étape divise l’amplitude par deux. Après étapes, l'amplitude vaut
Sur notre exemple : , on garde ; , on garde ; , on garde ; , on garde . Quatre étapes, amplitude , et toutes ces images sont des décimaux exacts : rien n'a été arrondi.
Amplitude et erreur ne sont pas la même chose. Après étapes, on connaît un intervalle de longueur qui contient . Si l'on retient le milieu de cet intervalle comme valeur approchée, l'erreur commise est au plus la moitié de l'amplitude :
Ici, après quatre étapes, le milieu approche à près. Lire « l'erreur vaut l'amplitude » est l'erreur la plus fréquente du chapitre.
Compter les étapes. Pour garantir une amplitude inférieure ou égale à , il faut , c'est-à-dire
Pour et : , donc étapes. Pour : , donc . Retenez l’ordre de grandeur : environ 3,3 étapes par décimale gagnée, puisque . Cette borne a priori du nombre d’étapes ne dépend que de l’amplitude initiale et de la précision ; un arrêt anticipé sur un milieu racine peut dépendre de la fonction. La dichotomie est lente, mais elle est sûre : elle converge pour toute fonction continue qui change de signe.
Bloc 2 sur 7 · Approfondir
Approfondir : la méthode de Newton, ou suivre la tangente
L'idée. Près d'un point , une courbe ressemble à sa tangente — c'est le sens même du nombre dérivé. Newton remplace donc l'équation , qu'on ne sait pas résoudre, par l'équation de la tangente en , qu'on sait résoudre : la tangente coupe l'axe des abscisses au point
On recommence en , et ainsi de suite :
Itération de Newton. , pourvu que .
Le signe est moins, et l'on divise par la dérivée : ces deux détails sont la formule. Un signe plus ou l’omission de la division ne donnent pas en général l’intersection de la tangente avec l’axe ; un cas particulier peut néanmoins coïncider, notamment si la racine est déjà atteinte.
Sur l'exemple. Pour et : , , donc
Puis et , d'où
Ensuite, en valeurs approchées : , , et . Ces approximations sont rapides, mais le nombre de chiffres garantis doit venir d’une borne d’erreur, et non de la seule proximité de deux affichages.
Pourquoi c'est si rapide, et quand ça l'est. Sous des hypothèses de régularité ( de classe , et sur l’intervalle considéré), on admet l'inégalité
où majore et minore sur un intervalle contenant et les itérés. Une borne de l’erreur au pas suivant est proportionnelle au carré de l’erreur précédente, dans ce cadre local : le nombre de chiffres exacts double à peu près à chaque itération. On dit que la convergence est quadratique, là où celle de la dichotomie est linéaire (l'erreur est seulement divisée par un facteur fixe, ici ). La démonstration de cette inégalité repose sur l'inégalité de Taylor-Lagrange, vue plus tard dans l'année ; ici, on l'utilise.
Les hypothèses ne sont pas décoratives. Plusieurs situations peuvent faire échouer Newton, notamment :
- la dérivée s'annule en un itéré : la tangente est horizontale, si , elle ne coupe pas l’axe. Si , la racine est déjà trouvée et on arrête avant la division ; dans les deux cas, la formule suivante n’est pas définie — et si est seulement très petite, l'itéré part très loin ;
- le point de départ est mal choisi : la suite peut osciller ou s'éloigner. Un cas favorable est une fonction de classe , avec et sur avec : en partant de , les itérés, tant que la racine n’est pas atteinte, sont décroissants et convergent vers . Pour , sur et l'on est parti de : c'est ce cas.
Quand s'arrêter ? Pas parce que est petit. Une image petite ne dit rien si la dérivée est petite aussi : le théorème des accroissements finis, sur le segment entre et , donne , donc où minore . Un minorant certifié donne ainsi un contrôle d’erreur ; le quotient utilisant seulement est une correction de Newton, pas une borne universelle. On peut aussi s’arrêter lorsqu’un encadrement à changement de signe a une largeur assez petite. La proximité de deux itérés seule n’est pas une garantie.
Deux méthodes, deux rôles. La dichotomie est lente, robuste, et donne une garantie (un encadrement). Newton fournit une valeur ; des hypothèses supplémentaires permettent aussi un encadrement ou une borne d’erreur certifiée. En pratique, on localise par dichotomie, puis on accélère par Newton.
Bloc 3 sur 7 · Exemple
Exemple guidé : Newton et un encadrement certifié
On veut approcher , racine positive de . Sur , est continue et strictement croissante, et : il y a une unique racine dans cet intervalle.
Dichotomie. Le milieu 3/2 a pour image 1/4>0 ; le milieu de , soit 5/4, a pour image −7/16<0. Après deux étapes, , largeur 1/4 et erreur sur le milieu au plus 1/8.
Newton depuis . La formule se simplifie en . Ainsi , puis .
Transformer une valeur en encadrement. Si , alors puisque . Pour , on obtient , largeur . Pour , , largeur , car .
Contrôle de précision. La première largeur est inférieure à 1/200 ; la seconde à 1/200000. Le milieu de chaque encadrement a une erreur au plus sa demi-largeur. Newton peut donc être accompagné d’une certification, lorsqu’on justifie l’encadrement ; la seule rapidité apparente des décimales n’aurait pas suffi.
Bloc 4 sur 7 · Visualiser
Visualiser : de la sécante à la tangente, puis à la solution
Figure (fig.math.secant-to-tangent, figure programmatique de la leçon de première sur le nombre dérivé, réutilisée ici parce qu'elle contient déjà une étape de Newton) : trois panneaux.
- Panneau 1. Un repère orthonormé, de à , et la parabole de . Le point est marqué d'un disque plein ; trois sécantes issues de passent par des points de plus en plus proches (, , ), et la tangente en , en trait épais, a pour équation — un triangle de pente en tirets rappelle . Une flèche courbe montre les sécantes qui tournent vers la tangente. Ce qu'il faut y lire pour cette leçon : la tangente coupe l'axe des abscisses en . Or : c'est exactement de la méthode de Newton appliquée à cette parabole en partant de . La solution voisine de l'équation est ; les itérés suivants valent , , — on voit doubler le nombre de chiffres exacts.
- Panneau 2. Le même point dans une fenêtre dix fois plus petite : la parabole et sa tangente y sont presque indiscernables, la parabole légèrement au-dessus. Le cartouche dit « de près, la courbe ressemble à sa tangente ». C'est toute la méthode de Newton : remplacer la courbe par sa tangente, résoudre sur la tangente, recommencer plus près.
- Panneau 3. Trois miniatures de fonctions sans nombre dérivé ou à tangente particulière : (deux demi-tangentes en ), (tangente verticale en ), (tangente horizontale en , que la courbe traverse). Pour cette leçon, ce sont les trois situations où Newton se dérègle : pas de tangente, tangente verticale, ou dérivée nulle — pour en 0, la tangente est l’axe lui-même et la racine est déjà atteinte : on arrête, car la formule donnerait 0/0.
Ce que la figure ne montre pas, et qu'il faut imaginer : la dichotomie. Sur le panneau 1, elle prendrait l'intervalle — où et — et le couperait en deux, encore et encore, sans jamais regarder la pente. Elle arriverait aussi à , mais après une dizaine d'étapes pour trois décimales, alors qu’après deux pas de Newton depuis 2, l’erreur vaut encore environ 0,049 ; les itérations suivantes sont nécessaires pour trois décimales. En revanche, elle n'aurait jamais eu besoin de la tangente : elle n’exige pas de dérivée, mais exige toujours continuité et changement de signe ou une racine à une borne. Pour autour de 0 ou à sa borne 0, cette condition de signes opposés n’est pas disponible ; il faut d’abord traiter ces cas autrement.
Continuez sur votre lancée
Vous avez découvert l’essentiel et un exemple. Retrouvez la suite du cours et les points à retenir, puis passez à l’entraînement dans votre compte.
- Les formules et les repères à retenir
- Les erreurs fréquentes expliquées
- Un exercice d’entraînement, avec la réponse attendue après chaque essai
L’accès gratuit comprend les cours de votre niveau choisi et 5 exercices par jour.
Vous êtes parent ? Avec Premium pour un enfant ou Famille : toutes les classes, les indices et le corrigé pas à pas pendant l’exercice, et le bilan de chaque séance dans votre espace. Voir les offres pour les parents
Sources
- BO spécial n°1 du 11 février 2021 — programme de mathématiques de la classe de MPSI
- J.-P. Demailly, Analyse numérique et équations différentielles, EDP Sciences
- J. Stewart, Analyse — concepts et contextes, De Boeck
- OpenStax, Calculus Volume1, 4.9 — formule de Newton et cas d’échec : https://openstax.org/books/calculus-volume-1/pages/4-9-newtons-method
Vous pensez avoir trouvé une erreur dans cette leçon ? Signalez-la.