Méthode de Newton
On considère une fonction $f$ strictement monotone sur un intervalle $[a\,;b]$ et telle qu'il existe un unique $x_0\in[a\,;b]$ solution de l'équation $f(x)=0$.
On cherche une valeur approchée de $x_0$.
On donne une application avec la fonction $f$ définie sur $[0\,;+\infty[$ par $f(x)=x^2-2$ (et la recherche donc d'une approximation de $\sqrt{2}$), puis on donne un algorithme générique pour toute fonction remplissant les conditions énoncées précédemment.
Exemple
Xmin = -1
Xmax = 3
Ymin = -2.2
Ymax = 2.2
function traceN(){
couleur = noir
peinture = blanc
transparence = 1
rectangle([-5,5],20,20)
traceG(4)
traceX()
traceY()
couleur = bleu
graphe(f,0,10)
couleur = rouge
}
function f(x){
return x*x-2
}
function newton(n){
traceN()
a = 2
for(i = 0; i < n-1; i++){
a = -f(a)/(2*a)+a
}
b = a
segment([a,0],[a,f(a)],[5,2])
segment([10,2*a*(10-a)+f(a)],[-10,2*a*(-10-a)+f(a)])
a = -f(a)/(2*a)+a
point([a,0])
couleur = noir
texte(a,[-0.5,1])
}
traceN()
curseur("k",1,1,50,1)
newton({k})
def f(x):
return x*x-2
def newton(n):
a = 2
for i in range(0,n):
a = -1.0*f(a)/(2*a)+a
return a
print(newton(2))
print(newton(3))
print(newton(4))
print(newton(5))
Cas générique
def f(x):
return x*x-2
def t(x):
return x**5-x-1
def deriv(f,a):
e = 10**(-9)
return (f(a+e)-f(a))/e
def newton(f,a,n):
s = a
for i in range(0,n):
s = -f(s)/deriv(f,s)+s
return s
print(newton(f,2,5))
print(newton(t,2,10))