Jeśli funkcja \(\displaystyle{ f(x) }\) jest funkcją ciągłą w przedziale \(\displaystyle{ [a,b] }\) taką, że w końcach tego przedziału przyjmuje wartości
różnych znaków, \(\displaystyle{ f(a)\cdot f(b) < 0,}\) to istnieje przynajmniej jeden punkt \(\displaystyle{ \alpha \in [a,b]}\), taki, że [/latex]
\(\displaystyle{ f(\alpha) = 0. }\)
Zakładamy, że funkcja posiada dokładnie jedno miejsce zerowe \(\displaystyle{ \alpha }\) w rozpatrywanym przedziale \(\displaystyle{ [a, b]. }\)
Metoda bisekcji polega na połowieniu przedziału \(\displaystyle{ [ a, b ]}\) na co raz mniejsze przedziały \(\displaystyle{ [a_{n}, b_{n}] \subset [a,b], n=1,2,.. }\)
Na początku wyznaczamy środek \(\displaystyle{ c = \frac{a+b}{2} }\) każdego przedziału , później obliczamy znak iloczynu \(\displaystyle{ f(c)\cdot f(b). }\)
Jeśli iloczyn jest ujemny, oznacza to, że poszukiwany pierwiastek znajduje się w przedziale \(\displaystyle{ [c, d],}\) jeśli zaś dodatni - w przedziale
\(\displaystyle{ [a,c]. }\)
Następnie rozpatrujemy nowy przedział zawierający latex] \alpha. [/latex]
Proces połowienia kontynuujemy dopóty, dopóki różnica \(\displaystyle{ |a_{n} - b_{n}| < \varepsilon, }\)
gdzie \(\displaystyle{ \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: \(\displaystyle{ \frac{|a_{n}-b_{n}|}{|a_{n}|}< \varepsilon }\)
lub spełniona nierówność:
\(\displaystyle{ |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:
Kod: Zaznacz cały
function f=f1(x)
f=x.^3-x.^2-1;
Przykładowe wywołanie programu:
Kod: Zaznacz cały
>> bisect('f1',1,2,10^(-4),40)
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.437500 -0.095947 0.062500
4 1.4375 1.5000 1.468750 0.011200 0.031250
5 1.4375 1.4688 1.453125 -0.043194 0.015625
6 1.4531 1.4688 1.460938 -0.016203 0.007812
7 1.4609 1.4688 1.464844 -0.002554 0.003906
8 1.4648 1.4688 1.466797 0.004310 0.001953
9 1.4648 1.4668 1.465820 0.000875 0.000977
10 1.4648 1.4658 1.465332 -0.000840 0.000488
11 1.4653 1.4658 1.465576 0.000017 0.000244
12 1.4653 1.4656 1.465454 -0.000411 0.000122
Dokładność metody bisekcji .
Jeśli funkcja \(\displaystyle{ f }\) jest ciągła w przedziale \(\displaystyle{ [a,b] }\) i taka, że \(\displaystyle{ f(a)\cdot f(b) <0, }\) to \(\displaystyle{ n-}\) ty krok
metody bisekcji przybliża poszukiwany pierwiastek równania z błędem nie mniejszym niż \(\displaystyle{ \frac{(b-a)}{2^{n+1}}.}\)
Dowód
Niech \(\displaystyle{ [a_{0}, b_{0}] }\) bedzie wyjściowym przedziałem zawierającym miejsce zerowe funkcji \(\displaystyle{ f, \ \ \alpha. }\)
Definiujemy środek przedziału \(\displaystyle{ [a_{0}, b_{0}] }\) to jest punkt \(\displaystyle{ c_{0} = \frac{b_{0}+c_{0}}{2} }\) i \(\displaystyle{ \alpha \in [a_{0},b_{0}]}\)
Stąd
\(\displaystyle{ |\alpha-c_{0}| < (b_{1}-a_{1}) = \frac{b_{0}-a_{0}}{2}. }\)
gdzie punkty \(\displaystyle{ a_{1}, b_{1} }\) są końcami nowego przedziału zawierającego \(\displaystyle{ \alpha. }\)
Jeśli przez \(\displaystyle{ c_{n} }\) oznaczymy wartość \(\displaystyle{ c }\) w \(\displaystyle{ n- }\) tej iteracji, to
\(\displaystyle{ |\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 wielomianu
\(\displaystyle{ f(x) = x^3 -x^2-1 }\) przyjęliśmy dokładność \(\displaystyle{ tol = 10^{-4} }\) i otrzymaliśmy
\(\displaystyle{ |\alpha - c_{n}| \leq \frac{b-a}{2^{n+1}} = \frac{2-1}{2^{n+1}} < 10^{-4} }\)
\(\displaystyle{ -(n+1) \log(2)< -4 }\)
\(\displaystyle{ n > \frac{4}{\log(2)} -1 \approx 12 }\)iteracji.