Metoda Bisekcji - połowienia - znajdowania pierwiastków równań bazuje na twierdzeniu Darboux "o przyjmowaniu wartości pośrednich".
Jeśli funkcja
\( f(x) \) jest funkcją ciągłą w przedziale
\( [a,\ \ b] \) taką, że w końcach tego przedziału przyjmuje wartości
różnych znaków,
\( f(a)\cdot f(b) < 0,\) to istnieje przynajmniej jeden punkt
\( \alpha \in [a, \ \ b]\), taki, że
\( f(\alpha) = 0. \)
Zakładamy, że funkcja posiada dokładnie jedno miejsce zerowe
\( \alpha \) w rozpatrywanym przedziale
\( [a, \ \ b]. \)
Metoda bisekcji polega na połowieniu przedziału
\( [ a,\ \ b ]\) na co raz mniejsze przedziały
\( [a_{n},\ \ b_{n}] \subset [a, \ \ b], n=1,2,.. \)
Na początku wyznaczamy środek
\( c = \frac{a+b}{2} \) każdego przedziału , później obliczamy znak iloczynu
\( f(c)\cdot f(b). \)
Jeśli iloczyn jest ujemny, oznacza to, że poszukiwany pierwiastek znajduje się w przedziale
\( [c, \ \ d],\) jeśli zaś dodatni - w przedziale
\( [a, \ \ c]. \)
Następnie rozpatrujemy nowy przedział zawierający
\( \alpha. \)
Proces połowienia kontynuujemy dopóty, dopóki różnica
\( |a_{n} - b_{n}| < \varepsilon, \)
gdzie
\( \varepsilon \) jest wartością przyjętej dokładności (tolerancji) wyniku.
Innym stop- kryterium, które możemy przyjąć, jest wartość błędu wględnego
\( \frac{|a_{n}-b_{n}|}{|a_{n}|}< \varepsilon \)
lub spełniona nierówność
\( |f(a_{n})| < \varepsilon.\)
Program Metody Bisekcji w OCTAVE
Kod: Zaznacz cały
function bisect(f,a,b,tol,n)
a0=a;
b0=b;
iter=0;
u=feval(f,a);
v=feval(f,b);
c=(a+b)*0.5;
err=abs(b-a)*0.5;
disp('__________________________________________________________________ ')
disp(' iter a b c f(c) |b-a|/2 ')
disp('___________________________________________________________________')
fprintf('\n')
if (u*v<=0)
while (err>tol)&(iter<=n)
w=feval(f,c);
fprintf('%2.0f %10.4f %10.4f %12.6f %10.6f %10.6f\n',iter,a,b,c,w,err)
if (w*u<0)
b=c;
v=w;
end;
if (w*u>0)
a=c;
u=w;
end;
iter=iter+1;
c=(a+b)*0.5;
err=abs(b-a)*0.5;
end;
if (iter>n)
disp('Metoda nie jest zbieżna')
end;
else
disp('Metoda nie może by stosowana f(a)f(b)>0')
end;
Przykładowa funkcja:
Przykładowe wywołanie programu:
Wyniki:
Kod: Zaznacz cały
______________________________________________________________
iter a b c f(c) |b-a|/2
______________________________________________________________
0 1.0000 2.0000 1.500000 0.125000 0.500000
1 1.0000 1.5000 1.250000 -0.609375 0.250000
2 1.2500 1.5000 1.375000 -0.291016 0.125000
3 1.3750 1.5000 1.567500 -0.095947 0.062500
4 1.4375 1.5000 1.568750 0.011200 0.031250
5 1.4375 1.4688 1.539250 -0.043194 0.015625
6 1.4531 1.4688 1.539038 -0.016203 0.007812
7 1.4609 1.4688 1.534844 -0.002554 0.003906
8 1.4648 1.4688 1.533218 0.004310 0.001953
9 1.4648 1.4668 1.533210 0.000875 0.000977
10 1.4648 1.4658 1.533209 -0.000840 0.000488
11 1.4653 1.4658 1.533205 0.000017 0.000244
12 1.4653 1.4656 1.533201 -0.000001 0.000122
Dokładność metody bisekcji .
Jeśli funkcja
\( f \) jest ciągła w przedziale
\( [a,b] \) i taka, że
\( f(a)\cdot f(b) <0, \) to
\( n-\) ty krok
metody bisekcji przybliża poszukiwany pierwiastek równania z błędem nie mniejszym niż
\( \frac{(b-a)}{2^{n+1}}.\)
Dowód
Niech
\( [a_{0}, b_{0}] \) bedzie wyjściowym przedziałem zawierającym miejsce zerowe funkcji
\( f, \ \ \alpha. \)
Definiujemy środek przedziału
\( [a_{0}, b_{0}]. \) to jest punkt
\( c_{0} = \frac{b_{0}+c_{0}}{2} \) i
\( \alpha \in [a_{0},b_{0}]\)
Stąd
\( |\alpha-c_{0}| < (b_{1}-a_{1}) = \frac{b_{0}-a_{0}}{2}. \)
gdzie punkty
\( a_{1}, b_{1} \) są końcami nowego przedziału zawierającego
\( \alpha. \)
Jeśli przez
\( c_{n} \) oznaczymy wartość
\( c \) w
\( n- \) tej iteracji, to
\( |\alpha - c_{n}| < |b_{n+1}- a_{n+1}| =\frac{b_{0}-a_{0}}{2^{n+1}}, \ \ n=0,1,2,...\)
Na przykład dla Pani wielomianu
\( f(x) = x^3 -3x+1 \)
przyjęliśmy dokładność
\( tol = 10^{-4} \)
i otrzymaliśmy
\( |\alpha - c_{n}| \leq \frac{b-a}{2^{n+1}} = \frac{2-1}{2^{n+1}} < 10^{-4} \)
\( -(n+1) \log(2)< -4 \)
\( n > \frac{4}{\log(2)} -1 \approx 12 \) iteracji.