La méthode de Newton-Raphson

Résumé

Le théorème de Bolzano assure qu’une fonction continue qui change de signe possède une racine, et la dichotomie la localise en gagnant un chiffre binaire par itération. Cette leçon étudie un procédé beaucoup plus rapide quand il fonctionne : la méthode de Newton-Raphson, qui remplace la courbe par sa tangente et prend comme nouvelle approximation le point où la tangente coupe l’axe. Les approximations ainsi obtenues se définissent l’une après l’autre pour les entiers $n \geq 0$ , et leur limite se comprend au moyen de la définition de la limite quand la variable tend vers l’infini, sans la théorie des suites. La leçon démontre, à l’aide de la convexité, que si la dérivée ne s’annule pas et que la fonction est convexe ou concave, les itérés qui partent du bon côté s’approchent de la racine sans la dépasser et convergent vers elle ; et, à l’aide du théorème des accroissements finis, que la valeur de la fonction, que l’on calcule, majore la distance à la racine, que l’on ne connaît pas. Elle montre ensuite, sur des exemples numériques, que le nombre de chiffres exacts double à chaque itération, et les façons dont la méthode échoue : une dérivée nulle, un cycle, une divergence. Les problèmes calculent des racines cubiques et des inverses sans diviser, brisent un cycle, étudient une racine double et trouvent la frontière exacte entre la convergence et la divergence pour l’arc tangente.

Objectifs d’apprentissage

Calculer les itérés de Newton-Raphson d’une fonction dérivable et y reconnaître le point où la tangente coupe l’axe.
Démontrer la convergence monotone des itérés quand la dérivée ne s’annule pas et que la fonction est convexe ou concave, et choisir un point de départ du bon côté.
Majorer la distance d’une approximation à la racine au moyen de la valeur de la fonction et d’un minorant de sa dérivée.
Reconnaître les façons dont la méthode échoue et la comparer avec la dichotomie, en rapidité et en sûreté.

L’itération

Soit $f$ une fonction dérivable dont on cherche la racine $r$ , et soit $x_0$ une première approximation. Près de $x_0$ , la courbe de $f$ ressemble à sa tangente, $y = f(x_0) + f'(x_0)(x - x_0)$ , selon la définition de la tangente donnée dans la leçon sur la dérivée comme limite ; dit avec la différentielle de la leçon sur les dérivées successives et la différentielle, l’accroissement $f(x_0 + \Delta x) - f(x_0)$ ressemble à $f'(x_0) \Delta x$ . La tangente coupe l’axe en un seul point si $f'(x_0) \neq 0$ , et il est naturel de le prendre comme nouvelle approximation : on l’obtient en égalant à zéro l’équation de la tangente. Répéter le procédé à partir du point obtenu, c’est la méthode de Newton-Raphson.

DéfinitionItérés de Newton-Raphson

Soient $f$ une fonction dérivable sur un intervalle $I$ et $x_0$ un point de $I$ . Les itérés de Newton-Raphson à partir de $x_0$ sont les nombres définis, l’un après l’autre, par

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

tant que $x_n$ est dans $I$ et que $f'(x_n) \neq 0$ . Si ces conditions sont remplies pour tout entier $n \geq 0$ , les itérés forment une fonction $n \mapsto x_n$ définie sur l’ensemble des entiers positifs ou nuls, qui n’est pas majoré, et la définition de la limite quand la variable tend vers l’infini, de la leçon sur les limites quand la variable tend vers l’infini, s’y applique. On dit que les itérés convergent vers $r$ si $\lim_{n \to \infty} x_n = r$ , c’est-à-dire si

(\forall \varepsilon > 0)(\exists M)(\forall n \geq 0)\left(n > M \rightarrow \abs{x_n - r} < \varepsilon\right)

Chaque itéré est le point où la tangente en $(x_n, f(x_n))$ coupe l’axe : en posant $y = 0$ et $x = x_{n+1}$ dans l’équation $y = f(x_n) + f'(x_n)(x - x_n)$ et en exprimant l’inconnue, on obtient la formule de la définition. La méthode ne demande pas que la fonction change de signe sur un intervalle donné, comme la dichotomie, mais qu’elle soit dérivable et que sa dérivée ne s’annule pas aux points par lesquels elle passe ; en revanche, rien n’assure d’avance que les itérés s’approchent d’une racine. On donne plus loin des conditions qui l’assurent.

ExempleLa racine carrée de 2

Appliquer la méthode de Newton-Raphson à $f(x) = x^2 - 2$ à partir de $x_0 = 2$ . Le calcul ci-dessous montre les trois premières tangentes et les points où elles coupent l’axe.

Démonstration

$x_{n+1} = x_n - \frac{x_n^2 - 2}{2x_n} = \frac{1}{2}\left(x_n + \frac{2}{x_n}\right), \qquad \resaltar{x_1 = \frac{3}{2}}$
La dérivée est $f'(x) = 2x$ , qui ne s’annule pas si $x > 0$ . L’itération prend la forme que voici : chaque approximation est la moyenne de celle qui la précède et de $2$ divisé par celle-ci. À partir de $x_0 = 2$ , la tangente $y = 2 + 4(x - 2)$ coupe l’axe en $\frac{3}{2}$ .
$x_2 = \frac{1}{2}\left(\frac{3}{2} + \frac{4}{3}\right) = \resaltar{\frac{17}{12}} \approx 1{,}416667$
La tangente en $\left(\frac{3}{2}, \frac{1}{4}\right)$ coupe l’axe beaucoup plus près de la racine.
$x_3 = \frac{1}{2}\left(\frac{17}{12} + \frac{24}{17}\right) = \resaltar{\frac{577}{408}} \approx 1{,}4142157, \qquad \sqrt{2} \approx 1{,}4142136$
Le troisième itéré a déjà cinq décimales exactes. Les erreurs, $x_n - \sqrt{2}$ , valent environ $0{,}59$ , $0{,}086$ , $0{,}0025$ et $0{,}0000021$ : chacune est de l’ordre du carré de celle qui la précède.

L’erreur de cet exemple s’élève au carré de façon exacte. De la formule de l’itération on tire, pour tout $x_n > 0$ , l’identité que voici :

x_{n+1} - \sqrt{2} = \frac{x_n^2 - 2\sqrt{2}\,x_n + 2}{2x_n} = \frac{\left(x_n - \sqrt{2}\right)^2}{2x_n}

Par conséquent, tous les itérés à partir du premier sont supérieurs ou égaux à $\sqrt{2}$ , et si $x_n \geq 1$ , la nouvelle erreur est au plus la moitié du carré de l’erreur actuelle : le quatrième itéré, $x_4 = \frac{665\,857}{470\,832}$ , a onze décimales exactes. Avec $2$ remplacé par un nombre strictement positif quelconque, le même procédé calcule des racines carrées ; il figure déjà dans les Métriques de Héron d’Alexandrie, au Ier siècle, et c’est pourquoi on l’appelle aussi méthode de Héron.

Isaac Newton décrivit sa méthode pour les équations polynomiales en 1669, dans un écrit qui circula sous forme manuscrite et fut publié en 1711 ; Joseph Raphson publia en 1690 un exposé plus simple, et Thomas Simpson la présenta en 1740 comme une méthode itérative pour des équations générales.