Méthode de Newton en Python

9.1 L'idée

On veut résoudre $f(x) = 0$, lorsqu'aucune formule n'est disponible. L'idée de Newton : on remplace la courbe par sa tangente, car on sait où une droite coupe l'axe des abscisses.

On part d'un nombre $x_0$. La tangente au point d'abscisse $x_0$ coupe l'axe en un nombre $x_1$. La tangente au point d'abscisse $x_1$ le coupe en $x_2$, et ainsi de suite.

9.2 La formule

La tangente au point d'abscisse $a$ a pour équation $y = f(a) + f'(a)(x - a)$. Elle coupe l'axe des abscisses là où $y = 0$. Si $f'(a) \neq 0$, cela donne $x = a - \dfrac{f(a)}{f'(a)}$. On obtient une suite définie par son premier terme et la relation $x_{n + 1} = x_n - \frac{f(x_n)}{f'(x_n)}.$

Exemple 34. Pour $f(x) = x^2 - 2$, on a $f'(x) = 2x$. La solution positive de $f(x) = 0$ est $\sqrt2$. Avec $x_0 = 2$ : $x_1 = 2 - \frac24 = 1{,}5, \qquad x_2 = 1{,}5 - \frac{0{,}25}{3} = \frac{17}{12} \approx 1{,}4167.$

9.3 Le programme

def f(x):
    return x**2 - 2

def df(x):
    return 2*x

def newton(x0, n):
    liste = [x0]
    x = x0
    for k in range(n):
        x = x - f(x) / df(x)
        liste.append(x)
    return liste

En langage naturel, l'instruction de la boucle s'écrit $x \leftarrow x - \dfrac{f(x)}{f'(x)}$. Chaque tâche a sa fonction : pour changer d'équation, on ne modifie que f et df.

La convergence est très rapide : le nombre de décimales justes double à peu près à chaque étape.

9.4 Une équation sans formule

Exemple 35. Soit $f(x) = x^3 + x - 1$. Sa dérivée, $f'(x) = 3x^2 + 1$, est strictement positive : $f$ est strictement croissante sur $\mathbb{R}$. Sur sa courbe, on voit qu'elle coupe l'axe des abscisses une seule fois, entre $0$ et $1$. Avec f et df adaptées, newton(1, 4) renvoie [1, 0.75, 0.686046511627907, 0.6823395825973142, 0.6823278039465127]. La solution vaut environ $0{,}6823$.

9.5 Des cas favorables

La méthode n'est pas magique. Si la tangente est horizontale, elle ne coupe pas l'axe : la formule diviserait par zéro. Si le point de départ est mal choisi, les nombres obtenus peuvent s'éloigner de la solution.

On se limite donc à des cas favorables : $f$ est strictement monotone autour de la solution, sa dérivée ne s'y annule pas, et on part assez près. Un calcul numérique donne une très bonne valeur approchée, mais il ne démontre rien sur la solution.