Licence CC BY-SA

Construction et analyse de la méthode de Newton

Dernière mise à jour :
Auteur :
Catégorie :

Juste avant de rentrer dans le vif du sujet, je vais vous donner les données du problème et un résultat d’analyse.

Puis, nous allons établir la méthode de Newton, nous en étudierons ensuite les différents comportements en variant progressivement les hypothèses auxquelles on soumet la fonction, ff, étudiée.

Les hypothèses et le cadre utilisé

Théorème d’inversion locale

Nous allons utiliser un théorème très fort d’analyse : le théorème d’inversion locale. L’énoncé général a un sens dans Rn\mathbf{R}^n mais nous nous limiterons au cas n=1n=1 qui correspond au contexte utilisé jusqu’alors. Je vais donner ici la forme utilisée de ce théorème, mais pour les plus curieux de nombreuses ressources existent à ce sujet (nécessitant la plupart du temps des notions de calcul différentiel).

Donnons-nous une fonction f:VaRf:V_a\to \mathbf{R} d’un voisinage, VaV_a, de aRa\in\mathbf{R}. On va supposer que ff est dérivable sur VaV_a.


Théorème

Si f(a)f'(a) est non nul alors il existe UaVaU_a\subset V_a un voisinage de aa (plus petit ou égal à VaV_a) tel que ff est une bijection de UaU_a dans f(Ua)f(U_a) et tel que g=f1g = f^{-1} est dérivable sur f(Ua)f(U_a).


On appelle gg l’inverse local (« inverse » est masculin !) de ff au voisinage de aa.

Cela signifie notamment que fg=gf=Idf\circ g = g\circ f = {\rm Id} localement autour de aa et f(a)f(a).

Ce n’est pas un résultat généralisable à toutes les fonctions dérivables ! La fonction xx2x\mapsto x^2 est de dérivée nulle en 00 et n’est pas une bijection autour de 00 (on a toujours (x)2=x2(-x)^2=x^2). Et la réciproque est également fausse : la fonction xx3x\mapsto x^3 est une bijection mais est de dérivée nulle en 00.

Fonction étudiée

Dans la suite, nous supposerons que ff est une fonction numérique de classe C3C^3 définie au voisinage VαV_\alpha d’un zéro simple, αR\alpha\in\mathbf{R}.

On suppose que α\alpha est un zéro simple, c’est-à-dire f(α)0f'(\alpha) \neq 0 et f(α+h)=f(α)h+o(h).f(\alpha +h) = f'(\alpha) h + o(h).

Ainsi, par le théorème d’inversion locale, il existe une application g:V0Rg : V_0 \to \mathbf{R} définie dans un voisinage de 00 suffisamment petit tel que l’on a : fg=gf=Id.f\circ g = g\circ f = {\rm Id}.

Ce que l’on va faire

Étant donnée une première approximation de α\alpha, disons xx, on va étudier ff et gg au voisinage de xx et y=f(x)y = f(x). Comme α=g(0)\alpha = g(0), on va commencer par développer l’expression X=g(Y)X=g(Y) au voisinage de yy en puissances de (Yy)(Y-y) puis nous prendrons Y=0Y=0 afin d’avoir une expression qui donne une meilleure approximation de α\alpha.

Construction de la méthode

Commençons donc par un premier développement de l’expression X=g(Y)X=g(Y) au voisinage de yy et en puissances de (Yy)(Y-y) (nous gardons les notations précédemment données).

X=g(y)+g(y)(Yy)+R2(Y)X = g(y) + g'(y)(Y-y) + R_2(Y)

avec R2(Y)R_2(Y) le reste à l’ordre 22 du développement limité.

Puisque y=f(x)y = f(x), on a g(y)=g(f(x))=xg(y) = g(f(x))= x, d’où : X=x+g(y)(Yy)+R2(Y).X = x + g'(y)(Y-y) + R_2(Y).

En Y=0Y=0, c’est-à-dire X=αX=\alpha, on a donc :

α=x+g(y)(y)+R2(0)\alpha = x +g'(y)\cdot(-y) + R_{2}(0)

On va maintenant calculer g(y)g'(y) et on obtiendra la méthode de Newton. Pour rappel, on a la formule : fg=Idf\circ g = {\rm Id}

d’où : (fg)g=1(f'\circ g) \cdot g' = 1

et donc : g=1fgg' = \frac{1}{f'\circ g}

à condition que fgf'\circ g soit non nul au voisinage du point dont on évalue gg'.

Mais comme α\alpha est une racine simple, cette dernière condition est vérifiée et on obtient : g(y)=1f(g(y))=1f(x).g'(y) = \frac{1}{f'(g(y))} = \frac{1}{f'(x)}.

Finalement, on a : α=xf(x)f(x)+R2(0).\alpha = x - \frac{f(x)}{f'(x)} + R_2(0).

On appelle méthode de Newton l’application : xxf(x)f(x).x \mapsto x - \frac{f(x)}{f'(x)}.

Dans la suite, il va s’agir de montrer que cette application permet bien d’approcher efficacement α\alpha. Intuitivement, on peut comprendre pourquoi ça marche : R2(0)R_2(0) sera très petit devant les autres termes et on devrait donc s’approcher de α\alpha.

Analyse de la méthode

Nous allons montrer, qu’étant donné xx proche de α\alpha, la méthode de Newton permet effectivement d’obtenir une meilleure approximation de α\alpha en l’évaluant en xx.

Plus symboliquement, nous noterons NN la méthode de Newton et nous allons montrer qu’au voisinage de α\alpha on a : N(α+h)=α+N(α)2h2+o(h2)N(\alpha + h) = \alpha +\frac{N''(\alpha)}{2}h^2 + o(h^2)

ce qui montre que pour hh assez petit, on a : N(α+h)αN(α)2h2|N(\alpha + h) - \alpha| \leq \frac{|N''(\alpha)|}{2} h^2

et donc pour x=α+hx = \alpha + h on obtient effectivement une meilleure approximation. On dit que cette convergence est quadratique car le terme majorant est de l’ordre de h2h^2.

L’hypothèse C3C^3 de ff va se révéler nécessaire à l’existence de N(α)N''(\alpha) que nous ne calculerons pas mais qui existe bien.

Calcul de N(α)N'(\alpha)

Calculons NN' au voisinage de α\alpha. Pour rappel : N(x)=xf(x)f(x)N(x) = x - \frac{f(x)}{f'(x)}

on a alors : N(x)=1f(x)f(x)f(x)f(x)(f(x))2=f(x)f(x)f(x)2N'(x) = 1 - \frac{f'(x)f'(x) - f(x)f''(x)}{(f'(x))^2} = \frac{f(x)f''(x)}{f'(x)^2}

mais en x=αx=\alpha on a f(x)=0f(x) = 0 et f(x)0f'(x)\neq 0 par hypothèse. Ainsi, on a bien N(α)=0N'(\alpha) = 0 et l’égalité énoncée : N(α+h)=α+N(α)2h2+o(h2).N(\alpha + h) = \alpha +\frac{N''(\alpha)}{2}h^2 + o(h^2) .

Sous des hypothèses plus faibles pour ff

Supposons plus largement que ff est de classe CmC^m avec un 00 d’ordre nn en α\alpha de sorte que m>n+2m>n+2. En d’autres termes, au voisinage de α\alpha on a : f(α+h)=hng(h)+Rm2(h)f(\alpha + h) = h^n g(h) + R_{m-2}(h)

gg est un polynôme de degré mn2m-n-2 non nul en h=0h=0. En particulier, on a : f(α+h)=f(n)n!hn+Rn+1(h).f(\alpha + h) = \frac{f^{(n)}}{n!}h^n + R_{n+1}(h).

Nous n’allons pas reconstruire NN mais simplement analyser son comportement dans un tel cas. Il faut en fait calculer (si possible) le terme : N(α)=f(x)f(x)f(x)2.N'(\alpha) = \frac{f(x)f''(x)}{f'(x)^2}.

Nous ferons d’une pierre deux coups en montrant que cette expression a du sens et qu’elle vaut (n1)/n(n-1)/n.

Commençons par le calcul de ff' et ff'' avec le développement limité en fonction de gg donné :

f(α+h)=nhn1g(h)+hng(h)+Rm2(h)f(α+h)=hn1[ng(h)+hg(h)]+Rm2(h)f(α+h)=(n1)hn2[ng(h)+hg(h)]+hn1[ng(h)+g(h)+hg(h)]+Rm2(h)f(α+h)=hn2[n(n1)g(h)+hg(h)(2+n)+h2g(h)]+Rm2(h)\begin{aligned} f'(\alpha + h) &= nh^{n-1}g(h) + h^ng'(h) + R_{m-2}'(h)\\ f'(\alpha + h) &= h^{n-1}\left[ng(h) + hg'(h)\right] + R_{m-2}'(h)\\ f''(\alpha + h) &= (n-1)h^{n-2}[ng(h) + hg'(h)] + h^{n-1}[ng'(h) + g'(h) + hg''(h)] + R_{m-2}''(h)\\ f''(\alpha + h) &= h^{n-2}\left[ n(n-1)g(h) + hg'(h)(2+n) + h^2g''(h)\right] + R_{m-2}''(h) \end{aligned}

C’est bien pour le calcul de Rm2(h)R_{m-2}''(h) que l’on a besoin d’avoir ff de classe CmC^m avec m>n+2m>n+2. Pour plus de lisibilité, on va oublier d’écrire les termes Rm2(h)R_{m-2}(h), Rm2(h)R_{m-2}'(h) et Rm2(h)R_{m-2}''(h) qui n’ont pas d’importance puisque bien plus petits que les autres pour un voisinage de α\alpha assez petit.

On remplace dans N(x)N'(x) (pour rappel, x=α+hx = \alpha + h) et on arrange les termes pour éliminer ceux en hph^p :

N(x)=f(x)f(x)f(x)2N(x)=hng(h)(hn2[n(n1)g(h)+hg(h)(2+n)+h2g(h)])(hn1[ng(h)+hg(h)])2N(x)=hn+n2g(h)(n(n1)g(h)+hg(h)(2+n)+h2g(h))h2n2(ng(h)+hg(h))2N(x)=n(n1)g(h)2+hg(h)g(h)(2+n)+h2g(h)g(h)(ng(h)+hg(h))2\begin{aligned} N'(x) &= \frac{f(x)f''(x)}{f'(x)^2}\\ N'(x) &= \frac{h^n g(h) \left(h^{n-2}\left[ n(n-1)g(h) + hg'(h)(2+n) + h^2g''(h)\right] \right)}{\left(h^{n-1}\left[ng(h) + hg'(h)\right] \right)^2}\\ N'(x) &= \frac{h^{n+n-2} g(h)\left(n(n-1)g(h) + hg'(h)(2+n) + h^2g''(h)\right)}{h^{2n-2}\left(ng(h) + hg'(h)\right)^2}\\ N'(x) &= \frac{n(n-1)g(h)^2 + hg'(h)g(h)(2+n) + h^2g''(h)g(h)}{(ng(h) + hg'(h))^2} \end{aligned}

Donc cette expression a bien du sens en x=αx=\alpha. Mais en x=αx=\alpha on a h=0h = 0, d’où :

N(α)=n(n1)g(0)2n2g(0)2=n1n.N'(\alpha) = \frac{n(n-1)g(0)^2}{n^2g(0)^2} = \frac{n-1}{n}.

Cela montre que dans un voisinage suffisamment petit de α\alpha on a : N(α+h)αn1nh|N(\alpha + h) - \alpha|\leq \frac{n-1}{n} |h|

et donc la méthode converge également pour une telle application ff. Cependant cette convergence n’est plus quadratique (sauf dans le cas n=1n=1 déjà traité), elle est linéaire.


Maintenant que nous savons manipuler la méthode de Newton en connaissant ses divers comportements, on peut prendre plaisir à donner quelques exemples dans lesquels elle est, ou non, efficace.