Metoda połowienia (bisekcji) — szukanie miejsc zerowych funkcji

Po co się tego uczymy?

To ta sama strategia "dziel na pół", którą poznałeś przy wyszukiwaniu binarnym — tylko zastosowana do zupełnie innego problemu: znajdowania rozwiązań równań, których nie da się łatwo policzyć wzorem. To pokazuje, jak JEDNA uniwersalna idea algorytmiczna działa w wielu różnych kontekstach.

Teoria

Metoda połowienia (ang. bisection method) to sposób znajdowania rozwiązania (np. miejsca, w którym funkcja przyjmuje wartość 0) przez: (1) wybranie przedziału [a, b], w którym WIEMY, że rozwiązanie się znajduje; (2) sprawdzenie ŚRODKA, czyli punktu x = (a + b) / 2; (3) sprawdzenie ZNAKU funkcji (czy zmienia się między a i x, czy między x i b); (4) ZAWĘŻENIE przedziału — wybieramy tę połowę, w której funkcja zmienia znak; (5) powtarzanie, aż różnica między a i b będzie bardzo mała (osiągniemy żądaną dokładność).

Kluczowy warunek: funkcja MUSI zmieniać znak w wybranym przedziale (wartość na jednym końcu dodatnia, na drugim ujemna) — inaczej metoda nie zadziała, bo nie ma gwarancji, że miejsce zerowe w ogóle tam jest.

Zalety metody połowienia: prosta do zrozumienia i zaimplementowania, ZAWSZE zbiega do rozwiązania (jeśli założenia są spełnione), nie wymaga znajomości pochodnych (w przeciwieństwie do bardziej zaawansowanych metod numerycznych).

Wady: działa TYLKO, gdy funkcja zmienia znak w przedziale, działa stosunkowo POWOLI (dzieli na pół w każdym kroku, więc dokładność rośnie liniowo z liczbą kroków), nie nadaje się do znajdowania WIELU miejsc zerowych naraz.

Zastosowania: znajdowanie miejsc zerowych funkcji, rozwiązywanie równań nieliniowych, szukanie punktu przecięcia wykresów, obliczanie kolizji w grach/grafice, znajdowanie wartości równowagi w fizyce i ekonomii.

Porównanie ze strategiami z innych lekcji tego działu: rekursja rozwiązuje problem przez powtarzanie samej siebie ("zrób to samo, tylko prościej"), programowanie dynamiczne zapamiętuje wcześniejsze wyniki ("nie licz tego dwa razy"), podejście zachłanne zawsze wybiera najlepszy krok TERAZ ("weź to, co się najbardziej opłaca"), a metoda połowienia dzieli problem na pół, aż do celu ("zawężaj obszar poszukiwań krok po kroku").

Schemat

SCHEMAT DZIAŁANIA:
START
  ↓
Wybierz przedział [a, b]
  ↓
Policz środek x = (a+b)/2
  ↓
Sprawdź znak funkcji
  ↓
Wybierz połowę z miejscem zerowym
  ↓
Zawęź przedział
  ↓
Jeśli dokładność wystarczająca → STOP

PRZYKŁAD - pierwiastek z 2 (x² - 2 = 0):
Przedział: [1, 2]      f(1) = -1     f(2) = +2
Środek: 1.5   → f(1.5) = 0.25 (dodatnia)   → nowy przedział [1, 1.5]
Środek: 1.25  → f(1.25) = -0.4375 (ujemna) → nowy przedział [1.25, 1.5]
Środek: 1.375 → f(1.375) = -0.1093 ...     → coraz węższy przedział
...aż dokładność 0.0001 → wynik ≈ 1.41421509

Przykład z życia

Zgubiłeś klucz w mieszkaniu i nie wiesz, w którym pokoju — zamiast szukać na oślep, dzielisz mieszkanie na pół, sprawdzasz jedną część, a potem dzielisz wybraną połowę dalej, aż znajdziesz klucz. To DOKŁADNIE ta sama strategia co metoda bisekcji, tylko zamiast "miejsca, gdzie funkcja = 0" szukasz "pokoju, gdzie jest klucz".

bisekcja.py

def f(x):
    return x**2 - 2

def bisekcja(a, b, dokladnosc):
    if f(a) * f(b) > 0:
        print("Brak miejsca zerowego w tym przedziale!")
        return None

    while (b - a) > dokladnosc:
        x = (a + b) / 2
        if f(a) * f(x) < 0:
            b = x
        else:
            a = x
    return (a + b) / 2

wynik = bisekcja(1, 2, 0.0001)
print("Pierwiastek z 2 ≈", wynik)
# Wynik: Pierwiastek z 2 ≈ 1.414215087890625

Komentarz i wyjaśnienie kodu

f(a) * f(b) > 0 to sprytny sposób sprawdzenia, czy funkcja NIE zmienia znaku w przedziale — jeśli obie wartości mają TEN SAM znak (obie dodatnie albo obie ujemne), ich iloczyn jest dodatni, co oznacza brak gwarancji miejsca zerowego.

Warunek if f(a) * f(x) < 0 sprawdza, czy miejsce zerowe leży MIĘDZY a i x (różne znaki → iloczyn ujemny) — jeśli tak, zawężamy przedział do [a, x] (przesuwając b = x), w przeciwnym razie do [x, b] (przesuwając a = x).

Pętla while (b - a) > dokladnosc kończy się, gdy przedział jest już wystarczająco WĄSKI — im mniejsza wartość dokladnosc, tym więcej iteracji potrzeba, ale wynik jest precyzyjniejszy.

Ćwiczenie samodzielne

Uruchom program dla różnych wartości dokladnosc (np. 0.1, 0.001, 0.0001) i zaobserwuj, jak zmienia się wynik i (jeśli dodasz licznik) liczba potrzebnych iteracji.

Zadania do pracy własnej

Znajdź pierwiastek z 3, używając funkcji x**2 - 3 i przedziału [1, 2]. Ustaw dokładność 0.0001 i sprawdź, czy wynik zgadza się z kalkulatorem.
Znajdź miejsce zerowe funkcji x**3 - 4*x + 1. Dobierz przedział samodzielnie (spróbuj np. [-3, 3]) — pamiętaj, że funkcja musi zmieniać znak na końcach przedziału.
Zmodyfikuj program tak, żeby wypisywał NUMER KROKU i DŁUGOŚĆ przedziału przy każdej iteracji. Obserwuj, jak szybko przedział się zawęża — po ilu krokach osiągana jest dokładność 0.0001, zaczynając od przedziału [1, 2]?

Typowe błędy

Wybór przedziału, w którym funkcja NIE zmienia znaku — metoda bisekcji zakłada, że f(a) i f(b) mają różne znaki; jeśli tak nie jest, algorytm nie znajdzie poprawnego wyniku (dlatego kod sprawdza to na wstępie i wypisuje ostrzeżenie).

Zbyt mała wartość dokladnosc przy funkcjach o bardzo płaskim przebiegu w pobliżu miejsca zerowego — może prowadzić do bardzo dużej liczby iteracji; w praktyce dodaje się też limit maksymalnej liczby kroków.

Mylenie metody bisekcji z wyszukiwaniem binarnym — obie stosują tę samą strategię "dziel na pół", ale wyszukiwanie binarne działa na SKOŃCZONEJ, POSORTOWANEJ liście danych, a bisekcja na CIĄGŁEJ funkcji matematycznej.

Nawiązanie do egzaminu zawodowego

Metoda bisekcji to kolejny (obok wyszukiwania binarnego) przykład strategii "dziel na pół", która pojawia się na maturze rozszerzonej w kontekście metod numerycznych. W kolejnej lekcji poznasz "szybkie potęgowanie" — jeszcze inne zastosowanie podobnej idei dzielenia problemu, tym razem do przyspieszenia obliczeń potęg.