1.5.2 Metoda bisekcji

Znaną metodę połowienia do poszukiwania elementu w uporządkowanym ciągu można również użyć do znajdowania miejsca zerowego funkcji w zadanym przedziale.
Dana jest funkcja f(x) oraz końce przedziału domkniętego [a,b].
W tym przedziale chcemy znaleźć punkt c, który jest miejscem zerowym tej funkcji, czyli f(c)=0
Tak postawiony problem ma rozwiązanie, jeśli funkcja f(x) jest ciągła w przedziale [a,b] oraz spełniony jest warunek, że wartości funkcji na końcach przedziału mają przeciwne znaki, tj. f(a) * f(b) <= 0.
Z tego wynika, że wykres funkcji f(x) musi w tym przedziale przynajmniej raz przeciąć oś Ox - ten punkt przecięcia jest właśnie szukanym miejsem zerowym funkcji. Jest to założenie oparte na twierdzeniu Bolzano-Cauchy`ego: Jeżeli funkcja jest ciągła w przedziale domkniętym i na jego końcach przyjmuje wartości różnych znaków, to między punktami przedziału znajduje się co najmniej jeden pierwiastek równania.
Metoda ta zawsze jest konwergentna - zbieżna, co gwarantuje odnalezienie pierwiastka równania, czasem jednak kosztem liczby iteracji.

Ogólny opis metody bisekcji

Użytkownik podaje wartości końców przedziału, w którym spodziewa się znaleźć rozwiązanie. Jego program sprawdza, czy wartości funkcji dla tych krańców są przeciwnego znaku. Jeśli tak tzn, że w tym przedziale na pewno funkcja przecina oś x. Program wg metody bisekcji, dzieli ten przedział na pół i sprawdza, czy środek tego przedziału jest szukanym miejscem zerowym (z założoną dokładnością). Jeśli tak to kończy swoje działanie i zwraca go (ten środek) jako wynik, jeśli nie to wybiera (w zależności od znaku funkcji w połowie przedziału) nowy, pomniejszony o połowę przedział i kontynuuje obliczenia.

Specyfikacja

Dane:

• funkcja f(x) ciągła w przedziale domkniętym [a,b] i spełniająca f(a) * f(b) < 0;
• epsilon - przyjęta dokładność obliczeń (epsilon>0)

Wyniki:

• c przybliżenie zera funkcji f w przedziale [a,b], spełniające warunki:
  | f ( c ) | <= epsilon (założone epsilon powinno być znacząco większe od używanej dokładności liczb rzeczywistych)

Algorytm:

1. Pobierz wartości końców przedziału [a,b]. Sprawdź czy f(a) * f(b) < 0
2. Jeśli f(a) * f(b) < 0, idź do polecenia 3, wpp wróć do polecenia 1.
3. Oblicz c = (a + b) / 2
4. Policz f(c).
5. Jeśli |f(c)| <= epsilon lub |a - b| <= epsilon zakończ obliczenia - c jest szukanym miejscem zerowym funkcji, wpp sprawdź znak f(c).
   Jeśli sign f(c) = sign f(a) podstaw a = c, wpp b = c. Wróć do polecenia 3
   Uwaga, Dzieki drugiemu warunkowi mamy pewność, że uniknie się zapętlenia.