Znajduje miejsce zerowe funkcji, połowiąc przedział, w którym zmienia się znak. O(log(...)).
Metoda bisekcji (połowienia) to sposób na znalezienie miejsca zerowego funkcji – czyli takiego x, dla którego funkcja daje 0. To dokładnie ten sam pomysł co wyszukiwanie binarne, tylko zamiast szukać liczby w tablicy, szukamy punktu, w którym wykres przecina oś.
Jak to działa? Bierzemy przedział [a, b], w którym funkcja po jednej stronie jest ujemna, a po drugiej dodatnia. Skoro przechodzi z minusa na plus, to gdzieś między a i b musi przeciąć zero. Liczymy środek c, sprawdzamy znak funkcji w tym środku i zostawiamy tę połowę, w której nadal jest zmiana znaku. I tak w kółko – przedział kurczy się o połowę.
Warunek startu: na końcach przedziału funkcja musi mieć różne znaki (jeden minus, drugi plus). Inaczej nie ma pewności, że w środku w ogóle jest miejsce zerowe, i metoda nie ma czego szukać.
Dlaczego wynik jest przybliżony? Bo prawie nigdy nie trafiamy dokładnie w zero. Zatrzymujemy się, gdy przedział zrobi się już bardzo wąski (np. krótszy niż 0,001), i za miejsce zerowe bierzemy jego środek.
Na maturze: klasyka działu numerycznego. Trzeba umieć wskazać, którą połowę zostawić po danym kroku, oraz policzyć, ile połowień zwęzi przedział do zadanej dokładności.
Prześledź, jak metoda połowi przedział, w którym funkcja f(x) = x² − 2 zmienia znak. Bieżący przedział jest podświetlony, kreska pokazuje środek, a plakietki + / − to znak funkcji na końcach i w środku.
Naciśnij „Krok", aby policzyć środek i odrzucić połowę, albo „Auto".
funkcja bisekcja(f, a, b, epsilon): dopóki (b - a) > epsilon: c ← (a + b) / 2 jeżeli f(c) = 0: zwróć c jeżeli f(a) * f(c) < 0: b ← c // zmiana znaku jest w lewej połowie w przeciwnym razie: a ← c // zmiana znaku jest w prawej połowie zwróć (a + b) / 2
def bisekcja(f, a, b, epsilon=1e-6):
"""Znajduje przybliżone miejsce zerowe funkcji f na przedziale [a, b].
Warunek: f(a) i f(b) muszą mieć różne znaki."""
while b - a > epsilon:
c = (a + b) / 2
if f(c) == 0:
return c
if f(a) * f(c) < 0:
b = c # miejsce zerowe jest w [a, c]
else:
a = c # miejsce zerowe jest w [c, b]
return (a + b) / 2
# Przykład: pierwiastek z 2 to miejsce zerowe funkcji x^2 - 2
f = lambda x: x * x - 2
print(round(bisekcja(f, 1, 2), 4)) # Wynik: 1.4142#include <iostream>
#include <cmath>
using namespace std;
double f(double x) { return x * x - 2; } // szukamy miejsca zerowego
double bisekcja(double a, double b, double epsilon) {
while (b - a > epsilon) {
double c = (a + b) / 2;
if (f(a) * f(c) < 0) b = c; // miejsce zerowe w [a, c]
else a = c; // miejsce zerowe w [c, b]
}
return (a + b) / 2;
}
int main() {
cout << bisekcja(1, 2, 1e-6) << "\n"; // Wynik: ok. 1.41421
}Pomysł jest ten sam – połowienie – ale wyszukiwanie binarne szuka gotowej liczby w posortowanej tablicy, a bisekcja szuka miejsca, w którym funkcja przechodzi przez zero. Zamiast porównywać wartości, patrzymy na znak funkcji.
Bo jeśli funkcja jest ciągła i po jednej stronie jest ujemna, a po drugiej dodatnia, to gdzieś między nimi musi przeciąć zero. Gdy oba znaki są takie same, takiej gwarancji nie ma i metoda nie wie, gdzie szukać.
Gdy przedział zrobi się dostatecznie wąski – krótszy niż zadana dokładność, na przykład 0,001. Wtedy za miejsce zerowe bierzemy jego środek. Rzadko trafiamy dokładnie w zero.
Znajdzie, o ile na starcie znaki na końcach są różne, a funkcja jest ciągła. Jeśli w przedziale są dwa miejsca zerowe, metoda dojdzie tylko do jednego z nich.
Weźmy funkcję f(x) = x² − 2 (jej miejsce zerowe to pierwiastek z 2, czyli około 1,414) i przedział [1, 2]. Wpisz odpowiedzi i kliknij Sprawdź.
Na starcie f(1) = −1, więc znak na lewym końcu jest , a f(2) = 2, więc na prawym końcu jest . Są różne, więc metoda ruszy.
Pierwszy środek to . Wartość f(1.5) = 0.25 jest dodatnia – tak samo jak na prawym końcu – więc zmiana znaku jest w lewej połowie i nowy przedział to `[1, ]`.
Uzupełnij, ile połowień zmniejszy długość przedziału [1, 2] (długość 1) do podanej wartości:
| Docelowa długość | Liczba połowień |
|---|---|
| 0,5 | |
| 0,25 | |
| 0,125 |
O(log((b-a)/ε))O(1)Czasowa O(log((b-a)/ε)). Każdy krok połowi długość przedziału, więc żeby z przedziału o długości b - a zejść do dokładności ε, wystarczy tyle kroków, ile razy trzeba tę długość podzielić na pół. Pamięć O(1) – trzymamy tylko dwa końce przedziału i jego środek.
Do tego hasła nie mamy jeszcze przypisanych pojedynczych zadań. Cały spis zadań maturalnych z tego działu jest tutaj:
Zagadnienia z tego samego obszaru matury – warto je powtórzyć razem: