Math-Linux.com

Knowledge base dedicated to Linux and applied mathematics.

Accueil > Mathématiques > Résolution numérique des équations non linéaires > Méthode de Newton

Méthode de Newton

Toutes les versions de cet article : [English] [français]

La méthode de Newton ou méthode de Newton-Raphson est une méthode numérique itérative de résolution numérique des équations du type f(x)=0. Elle repose sur la méthode du point fixe avec une fonction g particulière qui dépend de la dérivée de f.

Définition

La méthode de Newton est une méthode de point fixe avec pour application g :

g(x)=x-\displaystyle\frac{f(x)}{f’(x)}


On voit clairement que rechercher un point fixe de l’application g revient à chercher une solution de l’équation

f(x)=0\quad (E).


On rappelle que la recherche d’un point fixe se fait via un algorithme itératif définit par la suite

x_{n+1}=g(x_n)


le schéma numérique de la méthode de Newton est donc donné par

x_{n+1}=x_n-\displaystyle\frac{f(x_n)}{f’(x_n)}

Interprétation géométrique

L’équation de la tangente à la courbe de f au point (x_n,f(x_n)) est donné par

y=f(x_n)+f’(x_n)(x-x_n)


x_{n+1} n’est rien d’autre que l’abscisse du point d’intersection de cette tangente avec l’axe (Ox), en effet


\begin{array}{lcl}
y&=&0\\
x&=&x_n-\displaystyle\frac{f(x_n)}{f’(x_n)}
\end{array}


On prend alors pour x_{n+1} :

x_{n+1}=x_n-\displaystyle\frac{f(x_n)}{f’(x_n)}

Convergence de la méthode de Newton

Théorème. Soit f\in\mathcal{C}^2([a,b]) et soit x_*\in]a,b[ tel que

f(x_*)=0


et

f’(x_*)\neq 0


alors il existe \delta>0 tel que la méthode de Newton converge pour tout élément x_0\in I_\delta=[x_*-\delta,x_*-\delta]

Preuve. Par hypothèse, f’ est continue et f’(x_*)\neq 0,
il existe donc un \eta>0 tel que :

f’(x)\neq 0 \quad \forall x \in[x_*-\eta,x_*-\eta]\subset [a,b]

La dérivée de g est définie par :

g’(x)=(x-\displaystyle\frac{f(x)}{f’(x)})’=\displaystyle\frac{f(x)f’’(x)}{f’(x)^2}

Par hypothèse, f(x_*)=0 et f’(x_*)\neq 0, par conséquent :

g’(x_*)=0


De plus, g’ est continue sur [x_*-\eta,x_*-\eta] vu que

f’(x)\neq 0 \quad \forall x \in[x_*-\eta,x_*-\eta]\subset [a,b]


écrivons la continuité de g’ en x_* dans l’intervalle [x_*-\eta,x_*-\eta]

\forall \varepsilon >0 \quad |x-x*|\leq \eta \Longrightarrow |g’(x)-g’(x_*)|\leq\varepsilon


c’est à dire

\forall \varepsilon >0 \quad |x-x*|\leq \eta \Longrightarrow |g’(x)|\leq\varepsilon


Il existe alors \delta<\eta tel que

|g’(x)|\leq\tau,\quad\forall x\in I_\delta=[x_*-\delta,x_*-\delta],\quad\tau\in]0,1[.


On a donc montré l’une des hypothèses du point fixe. Il reste à montrer à présent que g est stable dans l’intervalle I_\delta, c’est à dire :

g(I_\delta)\subset I_\delta


En utilisant le théorème de la moyenne on montre qu’il existe un élément
\xi\in]x,x_*[ tel que


\begin{array}{ccl}
|g(x)-g(x_*)|&=&|g’(\xi})||x-x_*|\leq\tau|x-x_*|<|x-x_*|\\
|g(x)-x_*)|&<&|x-x_*|
\end{array}


d’oà¹

g(I_\delta)\subset I_\delta


On a donc montré que :
- g\in\mathcal{C}^1(I_\delta) et g(I_\delta)\subset I_\delta
- il existe une constante \tau dans ]0,1[ telle que |g’ (x)|\leq \tau.
On conclut alors à l’aide du théorème du point fixe :
la suite définie par x_{n+1} = g(x_n ) converge vers x_* le point fixe de g \forall x_0\in I_\delta.

Ordre de convergence de la méthode de Newton

Théorème.
Si
- g’(x_*)=0
- g’’ est continue sur un ouvert \mathcal{O} contenant x_*
- g’’(x_*)\neq0

alors il existe \delta>0 telle que la suite définie par x_{n+1} = g(x_n ) converge vers x_* le point fixe de g \forall x_0\in I_\delta=[x_*-\delta,x_*-\delta]. L’ordre de convergence de la méthode de Newton est alors 2 : la convergence est quadratique.

Preuve. Comme précédemment, on montre qu’il existe \delta>0et \tau\in]0,1[ tels que

|g’(x)|\leq\tau,\quad\forall x \in I_\delta=[x_*-\delta,x_*-\delta] \subset\mathcal{O}


Puisque g’(x_*)=0, on introduit un développement de Taylor au voisinage de x_* de de la fonction g d’ordre 2, en utilisant le fait évidemment que e_n=x_n-x_* tend vers 0.


\begin{array}{ccl}
x_{n+1}&=&g(x_n)\\
&=&g(e_n+x_*)\\
&=&g(x_*)+e_ng’(x_*)+\displaystyle\frac{e_n^2}{2&nbsp;!}g’’(\xi_n)\\
&=&x_*+0+\displaystyle\frac{e_n^2}{2&nbsp;!}g’’(\xi_n)\\
&=&x_*+\displaystyle\frac{e_n^2}{2&nbsp;!}g’’(\xi_n)\\
\end{array}


avec \xi_n\in]x_*,e_n+x_*[=]x_*,x_n[, d’oà¹

e_{n+1}=x_{n+1}-x_*=\displaystyle\frac{e_n^2}{2&nbsp;!}g’’(\xi_n)


et

\lim_{n\to\infty}\frac{|e_{n+1}|}{|e_{n}|^2}=|\frac{g’’(x_*)}{2}|


la constante d’erreur asymptotique est C=\displaystyle|\frac{g’’(x_*)}{2}| et la convergence est quadratique, c’est à dire d’ordre 2 puisque par hypothèse g’’(x_*)\neq0.

Multiplicité d’une racine

Soit p\in\mathbf{N}, on dit que f possède une racine de multiplicité ou d’ordre p si


\begin{array}{lcl}
f(x_*)&=&f’(x_*)=f’’(x_*)=f^{(3)}(x_*)=\ldots=f^{(p-1)}(x_*)=0\\
f^{(p)}(x_*)&\neq& 0
\end{array}


et f peut s’écrire comme suit :

f(x)=(x-x_*)^ph(x)


avec h(x_*)\neq0.

Convergence de la méthode de Newton : racine simple

Théorème. Si f\in\mathcal{C}^2([a,b]) et f possède une racine simple alors la méthode
de Newton converge au moins avec un ordre quadratique (ordre 2).

Preuve. Si f possède une racine simple alors


\begin{array}{lcl}
f(x_*)&=&0\\
f^{’}(x_*)&\neq& 0
\end{array}


La méthode de Newton converge.

La dérivée de g est définie par :

g’(x)=(x-\displaystyle\frac{f(x)}{f’(x)})’=\displaystyle\frac{f(x)f’’(x)}{f’(x)^2}


La dérivée seconde de g est définie par :

g’’(x)=\displaystyle\frac{f’(x)^3f’’(x) +    f’(x)^2f(x)f^{(3)}(x) - 2 f’(x) f’’^2(x)f(x)             }{f’(x)^4}


et

g’’(x_*)=\displaystyle\frac{f’’(x_*)}{f’(x_*)}


Si f’’(x_*)\neq 0
alors
- g’(x_*)=0
- g’’ est continue sur un ouvert \mathcal{O} contenant x_*
- g’’(x_*)\neq0

Si f’’(x_*)=0, alors g’’(x_*)=0, on doit faire une étude plus poussée en introduisant un développement de Taylor au voisinage de x_* de de la fonction g à l’ordre 3, en utilisant le fait évidemment que e_n tend vers 0. Cela donne


\begin{array}{ccl}
x_{n+1}&=&g(x_n)\\
&=&g(e_n+x_*)\\
&=&g(x_*)+e_ng’(x_*)+\displaystyle\frac{e_n^2}{2&nbsp;!}g’’(x_*)
+\displaystyle\frac{e_n^3}{3&nbsp;!}g^{(3)}(\xi_n)\\
&=&x_*+0+0
+\displaystyle\frac{e_n^3}{3&nbsp;!}g^{(3)}(\xi_n)\\
&=&x_*+\displaystyle\frac{e_n^3}{3&nbsp;!}g^{(3)}(\xi_n)\\
\end{array}


avec \xi_n\in]x_*,e_n+x_*[=]x_*,x_n[, d’oà¹

e_{n+1}=x_{n+1}-x_*=\displaystyle\frac{e_n^3}{3&nbsp;!}g^{(3)}(\xi_n)


et

\lim_{n\to\infty}\frac{|e_{n+1}|}{|e_{n}|^3}=|\displaystyle\frac{g^{(3)}(x_*)}{3&nbsp;!}|


la constante d’erreur asymptotique est C=\displaystyle|\frac{g^{(3)}(x_*)}{3&nbsp;!}| et la convergence est cubique si g^{(3)}(x_*)\neq 0 c’est à dire d’ordre 3. Si g^{(3)}(x_*)=0 il faudra faire un développement de Taylor d’ordre 4 de g au voisinage
de x_*.

On a donc montré que la convergence de la méthode de Newton est au moins quadratique.

Convergence de la méthode de Newton : racine multiple

Théorème. Supposons que f possède une racine de multiplicité d’ordre p. Alors la méthode de Newton converge linéairement (ordre 1) et la constante d’erreur asymptotique est :

C=1-\frac{1}{p}

Preuve. f possède une racine de multiplicité d’ordre p\geq2, par suite il existe une application h telle que :

f(x)=(x-x_*)^ph(x)


avec h(x_*)\neq0.
On montre alors que la dérivée g’ de g est définie comme suit :


\begin{array}{ccl}
g’(x)=1&-&\displaystyle\frac{(ph(x)+(x-x_*)h’(x))(h(x)+
(x-x_*)h’(x))}{(ph(x)+(x-x_*)h’(x))^2}\\
&+& \displaystyle\frac{(x-x_*)h(x)(ph’(x)+h’(x)+(x-x_*)h’’(x))}{(ph(x)+(x-x_*)h’(x))^2}
\end{array}


Par suite :

g’(x_*)=1-\frac{1}{p}


donc g’(x_*)\neq 0 puisque p\geq2. Un développement de Taylor au voisinage de x_* de de la fonction g à l’ordre 1 donne


\begin{array}{ccl}
x_{n+1}&=&g(x_n)\\
&=&g(e_n+x_*)\\
&=&g(x_*)+e_ng’(\xi_n)\\
&=&x_*+e_ng’(\xi_n)
\end{array}


avec \xi_n\in]x_*,e_n+x_*[=]x_*,x_n[, d’oà¹

e_{n+1}=x_{n+1}-x_*=e_ng’(\xi_n)


La convergence est alors d’ordre 1 donc linéaire puisque :

\lim_{n\to\infty}\frac{|e_{n+1}|}{|e_{n}|}=|g’(x_*)|=|1-\frac{1}{p}|=1-\frac{1}{p}


avec pour constante asymptotique

C=1-\frac{1}{p}.

Méthode de Newton modifiée

Nous avons vu précédemment que lorsque la fonction $f$ possède des racines multiples
l’ordre de convergence se trouve détérioré puisqu’on obtient seulement un ordre de convergence linéaire. Comment récupérer un ordre de convergence quadratique (ordre 2), lorsque les racines sont d’un ordre p\geq2 ? C’est l’objet de la méthode de Newton modifiée.

Définition.

On appelle méthode de Newton modifiée d’ordre p, la méthode de point fixe avec pour application

g(x)=x-p\displaystyle\frac{f(x)}{f’(x)}

Théorème. Supposons que f possède une racine de multiplicité d’ordre p. Alors la méthode de Newton modifiée converge au moins quadratiquement(ordre 2).

Preuve.
On montre alors que la dérivée
g’ de g
est définie comme suit :
g’(x)=1 - p((ph(x)+(x-x_*)h’(x))(h(x)+(x-x_*)h’(x)) + (x-x_*)h(x)(ph’(x)+h’(x)+(x-x_*)h’’(x)))/((ph(x)+(x-x_*)h’(x))^2)
Par suite :

g’(x_*)=0


On conclut donc comme précédemment que la méthode de Newton modifiée est au moins quadratique.

Un message, un commentaire ?

comments powered by Disqus