Méthode de 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$.
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 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))