Comment appliquer la méthode de Newton avec python ?

En analyse numérique, la méthode de Newton ou méthode de Newton-Raphson1 est, dans son application la plus simple, un algorithme efficace pour trouver numériquement une approximation précise d'un zéro (ou racine) d'une fonction réelle d'une variable réelle wikipedia. Exemple d'implémentation de la méthode avec python:

Solution 1

from scipy import misc

def NewtonsMethod(f, x, tolerance=0.000001):
    while True:
        x1 = x - f(x) / misc.derivative(f, x) 
        t = abs(x1 - x)
        if t < tolerance:
            break
        x = x1
    return x

def f(x):
    return (1.0/4.0)*x**3+(3.0/4.0)*x**2-(3.0/2.0)*x-2

x = 4

x0 = NewtonsMethod(f, x)

print('x: ', x)
print('x0: ', x0)
print("f(x0) = ", ((1.0/4.0)*x0**3+(3.0/4.0)*x0**2-(3.0/2.0)*x0-2 ))

donne

x:  4
x0:  2.0000002745869883
f(x0) =  1.2356416165815176e-06

Solution 2 (scipy)

from scipy.optimize import newton

def f(x):
    return (1.0/4.0)*x**3+(3.0/4.0)*x**2-(3.0/2.0)*x-2

x = 4

x0 = newton(f, x, fprime=None, args=(), tol=1.48e-08, maxiter=50, fprime2=None)

print('x: ', x)
print('x0: ', x0)
print("f(x0) = ", ((1.0/4.0)*x0**3+(3.0/4.0)*x0**2-(3.0/2.0)*x0-2 ))

donne

x:  4
x0:  2.000000000000008
f(x0) =  3.597122599785507e-14

Tracer la figure ci-dessus avec matplotlib

Code utilisé pour tracer la figure de l'exemple ci-dessus:

#!/usr/bin/env python

from pylab import *

t = arange(-6.0, 4.0, 0.01)
s= t*t*t/4.0+3.0*t*t/4.0-3*t/2.0-2.0

ax = subplot(111)

ax.plot(t, s)

ax.scatter([-4,-1,2],[0,0,0])

ax.grid(True)

ax.spines['left'].set_position('zero')
ax.spines['right'].set_color('none')
ax.spines['bottom'].set_position('zero')
ax.spines['top'].set_color('none')

ax.set_xlim(-6,6)
ax.set_ylim(-20,20)

text(-3.0, 12,
     r"$f(x)=(1/4)*X^3+(3/4)*X^2-(3/2)*X-2$", horizontalalignment='center',
     fontsize=8)

plt.title("How to implement the Newton's method using python \n for finding the zeroes of a real-valued function",fontsize=10)

plt.xticks(fontsize=8)
plt.yticks(fontsize=8)

plt.savefig('NewtonMethodExemple.png')
show()

Remarque: Avec numpy il est possible de déterminer les racines d'un polynôme avec la méthode root. Par exemple le polynôme suivant possède 3 racines: -4, 2 et -1.

$$P(x)=\frac{x^3}{4}+\frac{3.x^2}{4}-\frac{3.x}{2}-2$$

Exemple:

>>> import numpy as np
>>> coeff = [1.0/4.0,3.0/4.0,-3.0/2.0,-2]
>>> np.roots(coeff)
array([-4.,  2., -1.])

On peut constater que la méthode de Newton donne bien ici les mêmes résultats.

Références