Metoda równego podziału
Metoda równego podziału, metoda połowienia, metoda bisekcji[1], metoda połowienia przedziału – jedna z metod rozwiązywania równań nieliniowych. Opiera się ona na twierdzeniu Darboux:
Jeżeli funkcja ciągła 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 .
Aby można było zastosować metodę równego podziału, muszą być spełnione założenia:
- funkcja jest ciągła w przedziale domkniętym
- funkcja przyjmuje różne znaki na końcach przedziału:
Przebieg algorytmuEdytuj
- Sprawdzenie, czy pierwiastkiem równania jest punkt czyli czy
Jeżeli tak jest algorytm kończy działanie, a punkt jest szukanym miejscem zerowym. - W przeciwnym razie, dopóki nie osiągniemy żądanej dokładności, czyli dopóki
- Zgodnie ze wzorem z punktu pierwszego ponownie wyznaczane jest dzieląc przedział na dwa mniejsze przedziały: i
- Wybierany jest koniec przedziału, którego wartość funkcji posiada znak przeciwny do i odpowiednio górny albo dolny kraniec przedziału ( albo ) przyjmuje wartość tj.
- Jeżeli to
- Jeżeli to
- Po osiągnięciu żądanej dokładności algorytm kończy działanie, a szukany pierwiastek równania wynosi
PrzykładEdytuj
Wyznaczyć pierwiastek równania w przedziale
Rozwiązanie:
- Obliczamy wartości funkcji na końcach przedziału: a
- Dzielimy przedział na połowy: i obliczamy wartość
- Ponieważ wartość funkcji dla jest różna od zera, algorytm jest kontynuowany. Mamy teraz dwa przedziały i Wybieramy ten, na którego końcach znaki funkcji są różne: lub Zatem pierwiastek leży w przedziale
- Dzielimy przedział na połowy: i obliczamy wartość funkcji: . Liczba 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 można znaleźć takie że gdzie jest pierwiastkiem równania), w rzadkich przypadkach można uzyskać dokładną wartość pierwiastka (gdy algorytm zostanie zakończony w 1. punkcie). Algorytm metody równego podziału jest blisko spokrewniony z wyszukiwaniem binarnym.
PseudokodEdytuj
Prezentacja metody równego podziału w języku Python 3. Początkowe wartości a i b muszą być wybrane w taki sposób, aby f(a) i f(b) były przeciwnego znaku oraz „otaczały” poszukiwane miejsce zerowe. Zmienna epsilon określa dokładność wyniku, np. 0,0001.
while abs(a - b) > epsilon: # dopóki nie uzyskamy zadanej dokładności
x1 = (a + b) / 2
if abs(f(x1)) <= epsilon: # jeżeli znaleźliśmy miejsce zerowe mniejsze bądź równe przybliżeniu zera
break
elif f(x1) * f(a) < 0:
b = x1 # nadpisywanie prawego krańca przedziału
else:
a = x1 # nadpisywanie lewego krańca przedziału
print((a + b) / 2) # zwracanie znalezionego miejsca zerowego
Zobacz teżEdytuj
Inne numeryczne metody wyznaczania pierwiastków równań:
- regula falsi
- metoda siecznych
- metoda Newtona (zwana również metodą Newtona-Raphsona lub metodą stycznych)
- odwrotna interpolacja kwadratowa
- metoda iteracji
PrzypisyEdytuj
- ↑ Piotr Krzyżanowski i Leszek Plaskota, Równania nieliniowe. Metoda bisekcji, kurs „Metody numeryczne”, wazniak.mimuw.edu.pl [dostęp 2022-01-18].