Deux vitesses de convergence : le cosinus itéré et la méthode de Newton

La stratégie. Deux suites $u_{n+1}=g(u_n)$ qui convergent, l'une lentement, l'autre foudroyamment. Dans les deux cas, l'outil est le même : l'égalité des accroissements finis entre $u_n$ et le point fixe, $g(u_n)-g(\ell )=g^{\prime }(c_n)(u_n-\ell )$. Tout se joue sur la taille de $g^{\prime }$ près de $\ell$.

a) Le cosinus itéré. Intervalle stable. Sur $[0,1]\subset \left[0,\frac{\pi }{2}\right]$, le cosinus est décroissant, donc $\cos ([0,1])=[\cos 1,1]$, et comme $\cos 1\approx 0,540>0$, cet intervalle est inclus dans $[0,1]$. Avec $u_0=0\in [0,1]$, la suite reste dans $[0,1]$.

Le point fixe. La fonction $h(x)=\cos x-x$ est continue sur $\mathbb{R}$, dérivable, de dérivée $h^{\prime }(x)=-\sin x-1\le 0$, nulle seulement aux points isolés où $\sin x=-1$ : $h$ est strictement décroissante sur $\mathbb{R}$ (caractérisation des fonctions strictement monotones), donc injective, et l'équation $h(x)=0$ a au plus une solution. Comme $h(0)=1>0$ et $h(1)=\cos 1-1<0$, le théorème des valeurs intermédiaires en fournit une dans $]0,1[$. Il existe un unique réel $\ell$ tel que $\cos \ell =\ell$, et $\ell \in ]0,1[$ ($\ell \approx 0,739085$).

La contraction. Soit $n\in \mathbb{N}$. Les réels $u_n$ et $\ell$ sont dans $[0,1]$ ; l'égalité des accroissements finis appliquée au cosinus entre $u_n$ et $\ell$ (si $u_n\ne \ell$) fournit $c_n$ strictement compris entre eux, donc dans $[0,1]$, tel que $$u_{n+1}-\ell =\cos u_n-\cos \ell =-\sin (c_n)(u_n-\ell ).$$ Sur $[0,1]\subset \left[0,\frac{\pi }{2}\right]$, le sinus est croissant et positif : $0\le \sin c_n\le \sin 1$. Donc $|u_{n+1}-\ell |\le (\sin 1)|u_n-\ell |$ (trivialement vrai si $u_n=\ell$). Par récurrence, $|u_n-\ell |\le (\sin 1{)}^n|u_0-\ell |=(\sin 1{)}^n\ell \le (\sin 1{)}^n$, puisque $\ell <1$. Comme $\sin 1\approx 0,841<1$, la suite converge vers $\ell$, géométriquement, de raison $\sin 1$.

Le nombre d'itérations. On veut $(\sin 1{)}^n\le 10^{-6}$, soit $n\ln (\sin 1)\le -6\ln 10$, soit, en divisant par $\ln (\sin 1)\approx -0,1726<0$ (ce qui renverse l'inégalité), $$n\ge \frac{6\ln 10}{-\ln (\sin 1)}\approx \frac{13,82}{0,1726}\approx 80,04.$$ Quatre-vingt-une itérations garantissent six décimales ; chaque décimale coûte environ $\frac{\ln 10}{0,1726}\approx 13$ itérations, toujours le même nombre : c'est la signature de la convergence géométrique. (Numériquement, $u_{20}\approx 0,73894$, $u_{40}\approx 0,7390851$ : la convergence réelle est un peu plus rapide, parce que la pente au point fixe vaut $\sin \ell \approx 0,674$ et non $\sin 1$.)

b) Newton et Héron. Pour $f(x)=x^2-a$, $f^{\prime }(x)=2x$, et $$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 exactement la méthode de Héron, qui n'est autre que la méthode de Newton appliquée à $x^2-a$ — géométriquement, on remplace la parabole par sa tangente en $x_n$ et l'on prend le point où la tangente coupe l'axe.

L'identité de l'erreur. Pour $x_n>0$, $$x_{n+1}-\sqrt{a}=\frac{x_n^2+a-2\sqrt{a}{x}_n}{2x_n}=\frac{(x_n-\sqrt{a}{)}^2}{2x_n}.$$ Si $x_0>0$, tous les $x_n$ sont strictement positifs (récurrence), et l'identité montre $x_n\ge \sqrt{a}$ pour $n\ge 1$. Alors $x_{n+1}-x_n=\frac{a-x_n^2}{2x_n}\le 0$ pour $n\ge 1$ : $(x_n{)}_{n\ge 1}$ est décroissante, minorée par $\sqrt{a}$, donc convergente, et sa limite est le point fixe $\sqrt{a}$ (même raisonnement qu'au chapitre 5). Enfin, pour $n\ge 1$, $2x_n\ge 2\sqrt{a}$ donne $$0\le x_{n+1}-\sqrt{a}\le \frac{(x_n-\sqrt{a}{)}^2}{2\sqrt{a}}.$$ L'erreur est élevée au carré à chaque étape : convergence quadratique.

Le compte pour $a=2$, $x_0=1$. Notons $e_n=x_n-\sqrt{2}$ et $c=\frac{1}{2\sqrt{2}}$ ; l'inégalité s'écrit $c{e}_{n+1}\le (c{e}_n{)}^2$, d'où par récurrence $c{e}_n\le (c{e}_1{)}^{2^{n-1}}$ pour $n\ge 1$. Or $x_1=1,5$, $e_1=1,5-\sqrt{2}\le 0,09$ (car $\sqrt{2}\ge 1,41$) et $c\le 0,36$ (car $2\sqrt{2}\ge 2,82>1/0,36$), donc $c{e}_1\le 0,0324<\frac{1}{30}$, et $$e_n\le 2\sqrt{2}\cdot 30^{-2^{n-1}}.$$ Pour $n=4$ : $2\sqrt{2}\cdot 30^{-8}\approx 4,3\cdot 10^{-12}$, insuffisant de justesse ; pour $n=5$ : $2\sqrt{2}\cdot 30^{-16}\approx 6,6\cdot 10^{-24}$. Cinq itérations garantissent douze décimales, là où le cosinus itéré en demandait quatre-vingt-une pour six. Numériquement, les erreurs $e_1,\dots ,e_4$ valent $8,6\cdot 10^{-2}$, $2,5\cdot 10^{-3}$, $2,1\cdot 10^{-6}$, $1,6\cdot 10^{-12}$ : le nombre de décimales double.

Newton pour la racine cubique. Pour $f(x)=x^3-2$, $f^{\prime }(x)=3x^2$, et $$x_{n+1}=x_n-\frac{x_n^3-2}{3x_n^2}=\frac{2x_n^3+2}{3x_n^2}=\frac{2}{3}{x}_n+\frac{2}{3x_n^2}:$$ on « moyenne » $x_n$ (compté deux fois) et $\frac{2}{x_n^2}$ (compté une fois). Avec $x_0=1$ : $x_1=\frac{4}{3}\approx 1,3333$, $x_2=\frac{2}{3}\cdot \frac{4}{3}+\frac{2}{3\cdot \frac{16}{9}}=\frac{8}{9}+\frac{3}{8}=\frac{91}{72}\approx 1,26389$, $x_3\approx 1,259933$, à comparer à $\sqrt[3]{2}\approx 1,259921$. Les erreurs valent $7,3\cdot 10^{-2}$, $4,0\cdot 10^{-3}$, $1,2\cdot 10^{-5}$ : même doublement.

c) L'explication. Dans les deux cas, la suite s'écrit $u_{n+1}=g(u_n)$ avec $g$ dérivable et $g(\ell )=\ell$, et l'égalité des accroissements finis donne $$u_{n+1}-\ell =g^{\prime }(c_n)(u_n-\ell ),c_n\text{ entre }{u}_n\text{ et }\ell .$$ Pour le cosinus, $g=\cos$ et $|g^{\prime }(\ell )|=\sin \ell \approx 0,674\ne 0$ : quand $u_n\to \ell$, $g^{\prime }(c_n)\to g^{\prime }(\ell )$ par continuité, et l'erreur est multipliée à chaque étape par un facteur qui tend vers $0,674$ — elle décroît géométriquement, ni plus ni moins vite. Pour Héron, $g(x)=\frac{1}{2}\left(x+\frac{a}{x}\right)$ et $g^{\prime }(x)=\frac{1}{2}\left(1-\frac{a}{x^2}\right)$, donc $g^{\prime }(\sqrt{a})=0$ : le facteur $g^{\prime }(c_n)$ tend vers $0$, l'erreur est multipliée par une quantité elle-même de plus en plus petite, et l'identité exacte du b) précise que ce facteur est de l'ordre de l'erreur elle-même — d'où le carré. La vitesse d'une suite $u_{n+1}=g(u_n)$ se lit sur $g^{\prime }(\ell )$ : géométrique de raison $|g^{\prime }(\ell )|$ si $0<|g^{\prime }(\ell )|<1$, quadratique si $g^{\prime }(\ell )=0$. C'est ce qui fait de Newton la méthode de référence : la fonction itérée $x-\frac{f(x)}{f^{\prime }(x)}$ a toujours une dérivée nulle en une racine simple de $f$.

Ce que l'exercice installe. La notion de vitesse de convergence que le programme demande d'illustrer : lente, géométrique, quadratique, avec le nombre d'itérations pour une précision donnée. Et le mécanisme qui la gouverne — la dérivée au point fixe — qu'on retrouvera pour les suites implicites en analyse asymptotique et dans tout travail pratique d'informatique.