Problème : la méthode de Newton converge quadratiquement

1) Un intervalle où tout est défini. $f^{\prime }$ est continue et $f^{\prime }(\ell )\ne 0$ : il existe $\delta >0$ tel que $|f^{\prime }(x)-f^{\prime }(\ell )|\le \frac{|f^{\prime }(\ell )|}{2}$ pour $|x-\ell |\le \delta$, et, $I$ étant ouvert, on peut prendre $\delta$ assez petit pour que $J\subset I$. Sur $J$, par l'inégalité triangulaire, $|f^{\prime }(x)|\ge |f^{\prime }(\ell )|-\frac{|f^{\prime }(\ell )|}{2}=\frac{|f^{\prime }(\ell )|}{2}>0$ : $f^{\prime }$ ne s'annule pas et $N$ est définie. Ensuite $N(\ell )=\ell -\frac{0}{f^{\prime }(\ell )}=\ell$ : la racine est un point fixe de $N$. Enfin, en réduisant au même dénominateur, $N(x)-\ell =(x-\ell )-\frac{f(x)}{f^{\prime }(x)}=\frac{(x-\ell )f^{\prime }(x)-f(x)}{f^{\prime }(x)}$.

2) Le terme d'ordre $1$ disparaît. Par Taylor-Young à l'ordre $2$ pour $f$ (de classe ${\mathcal{C}}^2$, avec $f(\ell )=0$) et à l'ordre $1$ pour $f^{\prime }$ (de classe ${\mathcal{C}}^1$) : $$f(\ell +h)=f^{\prime }(\ell )h+\frac{f^{\prime \prime }(\ell )}{2}{h}^2+o(h^2)$$ et $$h{f}^{\prime }(\ell +h)=h\left(f^{\prime }(\ell )+f^{\prime \prime }(\ell )h+o(h)\right)=f^{\prime }(\ell )h+f^{\prime \prime }(\ell )h^2+o(h^2).$$ En soustrayant : $h{f}^{\prime }(\ell +h)-f(\ell +h)=\frac{f^{\prime \prime }(\ell )}{2}{h}^2+o(h^2)$. Par le 1), on divise par $f^{\prime }(\ell +h)$, qui tend vers $f^{\prime }(\ell )\ne 0$ : $$N(\ell +h)-\ell =\frac{\frac{f^{\prime \prime }(\ell )}{2}{h}^2+o(h^2)}{f^{\prime }(\ell )+o(1)}=\frac{f^{\prime \prime }(\ell )}{2f^{\prime }(\ell )}{h}^2+o(h^2).$$ Le terme d'ordre $1$ s'est détruit : $f^{\prime }(\ell )h$ figurait dans $h{f}^{\prime }(\ell +h)$ et dans $f(\ell +h)$ avec le même coefficient. C'est toute l'idée de Newton : remplacer $f$ par sa tangente, c'est reproduire exactement sa partie d'ordre $1$, si bien que l'erreur commise est d'ordre $2$. Autrement dit, $N$ admet en $\ell$ un développement limité d'ordre $1$ sans terme en $h$ : $N$ est dérivable en $\ell$ et $N^{\prime }(\ell )=0$.

3) Une majoration, puis la convergence. D'après le 2), $\frac{N(\ell +h)-\ell }{h^2}\to C=\frac{f^{\prime \prime }(\ell )}{2f^{\prime }(\ell )}$ quand $h\to 0$. Une fonction qui a une limite finie est bornée au voisinage du point : il existe $\eta \in \left]0,\delta \right]$ tel que ce quotient soit, en valeur absolue, au plus $K=|C|+1$ pour $0<|h|\le \eta$ ; l'inégalité étant triviale en $h=0$, $$|N(x)-\ell |\le K(x-\ell {)}^2\text{pour }|x-\ell |\le \eta .$$ (L'inégalité de Taylor-Lagrange, que donnera le chapitre sur l'intégration, n'est pas nécessaire : un quotient qui a une limite est borné.)

Supposons $|e_0|\le \min \left(\eta ,\frac{1}{2K}\right)$ et montrons par récurrence que $x_n$ est défini, que $|e_n|\le \eta$ et que $K|e_n|\le {\left(\frac{1}{2}\right)}^{2^n}$. Au rang $0$, c'est l'hypothèse : $K|e_0|\le \frac{1}{2}$. Si c'est vrai au rang $n$, alors $x_n\in [\ell -\eta ,\ell +\eta ]\subset J$, $x_{n+1}=N(x_n)$ est défini, et, en multipliant par $K$ la majoration précédente, $$K|e_{n+1}|\le (K|e_n|{)}^2\le {\left({\left(\frac{1}{2}\right)}^{2^n}\right)}^2={\left(\frac{1}{2}\right)}^{2^{n+1}},$$ tandis que $$|e_{n+1}|\le (K|e_n|)|e_n|\le \frac{1}{2}|e_n|\le \eta .$$ Ce qui achève la récurrence. En particulier $e_n\to 0$ : la suite de Newton converge vers $\ell$ dès que $x_0$ est assez proche de $\ell$ — et vite, puisque ${\left(\frac{1}{2}\right)}^{2^n}$ est inférieur à $10^{-9}$ dès $n=5$.

4) L'équivalent, et les décimales. On suppose $f^{\prime \prime }(\ell )\ne 0$, donc $C\ne 0$, et $e_n\ne 0$ pour tout $n$. Comme $e_n\to 0$, on compose le développement du 2) avec la suite $(e_n)$ : $$e_{n+1}=N(\ell +e_n)-\ell =C{e}_n^2+o(e_n^2),$$ donc $e_{n+1}\sim C{e}_n^2$. Si $|e_n|\approx 10^{-d}$, alors $|e_{n+1}|\approx |C|10^{-2d}$ : le nombre $d$ de décimales exactes double à chaque itération, à la constante ${\log }_{10}|C|$ près, négligeable dès que $d$ est grand. C'est la convergence quadratique.

5) Deux exemples. Héron : $f(x)=x^2-2$, $\ell =\sqrt{2}$, $f^{\prime }(\ell )=2\sqrt{2}$, $f^{\prime \prime }(\ell )=2$, donc $C=\frac{1}{2\sqrt{2}}\approx 0,3536$. Ici $N(x)=\frac{1}{2}\left(x+\frac{2}{x}\right)$, et le calcul exact de l'exercice résolu sur la méthode de Héron donne $N(x)-\sqrt{2}=\frac{(x-\sqrt{2}{)}^2}{2x}$, soit $e_{n+1}=\frac{e_n^2}{2x_n}$ : le rapport $\frac{e_{n+1}}{e_n^2}=\frac{1}{2x_n}$ tend vers $\frac{1}{2\sqrt{2}}=C$. Le théorème et le calcul exact disent la même chose ; à partir de $x_0=1$, ce rapport vaut $0,5$ ; $0,333$ ; $0,3529$ ; $0,35355$.

La racine cubique de $2$ : $f(x)=x^3-2$, $\ell =2^{1/3}$, $f^{\prime }(\ell )=3{\ell }^2$, $f^{\prime \prime }(\ell )=6\ell$, donc $C=\frac{6\ell }{6{\ell }^2}=\frac{1}{\ell }=2^{-1/3}\approx 0,7937$ : c'est la limite des rapports observés. Pourquoi le premier en est-il loin ? Ici $N(x)=\frac{2x^3+2}{3x^2}$, et, en utilisant ${\ell }^3=2$, un calcul exact donne $N(\ell +h)-\ell =\frac{h^2(3\ell +2h)}{3(\ell +h{)}^2}$, donc $$\frac{e_{n+1}}{e_n^2}=\frac{3\ell +2e_n}{3x_n^2},$$ qui ne vaut $\frac{1}{\ell }$ qu'à la limite. Au départ, $x_0=1$ et $e_0\approx -0,26$ : l'erreur n'est pas petite, le reste $o(e_n^2)$ pèse, et le rapport vaut $\frac{3\ell +2e_0}{3}\approx 1,087$. L'équivalent est asymptotique : il décrit la vitesse près de la racine, pas le premier pas. Les nombres de décimales exactes successifs valent environ $0,6$ ; $1,1$ ; $2,4$ ; $4,9$ ; $9,9$ ; $19,9$ : ils doublent.

6) La racine double. Avec $f(x)=(x-\ell {)}^{2}g(x)$, on a $f^{\prime }(x)=2(x-\ell )g(x)+(x-\ell {)}^2{g}^{\prime }(x)$, et pour $h\ne 0$ assez petit : $$N(\ell +h)-\ell =h-\frac{h^{2}g(\ell +h)}{2hg(\ell +h)+h^2{g}^{\prime }(\ell +h)}=h\left(1-\frac{g(\ell +h)}{2g(\ell +h)+h{g}^{\prime }(\ell +h)}\right).$$ Par continuité de $g$ et de $g^{\prime }$ en $\ell$, la fraction tend vers $\frac{g(\ell )}{2g(\ell )}=\frac{1}{2}$ — c'est ici que sert $g(\ell )\ne 0$, qui assure aussi que le dénominateur ne s'annule pas près de $\ell$. Donc $$N(\ell +h)-\ell \sim \frac{h}{2}.$$ Le terme d'ordre $1$ ne disparaît plus : $N^{\prime }(\ell )=\frac{1}{2}$, et l'on retombe sur un point fixe attractif ordinaire. Comme le rapport $\frac{N(\ell +h)-\ell }{h}$ tend vers $\frac{1}{2}$, il est compris entre $\frac{1}{4}$ et $\frac{3}{4}$ pour $h$ assez petit : pour $x_0$ assez proche de $\ell$, $|e_{n+1}|\le \frac{3}{4}|e_n|$ à chaque pas (par récurrence, la suite reste dans ce voisinage), donc $e_n\to 0$ ; si de plus $e_n\ne 0$ pour tout $n$, $\frac{e_{n+1}}{e_n}\to \frac{1}{2}$ : convergence géométrique de raison $\frac{1}{2}$, une décimale toutes les trois ou quatre itérations au lieu d'un doublement. L'exemple : $\ell =1$, $g(x)=x+2$, $g(1)=3\ne 0$ ; le calcul exact donne $N(1+h)-1=\frac{h(2h+3)}{3(h+2)}$, et à partir de $x_0=2$ les rapports $\frac{e_{n+1}}{e_n}$ valent $0,556$ ; $0,536$ ; $0,522$ ; $0,512$ ; $0,506$. (Le mot « racine double » sera défini pour les polynômes dans le chapitre qui leur est consacré ; ici, l'hypothèse est la factorisation elle-même.)

Le théorème obtenu — la convergence quadratique de la méthode de Newton. Soit $f$ de classe ${\mathcal{C}}^2$ sur un intervalle ouvert $I$, et $\ell \in I$ une racine simple de $f$ ($f(\ell )=0$, $f^{\prime }(\ell )\ne 0$). Il existe $\eta >0$ et $K>0$ tels que, pour tout $x_0$ vérifiant $|x_0-\ell |\le \min \left(\eta ,\frac{1}{2K}\right)$, la suite de Newton $x_{n+1}=x_n-\frac{f(x_n)}{f^{\prime }(x_n)}$ soit bien définie, converge vers $\ell$ et vérifie $|x_{n+1}-\ell |\le K|x_n-\ell {|}^2$ ; si de plus $f^{\prime \prime }(\ell )\ne 0$ (et $x_n\ne \ell$), alors $x_{n+1}-\ell \sim \frac{f^{\prime \prime }(\ell )}{2f^{\prime }(\ell )}(x_n-\ell {)}^2$ : le nombre de décimales exactes double à chaque itération. En une racine double, la convergence n'est plus que géométrique, de raison $\frac{1}{2}$.

Ce que le problème installe. La vitesse d'une suite récurrente $u_{n+1}=\phi (u_n)$ se lit sur le développement de $\phi$ au point fixe : un terme d'ordre $1$ non nul, avec $0<|{\phi }^{\prime }(\ell )|<1$, donne une convergence géométrique (le problème du TD 6, et la racine double de la question 6) ; un terme d'ordre $1$ nul, ${\phi }^{\prime }(\ell )=0$, donne une convergence quadratique (Newton en une racine simple). Ce qui était observé au premier semestre est désormais démontré. C'est l'algorithme des logiciels qui résolvent $f(x)=0$ — en sciences industrielles, ceux qui inversent une loi entrée-sortie comme celle de l'embiellage de l'exercice 4, où l'on cherche l'angle qui donne une position — avec ses deux précautions : partir près de la racine, se méfier des racines multiples.