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

I — Une itération issue d'une tangente

1. Construction géométrique

Pour $f(x)=x^2-2$, on a $f'(x)=2x$. La tangente en $u>0$ a pour équation

$$y=f(u)+f'(u)(x-u) =u^2-2+2u(x-u).$$

Ainsi

$$y=2ux-u^2-2.$$

Elle coupe l'axe des abscisses lorsque

$$2ux-u^2-2=0,$$

donc à l'abscisse

$$T(u)=\frac{u^2+2}{2u} =\frac12\left(u+\frac2u\right).$$

La relation de récurrence est donc

$$\boxed{x_{n+1}=\frac12\left(x_n+\frac2{x_n}\right).}$$

Sur le croquis, $x_{n+1}$ est l'abscisse où la tangente en $(x_n,f(x_n))$ coupe l'axe horizontal. Une nouvelle tangente est ensuite tracée au point de la courbe d'abscisse $x_{n+1}$. La suite traduit exactement cette construction géométrique.

Point de méthode. La formule n'est pas un procédé algébrique tombé du ciel : elle est la traduction de la linéarisation de $f$ au voisinage du point courant.

2. Observation numérique

On obtient

$$x_1=\frac12\left(2+\frac22\right)=\frac32,$$

puis

$$x_2 =\frac12\left(\frac32+\frac{2}{3/2}\right) =\frac12\left(\frac32+\frac43\right) =\frac{17}{12}.$$

Enfin

$$x_3 =\frac12\left(\frac{17}{12}+\frac{24}{17}\right) =\frac{577}{408} \simeq1{,}41421568627.$$

Avec $\sqrt2\simeq1{,}41421356237$, les erreurs sont approximativement

$$\begin{array}{c|c} n & |x_n-\sqrt2|\\ \hline 0 & 5{,}86\times10^{-1}\\ 1 & 8{,}58\times10^{-2}\\ 2 & 2{,}45\times10^{-3}\\ 3 & 2{,}12\times10^{-6} \end{array}$$

Ces valeurs suggèrent à la fois la convergence vers $\sqrt2$ et une accélération spectaculaire de l'erreur. Une conjecture raisonnable est que l'erreur suivante se comporte comme une constante multipliée par le carré de l'erreur précédente.

À ce stade, rien n'est démontré : quatre valeurs numériques ne prouvent ni la convergence de toute la suite, ni une loi asymptotique.

3. Convergence dans l'exemple

Pour $x>0$,

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

De même,

$$T(x)-x = \frac{x^2+2-2x^2}{2x} = \frac{2-x^2}{2x}.$$

Si $x>\sqrt2$, alors

$$T(x)-\sqrt2\geq0$$

et

$$T(x)-x<0.$$

Ainsi

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

Comme $x_0=2>\sqrt2$, une récurrence montre que

$$\sqrt2\leq x_{n+1}<x_n$$

tant que $x_n>\sqrt2$. Si un terme vaut $\sqrt2$, la suite devient constante ; sinon elle est strictement décroissante et minorée par $\sqrt2$. Elle converge donc vers une limite $\ell\geq\sqrt2$.

La relation de récurrence et la positivité de $\ell$ donnent, par passage à la limite,

$$\ell=\frac12\left(\ell+\frac2\ell\right),$$

d'où

$$\ell^2=2.$$

Comme $\ell>0$,

$$\boxed{\ell=\sqrt2.}$$

4. Première estimation quadratique

Avec

$$e_n=x_n-\sqrt2\geq0,$$

l'identité précédente donne

$$e_{n+1}=\frac{e_n^2}{2x_n}.$$

Or $x_n\geq\sqrt2$, donc

$$0\leq e_{n+1} \leq \frac{1}{2\sqrt2}\,e_n^2.$$

On peut prendre

$$\boxed{C=\frac1{2\sqrt2}.}$$

Cette relation est d'une nature entièrement différente d'une simple observation décimale : elle vaut pour tout $n$, et elle montre que, dès que l'erreur est petite, son carré est beaucoup plus petit encore. La rapidité observée à la question 2 est donc expliquée par une identité exacte.

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

5. Définition générale

La tangente à la courbe de $f$ au point d'abscisse $u$, avec $f'(u)\neq0$, a pour équation

$$y=f(u)+f'(u)(x-u).$$

Son intersection avec l'axe des abscisses vérifie

$$0=f(u)+f'(u)(x-u),$$

donc

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

Le domaine de définition de la transformation de Newton est

$$D=\{u : f'(u)\neq0\}.$$

Pour $u\in D$, on pose

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

Pour $u\in D$,

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

Les points fixes de $N_f$ sont donc exactement les zéros de $f$ situés dans ce domaine.

6. Un critère global sur un intervalle convexe

Soit $x\in(\alpha,b]$. Comme $f' >0$ sur $[\alpha,b]$, la fonction $f$ est strictement croissante. Puisque $f(\alpha)=0$,

$$f(x)>0.$$

Il en résulte immédiatement

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

La convexité fournit l'autre inégalité. La courbe est au-dessus de sa tangente en $x$, donc

$$f(\alpha)\geq f(x)+f'(x)(\alpha-x).$$

Comme $f(\alpha)=0$,

$$f(x)\leq f'(x)(x-\alpha).$$

Puisque $f'(x)>0$,

$$\frac{f(x)}{f'(x)}\leq x-\alpha,$$

et donc

$$N_f(x) =x-\frac{f(x)}{f'(x)} \geq\alpha.$$

Ainsi

$$\boxed{\alpha\leq N_f(x)<x.}$$

Partant de $x_0\in(\alpha,b]$, tous les termes restent dans $[\alpha,b]$. La suite est décroissante tant qu'elle n'a pas atteint $\alpha$, et minorée par $\alpha$. Elle converge donc vers un réel $\ell\in[\alpha,b]$.

La fonction $N_f$ est continue sur $[\alpha,b]$, car $f'$ ne s'y annule pas. En passant à la limite dans

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

on obtient

$$\ell=N_f(\ell),$$

donc $f(\ell)=0$. Comme $f$ est strictement croissante et $f(\alpha)=0$, ce zéro est unique :

$$\boxed{\ell=\alpha.}$$

Le résultat est global sur l'intervalle $[\alpha,b]$, du côté droit de la racine : aucun voisinage petit de $\alpha$ n'est imposé au point initial.

Le rôle des hypothèses est visible dans les deux inégalités :

• $f'>0$ garantit que $f(x)>0$, que le quotient de Newton est défini et que $N_f(x)<x$ ;
• la convexité donne, par la position de la courbe par rapport à sa tangente, l'inégalité $N_f(x)\geq\alpha$.

La géométrie empêche donc ici les itérés de « dépasser » la racine vers la gauche.

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

7. La fonction d'itération près de la racine

Comme $f'(\alpha)\neq0$ et $f'$ est continue, il existe un voisinage $J$ de $\alpha$ sur lequel $f'$ garde un signe constant et ne s'annule pas.

Sur $J$,

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

est de classe $\mathcal C^1$. En dérivant,

$$N_f'(x) = 1-\frac{(f'(x))^2-f(x)f''(x)}{(f'(x))^2},$$

d'où

$$\boxed{ N_f'(x)=\frac{f(x)f''(x)}{(f'(x))^2}. }$$

Comme $f(\alpha)=0$,

$$N_f(\alpha)=\alpha$$

et

$$\boxed{N_f'(\alpha)=0.}$$

Ce dernier fait est le mécanisme local essentiel : au voisinage de la racine, la fonction d'itération est beaucoup plus plate qu'une application contractante quelconque.

8. Théorème de convergence locale

La fonction $N_f'$ est continue au voisinage de $\alpha$ et

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

Fixons par exemple

$$q=\frac12.$$

Il existe $r>0$, choisi assez petit pour que

$$[\alpha-r,\alpha+r]\subset J$$

et

$$|N_f'(x)|\leq q \qquad \text{pour tout }x\in[\alpha-r,\alpha+r].$$

Pour tout $x$ de cet intervalle, le théorème des accroissements finis appliqué à $N_f$ entre $x$ et $\alpha$ donne

$$|N_f(x)-N_f(\alpha)| \leq q|x-\alpha|.$$

Comme $N_f(\alpha)=\alpha$,

$$\boxed{ |N_f(x)-\alpha| \leq q|x-\alpha|. }$$

En particulier,

$$|N_f(x)-\alpha| \leq qr<r,$$

donc

$$N_f([\alpha-r,\alpha+r]) \subset[\alpha-r,\alpha+r].$$

L'intervalle est invariant.

Si $x_0$ y appartient, tous les $x_n$ y appartiennent donc et la suite est bien définie. En outre,

$$|x_{n+1}-\alpha| \leq q|x_n-\alpha|.$$

Par récurrence,

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

Comme $0<q<1$,

$$q^n\longrightarrow0,$$

et finalement

$$\boxed{x_n\longrightarrow\alpha.}$$

Stratégie de preuve. On ne cherche pas d'abord à étudier directement la suite. On étudie la fonction d'itération. Le fait $N_f'(\alpha)=0$ permet de rendre $N_f$ contractante sur un voisinage assez petit ; le théorème des accroissements finis transforme cette information différentielle en une estimation sur les itérés.

9. Local contre global

Le théorème de la question 6 demande des hypothèses fortes sur tout un intervalle : signe strict de $f'$ et convexité. En échange, tout point initial de cet intervalle, du côté considéré, converge.

Le théorème de la question 8 ne demande ni convexité globale ni monotonie de $f$ sur un grand intervalle. Une racine simple et une régularité locale suffisent. En revanche, il ne garantit la convergence que pour les points initiaux suffisamment proches de $\alpha$.

Rien dans la preuve ne contrôle ce que fait $N_f$ loin de $\alpha$ : le dénominateur peut s'annuler, l'itération peut sortir de la zone où $|N_f'|<1$, ou la dynamique peut posséder d'autres comportements. La partie V montrera que cette réserve n'est pas seulement technique.

IV — Estimation de l'erreur et ordre de convergence

10. Formule exacte de l'erreur à un facteur intermédiaire près

Appliquons Taylor-Lagrange à $f$, entre $x_n$ et $\alpha$. Il existe $\xi_n$ entre ces deux points tel que

$$f(\alpha) = f(x_n)+f'(x_n)(\alpha-x_n) +\frac12f''(\xi_n)(\alpha-x_n)^2.$$

Comme $f(\alpha)=0$ et $e_n=x_n-\alpha$,

$$0 = f(x_n)-f'(x_n)e_n +\frac12f''(\xi_n)e_n^2.$$

Ainsi

$$\frac{f(x_n)}{f'(x_n)} = e_n-\frac{f''(\xi_n)}{2f'(x_n)}e_n^2.$$

Or

$$e_{n+1} = x_{n+1}-\alpha = e_n-\frac{f(x_n)}{f'(x_n)}.$$

Par conséquent

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

Reprenons le segment $K=[\alpha-r,\alpha+r]$ construit à la question 8, en diminuant $r$ si nécessaire. Tous les $x_n$ ainsi que les points $\xi_n$ appartiennent à $K$. Les fonctions $|f'|$ et $|f''|$ y sont continues et $f'$ ne s'y annule pas ; il existe donc

$$m=\min_{x\in K}|f'(x)|>0$$

et

$$M=\max_{x\in K}|f''(x)|<+\infty.$$

Donc

$$|e_{n+1}| \leq \frac{M}{2m}|e_n|^2.$$

On peut prendre

$$\boxed{C=\frac{M}{2m}.}$$

11. Une contraction qui s'accélère

Supposons que la suite n'atteigne pas $\alpha$ en un nombre fini d'étapes. Les erreurs sont alors toutes non nulles. D'après la question 10,

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

Or $e_n\to0$, donc

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

À la question 8, on obtenait un facteur de contraction fixe $q<1$ : l'erreur décroissait au moins géométriquement. Ici, le facteur effectif entre deux erreurs successives tend lui-même vers $0$. Plus on approche de la racine, plus la contraction devient forte. C'est le premier signe précis de l'accélération propre à la méthode de Newton près d'une racine simple.

12. Ordre exactement $2$

La formule de la question 10 donne, lorsque $e_n\neq0$,

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

Comme

$$x_n\longrightarrow\alpha$$

et $\xi_n$ est situé entre $x_n$ et $\alpha$,

$$\xi_n\longrightarrow\alpha.$$

Par continuité de $f'$ et $f''$,

$$\frac{|f''(\xi_n)|}{2|f'(x_n)|} \longrightarrow \frac{|f''(\alpha)|}{2|f'(\alpha)|}.$$

Sous l'hypothèse $f''(\alpha)\neq0$, cette limite est finie et strictement positive. Donc

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

et la convergence est d'ordre exactement $2$.

Si $f''(\alpha)=0$ et si les erreurs restent non nulles, la même formule conduit seulement à

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

Cela exclut l'ordre exactement $2$ au sens défini ici, mais ne suffit pas à déterminer un ordre exact supérieur : une régularité et une information supplémentaires sur les dérivées suivantes seraient nécessaires. Il peut aussi arriver que la racine soit atteinte en un nombre fini d'étapes.

Par exemple, pour

$$f(x)=x+x^3, \qquad \alpha=0,$$

on a $f'(0)=1$ mais $f''(0)=0$, et

$$N_f(x) = x-\frac{x+x^3}{1+3x^2} = \frac{2x^3}{1+3x^2}.$$

Ainsi, pour $x$ petit,

$$N_f(x)\sim2x^3,$$

ce qui fait apparaître un comportement cubique plutôt que quadratique.

V — Les limites du théorème

13. Un cycle de Newton

On considère

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

Sa dérivée est

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

Les deux points critiques sont

$$\pm a, \qquad a=\sqrt{\frac23}.$$

Or

$$p(a) = a^3-2a+2 = 2-\frac43a > 2-\frac43 = \frac23>0,$$

et

$$p(-a)=2+\frac43a>0.$$

La fonction tend vers $-\infty$ lorsque $x\to-\infty$, puis croît jusqu'au maximum local en $-a$, qui est positif. Elle possède donc exactement un zéro sur $]-\infty,-a[$. Entre les deux points critiques elle reste positive, puisque son minimum local $p(a)$ est positif, et elle est ensuite croissante et positive.

De plus,

$$p(-2)=-2<0, \qquad p(-1)=3>0,$$

donc

$$\boxed{\alpha\in]-2,-1[.}$$

Comme $\alpha<-a$, on a

$$p'(\alpha)>0,$$

donc le zéro est simple.

La fonction de Newton est

$$N_p(x) = x-\frac{x^3-2x+2}{3x^2-2}.$$

En $0$,

$$N_p(0) = 0-\frac2{-2} = 1.$$

En $1$,

$$N_p(1) = 1-\frac1{1} = 0.$$

Par conséquent, si $x_0=0$,

$$0,\ 1,\ 0,\ 1,\ \ldots$$

et la suite ne converge pas.

On a donc un polynôme de classe $\mathcal C^\infty$, avec un unique zéro réel simple, pour lequel Newton échoue depuis un point initial où toutes les itérations considérées sont parfaitement définies.

L'affirmation

« Si $f$ est suffisamment régulière et possède un zéro réel simple, alors la suite de Newton converge vers ce zéro depuis tout point initial où l'itération est définie »

est donc fausse.

Ce contre-exemple sépare nettement convergence locale et convergence globale.

14. Une racine multiple : convergence seulement linéaire

Soit

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

Pour $x\neq\alpha$,

$$f'(x)=m(x-\alpha)^{m-1}.$$

Donc

$$N_f(x) = x-\frac{(x-\alpha)^m}{m(x-\alpha)^{m-1}} = x-\frac{x-\alpha}{m}.$$

Ainsi

$$N_f(x)-\alpha = \left(1-\frac1m\right)(x-\alpha).$$

Si $e_n=x_n-\alpha$,

$$e_{n+1} = \left(1-\frac1m\right)e_n,$$

d'où

$$\boxed{ e_n= \left(1-\frac1m\right)^n e_0. }$$

Le rapport des erreurs est constant :

$$\frac{|e_{n+1}|}{|e_n|} = 1-\frac1m\in(0,1).$$

Le rapport tend donc vers le nombre $1-1/m\in(0,1)$ : au sens de la définition donnée dans le sujet, la convergence est linéaire (ou d'ordre $1$). En outre,

$$\frac{|e_{n+1}|}{|e_n|^2} = \frac{1-1/m}{|e_n|}\longrightarrow+\infty,$$

puisque $|e_n|\to0$. Elle n'est donc pas au moins quadratique.

Ici

$$f'(\alpha)=0.$$

La racine n'est pas simple. C'est précisément l'hypothèse qui disparaît, et avec elle le mécanisme

$$N_f'(\alpha)=0$$

utilisé pour obtenir l'accélération quadratique.

La méthode peut donc encore converger vers une racine multiple, mais la convergence quadratique disparaît ici : elle est remplacée par une convergence linéaire.

15. Synthèse des hypothèses

Un énoncé correct est le suivant.

Théorème de convergence locale de Newton.
Soit $I$ un intervalle ouvert, $f\in\mathcal C^2(I)$ et $\alpha\in I$ une racine simple de $f$, c'est-à-dire

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

Alors il existe $r>0$ tel que, pour tout

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

la suite de Newton

$$x_{n+1} = x_n-\frac{f(x_n)}{f'(x_n)}$$

est bien définie, reste dans ce voisinage et converge vers $\alpha$. De plus, il existe $C>0$ tel que

$$|x_{n+1}-\alpha| \leq C|x_n-\alpha|^2.$$

La convergence est donc au moins quadratique. Si, en outre,

$$f''(\alpha)\neq0$$

et si la racine n'est pas atteinte en un nombre fini d'étapes, alors

$$\frac{|x_{n+1}-\alpha|}{|x_n-\alpha|^2} \longrightarrow \frac{|f''(\alpha)|}{2|f'(\alpha)|},$$

et la convergence est d'ordre exactement $2$.

Le rôle des hypothèses se résume ainsi.

\renewcommand{\arraystretch}{1.22} \begin{array}{|>{\raggedright\arraybackslash}p{0.25\linewidth}|>{\raggedright\arraybackslash}p{0.65\linewidth}|} \hline \textbf{Hypothèse ou condition} & \textbf{Rôle} \\ \hline $f'(\alpha)\neq0$ & Rend la racine simple ; garantit que $f'$ reste non nul dans un voisinage ; permet de définir $N_f$ près de $\alpha$ et donne $N_f'(\alpha)=0$. \\ \hline $f\in\mathcal C^2$ près de $\alpha$ & Assure la continuité de $N_f'$ dans la preuve locale et permet Taylor-Lagrange ainsi que l'estimation quadratique. Cette régularité est suffisante pour la preuve donnée ; elle n'est pas revendiquée comme minimale. \\ \hline $x_0$ suffisamment proche de $\alpha$ & Maintient les itérés dans la zone où $N_f$ est contractante et où le dénominateur ne s'annule pas. Le cycle $0\leftrightarrow1$ montre qu'on ne peut pas supprimer cette restriction en général. \\ \hline Convexité sur un intervalle & Dans le critère global de la partie II, empêche les tangentes de produire un itéré situé de l'autre côté de la racine : elle fournit $N_f(x)\geq\alpha$. Elle n'est pas nécessaire au théorème local. \\ \hline $f'$ de signe constant non nul sur l'intervalle & Garantit que l'itération y est définie, que $f$ est strictement monotone et que l'itéré progresse vers la racine dans le critère global. \\ \hline $f''(\alpha)\neq0$ & N'est pas nécessaire à la convergence locale ni à la majoration quadratique ; elle sert à obtenir une limite quadratique strictement positive et donc l'ordre \textbf{exactement} $2$. \\ \hline \end{array}

Pour la préparation à l'agrégation

Quatre éléments sont particulièrement réutilisables.

1. Le théorème à savoir formuler proprement. Au voisinage d'une racine simple d'une fonction $\mathcal C^2$, Newton est bien défini pour tout point initial suffisamment proche et converge au moins quadratiquement.

2. Le canevas de preuve.

   $$$$

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

puis continuité de $N_f'$, contraction locale par le théorème des accroissements finis, et enfin Taylor-Lagrange pour passer de la convergence à l'estimation quadratique. 3. **La distinction local/global.** La convexité et la monotonie peuvent fournir un théorème global sur un intervalle, mais la régularité et la simplicité de la racine ne suffisent pas à garantir une convergence depuis tout point initial. 4. **Deux contre-exemples à retenir.**

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

donne le cycle de Newton $0\leftrightarrow1$, malgré un unique zéro réel simple ; et

f(x)=(x-\alpha)^m,\qquad m\geq2,

$$montre qu'une racine multiple peut faire tomber la convergence de quadratique à linéaire.$$