Aller au contenu principal
ESPRIT VIF
Créer un compte
Se connecterMon compteCréer un compte
Mon compte

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

Nombre dérivé : les sécantes issues de A pivotent vers la tangente ; zoom où courbe et tangente se confondent ; deux cas sans nombre dérivé en 0 — Trois panneaux. Panneau 1 : repère orthonormé, x de −0,5 à 4,5, y de −2 à 6
Nombre dérivé : les sécantes issues de A pivotent vers la tangente ; zoom où courbe et tangente se confondent ; deux cas sans nombre dérivé en 0 · Ouvrir la figure en grand

Bloc 1 sur 7 · Comprendre

Comprendre : localiser, puis resserrer

Beaucoup d'équations n'ont pas de solution « en formule ». x3+x−3=0x^3+x-3=0 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 ff continue sur [a ; b][a\,;\,b] avec f(a)<0<f(b)f(a) < 0 < f(b). Le théorème des valeurs intermédiaires garantit une solution α∈ ]a ; b[\alpha \in\ ]a\,;\,b[ de f(x)=0f(x) = 0. Si de plus ff 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 f(x)=x3+x−3f(x) = x^3 + x - 3, dont la dérivée f′(x)=3x2+1f'(x) = 3x^2 + 1 est toujours strictement positive. On a f(1)=−1<0f(1) = -1 < 0 et f(2)=7>0f(2) = 7 > 0 : la solution α\alpha est dans ]1 ; 2[]1\,;\,2[. L'intervalle a une amplitude de 11 ; c'est le point de départ.

Dichotomie. On coupe l'intervalle en deux par son milieu m=a+b2m = \dfrac{a + b}{2}, on calcule le signe de f(m)f(m), et on garde la moitié sur laquelle ff change encore de signe. Si f(m)=0f(m)=0, on a trouvé une racine et on peut arrêter. Sinon chaque étape divise l’amplitude par deux. Après nn étapes, l'amplitude vaut

b−a2n.\frac{b - a}{2^n}.

Sur notre exemple : f(1,5)=1,875>0f(1{,}5) = 1{,}875 > 0, on garde [1 ; 1,5][1\,;\,1{,}5] ; f(1,25)=0,203125>0f(1{,}25) = 0{,}203125 > 0, on garde [1 ; 1,25][1\,;\,1{,}25] ; f(1,125)=−0,451171875<0f(1{,}125) = -0{,}451171875 < 0, on garde [1,125 ; 1,25][1{,}125\,;\,1{,}25] ; f(1,1875)=−0,137939453125<0f(1{,}1875) = -0{,}137939453125 < 0, on garde [1,1875 ; 1,25][1{,}1875\,;\,1{,}25]. Quatre étapes, amplitude 116=0,0625\dfrac{1}{16} = 0{,}0625, 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 nn étapes, on connaît un intervalle de longueur b−a2n\dfrac{b - a}{2^n} qui contient α\alpha. Si l'on retient le milieu de cet intervalle comme valeur approchée, l'erreur commise est au plus la moitié de l'amplitude :

∣α−mn∣≤b−a2n+1.\left\lvert \alpha - m_n \right\rvert \le \frac{b - a}{2^{n + 1}}.

Ici, après quatre étapes, le milieu 1,218751{,}21875 approche α\alpha à 132=0,03125\dfrac{1}{32} = 0{,}03125 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 à ε\varepsilon, il faut 2n≥b−aε2^n \ge \dfrac{b - a}{\varepsilon}, c'est-à-dire

n≥log⁡2 ⁣(b−aε).n \ge \log_2\!\left(\frac{b - a}{\varepsilon}\right).

Pour b−a=1b - a = 1 et ε=10−3\varepsilon = 10^{-3} : 29=512<1000≤1024=2102^{9} = 512 < 1000 \le 1024 = 2^{10}, donc n=10n = 10 étapes. Pour 10−610^{-6} : 220=1 048 576≥106>2192^{20} = 1\,048\,576 \ge 10^6 > 2^{19}, donc n=20n = 20. Retenez l’ordre de grandeur : environ 3,3 étapes par décimale gagnée, puisque 23,32≈102^{3{,}32} \approx 10. 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 x0x_0, une courbe ressemble à sa tangente — c'est le sens même du nombre dérivé. Newton remplace donc l'équation f(x)=0f(x) = 0, qu'on ne sait pas résoudre, par l'équation de la tangente en x0x_0, qu'on sait résoudre : la tangente y=f(x0)+f′(x0) (x−x0)y = f(x_0) + f'(x_0)\,(x - x_0) coupe l'axe des abscisses au point

x1=x0−f(x0)f′(x0).x_1 = x_0 - \frac{f(x_0)}{f'(x_0)}.

On recommence en x1x_1, et ainsi de suite :

Itération de Newton. xn+1=xn−f(xn)f′(xn)\quad x_{n + 1} = x_n - \dfrac{f(x_n)}{f'(x_n)}, pourvu que f′(xn)≠0f'(x_n) \ne 0.

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 f(x)=x3+x−3f(x) = x^3 + x - 3 et x0=2x_0 = 2 : f(2)=7f(2) = 7, f′(2)=13f'(2) = 13, donc

x1=2−713=1913≈1,4615.x_1 = 2 - \frac{7}{13} = \frac{19}{13} \approx 1{,}4615.

Puis f ⁣(1913)=34792197f\!\left(\dfrac{19}{13}\right) = \dfrac{3479}{2197} et f′ ⁣(1913)=1252169f'\!\left(\dfrac{19}{13}\right) = \dfrac{1252}{169}, d'où

x2=1913−34792197⋅1691252=1913−347916 276=20 30916 276≈1,2478.x_2 = \frac{19}{13} - \frac{3479}{2197} \cdot \frac{169}{1252} = \frac{19}{13} - \frac{3479}{16\,276} = \frac{20\,309}{16\,276} \approx 1{,}2478.

Ensuite, en valeurs approchées : x3≈1,2142x_3 \approx 1{,}2142, x4≈1,21341x_4 \approx 1{,}21341, et α≈1,21341\alpha \approx 1{,}21341. 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é (ff de classe C2C^2, et ∣f′∣⩾m>0|f'|\geqslant m>0 sur l’intervalle considéré), on admet l'inégalité

∣xn+1−α∣≤M2m ∣xn−α∣2,\left\lvert x_{n + 1} - \alpha \right\rvert \le \frac{M}{2m}\,\left\lvert x_n - \alpha \right\rvert^2,

où MM majore ∣f′′∣\lvert f'' \rvert et m>0m>0 minore ∣f′∣\lvert f' \rvert sur un intervalle contenant α\alpha 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 22). 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 f(xn)≠0f(x_n)\neq0, elle ne coupe pas l’axe. Si f(xn)=0f(x_n)=0, 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 f′f' 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 C2C^2, avec f′>0f'>0 et f′′⩾0f''\geqslant0 sur [a ; b][a\,;\,b] avec f(a)<0<f(b)f(a) < 0 < f(b) : en partant de x0=bx_0 = b, les itérés, tant que la racine n’est pas atteinte, sont décroissants et convergent vers α\alpha. Pour x3+x−3x^3 + x - 3, f′′(x)=6x>0f''(x) = 6x > 0 sur [1 ; 2][1\,;\,2] et l'on est parti de 22 : c'est ce cas.

Quand s'arrêter ? Pas parce que f(xn)f(x_n) 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 xnx_n et α\alpha, donne ∣f(xn)∣⩾m∣xn−α∣|f(x_n)|\geqslant m|x_n-\alpha|, donc ∣xn−α∣≤∣f(xn)∣m\lvert x_n - \alpha \rvert \le \dfrac{\lvert f(x_n) \rvert}{m} où m>0m>0 minore ∣f′∣\lvert f' \rvert. Un minorant certifié m>0m>0 donne ainsi un contrôle d’erreur ; le quotient utilisant seulement f′(xn)f'(x_n) 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 2\sqrt2, racine positive de f(x)=x2−2f(x)=x^2-2. Sur [1;2][1;2], ff est continue et strictement croissante, f(1)=−1f(1)=-1 et f(2)=2f(2)=2 : il y a une unique racine α\alpha dans cet intervalle.

Dichotomie. Le milieu 3/2 a pour image 1/4>0 ; le milieu de [1;3/2][1;3/2], soit 5/4, a pour image −7/16<0. Après deux étapes, α∈[5/4;3/2]\alpha\in[5/4;3/2], largeur 1/4 et erreur sur le milieu au plus 1/8.

Newton depuis x0=3/2x_0=3/2. La formule se simplifie en xn+1=(xn+2/xn)/2x_{n+1}=(x_n+2/x_n)/2. Ainsi x1=(3/2+4/3)/2=17/12x_1=(3/2+4/3)/2=17/12, puis x2=(17/12+24/17)/2=577/408x_2=(17/12+24/17)/2=577/408.

Transformer une valeur en encadrement. Si xn>α>0x_n>\alpha>0, alors 2/xn<α<xn2/x_n<\alpha<x_n puisque α2=2\alpha^2=2. Pour x1x_1, on obtient 24/17<α<17/1224/17<\alpha<17/12, largeur 1/2041/204. Pour x2x_2, 816/577<α<577/408816/577<\alpha<577/408, largeur 1/2354161/235416, car 5772−2×4082=1577^2-2\times408^2=1.

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é, xx de −0,5-0{,}5 à 4,54{,}5, et la parabole de f(x)=x2−3x+1f(x) = x^2 - 3x + 1. Le point A(2 ; −1)A(2\,;\,-1) est marqué d'un disque plein ; trois sécantes issues de AA passent par des points MM de plus en plus proches (h=2h = 2, 11, 0,50{,}5), et la tangente en AA, en trait épais, a pour équation y=x−3y = x - 3 — un triangle de pente en tirets rappelle f′(2)=1f'(2) = 1. 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 x=3x = 3. Or 2−f(2)f′(2)=2−−11=32 - \dfrac{f(2)}{f'(2)} = 2 - \dfrac{-1}{1} = 3 : c'est exactement x1x_1 de la méthode de Newton appliquée à cette parabole en partant de x0=2x_0 = 2. La solution voisine de l'équation x2−3x+1=0x^2 - 3x + 1 = 0 est 3+52≈2,618\dfrac{3 + \sqrt{5}}{2} \approx 2{,}618 ; les itérés suivants valent x2=83≈2,6667x_2 = \dfrac{8}{3} \approx 2{,}6667, x3≈2,6190x_3 \approx 2{,}6190, x4≈2,61803x_4 \approx 2{,}61803 — on voit doubler le nombre de chiffres exacts.
  • Panneau 2. Le même point AA 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 : y=∣x∣y = \lvert x \rvert (deux demi-tangentes en OO), y=xy = \sqrt{x} (tangente verticale en OO), y=x3y = x^3 (tangente horizontale en OO, 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 x3x^3 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 [2 ; 3][2\,;\,3] — où f(2)=−1<0f(2) = -1 < 0 et f(3)=1>0f(3) = 1 > 0 — et le couperait en deux, encore et encore, sans jamais regarder la pente. Elle arriverait aussi à 2,6182{,}618, 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 ∣x∣|x| autour de 0 ou x\sqrt{x} à 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.

Accès rapide