Dans ce document on introduit une méthode permettant d’évaluer numériquement une solution de l’équation f(x)=0, avec f une fonction de R dans R (lorsque la solution existe, bien sur) : la méthode de dichotomie.
La méthode de dichotomie est efficace et converge relativement vite. De plus, les conditions de son utilisation sont assez simples : la fonction f doit seulement être continue et changer de signe sur l’intervalle choisi ;
La méthode de Newtonconverge étonnement vite ! Les conditions de son utilisation sont cependant plus contraignantes : la fonction fdoit être dérivable.
Méthode de la dichotomie
Le raisonnement à mettre en œuvre s’appuie sur le théorème des valeurs intermédiaires.
Théorème des valeurs intermédiaires
Soit f:[a,b]→R une fonction continue sur un segment. Si f(a)⋅f(b)⩽0, alors il existe ℓ∈[a,b] tel que f(ℓ)=0.
Principe de résolution du problème
Info
On choisit un intervalle [a,b] dans lequel on pense que la fonction f s’annule une seule fois (il peut donc être nécessaire de limiter la largeur de cet intervalle).
Étape 1. On détermine les coordonnées du point milieu de l’intervalle : 2a+b
Si f(a)⋅f(2a+b)⩽0, le théorème des valeurs intermédiaires permet de conclure qu’il existe un point c∈[a,2a+b] tel que f(c)=0.
Si f(a)⋅f(2a+b)⩾0, le théorème des valeurs intermédiaires permet de conclure qu’il existe un point c∈[2a+b,b] tel que f(c)=0.
On est donc parvenu, à l’issu de cette étape, à définir un intervalle dans lequel f(x)=0, de longueur moitié par rapport à l’intervalle initial.
Étape suivante. On répète le processus mis en œuvre dans l’Étape 1 pour l’intervalle [a,2a+b] ou [2a+b,b].
Étapes suivantes. On continue à répéter le processus jusqu’à ce que l’intervalle soit de longueur inférieure à une longueur choisie (arbitrairement).
La méthode converge-t-elle réellement ?
On construit deux suites (an) et (bn) qui évoluent comme les bornes de l’intervalle, et la suite (xn), zéro de f pour chaque intervalle.
Au rang 0. On pose a0=a, b0=b. Comme f(a)⋅f(b)⩽0, il existe une solution, notée x0, de l’équation f(x)=0 dans l’intervalle [a0,b0].
Au rang 1. Si f(a0)⋅f(2a0+b0)⩽0, alors on pose a1=a0 et b1=2a0+b0, sinon on pose a1=2a0+b0 et b1=b0.
Comme f(a1)⋅f(b1)⩽0, il existe une solution, notée x1, de l’équation f(x)=0 dans l’intervalle [a1,b1].
Au rang n. On suppose construit un intervalle [an,bn], de longueur 2nbn−an, contenant une solution xn de l’équation f(x)=0.
Si f(an)⋅f(2an+bn)⩽0, alors on pose an+1=an et bn+1=2an+bn, sinon on pose an+1=2an+bn et bn+1=bn. Comme f(an+1)⋅f(bn+1)⩽0, il existe une solution, notée xn+1, de l’équation f(x)=0 dans l’intervalle [an+1,bn+1].
Étude des suites construites
Par construction :
- an⩽xn⩽bn
- (an) est une suite croissante, (bn) une suite décroissante.
La limite de (bn−an) tend donc vers 0 lorsque n tend vers +∞ :
lim(bn−an)n→+∞0
Les suites (an) et (bn) sont adjacentes. Elles admettent donc une même limite, ℓ.
Par application du théorème des gendarmes, on peut aussi en conclure que
lim(xn)n→+∞ℓ
et, comme f est une fonction continue,
f(ℓ)=n→+∞limf(xn)=n→+∞lim0=0
En conclusion, les suites (an) et (bn) tendent vers la valeur ℓ, solution de f(x)=0.
Remarque
En pratique, on arrête le processus dès que bn−an=2nb−a
est inférieur à la précision souhaitée.
Exemple : Approximation de 10
On définit la fonction f définie par f(x)=x2−10. f est
une fonction continue sur R qui s’annule en 10 et −10.
On limite l’étude à l’intervalle [3;4] puisque : f(3)=32−10=−1<0 et f(4)=42−10=6>0 entraîne 10∈[3;4].
On écrit le processus itératif :
On pose a0=3 et b0=4. f(a0)⩽0 et f(b0)⩾0.
2a0+b0=3,5 donc f(2a0+b0)=f(3,5)=3,52−10=2,25⩾0.
f(a0)⋅f(2a0+b0)⩽0, on en
déduit que 10 est dans l’intervalle [3;3,5].
On pose a1=3 et b1=3,5.
2a1+b1=3,25 donc f(2a1+b1)=f(3,25)=0,5625⩾0.
f(a1)⋅f(2a1+b1)⩽0, on en
déduit que 10 est dans l’intervalle [3;3,25].
On pose a2=3 et b2=3,25.
2a2+b2=3,125 donc f(2a2+b2)=f(3,125)=−0,23⋅⋅⋅⩽0.
f(b2)⩾0, f s’annule sur l’intervalle [3,125;3,25].
À ce stade, on a donc démontré que : 3,125⩽10⩽3,25.
Avec quelques étapes de plus, on obtient :
a0=3
b0=4
a1=3
b1=3,5
a2=3
b2=3,25
a3=3,125
b3=3,25
a4=3,125
b4=3,1875
a5=3,15625
b5=3,1875
a6=3,15625
b6=3,171875
a7=3,15625
b7=3,164062
a8=3,16015
b8=3,164062
En 8 étapes, on obtient donc l’encadrement :
3,160⩽10⩽3,165
ce qui donne les deux premières décimales du résultat.
Nombre d’itérations nécessaires pour atteindre un résultat
La longueur de l’intervalle [an,bn] est 2nb−a puisqu’il a
été nécessaire de découper n fois l’intervalle de départ en deux pour
parvenir à cet intervalle.
On peut alors rechercher le nombre d’itérations nécessaires pour
atteindre une précision choisie lors de la phase préliminaire de l’étude ; il suffit de rechercher le nombre n tel que 2nb−a⩽10−N :