Wyznacza miejsce zerowe funkcji ciągłej przez wielokrotne dzielenie przedziału na połowy.
Metoda bisekcji (zwana też metodą połowienia przedziałów) służy do przybliżonego wyznaczania miejsc zerowych funkcji ciągłej na zadanym przedziale.
Założenia: wybieramy przedział [a, b], na którym funkcja zmienia znak – tzn. f(a) · f(b) < 0. Z twierdzenia Darboux wynika wtedy, że w przedziale istnieje co najmniej jedno miejsce zerowe.
Algorytm: w każdej iteracji obliczamy środek przedziału s = (a + b) / 2 i sprawdzamy znak f(s). Jeśli f(a) · f(s) < 0, miejsce zerowe leży w lewej połowie – zawężamy przedział do [a, s]. W przeciwnym razie – do [s, b]. Powtarzamy aż przedział zwęzi się poniżej zadanej dokładności eps.
Złożoność O(log n) wynika z tego, że w każdej iteracji długość przedziału maleje dwukrotnie – to klasyczny algorytm typu "dziel i zwyciężaj" zastosowany do ciągłych funkcji.
Na maturze: zadania na bisekcję pojawiają się w arkuszach rozszerzonych, często z funkcjami niewielomianowymi, gdzie nie da się znaleźć miejsc zerowych analitycznie.
funkcja bisekcja(f, a, b, eps): // założenie: f(a) * f(b) < 0 dopóki b - a > eps: s ← (a + b) / 2 jeżeli f(s) = 0: zwróć s jeżeli f(a) * f(s) < 0: // miejsce zerowe w lewej połowie b ← s w przeciwnym razie: // miejsce zerowe w prawej połowie a ← s zwróć (a + b) / 2
def bisekcja(f, a, b, eps=1e-6):
if f(a) * f(b) >= 0:
return None
while b - a > eps:
s = (a + b) / 2
if f(s) == 0:
return s
if f(a) * f(s) < 0:
b = s
else:
a = s
return (a + b) / 2
# Przykład użycia: szukamy miejsca zerowego f(x) = x^2 + 5x + 3
def f(x):
return x**2 + 5*x + 3
print(round(bisekcja(f, -5, -2), 4))
# Wynik: -4.3028 (dokładne miejsce zerowe to -(5+√13)/2)
print(round(bisekcja(f, -1, 0), 4))
# Wynik: -0.6972O(log n)O(1)Zagadnienia z tego samego obszaru matury – warto je powtórzyć razem: