Méthode de Newton

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>0$et $\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 !}g’’(\xi_n)\\ &=&x_*+0+\displaystyle\frac{e_n^2}{2 !}g’’(\xi_n)\\ &=&x_*+\displaystyle\frac{e_n^2}{2 !}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 !}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 !}g’’(x_*) +\displaystyle\frac{e_n^3}{3 !}g^{(3)}(\xi_n)\\ &=&x_*+0+0 +\displaystyle\frac{e_n^3}{3 !}g^{(3)}(\xi_n)\\ &=&x_*+\displaystyle\frac{e_n^3}{3 !}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 !}g^{(3)}(\xi_n)$$
et

$$\lim_{n\to\infty}\frac{|e_{n+1}|}{|e_{n}|^3}=|\displaystyle\frac{g^{(3)}(x_*)}{3 !}|$$
la constante d’erreur asymptotique est $C=\displaystyle|\frac{g^{(3)}(x_*)}{3 !}|$ 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 :

$$ \displaystyle \begin{array}{ccl} 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) \end{array} $$

Par suite :

$$g’(x_*)=0$$
On conclut donc comme précédemment que la méthode de Newton modifiée est au moins quadratique.