2.1 Algorytm bisekcji
Algorytm bisekcji jest prostą metodą znajdowania korzeni funkcji jednowymiarowych. Celem jest znalezienie pierwiastka \(x_0\) takiego, że \(f(x_0)=0\). Algorytm zaczyna od dużego przedziału, o którym wiadomo, że zawiera korzeń, a następnie sukcesywnie zmniejsza rozmiar przedziału, aż do znalezienia korzenia. Podstawą teoretyczną algorytmu jest twierdzenie o wartościach pośrednich, które mówi, że jeśli funkcja ciągła przyjmuje wartości \(f(a)\) i \(f(b)\) w punktach końcowych przedziału \(\), to \(f)\) musi przyjmować wszystkie wartości pomiędzy \(f(a)\) i \(f(b)\) gdzieś w przedziale. Jeśli więc \(f(a) < \gamma < f(b)\), to istnieje taka \(c)\), że \(f(c)= \gamma\).
Korzystając z tych informacji, możemy przedstawić algorytm bisekcji. \, czy \tekst{znak}(f(b))\). W przeciwnym razie przedział nie zawiera korzenia i może być konieczne jego rozszerzenie. Wtedy możemy kontynuować:
-
Niech \(c = \frac{a + b}{2}\).
-
Jeśli \(f(c) = 0\), zatrzymaj się i zwróć \(c).
-
Jeżeli \tekst{znak}(f(a))\), to ustaw \tekst{znak}(f(c))\). Else if \text{sign}(f(b))\netext{sign}(f(c))\), then set \(a\leftarrow c\).
-
Goto the beginning and repeat until convergence (see below).
Po ∗ iteracjach rozmiar przedziału obejmującego korzeń będzie ∗(2^{-n}(b-a)∗).
Algorytm bisekcji jest użyteczny, koncepcyjnie prosty i łatwy do zaimplementowania. W szczególności, nie potrzebujesz żadnych specjalnych informacji o funkcji \(f\) z wyjątkiem zdolności do oceny jej w różnych punktach przedziału. Wadą tego algorytmu jest to, że jest on użyteczny tylko w jednym wymiarze, a jego zbieżność jest liniowa, co jest najwolniejszym tempem zbieżności dla algorytmów, które będziemy omawiać (więcej na ten temat później).
Algorytm bisekcji może napotkać problemy w sytuacjach, gdy funkcja \(f) nie jest dobrze zachowująca się. Idealna sytuacja dla algorytmu bisekcji wygląda mniej więcej tak.
Idealna konfiguracja dla algorytmu bisekcji.
Tutaj funkcje \(f(a)\) i \(f(b)\) są przeciwnych znaków i korzeń jest wyraźnie pomiędzy \(a)\) i \(b)\).
W poniższym scenariuszu algorytm nie zostanie uruchomiony, ponieważ \(f(a)>0\) i \(f(b)>0\).
Podzielna \(f)\) w korzeniu jest \(0\).
W tym kolejnym scenariuszu, istnieją dwa korzenie pomiędzy a i b, oprócz tego, że f(a)>0 i f(b)>0. Należałoby zmniejszyć długość przedziału początkowego, aby znaleźć któryś z korzeni.
Dwa korzenie w przedziale.
W poniższym scenariuszu algorytm zostanie uruchomiony, ponieważ \(f(a)\) i \(f(b)\) są przeciwnego znaku, ale nie ma korzenia.
Interwał zawiera asymptotę, ale nie ma korzenia.
Konwergencja algorytmu bisekcji może być określona albo przez posiadanie \(|b-a|<varepsilon\) dla jakiegoś małego \ albo posiadanie \(|f(b)-f(a)|<varepsilon\). To, które kryterium zostanie użyte, zależy od konkretnego zastosowania oraz od tego, jakie rodzaje tolerancji są wymagane.
2.1.1 Przykład: Kwantyle
Dając funkcję rozkładu kumulatywnego \(F(x)\) i liczbę \(p w (0, 1)\), kwantyl \(F)\) jest liczbą \(x)\) taką, że \(F(x) = p\). Algorytm bisekcji może być użyty do znalezienia kwantyla \(x\) dla danego \(p\) przez zdefiniowanie funkcji \(g(x) = F(x) – p\) i rozwiązanie dla wartości \(x\), która osiąga \(g(x) = 0\).
Innym sposobem, aby to ująć jest to, że odwracamy CDF, aby obliczyć \(x = F^{-1}(p)\). Tak więc algorytm bisekcji może być użyty do inwersji funkcji w takich sytuacjach.
.