Metoda równego podziału

Metoda równego podziału, metoda połowienia, metoda bisekcji^[1], 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:

Jeżeli funkcja ciągła $f(x)$ zmiennej rzeczywistej $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.$

A więc, aby można było zastosować metodę równego podziału, muszą być spełnione warunki:

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.$

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

Poszukiwanie pierwiastka głównie polega na iteracyjnym wyznaczaniu punktu środkowego $c$ odcinka $[a,b]$ , którego końce zmienia się w trakcie kolejnych iteracji: jeżeli w punkcie środkowym funkcja ma wartość przeciwną niż w końcu $a$ przedziału, to za prawy koniec przedziału przyjmuje się punkt $c$ , podstawiając $a=c$ ; w przeciwnym wypadku zmienia się lewy koniec przedziału podstawiając $b=c$ . Dokładniej opisuje to poniższy schemat:

Oblicz punkt środkowy przedziału $[a,b]$ , tj. $c={\tfrac {a+b}{2}}.$
Jeżeli $|f(c)|<\epsilon$ lub $(b-a)/2<\epsilon$ , tj. gdy osiągnięto żądaną dokładność, to algorytm kończy działanie, a szukany pierwiastek równania wynosi $c$ .
Jeżeli $f(a)f(c)<0,$ to zmień prawy koniec przedziału podstawiając $b=c$ , w przeciwnym wypadku zmień lewy koniec przedziału podstawiając $a=c.$
Wykres zmian współrzędnej punktu środkowego w kolejnych krokach metody bisekcji szukania pierwiastka funkcji $f(x)=x^{3}-x-2$
Wróć do punktu 1.

Przykład

Wyznaczyć pierwiastek równania $f(x)=x^{3}-x-2$ w przedziale $[1;2]$ z dokładnością $\epsilon =10^{-12}$

Rozwiązanie:

Ponieważ funkcja jest ciągła oraz $f(1)f(2)<0$ , to z tw. Darboux wynika, że musi istnieć pierwiastek w przedziale $[1;2]$ . Iterowanie metody bisekcji na tym przedziale daje coraz dokładniejsze przybliżenia tego pierwiastka.

I iteracja

Obliczamy środek przedziału: $c={\tfrac {1+2}{2}}=1.5$ .
Ponieważ $|f(c)|=|f(1.5)|=|-0.125|>\epsilon$ oraz $(b-a)/2=0.5>\epsilon$ , to algorytm nie jest zakończony.
Mamy teraz dwa przedziały $[1;1.5]$ oraz $[1.5;2].$ Wybieramy ten, na którego końcach znaki funkcji są różne; ponieważ $f(1)f(1.5)=-2\cdot (-0.125)>0$ , to zmieniamy lewy koniec przedziału, przyjmując $a=1.5$ Zatem pierwiastek leży w przedziale $[1.5;2].$

II iteracja

Obliczamy środek przedziału: $c={\tfrac {1.5+2}{2}}=1.75$ .
Ponieważ $|f(c)|=|f(1.75)|=1.609375>\epsilon$ oraz $(b-a)/2=0.25>\epsilon$ , to algorytm nie jest zakończony.
Mamy teraz dwa przedziały $[1.5;1.75]$ oraz $[1.75;2].$ Wybieramy ten, na którego końcach znaki funkcji są różne; ponieważ $f(1.5)\cdot f(1.75)=-0.125\cdot 1.609375<0$ , to zmieniamy prawy koniec przedziału, przyjmując $b=1.75$ . Zatem pierwiastek leży w przedziale $[1.5;1.75].$

III iteracja

Obliczamy środek przedziału: $c={\tfrac {1.5+1.75}{2}}=1.625$ .
Ponieważ $|f(c)|=|f(1.625)|=...>\epsilon$ oraz $(b-a)/2=0.125>\epsilon$ , to algorytm nie jest zakończony.
itd.

Kontynuując proces po 39 iteracjach mamy wynik: pierwiastek $c=1.521379706805\pm 0.000000000001$ określony z dokładnością do $\epsilon =10^{-12}$ .

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 $\epsilon >0$ można znaleźć takie $c,$ że $\mid x-c\mid <\epsilon$ oraz $c$ jest pierwiastkiem równania. W rzadkich przypadkach można uzyskać dokładną wartość pierwiastka, tj. $f(c)=0$ - zależy to od przyjętych na początku końców $a,b$ 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 $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.

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:

III. Wyszukiwanie elementów w zbiorze:

Przypisy

↑ Piotr Krzyżanowski i Leszek Plaskota, Równania nieliniowe. Metoda bisekcji, kurs „Metody numeryczne”, wazniak.mimuw.edu.pl [dostęp 2022-01-18].

Bibliografia

Zenon Fortuna, Bohdan Macukow, Janusz Wąsowski, Metody numeryczne, Wydawnictwa Naukowo-Techniczne, Warszawa 2006, ISBN 978-83-7926-281-6, str. 114-119

Linki zewnętrzne

Eric W.E.W. Weisstein Eric W.E.W., Bisection, [w:] MathWorld, Wolfram Research (ang.). [dostęp 2025-10-06].
Dichotomy method (ang.), Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2025-10-06].

[1] Piotr Krzyżanowski i Leszek Plaskota, Równania nieliniowe. Metoda bisekcji, kurs „Metody numeryczne”, wazniak.mimuw.edu.pl [dostęp 2022-01-18].

[1]