Approximation des solutions d'une équationMéthode de la dichotomie
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$, en procédant en plusieurs étapes :
Calcul du point médian : Calculer $c=\dfrac{a+b}{2}$, milieu du segment $[a;\,b]$.
Évaluation de la fonction : Déterminer le signe de $f(c)$ (en calculant $f(c)$).
Réduction de l'intervalle : Selon le signe de $f(c)$, remplacer $a$ ou $b$ par $c$ de manière à réduire la taille de l'intervalle $[a;\, b]$ .
Si $f(c)$ a le même signe que $f(a)$, remplacer $a$ par $c$ ; sinon, remplacez $b$ par $c$.
Répéter le processus : Répéter les étapes précédentes jusqu'à obtenir un intervalle de largeur voulue ou suffisante en fonction du critère d'arrêt.
Exemple
Xmin = -1
Xmax = 3
Ymin = -2.2
Ymax = 2.2
function traceD(){
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 dicho(n){
traceD()
a = 0
b = 2
for(i = 0; i < n-1; i++){
c = (a+b)/2
if( f(c) < 0){
a = c
}
else{
b = c
}
}
point([a,0])
point([b,0])
segment([a,0],[a,f(a)],[5,2])
segment([0,f(a)],[a,f(a)],[5,2])
segment([b,0],[b,f(b)],[5,2])
segment([0,f(b)],[b,f(b)],[5,2])
c = (a+b)/2
if( f(c) < 0){
a = c
}
else{
b = c
}
couleur = vert
point([c,0])
segment([c,0],[c,f(c)],[5,2])
segment([0,f(c)],[c,f(c)],[5,2])
couleur = noir
texte(c,[-0.5,1])
}
traceD()
curseur("k",1,1,50,1)
dicho({k})
def f(x):
return x*x-2
def dicho(n):
a = 0
b = 10
for i in range(0,n):
c = (a+b)/2.0
if f(c) < 0:
a = c
else:
b = c
return [a,b]
print(dicho(10))
print(dicho(20))
print(dicho(25))
print(dicho(30))
print(dicho(40))
print(dicho(43))
Cas générique
def f(x):
return x*x-2
def t(x):
return x**5-x-1
def dicho(g,a,b,n):
for i in range(0,n):
c = (a+b)/2.0
if g(a)*g(c) > 0:
a = c
else:
b = c
return [a,b]
print(dicho(f,0,10,50))
print(dicho(t,0,10,50))Méthode de la sécante
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$, en procédant en plusieurs étapes :
Calcul de la pente : Utiliser les points $(a;\,f(a))$ et $(b;\,f(b))$ pour déterminer la pente $m$ de la droite passant par ces deux points.
On a $m=\dfrac{f(b)-f(a)}{b-a}$.
Calcul du point d'intersection : Déterminer l'équation de la sécante à l'aide de la pente $m$ et des coordonnées du point $(a;\,f(a))$ : $y=mx+f(a)-ma$.
Déterminer l'abscisse $c$ du point de la sécante qui coupe l'axe des abscisses $c = a-\dfrac{f(a)(b-a)}{f(b)-f(a)}$.
Le nombre $c$ est approximation de $x_0$.
Réduction de l'intervalle : Selon le signe de $f(c)$, remplacer $a$ ou $b$ par $c$ de manière à réduire la taille de l'intervalle $[a;\, b]$ .
Si $f(c)$ a le même signe que $f(a)$, remplacer $a$ par $c$ ; sinon, remplacez $b$ par $c$.
Répéter le processus : Répéter les étapes précédentes jusqu'à obtenir un intervalle de largeur voulue ou suffisante en fonction du critère d'arrêt.
Exemple
Xmin = -1
Xmax = 3
Ymin = -2.2
Ymax = 2.2
function traceS(){
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 dicho(n){
traceS()
a = 0
b = 2
for(i = 0; i < n-1; i++){
c = a-f(a)*(b-a)/(f(b)-f(a))
if( f(c) < 0 ){
a = c
}
else{
b = c
}
}
segment([a,f(a)],[b,f(b)])
c = a-f(a)*(b-a)/(f(b)-f(a))
if( f(c) < 0 ){
a = c
}
else{
b = c
}
couleur = vert
point([c,0])
segment([c,0],[c,f(c)],[5,2])
segment([0,f(c)],[c,f(c)],[5,2])
couleur = noir
texte(c,[-0.5,1])
}
traceS()
curseur("k",1,1,50,1)
dicho({k})
def f(x):
return x*x-2
def secante(n):
a = 0
b = 10
for i in range(0,n):
c = a-f(a)*(b-a)*1.0/(f(b)-f(a))
if f(c) < 0:
a = c
else:
b = c
return c
print(secante(10))
print(secante(20))
print(secante(30))
print(secante(40))
print(secante(94))
print(secante(95))
Cas générique
def f(x):
return x*x-2
def t(x):
return x**3-2
def secante(f,a,b,n):
for i in range(0,n):
c = a-f(a)*(b-a)*1.0/(f(b)-f(a))
if f(c)*f(a) < 0:
a = c
else:
b = c
return c
print(secante(f,0,10,50))
print(secante(t,0,2,200))Méthode de Newton
On considère une fonction $f$ strictement monotone sur un intervalle $[a\,;b]$ et telle qu'il existe un unique $\alpha\in[a\,;b]$ solution de l'équation $f(x)=0$.
On cherche une valeur approchée de $\alpha$.
Choix du point initial : Sélectionner un point initial $u_0$ « proche » de la solution recherchée.
Détermination de la tangente : Déterminer l'équation réduite de la tangente à la courbe de la fonction $f$ au point d'abscisse $u_0$ :
$$y=f'(u_0)(x-u_0)+f(u_0).$$
Trouver l'intersection avec l'axe des abscisses : Déterminer le point $u_1$ où la tangente coupe l'axe des abscisses.
$$u_1=u_0-\dfrac{f(u_0)}{f'(u_0)}.$$
Le nombre $u_1$ est valeur approchée de $\alpha$.
Répéter le processus : Répéter les étapes précédentes en remplaçant $u_0$ par $u_1$, puis $u_1$ par $u_2$ etc.
Critère d'arrêt : définir un critère d'arrêt comme un nombre d'étapes précis, une valeur de $f(u_n)$ suffisamment proche de $0$, ou un écart minimal entre $u_{n+1}$ et $u_n$.
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))