Metoda Połowienia (Bisekcja) – Wyszukiwanie binarne w informatyce

W informatyce wykorzystuje się wiele rozwiązań pochodzących bezpośrednio z matematyki, w tym chodzi oczywiście o metodę połowienia. Poniższy artykuł przedstawi Ci zasadę działania bisekcji, praktyczny przykład oraz implementacje w różnych językach.

Co to jest metoda połowienia (bisekcja)?

Metoda połowienia (nazywana też bisekcją lub wyszukiwaniem binarnym) to sposób wyznaczania miejsca zerowego funkcji. Jednak istotne jest spełnienie trzech wymogów:

1. Funkcja w danym zakresie jest ciągła – wartości funkcji nie wykonują nagłych “skoków”, czyli nie istnieją przerwy w kolejnych wartościach,
2. Funkcja jest określona – dla każdej wartości argumentu x, z konkretnego przedziału można obliczyć wartość funkcji,
3. Wartości funkcji dla liczb znajdujących się na końcach przedziału mają różne znaki.

Jej zastosowanie jest szerokie, chodzi o dziedziny takie jak matematyka, fizyka, inżynieria, ekonomia, a także programowanie komputerowe.

Zasada działania metody połowienia jest prosta, należy zakres danej funkcji podzielić na dwa (np. od 1 do 10 na 2, to 5) i sprawdzić, czy dla środkowej wartości (w tym przypadku 5) funkcja zwraca zero (czyli szukane miejsce zerowe), a jeśli nie to czy jest większa czy mniejsza od poszukiwanej. Następnie szuka się dalej poprzez dzielenie zakresu na pół (stąd nazwa) i sprawdzanie kolejnych wartości. Te kroki powtarza się cały czas (metoda iteracyjna) dopóki nie znajdzie się poszukiwanego elementu lub nie osiągnie się danego przybliżenia.

Głównym celem tej techniki jest znalezienie miejsca zerowego funkcji, czyli punktu, w którym wartość funkcji wynosi zero. Załóżmy, że mamy funkcję ciągłą f(x) na danym przedziale [a, b], gdzie na krańcach tego przedziału funkcja przyjmuje różne znaki, czyli f(a) * f(b) < 0. Wtedy istnieje co najmniej jedno miejsce zerowe funkcji f(x) w przedziale [a, b].

Warto zauważyć, że w dalszej części artykułu stosuje się również zmienną epsilon, która wskazuje na to, jak dokładne ma być wyszukiwanie. Im dokładniejsze jest wyszukiwanie binarne, tym więcej iteracji trwa, także dla zmniejszenia ich ilości, stosuje się określone przybliżenie, czyli tzw. błąd obliczeniowy. Przykładowo gdyby szukana wartość to byłaby 1,414213562, ale w wyniku algorytmu uzyska się liczbę 1,414 to epsilon w tym przypadku wynosi 1,414213562 – 1,414 = 0,000213562. Jest to więc różnica między znalezioną wartością, a tą której się szuka.

Metoda połowienia okazuje się szczególnie użyteczna w przypadkach, gdy funkcja jest zbyt skomplikowana, by można było obliczyć jej miejsca zerowe w standardowy sposób.

Dodatkową zaletą metody połowienia jest jej szybka zbieżność dla wielu funkcji. Warto jednak pamiętać, że metoda ta może być bardziej czasochłonna niż niektóre bardziej zaawansowane metody, zwłaszcza gdy wymagana jest bardzo wysoka dokładność.

Na czym polega metoda połowienia – przykład zastosowania

Poniżej przeprowadzę metodę połowienia krok po kroku. Pozwoli Ci to łatwo zrozumieć w jaki sposób należy stosować bisekcję.

Specyfikacja:

f(x) = x2 − 4

a = 1

b = 3

Wybór przedziału początkowego

Konieczne jest wybranie przedziału [a, b], w którym wartości funkcji mają różne znaki, czyli jeden jest na plusie, a drugi na minusie, co można sprawdzić poprzez działanie f(a) * f(b) < 0. Jeśli jedna z wartości funkcji jest na minusie, a druga na plusie, to wynik tego działania będzie mniejszy od zera (na minusie).

Na potrzeby tego przykładu wybrano zakres [1, 3].

Sprawdzenie wartości funkcji na końcach przedziału

Po wybraniu zakresu, konieczne jest sprawdzenie, czy jest odpowiedni do metody bisekcji, a więc czy posiada różne znaki na obu końcach.

f(1) = 1² − 4 = 1 – 4 = −3

f(3) = 3² − 4 = 9 – 4 = 5

Ponieważ f(1) * f(3) < 0, czyli -3 * 5 = -15 co jest oczywiście mniejsze od zera, można przejść do następnego kroku.

Obliczenie środka przedziału

Środek przedziału c (wartość x środka przedziału) uzyskuje się poprzez wzór (a + b )/ 2.

c = (1 + 3) / 2 = 4 / 2 = 2

Sprawdzenie wartości funkcji w punkcie c

W tym momencie należy sprawdzić jaką wartość posiada funkcja w punkcie c, a więc czy jest to miejsce zerowe.

f(2) = 2² − 4 = 0

Ponieważ f(2) = 0, znaleźliśmy dokładnie miejsce zerowe funkcji. Pod spodem znajduje się wykres tej funkcji, który udowadnia skuteczność metody połowienia.

W sytuacji gdy nie znaleziono by jeszcze miejsca zerowego funkcji, należy sprawdzić, czy liczba zwracana przez funkcję dla znalezionej wartości x jest mniejsza od zera. Jeśli tak, to wtedy za zmienną b, podstawia się wartość x, więc zakres to [a, x]. Jeśli jednak liczba jest większa od zera, to za zmienną a, podstawia się wartość x, więc zakres to [x, b]. Następnie ponownie wykonuje się krok 3 (obliczenie środka przedziału) oraz 4 (sprawdzenie wartości funkcji w punkcie c). Następnie powtarza się te kroki cały czas, dopóki nie zostanie znalezione miejsce zerowe lub nie osiągniemy dokładności większej niż określone przybliżenie.

Następnie powtarza się te kroki cały czas, dopóki nie zostanie znalezione miejsce zerowe.

Jak wykorzystać bisekcję – implementacja algorytmu

Poniżej znajdziesz metodę połowienia (bisekcję) w formie pseudokodu, schematu blokowego oraz implementacji w Pythonie, Javie i C++. Ich działanie jest stosunkowo proste.

Iteracyjna metoda połowienia – schemat blokowy i pseudokod

Pamiętaj, aby zawsze zdefiniować funkcję f(x), będącą funkcją matematyczną, której miejsca zerowego szukasz.

Opis iteracyjnej metody połowienia – pseudokod

• 1 linia – Definicja funkcji metodaPolowienia z trzema parametrami: a, b, oraz epsilon. Epsilon jest małą liczbą, która reprezentuje tolerancję, czyli dokładność, z jaką chcemy znaleźć miejsce zerowe funkcji. Określa, jak blisko siebie muszą być wartości a i b, aby zakończyć iteracje. Innymi słowy, epsilon jest maksymalną dopuszczalną różnicą między a i b dla zakończenia algorytmu.
• 2 linia – Warunek sprawdzający, czy iloczyn wartości funkcji w punktach a i b jest większy lub równy 0. Jeśli warunek jest spełniony, oznacza to, że funkcja nie zmienia znaku w przedziale [a,b], co uniemożliwia zastosowanie metody bisekcji.
• 3 linia – Jeśli zastosowanie bisekcji jest niemożliwe zwracany jest komunikat “Niepoprawne argumenty”.
• 4 linia – Pętla dopóki (odpowiednik while), która będzie wykonywać się dopóki różnica między b, a a jest większa niż wartość epsilon. Warunek |b – a| > epsilon gwarantuje, że pętla będzie działać, dopóki długość przedziału [a,b] jest większa niż zadana dokładność epsilon. Zastosowanie znaku | w |b – a|, pozwala zawsze uzyskać wartość dodatnią, nawet jeśli w wyniku odejmowania uzyskano liczbę ujemną (zmienia znak na plus).
• 5 linia – Obliczenie środka przedziału c jako średniej wartości a i b.
• 6 linia – Warunek sprawdzający, czy wartość funkcji w punkcie c jest równa 0. Jeśli warunek jest spełniony, oznacza to, że dokładnie trafiliśmy na miejsce zerowe w punkcie c.
• 7 linia – W takim przypadku (spełniony warunek) zwracamy wartość c.
• 8 linia – Warunek sprawdzający, czy iloczyn wartości funkcji w punktach a i c jest mniejszy niż 0. Jeśli warunek jest spełniony, oznacza to, że miejsce zerowe znajduje się w przedziale [a,c].
• 9 linia – Przy spełnionym warunku przesuwamy prawy koniec przedziału b do punktu c.
• 10 linia – Instrukcja wykonywana w przypadku, gdy iloczyn wartości funkcji w punktach a i c nie jest mniejszy niż 0. Oznacza to, że miejsce zerowe znajduje się w przedziale [c,b].
• 11 linia – W takim przypadku (spełniony warunek) przesuwamy lewy koniec przedziału a do punktu c.
• 12 linia – Po zakończeniu pętli zwracamy średnią wartość a i b jako przybliżenie pierwiastka funkcji w przedziale [a,b].

Iteracyjna metoda połowienia – Python, C++ i Java

Pamiętaj o dokonaniu zmiany w kodzie jeśli chodzi o funkcję matematyczną f(x), na taką, która Cię interesuje. Dzięki temu wyszukiwanie binarne będzie działało prawidłowo w pythonie. javie czy też C++.

Rekurencyjna metoda połowienia – schemat blokowy i pseudokod

Kluczowe jest zdefiniowanie funkcji f(x), dzięki której kod będzie działał prawidłowo.

Opis rekurencyjnej metody połowienia – pseudokod

• 1 linia – Definicja funkcji metodaPolowieniaRekurencyjna z trzema parametrami: a, b, oraz epsilon.
• 2 linia – Warunek sprawdzający, czy iloczyn wartości funkcji w punktach a i b jest większy lub równy 0. Jeśli warunek jest spełniony, oznacza to, że funkcja nie zmienia znaku w przedziale [a,b], co uniemożliwia zastosowanie metody bisekcji.
• 3 linia – Przy spełnionym warunku zwraca komunikat “Niepoprawne argumenty”.
• 4 linia – Warunek sprawdzający, czy różnica między b i a jest mniejsza lub równa epsilon. Jeśli warunek jest spełniony, oznacza to, że przedział [a, b] jest wystarczająco mały i odpowiednio przybliża miejsce zerowe funkcji.
• 5 linia – Po spełnieniu warunku zwraca środek przedziału (a + b) / 2.
• 6 linia – Obliczenie środka przedziału c jako (a + b) / 2.
• 7 linia – Warunek sprawdzający, czy wartość funkcji w punkcie c jest równa 0. Jeśli warunek jest spełniony, oznacza to, że punkt c jest rozwiązaniem równania i zwracamy go jako przybliżone miejsce zerowe.
• 8 linia – Zwraca wartość zmiennej c.
• 9 linia – Warunek sprawdzający, czy iloczyn wartości funkcji w punktach a i c jest mniejszy od 0. Jeśli warunek jest spełniony, oznacza to, że miejsce zerowe znajduje się w przedziale [a, c],
• 10 linia – Po spełnieniu warunku wywołujemy rekurencyjnie metodaPolowieniaRekurencyjna dla przedziału [a, c].
• 11 linia – Wywołanie rekurencyjne metodaPolowieniaRekurencyjna dla przedziału [c, b].

Rekurencyjna metoda połowienia – Python, C++ i Java

Pamiętaj o dokonaniu zmian w kodzie na interesującą Ciebie funkcję.

Metoda połowienia jest niezwykle użytecznym narzędziem w analizie matematycznej i naukach technicznych. Jej prostota i intuicyjność sprawiają, że może być stosowana zarówno przez początkujących, jak i zaawansowanych użytkowników. Metoda połowienia znajduje szerokie zastosowanie w rozwiązywaniu różnych problemów numerycznych, takich jak wyznaczanie pierwiastków funkcji, rozwiązywanie równań nieliniowych czy optymalizacja funkcji.

Warto pamiętać, że metoda połowienia nie zawsze gwarantuje znalezienie dokładnego miejsca zerowego, ale jej wyniki są na tyle precyzyjne, że stanowi ona potężne narzędzie w analizie matematycznej.

Najczęściej zadawane pytania o metodę połowienia