Metoda de bisecție - Bisection method

Câțiva pași ai metodei de bisecție aplicate în domeniul de pornire [a ₁ ; b ₁ ]. Punctul roșu mai mare este rădăcina funcției.

În matematică , metoda bisecției este o metodă de găsire a rădăcinilor care se aplică oricărei funcții continue pentru care se cunosc două valori cu semne opuse. Metoda constă în împărțirea repetată a intervalului definit de aceste valori și apoi selectarea subintervalului în care funcția schimbă semnul și, prin urmare, trebuie să conțină o rădăcină . Este o metodă foarte simplă și robustă, dar este și relativ lentă. Din această cauză, este adesea folosit pentru a obține o aproximare aproximativă la o soluție care este apoi utilizată ca punct de plecare pentru metode care converg mai rapid. Metoda se mai numește metoda de înjumătățire a intervalului , metoda de căutare binară sau metoda dihotomiei .

Pentru polinoame , există metode mai elaborate pentru testarea existenței unei rădăcină într - un interval ( regula semnelor lui Descartes , teorema lui Sturm , teorema lui Budan ). Permit extinderea metodei de bisecție în algoritmi eficienți pentru găsirea tuturor rădăcinilor reale ale unui polinom; vezi Izolarea rădăcinii reale .

Metoda

Metoda este aplicabilă pentru rezolvarea numerică a ecuației f ( x ) = 0 pentru variabila reală x , unde f este o funcție continuă definită pe un interval [ a , b ] și unde f ( a ) și f ( b ) au semne opuse . În acest caz , a și b se spune bracketing o rădăcină deoarece, prin teorema valoare intermediară , funcția continuă f trebuie să aibă cel puțin o rădăcină în intervalul ( a , b ).

La fiecare pas, metoda împarte intervalul în două părți / jumătăți calculând punctul mediu c = ( a + b ) / 2 al intervalului și valoarea funcției f ( c ) în acel punct. Cu excepția cazului în care c este el însuși o rădăcină (ceea ce este foarte puțin probabil, dar posibil), există acum doar două posibilități: fie f ( a ) și f ( c ) au semne opuse și paranteze o rădăcină, fie f ( c ) și f ( b ) au semne opuse și paranteze o rădăcină. Metoda selectează subintervalul care este garantat a fi o paranteză ca noul interval care va fi utilizat în pasul următor. În acest fel, un interval care conține un zero de f este redus în lățime cu 50% la fiecare pas. Procesul este continuat până când intervalul este suficient de mic.

În mod explicit, dacă f ( a ) și f ( c ) au semne opuse, atunci metoda setează c ca nouă valoare pentru b , iar dacă f ( b ) și f ( c ) au semne opuse atunci metoda setează c ca nou a . (Dacă f ( c ) = 0 atunci c poate fi luat ca soluție și procesul se oprește.) În ambele cazuri, noile f ( a ) și f ( b ) au semne opuse, deci metoda este aplicabilă acestui interval mai mic .

Sarcini de iterație

Intrarea pentru metodă este o funcție continuă f , un interval [ a , b ] și valorile funcției f ( a ) și f ( b ). Valorile funcției sunt de semn opus (există cel puțin o trecere zero în interval). Fiecare iterație efectuează acești pași:

Calculați c , punctul de mijloc al intervalului, c = a + b/2.
Calculați valoarea funcției la punctul mediu, f ( c ).
Dacă convergența este satisfăcătoare (adică c - a este suficient de mică sau | f ( c ) | este suficient de mică), returnați c și opriți iterarea.
Examinați semnul f ( c ) și înlocuiți fie ( a , f ( a )), fie ( b , f ( b )) cu ( c , f ( c )), astfel încât să existe o trecere zero în noul interval.

Atunci când implementați metoda pe un computer, pot apărea probleme cu precizie finită, deci există adesea teste de convergență suplimentare sau limite la numărul de iterații. Deși f este continuu, precizia finită poate împiedica o valoare a funcției să fie vreodată zero. De exemplu, considerați $f (x) = x - π$ ; nu va exista niciodată o reprezentare finită a lui x care să dea zero. În plus, diferența dintre a și b este limitată de precizia în virgulă mobilă; adică, ca diferență între a și b scade, la un moment dat punctul de mijloc al [ a , b ] va fi identic numeric ( până la virgulă mobilă de precizie) , fie a sau b ..

Algoritm

Metoda poate fi scrisă în pseudocod după cum urmează:

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

Exemplu: Găsirea rădăcinii unui polinom

Să presupunem că metoda de bisecție este utilizată pentru a găsi o rădăcină a polinomului

{\ displaystyle f (x) = x ^ {3} -x-2 \ ,.}

În primul rând, două numere și trebuie găsite astfel încât și au semne opuse. Pentru funcția de mai sus și îndepliniți acest criteriu, ca ${\ displaystyle a}$ ${\ displaystyle b}$ ${\ displaystyle f (a)}$ ${\ displaystyle f (b)}$ ${\ displaystyle a = 1}$ ${\ displaystyle b = 2}$

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

și

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

Deoarece funcția este continuă, trebuie să existe o rădăcină în intervalul [1, 2].

În prima iterație, punctele finale ale intervalului care paranteze rădăcina sunt și , deci punctul de mijloc este ${\ displaystyle a_ {1} = 1}$ ${\ displaystyle b_ {1} = 2}$

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

Valoarea funcției la punctul mediu este . Deoarece este negativ, este înlocuit cu pentru următoarea iterație pentru a se asigura că și au semne opuse. Pe măsură ce acest lucru continuă, intervalul dintre și va deveni din ce în ce mai mic, convergând la rădăcina funcției. Vedeți acest lucru în tabelul de mai jos. ${\ displaystyle f (c_ {1}) = (1.5) ^ {3} - (1.5) -2 = -0.125}$ ${\ displaystyle f (c_ {1})}$ ${\ displaystyle a = 1}$ ${\ displaystyle a = 1.5}$ ${\ displaystyle f (a)}$ ${\ displaystyle f (b)}$ ${\ displaystyle a}$ ${\ displaystyle b}$

Repetare	${\ displaystyle a_ {n}}$	${\ displaystyle b_ {n}}$	${\ displaystyle c_ {n}}$	${\ displaystyle 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
10	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

După 13 iterații, devine evident că există o convergență la aproximativ 1.521: o rădăcină pentru polinom.

Analiză

Se garantează că metoda converge la o rădăcină a lui f dacă f este o funcție continuă pe intervalul [ a , b ] și f ( a ) și f ( b ) au semne opuse. Eroarea absolută este înjumătățită la fiecare pas , astfel metoda converge liniar . Mai exact, dacă c ₁ =a + b/2este punctul mediu al intervalului inițial, iar c _n este punctul mediu al intervalului din etapa a n- a, atunci diferența dintre c _n și o soluție c este mărginită de

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

Această formulă poate fi utilizată pentru a determina, în prealabil, o limită superioară a numărului de iterații de care metoda bisecării are nevoie pentru a converge la o rădăcină într-o anumită toleranță. Numărul n de iterații necesare pentru a obține o toleranță necesară ε (adică o eroare garantată a fi cel mult ε), este delimitat de

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

unde dimensiunea paranteză inițială și dimensiunea paranteză necesară Principala motivație pentru utilizarea metodei de bisecție este că peste setul de funcții continue, nicio altă metodă nu poate garanta producerea unei estimări c _n a soluției c care în cel mai rău caz are o valoare absolută eroare cu mai puțin de n _1/2 iterații. Acest lucru este valabil și în cazul mai multor ipoteze comune despre funcția f și comportamentul funcției în vecinătatea rădăcinii. ${\ displaystyle \ epsilon _ {0} = | ba |}$ ${\ displaystyle \ epsilon \ leq \ epsilon _ {0}.}$ ${\ displaystyle \ epsilon}$

Cu toate acestea, în ciuda faptului că metoda de bisecție este optimă în ceea ce privește performanța în cel mai rău caz în conformitate cu criteriile de eroare absolută, este sub-optimă în ceea ce privește performanța medie în ipotezele standard, precum și performanța asimptotică . Alternativele populare la metoda de bisecție, cum ar fi metoda secantă , metoda Ridders sau metoda lui Brent (printre altele), au de obicei performanțe mai bune, deoarece schimbă performanța în cel mai rău caz pentru a obține ordine mai mari de convergență la rădăcină. Și, o îmbunătățire strictă a metodei de bisecție poate fi realizată cu un ordin de convergență mai mare, fără a face schimb de performanțe în cel mai rău caz cu metoda ITP .

Vezi si

Algoritm de căutare binară
Algoritm Lehmer – Schur , generalizarea metodei bisecției în planul complex
Intervalele imbricate

Referințe

Burden, Richard L .; Faires, J. Douglas (1985), "2.1 Algoritmul de bisecție", Analiză numerică (ediția a 3-a), PWS Publishers, ISBN 0-87150-857-5

Lecturi suplimentare

Corliss, George (1977), "Care rădăcină găsește algoritmul de bisecție?", SIAM Review , 19 (2): 325-327, doi : 10.1137 / 1019044 , ISSN 1095-7200
Kaw, Autar; Kalu, Egwu (2008), Metode numerice cu aplicații (prima ediție), arhivat din original la 13.04.2009

linkuri externe

Weisstein, Eric W. „Bisecție” . MathWorld .
Note despre metodele de bisecție , PPT, Mathcad, Maple, Matlab, Mathematica de la Holistic Numerical Methods Institute

Languages

In other projects