Metoda równego podziału
Z Wikipedii
Metoda równego podziału (metoda połowienia, metoda bisekcji, metoda połowienia przedziału) - 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 , czyli czy f(x1) = 0.
- Jeżeli tak jest, algorytm kończy się. W przeciwnym razie x1 dzieli przedział [a,b] na dwa mniejsze przedziały [a,x1] i [x1,b].
- Następnie wybierany jest ten przedział, dla którego spełnione jest drugie założenie, tzn. albo f(x1)f(a) < 0 albo f(x1)f(b) < 0. Cały proces powtarzany jest dla wybranego przedziału.
Działanie algorytmu kończy się w punkcie 2, lub po osiągnięciu żądanej dokładności przybliżenia pierwiastka.
[edytuj] Przykład
Wyznaczyć pierwiastek równania x3 − 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: i obliczamy wartość f(x1) = 1.
- Ponieważ wartość funkcji dla x1 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 - lub . Zatem pierwiastek leży w przedziale [ − 2,0]
- Dzielimy przedział na połowy: i obliczamy wartość funkcji f( − 1) = 1 – liczba x2 nie jest zatem pierwiastkiem.
- Znowu dzielimy przedział na dwa podprzedziały, wybieramy jeden z nich itd.
Uwaga: rozwiązanie można wyznaczyć z dowolną dokładnością (czyli dla każdego ε > 0 można znaleźć takie x0, że 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.
[edytuj] Pseudokod
Prezentacja bisecji w języku Visual Basic. Zmienne xL i xR odpowiadają punktom a i b powyżej. Początkowe wartości xL i xR muszą być wybrane w taki sposób, aby f(xL) i f(xR) były przeciwnego znaku. Zmiena epsilon określa dokładność wyniku.
'Metoda bisecji 'Początkowa pętla Do While (abs(xR - xL)) > epsilon 'Obliczanie wartości punktu środkowego xM = (xR + xL) / 2 'Znajdowanie f(xM) If ((f(xL) * f(xM)) > 0) Then 'Odrzuć lewą połowę xL = xM Else 'Odrzuć prawą połowę xR = xM End If Loop
Inne numeryczne metody wyznaczania pierwiastków równań:
- regula falsi
- metoda siecznych
- metoda stycznych
- metoda iteracji