Méthode de Newton : convergence locale et contre-exemples

Pour une fonction réelle $f$, la méthode de Newton cherche à approcher un zéro de $f$ en remplaçant localement sa courbe par une tangente. Le but est de comprendre jusqu'où cette idée géométrique peut être transformée en théorèmes : dans quels cas l'itération converge-t-elle, à quelle vitesse, et que peut-il se passer lorsque le point initial est mal choisi ou lorsqu'une hypothèse essentielle disparaît ?

I — Une itération issue d'une tangente

On considère

$$f(x)=x^2-2$$

et on cherche son zéro positif. On part de $x_0=2$.

1. Soit $u>0$.

   (a) Écrire l'équation de la tangente à la courbe de $f$ au point d'abscisse $u$.

   (b) Déterminer l'abscisse $T(u)$ du point où cette tangente coupe l'axe des abscisses.

   (c) On définit $x_{n+1}=T(x_n)$. Représenter sur un croquis les trois premières étapes de la construction et expliquer le lien entre la géométrie du tracé et la relation de récurrence obtenue.

2. Calculer $x_1$ et $x_2$ exactement, puis donner une valeur décimale de $x_3$. En utilisant

$$\sqrt2\simeq 1{,}41421356237,$$

observer les erreurs $|x_n-\sqrt2|$ pour $n=0,1,2,3$ et formuler une conjecture sur la convergence et sur sa rapidité. Il s'agit à ce stade d'une observation, non d'une preuve.

3. Pour $x>0$, établir les deux identités

$$T(x)-\sqrt2=\frac{(x-\sqrt2)^2}{2x}, \qquad T(x)-x=\frac{2-x^2}{2x}.$$

En déduire que, si $x>\sqrt2$, alors

$$\sqrt2\leq T(x)<x.$$

Montrer que la suite $(x_n)$ converge et déterminer sa limite.

4. En posant $e_n=x_n-\sqrt2$, obtenir une majoration de la forme

$$0\leq e_{n+1}\leq C e_n^2$$

avec une constante $C$ indépendante de $n$. Expliquer en quoi ce résultat transforme l'observation numérique de la question 2 en une propriété démontrée.

II — De la construction géométrique à un premier théorème global

5. Soit $f$ une fonction dérivable sur un intervalle et soit $u$ tel que $f'(u)\neq0$. À partir de l'équation de la tangente à la courbe de $f$ au point $(u,f(u))$, retrouver la transformation

$$N_f(u)=u-\frac{f(u)}{f'(u)}.$$

Préciser son domaine de définition et expliquer pourquoi ses points fixes sont exactement les zéros de $f$ appartenant à ce domaine.

La suite

$$x_{n+1}=N_f(x_n)$$

est appelée suite de Newton associée à $f$.

On rappelle que $f\in\mathcal C^1(J)$ signifie que $f$ est dérivable sur $J$ et que $f'$ y est continue ; $f\in\mathcal C^2(J)$ signifie que $f$ est deux fois dérivable et que $f''$ y est continue.

6. Soient $\alpha<b$ et $f\in\mathcal C^1([\alpha,b])$ tels que

$$f(\alpha)=0,\qquad f'(x)>0\quad\text{pour tout }x\in[\alpha,b],$$

et supposons $f$ convexe sur $[\alpha,b]$.

On pourra utiliser le fait que la courbe d'une fonction convexe dérivable est située au-dessus de chacune de ses tangentes.

(a) Montrer que, pour tout $x\in(\alpha,b]$,

$$\alpha\leq N_f(x)<x.$$

(b) En déduire que, pour tout $x_0\in(\alpha,b]$, la suite de Newton est bien définie et converge vers $\alpha$.

(c) Ce résultat est-il local ou global sur l'intervalle considéré ? Identifier précisément le rôle joué par la convexité et par le signe de $f'$.

III — Ce que l'on peut garantir près d'une racine simple

Pour la suite, on utilisera au besoin le théorème des accroissements finis : si $g$ est continue sur $[a,b]$ et dérivable sur $]a,b[$, alors il existe $c\in]a,b[$ tel que

$$g(b)-g(a)=g'(c)(b-a).$$

Soit $I$ un intervalle ouvert, $f\in\mathcal C^2(I)$, et $\alpha\in I$ tel que

$$f(\alpha)=0,\qquad f'(\alpha)\neq0.$$

Un tel zéro est dit simple. On appellera ici voisinage de $\alpha$ un intervalle contenant $\alpha$ en son intérieur.

7. Montrer qu'il existe un voisinage $J$ de $\alpha$ sur lequel $f'$ ne s'annule pas. Sur ce voisinage, calculer la dérivée de $N_f$ et montrer que

$$N_f(\alpha)=\alpha,\qquad N_f'(\alpha)=0.$$

8. À partir du résultat précédent, démontrer qu'il existe $r>0$ tel que, pour tout

$$x_0\in[\alpha-r,\alpha+r],$$

la suite de Newton est bien définie, reste dans cet intervalle et converge vers $\alpha$.

Obtenir en outre une estimation géométrique de l'erreur : il existe une constante $q\in(0,1)$, indépendante de $n$, telle que

$$|x_n-\alpha|\leq q^n|x_0-\alpha|$$

pour tout $n$.

9. Comparer le théorème obtenu à la question 8 avec celui de la question 6. Quelles hypothèses ont été gagnées ou perdues ? Pourquoi la question 8 ne permet-elle pas encore d'affirmer une convergence pour tout point initial où la formule de Newton a un sens ?

IV — Estimation de l'erreur et ordre de convergence

On pourra utiliser la formule de Taylor-Lagrange à l'ordre $2$ : si $g\in\mathcal C^2$ sur un intervalle contenant $a$ et $b$, alors il existe $\xi$ entre $a$ et $b$ tel que

$$g(b)=g(a)+g'(a)(b-a)+\frac12 g''(\xi)(b-a)^2.$$

On reprend les hypothèses de la partie III et un point initial assez proche de $\alpha$ pour que la convergence de la question 8 soit acquise. On pose

$$e_n=x_n-\alpha.$$

10. Montrer que, pour chaque $n$, il existe un réel $\xi_n$ situé entre $x_n$ et $\alpha$ tel que

$$e_{n+1} = \frac{f''(\xi_n)}{2f'(x_n)}\,e_n^2.$$

En déduire qu'il existe une constante $C>0$, indépendante de $n$, telle que

$$|e_{n+1}|\leq C|e_n|^2.$$

On dira qu'une suite convergeant vers $\alpha$ converge au moins quadratiquement s'il existe $C>0$ et un rang $n_0$ tels que

$$|e_{n+1}|\leq C|e_n|^2\qquad(n\geq n_0).$$

11. Si la suite n'atteint pas $\alpha$ en un nombre fini d'étapes, montrer que

$$\frac{|e_{n+1}|}{|e_n|}\longrightarrow0.$$

Interpréter ce résultat en termes d'accélération de la convergence. Pourquoi est-il plus fort que l'estimation géométrique obtenue à la question 8 ?

On dira que la convergence est d'ordre exactement $2$ si, lorsque les erreurs ne deviennent pas nulles à partir d'un certain rang,

$$\frac{|e_{n+1}|}{|e_n|^2}$$

admet une limite finie strictement positive.

12. On suppose de plus que $f''(\alpha)\neq0$ et que la suite n'atteint pas exactement $\alpha$ en un nombre fini d'étapes. Montrer que

$$\lim_{n\to\infty} \frac{|e_{n+1}|}{|e_n|^2} = \frac{|f''(\alpha)|}{2|f'(\alpha)|}.$$

Conclure que la convergence est alors d'ordre exactement $2$.

Que peut-on affirmer si $f''(\alpha)=0$ ? Justifier pourquoi il serait incorrect de conclure, sans hypothèse supplémentaire, que l'ordre est exactement $2$.

V — Les limites du théorème

13. On considère

$$p(x)=x^3-2x+2.$$

(a) Montrer que $p$ possède un unique zéro réel $\alpha$, que ce zéro appartient à $]-2,-1[$, et qu'il est simple.

(b) Étudier la suite de Newton issue de $x_0=0$.

(c) En déduire qu'une fonction polynomiale de classe $\mathcal C^\infty$, possédant un unique zéro réel simple, peut néanmoins avoir une suite de Newton non convergente alors que le point initial et tous les itérés obtenus appartiennent au domaine de définition de $N_p$.

Formuler explicitement l'affirmation globale trop forte que cet exemple réfute.

On dira qu'une convergence vers $\alpha$ est linéaire si, lorsque les erreurs restent non nulles, il existe $\lambda\in(0,1)$ tel que

$$\frac{|e_{n+1}|}{|e_n|}\longrightarrow\lambda.$$

14. Soit $m\geq2$ et

$$f(x)=(x-\alpha)^m.$$

Pour $x_0\neq\alpha$, calculer explicitement la suite de Newton. Montrer qu'elle converge vers $\alpha$ avec un rapport d'erreurs constant strictement compris entre $0$ et $1$, puis vérifier qu'elle n'est pas au moins quadratique. Quelle hypothèse du théorème local est ici mise en défaut, et quelle conclusion disparaît avec elle ?

15. À partir des résultats précédents, formuler un théorème de convergence locale de Newton aussi précis que possible. Puis, pour chacune des hypothèses ou conditions suivantes, indiquer le rôle qu'elle joue dans les preuves et les conclusions obtenues :

• $f'(\alpha)\neq0$ ;
• $f\in\mathcal C^2$ au voisinage de $\alpha$ ;
• proximité du point initial avec $\alpha$ ;
• convexité sur un intervalle ;
• signe constant non nul de $f'$ sur cet intervalle ;
• condition $f''(\alpha)\neq0$.

On distinguera soigneusement ce qui concerne l'existence de l'itération, la convergence locale, une convergence globale sur un intervalle et l'ordre exact de convergence.