Méthode de la bissection - Bisection method

Quelques étapes de la méthode de bissection appliquée sur l'intervalle de départ [a ₁ ;b ₁ ]. Le plus gros point rouge est la racine de la fonction.

En mathématiques , la méthode de la bissection est une méthode de recherche de racine qui s'applique à toutes les fonctions continues pour lesquelles on connaît deux valeurs de signes opposés. La méthode consiste à diviser plusieurs fois en deux l' intervalle défini par ces valeurs puis à sélectionner le sous-intervalle dans lequel la fonction change de signe, et doit donc contenir une racine . C'est une méthode très simple et robuste, mais elle est aussi relativement lente. Pour cette raison, il est souvent utilisé pour obtenir une approximation grossière d'une solution qui est ensuite utilisée comme point de départ pour des méthodes convergeant plus rapidement. La méthode est également appelée méthode de réduction de moitié par intervalle , laméthode de recherche binaire , ou la méthode de dichotomie .

Pour polynômes , des méthodes plus élaborées existent pour tester l'existence d'une racine dans un intervalle ( la règle de Descartes des signes , le théorème de Sturm , le théorème de Budan ). Ils permettent d'étendre la méthode de bissection à des algorithmes efficaces pour trouver toutes les racines réelles d'un polynôme ; voir Isolation de la racine réelle .

La méthode

La méthode est applicable pour résoudre numériquement l'équation f ( x ) = 0 pour la variable réelle x , où f est une fonction continue définie sur un intervalle [ a , b ] et où f ( a ) et f ( b ) ont des signes opposés . Dans ce cas , on dit que a et b encadrent une racine puisque, d'après le théorème des valeurs intermédiaires , la fonction continue f doit avoir au moins une racine dans l'intervalle ( a , b ).

À chaque étape, la méthode divise l'intervalle en deux parties/moitiés en calculant le milieu c = ( a + b ) / 2 de l'intervalle et la valeur de la fonction f ( c ) à ce point. A moins que c ne soit lui-même une racine (ce qui est très improbable, mais possible) il n'y a maintenant que deux possibilités : soit f ( a ) et f ( c ) ont des signes opposés et mettent entre parenthèses une racine, soit f ( c ) et f ( b ) ont des signes opposés et mettent entre parenthèses une racine. La méthode sélectionne le sous-intervalle qui est garanti être une parenthèse comme nouvel intervalle à utiliser à l'étape suivante. De cette façon, un intervalle qui contient un zéro de f est réduit en largeur de 50 % à chaque pas. Le processus est poursuivi jusqu'à ce que l'intervalle soit suffisamment petit.

Explicitement, si f ( a ) et f ( c ) ont des signes opposés, alors la méthode définit c comme nouvelle valeur pour b , et si f ( b ) et f ( c ) ont des signes opposés alors la méthode définit c comme la nouvelle un . (Si f ( c )=0 alors c peut être pris comme solution et le processus s'arrête.) Dans les deux cas, les nouveaux f ( a ) et f ( b ) ont des signes opposés, donc la méthode est applicable à cet intervalle plus petit .

Tâches d'itération

L'entrée de la méthode est une fonction continue f , un intervalle [ a , b ] et les valeurs de fonction f ( a ) et f ( b ). Les valeurs des fonctions sont de signe opposé (il y a au moins un passage à zéro dans l'intervalle). Chaque itération exécute ces étapes :

Calculer c , le milieu de l'intervalle, c = a + b/2.
Calculez la valeur de la fonction au milieu, f ( c ).
Si la convergence est satisfaisante (c'est-à-dire que c - a est suffisamment petit, ou | f ( c )| est suffisamment petit), retourne c et arrête l'itération.
Examinez le signe de f ( c ) et remplacez ( a , f ( a )) ou ( b , f ( b )) par ( c , f ( c )) afin qu'il y ait un passage par zéro dans le nouvel intervalle.

Lors de la mise en œuvre de la méthode sur un ordinateur, il peut y avoir des problèmes de précision finie, il y a donc souvent des tests de convergence supplémentaires ou des limites au nombre d'itérations. Bien que f soit continue, une précision finie peut empêcher une valeur de fonction d'être nulle. Par exemple, considérons $f (x) = x - π$ ; il n'y aura jamais de représentation finie de x qui donne zéro. De plus, la différence entre a et b est limitée par la précision en virgule flottante ; c'est-à-dire que lorsque la différence entre a et b diminue, à un moment donné, le milieu de [ a , b ] sera numériquement identique à (avec une précision en virgule flottante de) a ou b ..

Algorithme

La méthode peut être écrite en pseudo-code comme suit :

INPUT: Function f, 
       endpoint values a, b, 
       tolerance TOL, 
       maximum iterations NMAX
CONDITIONS: a < b, 
            either f(a) < 0 and f(b) > 0 or f(a) > 0 and f(b) < 0
OUTPUT: value which differs from a root of f(x) = 0 by less than TOL
 
N ← 1
while N ≤ NMAX do // limit iterations to prevent infinite loop
    c ← (a + b)/2 // new midpoint
    if f(c) = 0 or (b – a)/2 < TOL then // solution found
        Output(c)
        Stop
    end if
    N ← N + 1 // increment step counter
    if sign(f(c)) = sign(f(a)) then a ← c else b ← c // new interval
end while
Output("Method failed.") // max number of steps exceeded

Exemple : Trouver la racine d'un polynôme

Supposons que la méthode de la bissection soit utilisée pour trouver une racine du polynôme

{\style d'affichage f(x)=x^{3}-x-2\,.}

Premièrement, deux nombres et doivent être trouvés tels que et ont des signes opposés. Pour la fonction ci-dessus, et satisfaire à ce critère, comme ${\style d'affichage a}$ ${\style d'affichage b}$ ${\style d'affichage f(a)}$ ${\style d'affichage f(b)}$ ${\style d'affichage a=1}$ ${\style d'affichage b=2}$

f(1)=(1)^{3}-(1)-2=-2

et

f(2)=(2)^{3}-(2)-2=+4\,.

Parce que la fonction est continue, il doit y avoir une racine dans l'intervalle [1, 2].

Dans la première itération, les points d'extrémité de l'intervalle qui encadre la racine sont et , donc le point médian est ${\style d'affichage a_{1}=1}$ ${\style d'affichage b_{1}=2}$

c_{1}={\frac {2}}=1.5

La valeur de la fonction au milieu est . Parce que est négatif, est remplacé par pour la prochaine itération pour s'assurer que et ont des signes opposés. Au fur et à mesure que cela continue, l'intervalle entre et deviendra de plus en plus petit, convergeant vers la racine de la fonction. Voyez cela se produire dans le tableau ci-dessous. $f(c_{1})=(1.5)^{3}-(1.5)-2=-0.125$ ${\style d'affichage f(c_{1})}$ ${\style d'affichage a=1}$ ${\style d'affichage a=1.5}$ ${\style d'affichage f(a)}$ ${\style d'affichage f(b)}$ ${\style d'affichage a}$ ${\style d'affichage b}$

Itération	${\style d'affichage a_{n}}$	${\style d'affichage b_{n}}$	${\style d'affichage c_{n}}$	${\style d'affichage f(c_{n})}$
1	1	2	1.5	−0.125
2	1.5	2	1,75	1.6093750
3	1.5	1,75	1,625	0,6660156
4	1.5	1,625	1.5625	0,2521973
5	1.5	1.5625	1.5312500	0,0591125
6	1.5	1.5312500	1.5156250	-0,0340538
7	1.5156250	1.5312500	1.5234375	0.0122504
8	1.5156250	1.5234375	1.5195313	−0,0109712
9	1.5195313	1.5234375	1.5214844	0,0006222
dix	1.5195313	1.5214844	1.5205078	−0,0051789
11	1.5205078	1.5214844	1.5209961	−0.0022794
12	1.5209961	1.5214844	1.5212402	-0,0008289
13	1.5212402	1.5214844	1.5213623	−0.0001034
14	1.5213623	1.5214844	1.5214233	0,0002594
15	1.5213623	1.5214233	1.5213928	0,0000780

Après 13 itérations, il devient évident qu'il y a une convergence vers environ 1,521 : une racine pour le polynôme.

Une analyse

La méthode est garantie de converger vers une racine de f si f est une fonction continue sur l'intervalle [ a , b ] et f ( a ) et f ( b ) ont des signes opposés. L' erreur absolue est réduite de moitié à chaque étape de sorte que la méthode converge linéairement . Plus précisément, si c ₁ =a + b/2est le milieu de l'intervalle initial, et c _n est le milieu de l'intervalle dans la n ième étape, alors la différence entre c _n et une solution c est bornée par

|c_{n}-c|\leq {\frac {|ba|}{2^{n}}}.

Cette formule peut être utilisée pour déterminer, à l'avance, une borne supérieure sur le nombre d'itérations dont la méthode de bissection a besoin pour converger vers une racine avec une certaine tolérance. Le nombre n d'itérations nécessaires pour atteindre une tolérance requise (c'est-à-dire une erreur garantie d'être au plus ε), est borné par

n\leq n_{1/2}\equiv \left\lceil \log _{2}\left({\frac {\epsilon _{0}}{\epsilon }}\right)\right\rceil ,

où la taille de parenthèse initiale et la taille de parenthèse requise La principale motivation pour utiliser la méthode de bissection est que sur l'ensemble des fonctions continues, aucune autre méthode ne peut garantir de produire une estimation c _n à la solution c qui dans le pire des cas a une valeur absolue erreur avec moins de n _1/2 itérations. Ceci est également vrai sous plusieurs hypothèses communes sur la fonction f et le comportement de la fonction au voisinage de la racine. $\epsilon _{0}=|ba|$ $\epsilon \leq \epsilon _{0}.$ ${\style d'affichage \epsilon }$

Cependant, bien que la méthode de bissection soit optimale en ce qui concerne les performances dans le pire des cas sous des critères d'erreur absolue, elle est sous-optimale par rapport aux performances moyennes sous les hypothèses standard ainsi qu'aux performances asymptotiques . Alternatives populaires à la méthode bissectrice, comme la méthode de la sécante , la méthode de Ridders ou la méthode de Brent (entre autres), généralement de meilleurs résultats car ils Compromis pire performance de cas pour obtenir une meilleure commandes de convergence à la racine. De plus, une amélioration stricte de la méthode de bissection peut être obtenue avec un ordre de convergence plus élevé sans compromettre les performances dans le pire des cas avec la méthode ITP .

Voir également

Algorithme de recherche binaire
Algorithme de Lehmer–Schur , généralisation de la méthode de la bissection dans le plan complexe
Intervalles imbriqués

Les références

Fardeau, Richard L.; Faires, J. Douglas (1985), "2.1 L'algorithme de bissection", Analyse numérique (3e éd.), PWS Publishers, ISBN 0-87150-857-5

Lectures complémentaires

Corliss, George (1977), « Quelle racine l'algorithme de bissection trouve-t-il ? », SIAM Review , 19 (2) : 325-327, doi : 10.1137/1019044 , ISSN 1095-7200
Kaw, Autar ; Kalu, Egwu (2008), Méthodes numériques avec applications (1ère éd.), archivé à partir de l'original le 2009-04-13

Liens externes

Weisstein, Eric W. "Bisection" . MathWorld .
Notes de méthode de bissection , PPT, Mathcad, Maple, Matlab, Mathematica du Holistic Numerical Methods Institute

Languages

In other projects