Metoda bisekcji – co to jest, algorytm i przykład

Co to jest metoda bisekcji?

Metoda bisekcji jest jednym z podstawowych rozwiązań numerycznych służących do znajdowania pierwiastka równania wielomianowego. Obejmuje ona przedział, w którym leży pierwiastek równania, i dzieli je na połowy w każdej iteracji, aż znajdzie pierwiastek. Dlatego metodę bisekcji nazywa się również metodą bracketingu.

Jednakże, ponieważ mechanizm działania jest podobny do algorytmu wyszukiwania binarnego, metoda bisekcji jest również znana jako metoda wyszukiwania binarnego, metoda halvingu lub metoda dychotomii. Opiera się ona przede wszystkim na twierdzeniu o wartości pośredniej.

Znajdowanie pierwiastków równań

W tym przykładzie rozważymy tylko równania z jedną zmienną niezależną. Może być liniowy lub nieliniowy. Równania liniowe służą do przedstawienia wykresu linii prostej, natomiast równania nieliniowe służą do przedstawienia krzywych.

Pierwiastek równania oznacza wartość zmiennej niezależnej spełniającej równanie. Na przykład: pierwiastek równania f(x)= 4-x² = 0 równa się 2, ponieważ f(2) = 4-2² = 0.

Rozważmy f(x) jako rzeczywistą funkcję ciągłą. Zgodnie z twierdzeniem o wartości pośredniej równanie f(x)=0 ma co najmniej jeden pierwiastek pomiędzy a i b, jeśli f(a)f(b) < 0. Funkcja f(x) ma pierwiastek „c”, pomiędzy A i B.

Graficzne przedstawienie metody bisekcji

Poniższy wykres przedstawia mechanizm działania metody bisekcji. Z wykresu widać, że pierwiastek równania jest zaznaczony na czerwono.

Najpierw:

Najpierw przyjęliśmy dwa wstępne przypuszczenia, a₁ oraz b_1, dla którego f(a₁)pełne wyżywienie₁) < 0. Zgodnie z twierdzeniem o wartości pośredniej pierwiastek powinien leżeć w [a₁b₁].
Możemy znaleźć środek a₁ oraz b_1,co jest b₂. Zatem początkowy odstęp jest teraz zredukowany do [a₁b₂], ponieważ f(a₁)pełne wyżywienie₂) < 0.
W ten sam sposób odstęp jest zmniejszany, aż do znalezienia przybliżonego rozwiązania.

Algorytm metody Bisekcji

Etapy stosowania algorytmu metody bisekcji do znalezienia pierwiastka równania f(x)=0 są następujące

Krok 1) Wybierz początkowe przypuszczenia a, b i współczynnik tolerancji e

Krok 2) Jeśli f(a)f(b) >=0, to pierwiastek nie leży w tym przedziale. Zatem rozwiązania nie będzie.

Krok 3) Znajdź punkt środkowy, c = (a+b)/2

(i) Jeżeli wartość funkcji punktu środkowego f(c) = 0, to c jest pierwiastkiem. Przejdź do kroku 5.
(ii) Jeśli f(a)f(c) < 0, pierwiastek leży pomiędzy a i c. Następnie ustaw a = a, b = c.
(iii) Inaczej ustaw a = c, b = b.

Krok 4) Jeżeli błąd bezwzględny jest większy niż współczynnik tolerancji lub (ba) > e, przejdź do kroku 3.

Krok 5) Wyświetl c jako przybliżony pierwiastek.

Zobaczmy przykład algorytmu metody bisekcji.
Musimy znaleźć pierwiastek następującej funkcji ciągłej, korzystając ze wzoru metody bisekcji.

fa(x) = x³ - x² + 2

Przykład metody bisekcji

Krok 1) Załóżmy,

         a = -10,
         b = 10 i
         e = 1% lub 0.01

Krok 2) Teraz sprawdzimy, czy f(a)f(b) >= 0, czy nie.

         f(a) = f(-10) = (-10)3 – (-10)2 + 2 = -1098
         f(b) = f(10) = (10)3 – (10)2 + 2 = 902
         f(a)f(b) = f(-10)f(10) = (-1098)(902) < 0

Zatem pierwiastek powyższej funkcji leży w tym przedziale [-10, 10].

Krok 3) Następnie najpierw zostanie obliczony punkt środkowy c.

Teraz należy sprawdzić następujące warunki:

(i) czy f(c) = 0:
f(c) = f(0) = (0)3 – (0)2 + 2 = 2 ≠ 0

(ii) jeśli f(a)f(c) < 0:
f(c)f(a) = 2*(-1098) < 0

Warunek jest spełniony. W następnej iteracji wartości będą następujące:

a = a = -10
b = do = 0

Krok 4) Ponieważ (ba) = (0-(-10)) = 10>0.05, proces zostanie powtórzony. Kolejne iteracje przedstawiono w tabeli.

Iteracja	a	b	c	ba	f(c)
1	-10	0	0	10	2
2	-5	0	-5	5	-148
3	-2.5	0	-2.5	2.5	-19.875
4	-1.25	0	-1.25	1.25	-1.52562
5	-1.25	-0.625	-0.625	0.625	1.36523
6	-1.25	-0.9375	-0.9375	0.3125	0.297119
7	-1.09375	-0.9375	-1.09375	0.15625	-0.50473
8	-1.01562	-0.9375	-1.01562	0.078125	-0.0791054
9	-1.01562	-0.976562	-0.976562	0.0390625	0.115003
10	-1.01562	-0.996094	-0.996094	0.0195312	0.0194703
11	-1.00586	-0.996094	-1.00586	0.00976562	-0.0294344

Krok 5) W jedenastej iteracji warunek z kroku 11 będzie fałszywy. Zatem pierwiastkiem tego równania jest -4.

Schemat logiczny metody bisekcji

Pseudo kod

Start
Set a, b, e
if f(a)*f(b) >=0 
	Output("Root does not exist in this interval")
	Stop
while (b-a)>e do   
	c ← (a + b)/2    
	if f(c) = 0
        	break    
	end if 
	if f(c)*f(a) < 0 then
      	b ← c    
	else        
		a ← c
end while
Output(c)
Stop

Przykład metody bisekcji w C/C++

Wejście:

#include<bits/stdc++.h>
using namespace std;
#define Error 0.01
double value(double x)
{
	return x*x*x - x*x + 2;
}
void bisection_method(double a, double b)
{
	if (value(a) * value(b) >= 0)
	{
		cout << "The root does not lie in this interval\n";
		return;
	}
	double c = a;
	while ((b-a) >= Error)
	{
		c = (a+b)/2;
		if (value(c) == 0.0)
			break;
		else if (value(c)*value(a) < 0)
			b = c;
		else
			a = c;
	}
	cout << "The root is :" << c;
}
int main()
{
	double a =-10 , b = 10;
	bisection_method(a, b);
	return 0;
}

Wyjście:

The root is :-1.00586

Przykład metody bisekcji w Python