Metoda Bisekcji (Połowienia przedziałów)

Metoda bisekcji to genialnie prosty algorytm numeryczny, który służy do przybliżonego znajdowania miejsc zerowych funkcji (czyli punktów, w których wykres funkcji przecina oś X, a więc $f(x) = 0$).

Na maturze często dostajemy zadanie: "Znajdź miejsce zerowe funkcji $f(x) = x^3 - 2x + 1$ w przedziale [a, b] z dokładnością do 0.0001". Do tego właśnie służy metoda bisekcji!

Jak działa Bisekcja?

Algorytm opiera się na prostym twierdzeniu matematycznym (Twierdzenie Darboux). Jeśli funkcja jest ciągła i na jednym końcu przedziału $a$ przyjmuje wartość ujemną, a na drugim końcu $b$ wartość dodatnią, to gdzieś pośrodku musi przecinać oś X!

Kroki algorytmu:

1. Liczymy środek przedziału: srodek = (a + b) / 2.
2. Obliczamy wartość funkcji w środku: f(srodek).
3. Jeśli f(srodek) == 0 (lub jest bardzo bliskie zeru), to znaleźliśmy miejsce zerowe!
4. Jeśli f(a) i f(srodek) mają różne znaki (czyli ich iloczyn jest mniejszy od zera), to miejsce zerowe musi leżeć w lewej połowie przedziału. Przesuwamy więc prawy koniec: b = srodek.
5. W przeciwnym razie miejsce zerowe leży w prawej połowie. Przesuwamy lewy koniec: a = srodek.
6. Powtarzamy proces, aż przedział [a, b] stanie się wystarczająco mały (np. b - a < epsilon).

Dzięki temu w każdym kroku przedział zawęża się o połowę! Algorytm działa w czasie logarytmicznym $O(\log n)$, więc osiąga ogromną precyzję w ułamku sekundy.

Implementacja

Zakładamy, że szukamy miejsca zerowego funkcji $f(x) = x^3 - 3x^2 + 2x - 6$ w przedziale [2, 4] z dokładnością do $10^{-5}$ (0.00001).

Python

# Nasza funkcja matematyczna
def f(x):
    return x**3 - 3*x**2 + 2*x - 6

def bisekcja(a, b, epsilon):
    # Sprawdzamy czy miejsce zerowe w ogóle jest w przedziale!
    if f(a) * f(b) > 0:
        return "Brak miejsca zerowego w przedziale lub funkcja nie zmienia znaku."
        
    # Dopóki szerokość przedziału jest większa niż nasza dokładność
    while (b - a) >= epsilon:
        srodek = (a + b) / 2.0
        
        # Jeśli trafiliśmy idealnie w punkt (rzadko się zdarza przy ułamkach)
        if f(srodek) == 0.0:
            return srodek
            
        # Zmiana znaku między a oraz srodek -> miejsce zerowe jest po lewej
        if f(a) * f(srodek) < 0:
            b = srodek
        else:
            # Miejsce zerowe jest po prawej
            a = srodek
            
    # Zwracamy ostateczny środek przedziału jako nasz wynik
    return (a + b) / 2.0

# Wywołanie
wynik = bisekcja(2.0, 4.0, 0.00001)
print(f"Miejsce zerowe: {wynik}")

C++

#include <iostream>
#include <cmath>
using namespace std;

// Zwracamy typ double, bo operujemy na ułamkach
double f(double x) {
    return pow(x, 3) - 3 * pow(x, 2) + 2 * x - 6;
}

void bisekcja(double a, double b, double epsilon) {
    if (f(a) * f(b) > 0) {
        cout << "Brak miejsca zerowego w przedziale." << endl;
        return;
    }
    
    // Dopóki przedział jest większy lub równy dokładności epsilon
    while ((b - a) >= epsilon) {
        double srodek = (a + b) / 2.0;
        
        if (f(srodek) == 0.0) {
            cout << "Miejsce zerowe: " << srodek << endl;
            return;
        }
        
        if (f(a) * f(srodek) < 0) {
            b = srodek; // Szukamy po lewej
        } else {
            a = srodek; // Szukamy po prawej
        }
    }
    
    cout << "Miejsce zerowe: " << (a + b) / 2.0 << endl;
}

int main() {
    bisekcja(2.0, 4.0, 0.00001);
    return 0;
}

[!IMPORTANT] Dla dociekliwych: Epsilon Zmienna epsilon określa przybliżenie. Zamiast pisać pętlę while (b - a >= epsilon), niektórzy programiści piszą po prostu stałą liczbę iteracji, np. for i in range(100):. Sto podziałów na pół gwarantuje precyzję, która przewyższa możliwości standardowych typów zmiennoprzecinkowych, i jest całkowicie odporna na błędy zaokrągleń ułamków bitych w procesorze!