Exercices corrigés : la résolution approchée d'équations (201-SN2-RE, ancien 201-NYA)

$f(x)=x^{3}+x^{2}-3$, $f(1)=-1<0<f(2)=9$. Milieu $1{,}5$ : $f(1{,}5)=2{,}625>0$, on garde $[1\,;1{,}5]$. Milieu $1{,}25$ : $f(1{,}25)\approx 0{,}516>0$, on garde $[1\,;1{,}25]$. Milieu $1{,}125$ : $f(1{,}125)\approx-0{,}311<0$, on garde $[1{,}125\,;1{,}25]$. Le milieu de ce dernier intervalle vaut $1{,}1875$. Piège : rendre le dernier milieu TESTÉ, $1{,}125$, au lieu du milieu de l'intervalle obtenu.

$f(x)=e^{x}+x-2$, $f(0)=-1<0<f(1)=e-1$. $f(0{,}5)\approx 0{,}149>0$ : $[0\,;0{,}5]$. $f(0{,}25)\approx-0{,}466<0$ : $[0{,}25\,;0{,}5]$. $f(0{,}375)\approx-0{,}170<0$ : $[0{,}375\,;0{,}5]$. Milieu : $0{,}4375$. Piège : bissecter $e^{x}$ et $2-x$ séparément ; seul le signe de leur DIFFÉRENCE dit de quel côté est la racine.

$f(x)=x^{2}-7$, $f'(x)=2x$, donc $x_{n+1}=x_{n}-\frac{x_{n}^{2}-7}{2x_{n}}$. $x_{1}=3-\frac{2}{6}=\frac{8}{3}\approx 2{,}666667$, puis $x_{2}=\frac{8}{3}-\frac{\frac{64}{9}-7}{\frac{16}{3}}=\frac{8}{3}-\frac{1}{48}=\frac{127}{48}\approx 2{,}646$.

$f(x)=x^{3}-10$, $f'(x)=3x^{2}$. $x_{1}=2-\frac{8-10}{12}=\frac{13}{6}\approx 2{,}166667$. $f(x_{1})\approx 0{,}171296$ et $f'(x_{1})\approx 14{,}083333$, donc $x_{2}\approx 2{,}166667-0{,}012163\approx 2{,}155$.

$f(x)=x^{3}-2x-5$, $f'(x)=3x^{2}-2$. $x_{1}=2-\frac{-1}{10}=2{,}1$. $f(2{,}1)=9{,}261-4{,}2-5=0{,}061$ et $f'(2{,}1)=11{,}23$, donc $x_{2}=2{,}1-\frac{0{,}061}{11{,}23}\approx 2{,}094568\approx 2{,}095$.

$f(x)=x^{4}+x-3$, $f'(x)=4x^{3}+1$. $x_{1}=1-\frac{-1}{5}=1{,}2$. $f(1{,}2)=2{,}0736+1{,}2-3=0{,}2736$ et $f'(1{,}2)=7{,}912$, donc $x_{2}=1{,}2-\frac{0{,}2736}{7{,}912}\approx 1{,}165$.

$f(x)=\sin x-\frac{x}{2}$, $f'(x)=\cos x-\frac{1}{2}$. $f(2)\approx-0{,}090703$ et $f'(2)\approx-0{,}916147$, donc $x_{1}\approx 1{,}900996$. Puis $f(x_{1})\approx-0{,}004520$ et $f'(x_{1})\approx-0{,}824232$, donc $x_{2}\approx 1{,}895512\approx 1{,}896$. Piège : la calculatrice en degrés donne $f(2)\approx-0{,}965$ et une suite qui n'a plus rien à voir avec l'équation.

$f(x)=\ln x+x-2$, $f'(x)=\frac{1}{x}+1$. $f(1{,}5)\approx-0{,}094535$ et $f'(1{,}5)\approx 1{,}666667$, donc $x_{1}\approx 1{,}556721$. Puis $f(x_{1})\approx-0{,}000697$ et $f'(x_{1})\approx 1{,}642376$, donc $x_{2}\approx 1{,}557146\approx 1{,}557$.

$f(x)=e^{x}-4x$, $f'(x)=e^{x}-4$. $f(0)=1$ et $f'(0)=-3$, donc $x_{1}=0-\frac{1}{-3}=\frac{1}{3}$. Puis $f\left(\frac{1}{3}\right)\approx 0{,}062279$ et $f'\left(\frac{1}{3}\right)\approx-2{,}604388$, donc $x_{2}\approx 0{,}333333+0{,}023913\approx 0{,}357$. Piège : la dérivée négative ; moins par moins, on AVANCE vers la droite.

Le minimum est là où $f'$ s'annule : on applique Newton à $g=f'$, soit $g(x)=4x^{3}+6x-5$ et $g'(x)=f''(x)=12x^{2}+6$. $x_{1}=1-\frac{5}{18}=\frac{13}{18}\approx 0{,}722222$. Puis $g(x_{1})\approx 0{,}840192$ et $g'(x_{1})\approx 12{,}259259$, donc $x_{2}\approx 0{,}722222-0{,}068535\approx 0{,}654$. Piège : écrire $x_{1}=x_{0}-\frac{f(x_{0})}{f'(x_{0})}$, qui cherche un zéro de $f$ et non son minimum.

$f(1)=1+3-5=-1<0$ et $f(2)=8+6-5=9>0$ ✓, et $f$ est continue comme polynôme. Algorithme : on calcule le milieu $m$ de l'intervalle, on évalue $f(m)$, puis on garde celle des deux moitiés dont les extrémités donnent des signes opposés. On recommence. À chaque tour, l'intervalle contient encore une racine et sa largeur est divisée par deux.

$m_{1}=1{,}5$ : $f(1{,}5)=3{,}375+4{,}5-5=2{,}875>0$, donc on garde $[1\ ;\ 1{,}5]$. $m_{2}=1{,}25$ : $f(1{,}25)=1{,}953125+3{,}75-5=0{,}703125>0$, on garde $[1\ ;\ 1{,}25]$. $m_{3}=1{,}125$ : $f(1{,}125)=1{,}423828+3{,}375-5=-0{,}201172<0$, on garde cette fois la moitié DROITE, $[1{,}125\ ;\ 1{,}25]$. Largeur atteinte : $0{,}125$, et la racine y est.

La largeur après $n$ itérations vaut $\frac{2-1}{2^{n}}=2^{-n}$. Pour garantir $2^{-n}\leq 10^{-6}$, il faut $n\geq\frac{6\ln 10}{\ln 2}\approx 19{,}93$, donc $n=20$ itérations. C'est un nombre connu D'AVANCE, indépendant de la fonction : c'est la grande force de la méthode, on peut promettre la précision avant d'avoir commencé.

Gagner une décimale, c'est diviser l'erreur par 10. Comme chaque itération la divise par 2, il faut $n$ tel que $2^{n}\geq 10$, soit $n\geq\frac{\ln 10}{\ln 2}\approx 3{,}32$ : il faut donc entre 3 et 4 itérations par décimale. C'est le rythme régulier caractéristique d'une convergence linéaire, et il faut le comparer au comportement de Newton, qui DOUBLE le nombre de décimales à chaque tour.

La GARANTIE. Si le signe change aux bornes et si la fonction est continue, la bissection converge toujours, quelle que soit la fonction, et l'on connaît l'erreur maximale à chaque étape. Newton est beaucoup plus rapide mais peut diverger, cycler, ou converger vers une autre racine que celle qu'on visait. C'est pourquoi les bibliothèques numériques sérieuses combinent les deux : bissection pour approcher sans risque, puis Newton pour finir vite.

La tangente en $x_{n}$ est $y=f(x_{n})+f'(x_{n})(x-x_{n})$. Elle coupe l'axe quand $y=0$, soit $x=x_{n}-\frac{f(x_{n})}{f'(x_{n})}$, à condition que $f'(x_{n})\neq 0$. On pose donc $x_{n+1}=x_{n}-\frac{f(x_{n})}{f'(x_{n})}$ : c'est la formule de Newton. Elle n'a rien de mystérieux, c'est une équation de droite résolue.

$f(2)=2$ et $f'(2)=4$, donc $x_{1}=2-\frac{2}{4}=1{,}5$ ✓. Puis $f(1{,}5)=0{,}25$ et $f'(1{,}5)=3$, donc $x_{2}=1{,}5-\frac{0{,}25}{3}=1{,}4166667$ ✓. Une itération de plus donne $x_{3}=1{,}4142157$, à comparer avec $\sqrt{2}=1{,}4142136$ : trois itérations depuis un point de départ médiocre suffisent pour cinq décimales exactes.

$f'(x)=2x$, donc $x_{n+1}=x_{n}-\frac{x_{n}^{2}-a}{2x_{n}}=\frac{2x_{n}^{2}-x_{n}^{2}+a}{2x_{n}}=\frac{x_{n}^{2}+a}{2x_{n}}=\frac{1}{2}\left(x_{n}+\frac{a}{x_{n}}\right)$. C'est la MOYENNE de $x_{n}$ et de $\frac{a}{x_{n}}$. L'interprétation est jolie : si $x_{n}$ est trop petit pour être $\sqrt{a}$, alors $\frac{a}{x_{n}}$ est trop grand, et la vraie racine est entre les deux. Cette formule était déjà connue des Babyloniens, bien avant que Newton n'en donne la justification générale.

$f'(x)=3x^{2}+3$. $f(1)=-1$ et $f'(1)=6$, donc $x_{1}=1+\frac{1}{6}=1{,}1666667$. Puis $f(x_{1})=0{,}0879630$ et $f'(x_{1})=7{,}0833333$, donc $x_{2}=1{,}1666667-0{,}0124183=1{,}1542484$. Enfin $f(x_{2})=0{,}0005378$ et $f'(x_{2})=6{,}9969$, donc $x_{3}=1{,}1541715$. La racine exacte vaut $1{,}1541715$ : sept décimales en trois tours.

La bissection avait donné, après trois itérations, l'encadrement $[1{,}125\ ;\ 1{,}25]$, soit une erreur pouvant atteindre $0{,}125$. Newton, après trois itérations, donne une erreur inférieure à $10^{-7}$. Le rapport est d'environ un million, et il reste énorme même en comptant qu'un tour de Newton coûte deux évaluations, de la fonction et de sa dérivée, contre une pour la bissection. C'est le prix à payer qui change : Newton exige de connaître $f'$ et un point de départ raisonnable, la bissection ne demande qu'un changement de signe.

Avec $\sqrt{2}=1{,}41421356$ : $e_{0}=\left|2-1{,}41421356\right|=0{,}58578644$ ; $e_{1}=\left|1{,}5-1{,}41421356\right|=0{,}08578644$ ; $e_{2}=\left|1{,}41666667-1{,}41421356\right|=0{,}00245310$ ; $e_{3}=\left|1{,}41421569-1{,}41421356\right|=2{,}1239\times 10^{-6}$.

$\frac{e_{1}}{e_{0}^{2}}=\frac{0{,}08578644}{0{,}34314}=0{,}25000$ ; $\frac{e_{2}}{e_{1}^{2}}=\frac{0{,}00245310}{0{,}0073593}=0{,}33333$ ; $\frac{e_{3}}{e_{2}^{2}}=\frac{2{,}1239\times 10^{-6}}{6{,}0177\times 10^{-6}}=0{,}35294$. Les rapports se STABILISENT autour de $0{,}3536\approx\frac{1}{2\sqrt{2}}$. C'est la signature de la convergence quadratique : l'erreur nouvelle est proportionnelle au carré de l'ancienne, avec une constante qui tend vers $\frac{f''(r)}{2f'(r)}=\frac{2}{2\times 2\sqrt{2}}=\frac{1}{2\sqrt{2}}$.

$x_{n+1}-\sqrt{a}=\frac{x_{n}^{2}+a}{2x_{n}}-\sqrt{a}=\frac{x_{n}^{2}+a-2\sqrt{a}\,x_{n}}{2x_{n}}=\frac{\left(x_{n}-\sqrt{a}\right)^{2}}{2x_{n}}=\frac{e_{n}^{2}}{2x_{n}}$. Le numérateur est un carré parfait, ce qui donne DEUX renseignements d'un coup : la convergence est quadratique, et $e_{n+1}$ est toujours positif, donc la suite approche la racine par valeurs supérieures dès le premier tour, quel que soit le point de départ positif.

Si l'erreur passe de $10^{-k}$ à environ $C\times 10^{-2k}$, le nombre de décimales exactes DOUBLE à chaque itération : 1, 2, 4, 8, 16. La bissection, elle, en gagne une toutes les 3,32 itérations. Pour atteindre 16 décimales à partir d'une décimale, Newton demande 4 tours, la bissection en demande une cinquantaine.

Elle rend le critère d'arrêt facile et sûr. Dès que deux itérés consécutifs coïncident sur $k$ décimales, le suivant en donnerait environ $2k$ : l'écart $\left|x_{n+1}-x_{n}\right|$ est donc une excellente estimation de l'erreur restante, ce qui n'est pas vrai des méthodes linéaires. En pratique, on arrête dès que cet écart passe sous la précision voulue, et l'on sait qu'on a en réalité bien mieux. C'est aussi pourquoi un programme qui ne converge pas en une dizaine d'itérations ne convergera pas du tout : il faut détecter l'échec, pas insister.

La formule divise par $f'(x_{n})$ : le calcul s'arrête sur une division par zéro. Géométriquement, la tangente est HORIZONTALE et ne coupe jamais l'axe. Exemple : $f(x)=x^{2}-1$ avec $x_{0}=0$ donne $f'(0)=0$, la méthode est bloquée dès le premier tour alors que les racines $\pm 1$ sont toutes proches.

$f(0)=2$ et $f'(x)=3x^{2}-2$, donc $f'(0)=-2$ et $x_{1}=0-\frac{2}{-2}=1$. Puis $f(1)=1-2+2=1$ et $f'(1)=1$, donc $x_{2}=1-\frac{1}{1}=0$. On est revenu au point de départ : la suite CYCLE entre 0 et 1 indéfiniment, sans jamais approcher la vraie racine, qui vaut environ $-1{,}7693$. Les deux tangentes de la figure se renvoient la balle. Aucun test sur $f(x_{n})$ ne détecte cela, seul un compteur d'itérations le fait.

$f(x)=x^{1/3}$ donne $f'(x)=\frac{1}{3}x^{-2/3}$, donc $x_{n+1}=x_{n}-\frac{x_{n}^{1/3}}{\frac{1}{3}x_{n}^{-2/3}}=x_{n}-3x_{n}=-2x_{n}$. Partant de $x_{0}=1$ : $1$, $-2$, $4$, $-8$, $16$, la suite double en valeur absolue et change de signe à chaque tour. Elle DIVERGE, alors que la racine, $x=0$, est le point de départ le plus naturel du monde. La raison est que la tangente est verticale en 0 : la courbe monte trop vite pour que sa tangente ramène vers la racine.

$f'(x)=2(x-1)$, donc $x_{n+1}=x_{n}-\frac{(x_{n}-1)^{2}}{2(x_{n}-1)}=x_{n}-\frac{x_{n}-1}{2}=\frac{x_{n}+1}{2}$. Partant de 2 : $1{,}5$, $1{,}25$, $1{,}125$, $1{,}0625$. La méthode converge bien vers 1, mais l'erreur n'est plus que DIVISÉE PAR DEUX à chaque tour : la convergence est devenue linéaire, exactement comme la bissection. C'est le comportement systématique sur une racine MULTIPLE, où $f$ et $f'$ s'annulent ensemble.

Un, la tangente est horizontale et la division est impossible. Deux, la suite cycle entre deux valeurs. Trois, la suite diverge, notamment quand la tangente est verticale près de la racine. Quatre, la convergence dégénère en linéaire sur une racine multiple. Protection : borner le nombre d'itérations, vérifier que $\left|f(x_{n})\right|$ diminue réellement, revenir à une bissection quand ce n'est pas le cas, et détecter les racines multiples en surveillant si $f'$ tend vers zéro en même temps que $f$.

GARANTIE : la bissection converge toujours si le signe change et si $f$ est continue ; Newton peut diverger, cycler ou changer de racine. VITESSE : linéaire de rapport $\frac{1}{2}$ pour la bissection, quadratique pour Newton. INFORMATION : la bissection demande seulement un encadrement à signes opposés ; Newton demande $f'$ et un point de départ proche. COÛT PAR ITÉRATION : une évaluation de $f$ pour la bissection, une évaluation de $f$ ET une de $f'$ pour Newton, soit environ le double.

Bissection : la largeur initiale vaut 1, il faut $2^{-n}\leq 10^{-10}$, donc $n\geq\frac{10\ln 10}{\ln 2}\approx 33{,}2$, soit 34 itérations. Newton depuis $x_{0}=1$ : les erreurs successives sont d'environ $1{,}5\times 10^{-1}$, $1{,}2\times 10^{-2}$, $8\times 10^{-5}$, puis $3\times 10^{-9}$ et enfin en dessous de $10^{-16}$. Le quatrième itéré est donc déjà exact, et la cinquième itération est celle qui le confirme par le critère d'arrêt, puisque $\left|x_{5}-x_{4}\right|<10^{-10}$ alors que $\left|x_{4}-x_{3}\right|\approx 3\times 10^{-9}$ : cinq itérations. Même en comptant deux évaluations par tour, Newton coûte environ dix évaluations contre trente-quatre.

On commence par quelques bissections pour amener l'itéré dans un voisinage sûr de la racine, puis on bascule sur Newton pour terminer. Si un pas de Newton sort de l'intervalle encadrant, ou si $\left|f\right|$ ne diminue pas, on rejette ce pas et l'on fait une bissection à la place. Le résultat cumule les deux avantages : on garde à tout instant un encadrement, donc la garantie de la bissection, ET la vitesse finale de Newton. C'est le principe des méthodes de Brent et de Dekker, présentes dans presque toutes les bibliothèques scientifiques.

L'équation s'écrit $f(x)=\cos x-x=0$. On dispose de $f'(x)=-\sin x-1$, facile à écrire, et $f(0)=1>0$ tandis que $f(1)=\cos 1-1\approx-0{,}4597<0$ : on a donc à la fois la dérivée et un bon encadrement, Newton est le bon choix. Depuis $x_{0}=1$ : $x_{1}=0{,}7503639$, $x_{2}=0{,}7391129$, $x_{3}=0{,}7390851$. La solution est $0{,}739085$ à $10^{-6}$ près, le fameux nombre de Dottie, seul point fixe du cosinus.

Parce que la formule de Cardan, exacte, est en pratique inutilisable : elle fait intervenir des racines cubiques de nombres COMPLEXES même lorsque les trois racines sont réelles, elle perd de la précision par annulations catastrophiques en arithmétique flottante, et elle n'existe tout simplement pas au delà du degré 4, théorème d'Abel. Newton, lui, ne demande rien d'autre que de savoir évaluer $f$ et $f'$, donc il s'applique aussi bien à un polynôme de degré 30 qu'à $\cos x-x$. En calcul numérique, une méthode générale et convergente vaut presque toujours mieux qu'une formule fermée fragile.

On remplace $f'(x_{n})$ par $\frac{f(x_{n})-f(x_{n-1})}{x_{n}-x_{n-1}}$, ce qui donne $x_{n+1}=x_{n}-f(x_{n})\cdot\frac{x_{n}-x_{n-1}}{f(x_{n})-f(x_{n-1})}$. Géométriquement, on trace la droite passant par les deux derniers points de la courbe et l'on prend son intersection avec l'axe. Il faut donc DEUX points de départ, contre un seul pour Newton.

$f(1)=-1$ et $f(2)=2$. $x_{2}=2-2\times\frac{2-1}{2-(-1)}=2-\frac{2}{3}=1{,}3333333$. Puis $f(x_{2})=-0{,}2222222$, donc $x_{3}=1{,}3333333-(-0{,}2222222)\times\frac{1{,}3333333-2}{-0{,}2222222-2}=1{,}3333333+0{,}0666667=1{,}4$. Enfin $f(1{,}4)=-0{,}04$ et $x_{4}=1{,}4+0{,}04\times\frac{1{,}4-1{,}3333333}{-0{,}04+0{,}2222222}=1{,}4146341$. On approche $\sqrt{2}=1{,}4142136$ sans avoir jamais dérivé.