Metoda równego podziału

Z Wikipedii

Metoda równego podziału (metoda połowienia, metoda bisekcji) -- jedna z metod rozwiązywania równań nieliniowych. Opiera się ona na twierdzeniu Bolzano-Cauchy'ego:

Jeżeli funkcja ciągła $f (x)$ ma na końcach przedziału domkniętego wartości różnych znaków, to wewnątrz tego przedziału, istnieje co najmniej jeden pierwiastek równania $f (x) = 0$ .

Aby można było zastosować metodę równego podziału, muszą być spełnione założenia:

funkcja $f (x)$ jest ciągła w przedziale domkniętym $[a; b]$
funkcja przyjmuje różne znaki na końcach przedziału: $f (a) f (b) < 0$

Przebieg algorytmu:

Należy sprawdzić, czy pierwiastkiem równania jest punkt $x_1=\frac{a+b}{2}$ , czyli czy $f (x 1) = 0$ .
Jeżeli tak jest, algorytm kończy się. W przeciwnym razie $x 1$ dzieli przedział $[a, b]$ na dwa mniejsze przedziały $[a, x 1]$ i $[x 1, b]$ .
Następnie wybierany jest ten przedział, dla którego spełnione jest drugie założenie, tzn. albo $f (x 1) f (a) < 0$ albo $f (x 1) f (b) < 0$ . Cały proces powtarzany jest dla wybranego przedziału.

Algorytm kończy się albo w punkcie 2, albo jest przerywany, gdy przedział będzie dostatecznie wąski.

[edytuj] Przykład

Wyznaczyć pierwiastek równania $x 3 - x + 1 = 0$ w przedziale $[ - 2;2]$ .

Rozwiązanie:

Obliczamy wartości funkcji na końcach przedziału: $f ( - 2) = - 5$ , a $f (2) = 7$ .
Dzielimy przedział na połowy: $x_1 = \frac{-2+2}{2} = 0$ i obliczamy wartość $f (x 1) = 1$ .
Ponieważ wartość funkcji dla $x 1$ jest różna od zera, algorytm jest kontynuowany. Mamy teraz dwa przedziały $[ - 2,0]$ i $[0,2]$ . Wybieramy ten, na którego końcach znaki funkcji są różne - $f(-2)f(0) = -5 \cdot 1 = -5 < 0$ lub $f(0)f(2) = 1 \cdot 7 = 7 > 0$ . Zatem pierwiastek leży w przedziale $[ - 2,0]$
Dzielimy przedział na połowy: $x_2 = \frac{-2+0}{2} = -1$ i obliczamy wartość funkcji $f ( - 1) = 1$ -- liczba $x 2$ nie jest zatem pierwiastkiem.
Znowu dzielimy przedział na dwa podprzedziały, wybieramy jeden z nich itd.

Uwaga: można uzyskać z dowolną rozwiązanie z dowolną dokładnością (czyli dla każdego $ε > 0$ można znaleźć takie $x 0$ , że $\mid x - x_0 \mid < \epsilon$ gdzie $x$ jest pierwiastkiem równania), w rzadkich przypadkach można uzyskać dokładną wartość pierwiastka (gdy algorytm zostanie zakończony w punkcie 2). Algorytm metody równego podziału jest blisko spokrewniony z wyszukiwaniem binarnym.