Approcher une solution : dichotomie et méthode de Newton

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

Dichotomie. On coupe l'intervalle en deux par son milieu $m = \dfrac{a + b}{2}$, on calcule le signe de $f(m)$, et on garde la moitié sur laquelle $f$ change encore de signe. Chaque étape divise l'amplitude par deux. Après $n$ étapes, l'amplitude vaut

$$\frac{b - a}{2^n}.$$

Sur notre exemple : $f(1{,}5) = 1{,}875 > 0$, on garde $[1\,;\,1{,}5]$ ; $f(1{,}25) = 0{,}203125 > 0$, on garde $[1\,;\,1{,}25]$ ; $f(1{,}125) = -0{,}451171875 < 0$, on garde $[1{,}125\,;\,1{,}25]$ ; $f(1{,}1875) = -0{,}137939453125 < 0$, on garde $[1{,}1875\,;\,1{,}25]$. Quatre étapes, amplitude $\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 $n$ étapes, on connaît un intervalle de longueur $\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 :

Ici, après quatre étapes, le milieu $1{,}21875$ approche $\alpha$ à $\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 $2^n \ge \dfrac{b - a}{\varepsilon}$, c'est-à-dire

Pour $b - a = 1$ et $\varepsilon = 10^{-3}$ : $2^{9} = 512 < 1000 \le 1024 = 2^{10}$, donc $n = 10$ étapes. Pour $10^{-6}$ : $2^{20} = 1\,048\,576 \ge 10^6 > 2^{19}$, donc $n = 20$. Retiens l'ordre de grandeur : environ 3,3 étapes par décimale gagnée, puisque $2^{3{,}32} \approx 10$. Et ce nombre ne dépend que de l'amplitude de départ et de la précision demandée — jamais de la fonction. La dichotomie est lente, mais elle est sûre : elle converge pour toute fonction continue qui change de signe.

L'idée. Près d'un point $x_0$, une courbe ressemble à sa tangente — c'est le sens même du nombre dérivé. Newton remplace donc l'équation $f(x) = 0$, qu'on ne sait pas résoudre, par l'équation de la tangente en $x_0$, qu'on sait résoudre : la tangente $y = f(x_0) + f'(x_0)\,(x - x_0)$ coupe l'axe des abscisses au point

On recommence en $x_1$, et ainsi de suite :

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

Le signe est moins, et l'on divise par la dérivée : ces deux détails sont la formule. Avec un signe plus, ou sans division, le point obtenu n'est plus l'intersection de la tangente avec l'axe, et la suite ne converge vers rien d'utile.

Sur l'exemple. Pour $f(x) = x^3 + x - 3$ et $x_0 = 2$ : $f(2) = 7$, $f'(2) = 13$, donc

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

Ensuite, en valeurs approchées : $x_3 \approx 1{,}2142$, $x_4 \approx 1{,}21341$, et $\alpha \approx 1{,}21341$. En quatre itérations, Newton donne six chiffres exacts ; la dichotomie, en quatre étapes, en donnait un.

Pourquoi c'est si rapide, et quand ça l'est. Sous des hypothèses de régularité ($f$ deux fois dérivable, $f'$ ne s'annulant pas près de $\alpha$), on admet l'inégalité

où $M$ majore $\lvert f'' \rvert$ et $m$ minore $\lvert f' \rvert$ sur un intervalle contenant $\alpha$ et les itérés. L'erreur est élevée au carré à chaque pas : 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 $2$). 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. Deux situations font échouer Newton :

• la dérivée s'annule en un itéré : la tangente est horizontale, elle ne coupe pas l'axe, $x_{n + 1}$ n'est pas défini — et si $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. Le cas favorable, celui des exercices de ce chapitre, est une fonction strictement croissante et convexe sur $[a\,;\,b]$ avec $f(a) < 0 < f(b)$ : en partant de $x_0 = b$, la suite de Newton est alors décroissante et converge vers $\alpha$. Pour $x^3 + x - 3$, $f''(x) = 6x > 0$ sur $[1\,;\,2]$ et l'on est parti de $2$ : c'est ce cas.

Quand s'arrêter ? Pas parce que $f(x_n)$ est petit. Une image petite ne dit rien si la dérivée est petite aussi : $\lvert f(x_n) \rvert \approx m\,\lvert x_n - \alpha \rvert$, donc $\lvert x_n - \alpha \rvert \le \dfrac{\lvert f(x_n) \rvert}{m}$ où $m$ minore $\lvert f' \rvert$. C'est le rapport de l'image à la dérivée qui mesure la distance à la solution, et l'on s'arrête quand deux itérés successifs sont proches et que la fonction change de signe entre les deux bornes d'un intervalle qui les contient — retour à la garantie de la dichotomie.

Deux méthodes, deux rôles. La dichotomie est lente, robuste, et donne une garantie (un encadrement). Newton est rapide, exigeant, et donne une valeur sans encadrement. En pratique, on localise par dichotomie, puis on accélère par Newton.

Énoncé. Soit $f(x) = x^3 + x - 3$ sur $\mathbb{R}$.

1. Montrer que $f(x) = 0$ admet une unique solution $\alpha$, et que $\alpha \in [1\,;\,2]$.
2. Combien d'étapes de dichotomie garantissent un intervalle d'amplitude inférieure ou égale à $10^{-3}$ ? Quelle erreur commet-on alors en retenant le milieu ?
3. Effectuer deux étapes de dichotomie et donner l'encadrement obtenu.
4. Calculer $x_1$ par la méthode de Newton en partant de $x_0 = 2$.

---

1. Existence et unicité. $f$ est dérivable sur $\mathbb{R}$ et $f'(x) = 3x^2 + 1 \ge 1 > 0$ : $f$ est strictement croissante, donc l'équation $f(x) = 0$ a au plus une solution. Comme $f(1) = 1 + 1 - 3 = -1 < 0$ et $f(2) = 8 + 2 - 3 = 7 > 0$, le théorème des valeurs intermédiaires en donne au moins une dans $]1\,;\,2[$. D'où l'unique solution $\alpha \in [1\,;\,2]$. Sans la stricte monotonie, on n'aurait pas l'unicité ; sans le changement de signe, on n'aurait pas l'existence.

2. Compter les étapes. L'amplitude de départ est $1$ ; après $n$ étapes elle vaut $\dfrac{1}{2^n}$. On veut $\dfrac{1}{2^n} \le 10^{-3}$, soit $2^n \ge 1000$. Or $2^9 = 512$ et $2^{10} = 1024$ : il faut $n = 10$ étapes. En retenant le milieu du dixième intervalle, l'erreur est au plus $\dfrac{1}{2^{11}} = \dfrac{1}{2048} < 5 \times 10^{-4}$ : la moitié de l'amplitude, pas l'amplitude.

3. Deux étapes, à la main. Milieu de $[1\,;\,2]$ : $1{,}5$, et $f(1{,}5) = 3{,}375 + 1{,}5 - 3 = 1{,}875 > 0$. Le changement de signe est entre $1$ et $1{,}5$ : on garde $[1\,;\,1{,}5]$. Milieu : $1{,}25$, et $f(1{,}25) = 1{,}953125 + 1{,}25 - 3 = 0{,}203125 > 0$. On garde $[1\,;\,1{,}25]$.

Les deux images sont des décimaux exacts : on peut écrire « $=$ ».

4. Un pas de Newton. $f(2) = 7$ et $f'(2) = 3 \times 4 + 1 = 13$, donc

Contrôle de cohérence : $x_1$ est bien dans $[1\,;\,2]$ et $f(x_1) = \dfrac{3479}{2197} > 0$, donc $\alpha < x_1$ — la suite descend vers $\alpha$, comme l'annonce le cas « croissante et convexe, départ à droite ».

Lecture. Deux étapes de dichotomie ont ramené l'amplitude à $0{,}25$ ; un seul pas de Newton a ramené l'écart à $\alpha$ de $0{,}79$ à environ $0{,}25$, et le suivant le ramène à environ $0{,}03$. Pour atteindre $10^{-3}$, la dichotomie a besoin de dix étapes ; Newton, de trois ou quatre. Mais seule la dichotomie t'a prouvé que $\alpha \in [1\,;\,1{,}25]$.

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é, $x$ de $-0{,}5$ à $4{,}5$, et la parabole de $f(x) = x^2 - 3x + 1$. Le point $A(2\,;\,-1)$ est marqué d'un disque plein ; trois sécantes issues de $A$ passent par des points $M$ de plus en plus proches ($h = 2$, $1$, $0{,}5$), et la tangente en $A$, en trait épais, a pour équation $y = x - 3$ — un triangle de pente en tirets rappelle $f'(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 = 3$. Or $2 - \dfrac{f(2)}{f'(2)} = 2 - \dfrac{-1}{1} = 3$ : c'est exactement $x_1$ de la méthode de Newton appliquée à cette parabole en partant de $x_0 = 2$. La solution voisine de l'équation $x^2 - 3x + 1 = 0$ est $\dfrac{3 + \sqrt{5}}{2} \approx 2{,}618$ ; les itérés suivants valent $x_2 = \dfrac{8}{3} \approx 2{,}6667$, $x_3 \approx 2{,}6190$, $x_4 \approx 2{,}61803$ — on voit doubler le nombre de chiffres exacts.
• Panneau 2. Le même point $A$ 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 = \lvert x \rvert$ (deux demi-tangentes en $O$), $y = \sqrt{x}$ (tangente verticale en $O$), $y = x^3$ (tangente horizontale en $O$, 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 — la tangente horizontale de $x^3$ en $0$ ne coupe pas l'axe, l'itération n'est pas définie.

Ce que la figure ne montre pas, et qu'il faut imaginer : la dichotomie. Sur le panneau 1, elle prendrait l'intervalle $[2\,;\,3]$ — où $f(2) = -1 < 0$ et $f(3) = 1 > 0$ — et le couperait en deux, encore et encore, sans jamais regarder la pente. Elle arriverait aussi à $2{,}618$, mais après une dizaine d'étapes pour trois décimales, là où deux pas de Newton suffisent. En revanche, elle n'aurait jamais eu besoin de la tangente : elle marche aussi sur les fonctions du panneau 3.

Trois nombres à distinguer après $n$ étapes de dichotomie. L'amplitude de l'intervalle, $\dfrac{b - a}{2^n}$ ; la borne d'erreur sur le milieu, $\dfrac{b - a}{2^{n + 1}}$ ; le nombre d'images de $f$ calculées, $n$ (une par étape, en plus des deux bornes initiales).

Le cas favorable pour Newton, celui des exercices : $f$ strictement croissante et convexe sur $[a\,;\,b]$, $f(a) < 0 < f(b)$, départ en $x_0 = b$. La suite est alors décroissante et converge vers $\alpha$ ; chaque itéré reste dans $[\alpha\,;\,b]$, et $f(x_n) > 0$ à chaque étape.

Ce qui n'est pas dans cette leçon. La démonstration de l'inégalité de convergence quadratique (Taylor-Lagrange), le théorème du point fixe et les fonctions contractantes, la méthode de la sécante, l'analyse de l'erreur d'arrondi en machine, et les systèmes de plusieurs équations.

1. Lancer la dichotomie sans changement de signe. Si $f(a)$ et $f(b)$ ont le même signe, l'algorithme tourne quand même et renvoie un nombre — qui n'approche aucune solution. Vérifier $f(a) \cdot f(b) < 0$ est la première ligne de toute rédaction, pas une formalité.
2. Confondre amplitude et erreur. Après $n$ étapes, l'intervalle a pour amplitude $\dfrac{b - a}{2^n}$ ; en retenant son milieu, l'erreur est au plus la moitié, $\dfrac{b - a}{2^{n + 1}}$. Quand l'énoncé demande « la borne d'erreur garantie », c'est la seconde.
3. Compter une étape de trop ou de moins. Une étape, c'est un milieu calculé et un intervalle divisé par deux. Les deux bornes initiales ne comptent pas comme étapes. Pour passer d'une amplitude $1$ à une amplitude $\le 10^{-3}$, il faut $10$ étapes ($2^{10} = 1024$), pas $9$ ($512 < 1000$).
4. Croire que la dichotomie va plus vite sur une fonction « gentille ». Le nombre d'étapes ne dépend que de $b - a$ et de $\varepsilon$. La régularité de $f$ ne change rien à la dichotomie ; elle change tout pour Newton.
5. Écrire Newton avec un signe plus, ou oublier la dérivée au dénominateur. $x_{n + 1} = x_n - \dfrac{f(x_n)}{f'(x_n)}$. Test rapide : sur $x^3 + x - 3$ depuis $2$, la bonne formule donne $\dfrac{19}{13} \approx 1{,}46$, à l'intérieur de $[1\,;\,2]$ ; un signe plus donnerait $2{,}54$, hors de l'intervalle.
6. S'arrêter parce que $f(x_n)$ est petit. Une image petite peut correspondre à un point éloigné si la dérivée est petite. La distance à la solution se contrôle par $\dfrac{\lvert f(x_n) \rvert}{m}$, avec $m$ un minorant de $\lvert f' \rvert$ — ou, plus sûrement, par un encadrement où $f$ change de signe.
7. Partir d'un point où la dérivée s'annule. La tangente est horizontale : $x_1$ n'est pas défini. Et près d'un tel point, la tangente presque horizontale envoie l'itéré très loin. Choisir $x_0$ du côté où $f$ et $f''$ ont le même signe (ici, $x_0 = b$ pour une fonction croissante convexe) évite l'incident.
8. Annoncer des décimales que le calcul ne garantit pas. $x_2 = \dfrac{20\,309}{16\,276}$ est exact ; « $x_2 \approx 1{,}2478$ » aussi. Mais écrire « $\alpha = 1{,}2478$ » est faux : $\alpha \approx 1{,}21341$. Un itéré de Newton n'est pas la solution, et rien dans la méthode ne dit à combien il en est — sauf l'encadrement, que seule la dichotomie ou un changement de signe fournit.

Le modèle d'entraînement. L'exercice associé à cette leçon pose une fonction $f(x) = x^3 + p\,x + q$ à coefficients entiers, dont la dérivée $3x^2 + p$ est strictement positive : l'unicité de la solution est démontrée, pas supposée. Il donne un intervalle $[A\,;\,B]$ où $f$ change de signe et demande, selon la variante, le nombre d'étapes de dichotomie qui garantit une amplitude donnée, la borne d'erreur en retenant le milieu, le milieu lui-même après quelques étapes, ou le premier itéré de Newton. Toutes les images calculées sont des entiers ou des décimaux exacts. Un modèle voisin, à choix multiples, propose quatre valeurs de $x_1$ dont trois sont bâties sur des erreurs réelles — signe plus, dérivée oubliée.

Énoncé type. Soit $f$ définie sur $\mathbb{R}$ par $f(x) = x^3 + 2x - 7$. Sa dérivée $f'(x) = 3x^2 + 2$ est strictement positive, donc $f$ est strictement croissante et l'équation $f(x) = 0$ admet une unique solution $\alpha$. De plus $f(1) = -4$ et $f(2) = 5$, donc $\alpha \in [1\,;\,2]$.

1. Combien d'étapes de dichotomie, à partir de cet intervalle, suffisent pour obtenir un intervalle d'amplitude inférieure ou égale à $10^{-2}$ ?
2. On applique la méthode de Newton à $f$ en partant de $x_0 = 2$. Calculer $x_1$.

Corrigé complet.

1. Compter. L'amplitude de départ est $2 - 1 = 1$ ; après $n$ étapes elle vaut $\dfrac{1}{2^n}$. On veut $\dfrac{1}{2^n} \le 10^{-2}$, soit $2^n \ge 100$. Or $2^6 = 64 < 100$ et $2^7 = 128 \ge 100$.

Sept étapes suffisent — et six ne suffisent pas.

Si l'on retenait alors le milieu du septième intervalle, l'erreur garantie serait $\dfrac{1}{2^8} = \dfrac{1}{256} \approx 0{,}0039$, la moitié de l'amplitude $\dfrac{1}{128}$. Remarque que ni $p$ ni $q$ n'ont servi : ce compte ne dépend pas de la fonction.

2. Un pas de Newton. On calcule l'image et la dérivée au point de départ : $f(2) = 8 + 4 - 7 = 5$ et $f'(2) = 3 \times 4 + 2 = 14$. Puis

3. Contrôler. $x_1 \in [1\,;\,2]$, et $f$ est croissante convexe sur cet intervalle ($f''(x) = 6x > 0$) avec un départ à droite : la suite doit descendre vers $\alpha$ tout en restant au-dessus. C'est le cas : $x_1 < x_0$, et $f\!\left(\dfrac{23}{14}\right) = \dfrac{12\,167}{2744} + \dfrac{23}{7} - 7 > 0$ puisque $\dfrac{12\,167}{2744} \approx 4{,}43$ et $\dfrac{23}{7} \approx 3{,}29$ : la somme dépasse $7$. Donc $\alpha < x_1$. $\checkmark$

Réponses : 7 étapes ; $x_1 = \dfrac{23}{14} \approx 1{,}643$.

Auto-contrôle. Ai-je vérifié le changement de signe avant de compter ? Ai-je distingué l'amplitude ($2^{-7}$) de l'erreur sur le milieu ($2^{-8}$) ? Le signe de la formule de Newton est-il un moins, et ai-je divisé par $f'(x_0)$ et non par $f(x_0)$ ? Mon $x_1$ est-il resté dans l'intervalle de localisation, du bon côté de $\alpha$ ?