Miejsca zerowe metodą połowienia

🎯 Po co Ci to?

Równania w rodzaju $x^3 - x - 1 = 0$ nie mają wzoru na pierwiastek, którego nauczyłbyś się jak dla kwadratowego — a jednak inżynier musi znać jego rozwiązanie z dokładnością do dziesiątej cyfry, bo od tego zależy, czy most stoi. Jak? Nie wzorem — algorytmem. Metoda połowienia (znasz ją z 1.4 jako zgadywankę, a z 6.2 jako wyszukiwanie binarne) tutaj poluje na miejsce zerowe funkcji: zawęża przedział, w którym pierwiastek musi się kryć, aż do dowolnej dokładności. To pierwsza z dwóch metod numerycznych tego działu — i dowód, że algorytmika liczy tam, gdzie algebra się poddaje.

✅ Czego się nauczysz

Po tej jednostce potrafisz:

  • wyjaśnić, dlaczego zmiana znaku funkcji gwarantuje pierwiastek w przedziale;
  • wykonać i zaprogramować metodę połowienia dla miejsca zerowego;
  • określić dokładność i liczbę kroków potrzebną do jej osiągnięcia.

🔁 Przypomnij sobie

Z 1.4/2.7: połowienie odrzuca połowę i zbiega logarytmicznie; z 6.2: binarne na monotonicznej własności; z 2.4: dokładność i próg (epsilon).

📘 Wyjaśnienie

Fundament: zmiana znaku. Jeśli funkcja ciągła (rysowana bez odrywania ołówka) ma na końcach przedziału różne znaki — powiedzmy $f(a) < 0$ i $f(b) > 0$ — to gdzieś między $a$ i $b$ musi przeciąć zero (nie da się przejść z minusa na plus, nie mijając zera). To twierdzenie z matematyki (własność Darboux) jest silnikiem całej metody: gwarantuje, że pierwiastek jest w przedziale, zanim zaczniemy go szukać.

Algorytm. Zajrzyj do środka przedziału $s = (a+b)/2$. Sprawdź znak $f(s)$: jeśli taki sam jak $f(a)$ — pierwiastek jest w prawej połowie (przesuń $a$ do $s$); jeśli taki sam jak $f(b)$ — w lewej ($b$ do $s$). Przedział skurczył się o połowę, a pierwiastek wciąż w środku. Powtarzaj, aż przedział będzie węższy niż żądana dokładność:

def miejsce_zerowe(f, a, b, eps=1e-9):
    # zakładamy f(a) i f(b) różnych znaków
    while b - a > eps:
        s = (a + b) / 2
        if f(a) * f(s) < 0:        # różne znaki na [a, s] → pierwiastek TU
            b = s
        else:
            a = s                   # pierwiastek w [s, b]
    return (a + b) / 2              # środek maleńkiego przedziału

(f(a) * f(s) < 0 to elegancki test „różne znaki": iloczyn liczb o przeciwnych znakach jest ujemny.) To dosłownie wyszukiwanie binarne (6.2) — tylko zamiast szukać wartości w tablicy, szukamy zera na osi liczbowej, a „posortowanie" zastępuje ciągłość i zmiana znaku.

💭 Pomyśl: Ile kroków potrzeba, by z przedziału długości 1 zejść do dokładności $10^{-9}$ (miliardowej)? Skorzystaj z tego, co wiesz o połowieniu (2.7).

Sprawdź odpowiedź

Każdy krok połowi długość, więc po $k$ krokach przedział ma długość $1/2^k$; chcemy $1/2^k < 10^{-9}$, czyli $2^k > 10^9$, więc $k = 30$ (bo $2^{30} \approx 10^9$ — znajoma liczba z 2.7!). Trzydzieści kroków na dziewięć cyfr dokładności. Chcesz dwa razy dokładniej (jeszcze jedna cyfra)? Dołóż ~3,3 kroku. Logarytmiczna zbieżność w pełnej krasie: dokładność rośnie wykładniczo z liczbą kroków. Za tanio, żeby nie skorzystać.

⚠️ Uwaga, pułapka

Metoda połowienia wymaga różnych znaków na końcach — bez tego założenia nie ma gwarancji pierwiastka i algorytm zwróci bzdurę (środek przedziału, w którym nic nie ma). Zawsze sprawdzaj f(a) * f(b) < 0 przed startem! Druga subtelność: jeśli w przedziale są dwa pierwiastki (albo parzysta ich liczba), znaki na końcach mogą być takie same — i metoda ich przeoczy. Połowienie znajduje jeden pierwiastek w przedziale ze zmianą znaku; szukanie wszystkich wymaga najpierw podziału osi na kawałki z pojedynczą zmianą znaku. Narzędzie zna swoje granice — Ty też musisz.

🌍 Powiązania

Metoda połowienia to najprostszy przedstawiciel metod numerycznych — dziedziny, która liczy to, czego nie da się rozwiązać wzorem: pierwiastki równań, całki, układy równań, równania różniczkowe opisujące pogodę i wytrzymałość konstrukcji. Rozpoznajesz w niej binarne (6.2) i połowienie (1.4) — ta sama idea „odrzuć połowę" obsługuje wyszukiwanie w tablicy, zgadywankę, szukanie zepsutej wersji programu (6.2) i teraz rozwiązywanie równań. Jeden pomysł, cztery zawody — znak naprawdę fundamentalnej idei.

🛠️ Teraz Ty

Bez komputera: metodą połowienia znajdź $\sqrt{2}$ jako pierwiastek $f(x) = x^2 - 2$ na przedziale $[1, 2]$ — wykonaj cztery kroki ręcznie, notując przedział i znaki. Z komputerem: zaimplementuj miejsce_zerowe, znajdź pierwiastek $x^3 - x - 1 = 0$ (jest jeden, blisko 1,32) i policz, ile kroków zajęło osiągnięcie $\varepsilon = 10^{-6}$ — czy zgadza się z Twoim oszacowaniem?

📐 Definicje tej lekcji

  • Miejsce zerowe — argument, dla którego funkcja przyjmuje wartość 0 (pierwiastek równania $f(x)=0$).
  • Metoda połowienia (bisekcji) — zawężanie przedziału ze zmianą znaku o połowę, aż do żądanej dokładności; koszt $\log_2(\text{szerokość}/\varepsilon)$ kroków.

📌 Najważniejsze w pigułce

  • Zmiana znaku funkcji ciągłej gwarantuje pierwiastek między końcami — to silnik metody.
  • Połowienie zbiega logarytmicznie: ~30 kroków na miliardową dokładność, +3,3 kroku na każdą kolejną cyfrę.
  • To wyszukiwanie binarne przeniesione z tablicy na oś liczbową — ale wymaga sprawdzenia znaków przed startem.

🎒 Zadania

  1. Funkcja $f(x) = x^2 - 5$. Sprawdź, że na $[2, 3]$ jest zmiana znaku, i wykonaj trzy kroki połowienia. Do jakiej wartości zbiegasz?
Wskazówka i odpowiedź

$f(2) = -1 < 0$, $f(3) = 4 > 0$ — zmiana znaku ✓. Krok 1: $s=2{,}5$, $f(2{,}5)=1{,}25>0$ → $[2; 2{,}5]$. Krok 2: $s=2{,}25$, $f=0{,}0625>0$ → $[2; 2{,}25]$. Krok 3: $s=2{,}125$, $f=-0{,}484<0$ → $[2{,}125; 2{,}25]$. Zbiegamy do $\sqrt{5} \approx 2{,}236$. Połowienie liczy pierwiastki niewymierne dowolnie dokładnie — coś, czego „na wzór" zrobić się nie da.

  1. Chcesz znaleźć pierwiastek z dokładnością do 12 cyfr po przecinku, startując z przedziału długości 10. Ile kroków? Ile trwałoby to, gdyby każdy krok zajmował mikrosekundę?
Wskazówka i odpowiedź

Potrzeba $1/2^k < 10^{-12}$ względem długości 10, czyli $10/2^k < 10^{-12}$ → $2^k > 10^{13}$ → $k \approx 44$. Czterdzieści cztery mikrosekundy — czyli 0,000044 s. Dwanaście cyfr dokładności w mgnieniu oka; to dlatego metody numeryczne są kręgosłupem inżynierii. Zwróć uwagę: dziesięciokrotnie większy przedział startowy dołożył ledwie ~3 kroki (jeden $\log_2 10$) — logarytm jest hojny.

  1. Dlaczego metoda połowienia nie znajdzie pierwiastka funkcji $f(x) = x^2$ (która ma pierwiastek podwójny w zerze) na przedziale $[-1, 1]$? Co pokazują znaki na końcach?
Wskazówka i odpowiedź

$f(-1) = 1 > 0$ i $f(1) = 1 > 0$ — takie same znaki, mimo że pierwiastek (x=0) jest w środku! Funkcja dotyka zera, ale go nie przecina (nie zmienia znaku), więc silnik metody (zmiana znaku) nie zadziała. Połowienie znajduje pierwiastki, w których funkcja przechodzi przez zero, nie te, w których go tylko dotyka. To ważne ograniczenie — pierwiastki podwójne wymagają innych metod (np. szukania zera pochodnej). Narzędzie trzeba znać także od strony tego, czego nie potrafi.

🔍 Sprawdź, czy umiesz

  • Uzasadnić zmianą znaku, że pierwiastek istnieje w przedziale.
  • Wykonać połowienie ręcznie i zaprogramować je z testem znaku.
  • Policzyć liczbę kroków dla żądanej dokładności i wskazać, kiedy metoda zawodzi.

Ucz się tej jednostki z asystentem