La méthode de Newton est une des méthodes algorithmiques de résolution d’équations. Elle vient palier au défaut majeur de la dichotomie, à savoir sa « lenteur ». Quel en est le principe ? Comment l’implémenter en Python ?

Principe mathématique de la méthode de Newton

On considère une fonction f continue et dérivable sur un intervalle [a ; b]. On pose alors \(x_0 = a\) et \(A_0(x_0;f(x_0))\) en lequel on trace une tangente.

Cette tangente coupe l’axe des abscisses en un point d’abscisse notée \(x_1\):

On considère alors le point \(A_1(x_1;f(x_1))\) en lequel on trace la tangente à la courbe:

Cette tangente coupe l’axe des abscisses en un point d’abscisse \(x_2\). On considère alors le point \(A_2(x_2;f(x_2))\) en lequel on trace la tangente à la courbe, qui coupe l’axe des abscisses en \(x_3\), etc.

On construit ainsi une suite de nombre sur l’axe des abscisses qui se rapprochent de la solution de l’équation : le point d’intersection de la courbe et de l’axe des abscisses.

La suite numérique définie par la méthode de Newton

Considérons un point \(A_n(x_n;f(x_n))\) ; l’équation de la tangente en ce point est:$$y=f'(x_n)(x-x_n)+f(x_n)$$et \(x_{n+1}\) est donc défini comme la solution de l’équation :$$0=f'(x_n)(x_{n+1}-x_n) + f(x_n)$$ soit: $$x_{n+1} = -\frac{f(x_n)}{f'(x_n)}+x_n.$$Il faut donc, pour que cette méthode fonctionne, que tous les \(f'(x_n)\) soient non nuls sur l’intervalle considéré.

Ainsi, nous allons considérer la suite \(x_n\) définie par:$$\begin{cases}x_0=a\\x_{n+1}=-\frac{f(x_n)}{f'(x_n)}+x_n\end{cases}$$

Implémentation en Python

Une fois la suite définie, il n’y a rien de bien compliqué dans l’implémentation en Python de la méthode:

def newton(fonction,derivee,a,e):
    delta = 1
    while delta > e:
        x = -fonction(a)/derivee(a) + a
        delta = abs(x - a)
        a = x
        
    return x , delta
        
print( newton(lambda x: 0.1*x**3-x+1 , lambda x: 0.3*x**2-1 , 0 , 0.001) )

La fonction newton admet quatre arguments:

• fonction représente la fonction f ;
• derivee représente la fonction dérivée de la fonction f ;
• a représente la valeur initiale de la suite;
• e représente l’erreur maximale souhaitée.

J’ai choisi ici d’écrire les fonctions à l’aide de l’opérateur Python lambda car je trouve cela plus sympa, mais on peut aussi définir les fonctions autrement:

def newton(a,e):
    delta = 1
    while delta > e:
        x = -fonction(a)/derivee(a) + a
        delta = abs(x - a)
        a = x
        
    return x , delta

def fonction(x):
    return 0.1*x**3-x+1

def derivee(x):
    return 0.3*x**2-1
        
print( newton(0 , 0.001) )

Certains préfèreront ce dernier script car plus facile à comprendre (plus intuitif). Notez que si on définit les fonctions comme ceci, nul besoin de les mettre en arguments de la fonction newton; la syntaxe de cette dernière est donc plus allégée.

Vitesse de convergence

La vitesse de convergence d’une suite est déterminée à l’aide d’une majoration de la forme:$$|x_n-\alpha|\leqslant v_n$$où \(v_n\) est une suite numérique et \(\alpha\) la limite de la suite \(x_n\).

Pour cette méthode, on arrive à démontrer que:$$|x_n-\alpha|\leqslant \big[ k|x_0-\alpha| \big]^{2^n},$$où \(k\) est une constante, ce qui est considéré comme une vitesse très rapide; on dit ici que la vitesse est quadratique, c’est-à-dire que la précision de l’approximation double à chaque étape contrairement à la dichotomie qui a une vitesse de convergence linéaire, c’est-à-dire où \(|x_n-\alpha|\leqslant q^n\).

Pour les plus curieux, si I est un intervalle compact contenant les \(x_n\) et \(\alpha\), et inclus dans le domaine de définition de f, $$k=\frac{\max_{x\in I}|f »(x)|}{2\min_{x\in I}|f'(x)|}.$$Mais ce n’est pas du tout au programme du lycée!

Et n’oubliez pas que si vous avez des problèmes en maths, je peux vous aider webcam (cours ponctuels ou réguliers).