319x319px|thumb |Kilka kroków metody bisekcji zastosowanych do przedziału początkowego . Większa czerwona kropka oznacza miejsce zerowe funkcji.
Metoda równego podziału, metoda połowienia, metoda bisekcji Piotr Krzyżanowski i Leszek Plaskota, Równania nieliniowe. Metoda bisekcji, kurs „Metody numeryczne”, wazniak.mimuw.edu.pl [dostęp 2022-01-18]., metoda połowienia przedziału – jedna z metod numerycznych znajdowania pierwiastków dowolnych funkcji ciągłych (w tym nieliniowych) jednej zmiennej rzeczywistej, dla której znane są dwie wartości o przeciwnych znakach. Metoda polega na wielokrotnym dzieleniu na pół przedziału zdefiniowanego przez te wartości, a następnie wybieraniu podprzedziału, w którym funkcja zmienia znak, a więc musi zawierać pierwiastek. Jest to metoda bardzo prosta i niezawodna.
W przypadku wielomianów istnieją bardziej zaawansowane metody testowania istnienia pierwiastka w danym przedziale (reguła znaków Descartesa, twierdzenie Sturma, twierdzenie Budana). Pozwalają one rozszerzyć metodę bisekcji do postaci wydajnych algorytmów służących do znajdowania wszystkich rzeczywistych pierwiastków wielomianu.
Podstawa teoretyczna metody Metoda opiera się na twierdzeniu Darboux:thumb|Metoda bisekcji|270x2709px
Jeżeli funkcja ciągła zmiennej rzeczywistej 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
A więc, aby można było zastosować metodę równego podziału, muszą być spełnione warunki: funkcja jest ciągła w przedziale domkniętym funkcja przyjmuje różne znaki na końcach przedziału:
Funkcja nie musi być przy tym różniczkowalna, a więc warunki te są mniej restrykcyjne, niż np. w metodzie Newtona.
Algorytm metody równego podziału jest blisko spokrewniony z wyszukiwaniem binarnym.
Przebieg algorytmu thumb| Odległość punktu środkowego od pierwiastka funkcji w kolejnych krokach metody bisekcji maleje logarytmicznie - przykład dla funkcji |270x270px
Poszukiwanie pierwiastka głównie polega na iteracyjnym wyznaczaniu punktu środkowego odcinka , którego końce zmienia się w trakcie kolejnych iteracji: jeżeli w punkcie środkowym funkcja ma wartość przeciwną niż w końcu przedziału, to za prawy koniec przedziału przyjmuje się punkt , podstawiając ; w przeciwnym wypadku zmienia się lewy koniec przedziału podstawiając . Dokładniej opisuje to poniższy schemat: Oblicz punkt środkowy przedziału , tj. Jeżeli lub , tj. gdy osiągnięto żądaną dokładność, to algorytm kończy działanie, a szukany pierwiastek równania wynosi . Jeżeli to zmień prawy koniec przedziału podstawiając , w przeciwnym wypadku zmień lewy koniec przedziału podstawiając thumb|Wykres zmian współrzędnej punktu środkowego w kolejnych krokach metody bisekcji szukania pierwiastka funkcji |270x270px Wróć do punktu 1.
Przykład Wyznaczyć pierwiastek równania w przedziale z dokładnością
Rozwiązanie:
Ponieważ funkcja jest ciągła oraz , to z tw. Darboux wynika, że musi istnieć pierwiastek w przedziale . Iterowanie metody bisekcji na tym przedziale daje coraz dokładniejsze przybliżenia tego pierwiastka.
I iteracja Obliczamy środek przedziału: . Ponieważ oraz , to algorytm nie jest zakończony. Mamy teraz dwa przedziały oraz Wybieramy ten, na którego końcach znaki funkcji są różne; ponieważ , to zmieniamy lewy koniec przedziału, przyjmując Zatem pierwiastek leży w przedziale II iteracja Obliczamy środek przedziału: . Ponieważ oraz , to algorytm nie jest zakończony. Mamy teraz dwa przedziały oraz Wybieramy ten, na którego końcach znaki funkcji są różne; ponieważ , to zmieniamy prawy koniec przedziału, przyjmując . Zatem pierwiastek leży w przedziale III iteracja Obliczamy środek przedziału: . Ponieważ oraz , to algorytm nie jest zakończony. itd. Kontynuując proces po 39 iteracjach mamy wynik: pierwiastek określony z dokładnością do .
Dalej podano program, który realizuje pokazany tu algorytm z dowolną dokładnością. Na wykresach pokazano obliczenia numeryczne nawiązujące do omówionego tu przykładu.
Uwaga: Rozwiązanie można wyznaczyć z dowolną dokładnością czyli dla każdego można znaleźć takie że oraz jest pierwiastkiem równania. W rzadkich przypadkach można uzyskać dokładną wartość pierwiastka, tj. - zależy to od przyjętych na początku końców przedziału, na którym poszukuje się pierwiastka - dalej algorytm może wybrać do obliczeń wartości funkcji tylko te punkty, które wynikają z dzielenia na połowy początkowego odcinka, nie przebiega przez continuum odcinka liczb rzeczywistych.
Program w Pythonie Zamieszczony tu program w języku Python oblicza pierwiastek zadanej funkcji z wysoką dokładnością. Początkowe wartości i muszą być wybrane w taki sposób, aby i były przeciwnego znaku oraz „otaczały” poszukiwane miejsce zerowe.
def bisekcja(funkcja, a, b, EPS =1e-12, max_iter=1000): """ Znajduje pierwiastek funkcji w przedziale [a, b] metodą bisekcji EPS - dokładność wyniku """ if funkcja(a) * funkcja(b) >= 0: raise ValueError("Funkcja musi mieć różne znaki na końcach przedziału [a, b].")
for _ in range(max_iter): c = (a + b) / 2 if abs(funkcja(c)) < EPS or (b - a)/2 < EPS: return c if funkcja(a) * funkcja(c) < 0: b = c else: a = c return (a + b)/2
# Przykład użycia def funkcja(x): return x**3 - x - 2 # Dane: a=1 # początek przedziału b=2 # koniec przedziału EPS = 1e-12 # dokładność obliczeń
pierwiastek = bisekcja(funkcja, a, b, EPS) decimals = max(0, -int("{:.0e}".format(EPS).split('e')[-1])) print(f"\nPierwiastek funkcji: {pierwiastek:.{decimals}f}")
Zobacz też I. Wyznaczania pierwiastków równań: metoda iteracji metoda Brenta metoda Newtona (zwana również metodą Newtona-Raphsona lub metodą stycznych) metoda siecznych odwrotna interpolacja kwadratowa regula falsi II. Wyznaczania ekstremów funkcji jednej i wielu zmiennych:
metoda Brenta (optymalizacja) metoda Newtona (optymalizacja)
III. Wyszukiwanie elementów w zbiorze:
binarne drzewo poszukiwań przeszukiwanie liniowe wyszukiwanie binarne
Przypisy
Bibliografia
Zenon Fortuna, Bohdan Macukow, Janusz Wąsowski, Metody numeryczne, Wydawnictwa Naukowo-Techniczne, Warszawa 2006, , str. 114-119
Linki zewnętrzne [dostęp 2025-10-06]. Dichotomy method , Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2025-10-06].
Kategoria:Algorytmy rozwiązywania równań nieliniowych