Méthode de Newton

Supposons que l'on souhaite résoudre numériquement l'équation

$$f(z) = 0\;.$$

La méthode consiste à écrire une solution $z$ comme point fixe d'une fonction $F$, choisie de manière à être contractante, avec le meilleur rapport de contraction possible sur un intervalle contenant le point fixe. Supposons que $f$ soit une application dérivable de $\mathbb{R}$ dans $\mathbb{R}$, et que l'on connaisse une valeur $x_0$ pas trop éloignée de la solution. L'équation de la tangente en $x_0$ au graphe de $f$ est :

$$y = f(x_0) + (x-x_0)f'(x_0)\;.$$

Si $f'(x_0)\neq 0$, cette droite coupe l'axe des $x$ au point :

$$x_1 = x_0 -\frac{f(x_0)}{f'(x_0)}\;.$$

Il est raisonnable d'espérer que $x_1$ soit beaucoup plus proche de la solution cherchée que $x_0$. La suite itérative que l'on se propose de calculer est donc $(F^{\circ n}(x_0))$, avec :

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

(Il faut bien sûr s'assurer que la suite est bien définie, c'est-à-dire que pour tout $n$, $f'(x_n)\neq 0$.)

Par exemple, si on souhaite calculer numériquement $\sqrt{2}$, on pourra l'écrire comme solution de l'équation $x^2-2=0$, et contruire la suite définie par $x_0=2$ et pour tout $n\geqslant 0$ :

$$x_{n+1} = x_n - \frac{x_n^2-2}{2x_n}\;.$$

La figure 6 montre une illustration graphique.

Figure 6: Méthode de Newton.

La précision de la méthode est décrite par le théorème suivant, que nous admettrons.

Théorème 13   Soit $f$ une application de $\mathbb{R}$ dans $\mathbb{R}$ et $z$ un réel tel que $f(z)=0$. On suppose que $f$ est deux fois continûment dérivable sur un intervalle ouvert contenant $z$, et que $f'(z)\neq 0$. Notons :

$$F(x) = x-\frac{f(x)}{f'(x)}\;,$$   et$$\quad M=\Big\vert\frac{f''(z)}{f'(z)}\Big\vert\;.$$

Il existe $h$, $0<h<1/M$ tel que pour tout $x_0\in[z-h,z+h]$, la suite itérative $(F^{\circ n}(x_0))$ est définie et vérifie :

$$\vert F^{\circ n}(x_0)-z\vert <\frac{1}{M} (M\vert x_0-z\vert)^{2^n}\;.$$ (2)

La majoration (2) traduit une convergence extrêmement rapide. Supposons pour fixer les idées que $M=1$ et $\vert x_0-z\vert=10^{-1}$, alors la précision sera de $10^{-2}$ à la première itération, $10^{-4}$ à la seconde, $10^{-8}$ à la troisième, et on peut s'attendre à $32$ décimales exactes à la cinquième itération. Chaque itération double le nombre de décimales exactes. En ce qui concerne la constante $M$, il est intuitivement normal que la méthode soit d'autant plus performante que la dérivée seconde est plus faible (la courbe est plus proche de sa tangente), et la dérivée plus grande.

Exemple : Reprenons l'équation $z^2-2 = 0$, en partant de $x_0=2$. Voici les $5$ premières valeurs de la suite $(F^{\circ n}(2))$, à comparer avec $\sqrt{2}\simeq 1.4142135623730950488$.

$$\begin{array}{\vert c\vert c\vert} \hline n&F^{\circ n}(2)\\... ...5623746899106\\ 5& 1.4142135623730950488\\ \hline \end{array}$$

La méthode de Newton est extrêmement précise. En revanche, elle nécessite une initialisation relativement proche de la solution que l'on cherche. Utiliser la méthode à partir d'un point quelconque peut conduire à des résultats numériquement instables, dans la mesure où deux suites récurrentes, même si elles partent de points très voisins, peuvent converger vers des valeurs très éloignées. Exemple : Considérons l'équation $\sin(\pi z)=0$, dont les solutions sont les entiers relatifs. Si $f(x)=\sin(\pi x)$, alors :

$$F(x) = x-\frac{\sin(\pi x)}{\pi\cos(\pi x)}\;.$$

Le tableau ci-dessous donne les valeurs de $F^{\circ 5}(x_0)$ pour quelques valeurs de $x_0$ proches de $0.5$, valeur en laquelle $f'$ s'annule.

$$\begin{array}{\vert c\vert cccccccccc\vert} \hline x_0&0.491... ...-14.&-20.&-33.&-101.&102.&34.&21.&15.&12.\\ \hline \end{array}$$