Przybliżony pierwiastek — Babilon i Newton

🎯 Po co Ci to?

Połowienie (7.5) policzy Ci $\sqrt{2}$ — ale w 30 krokach na 9 cyfr. Cztery tysiące lat temu babilońscy rachmistrze robili to szybciej, bez pojęcia funkcji i pochodnej, metodą tak sprytną, że używamy jej do dziś (siedzi wewnątrz sprzętowej instrukcji pierwiastka w procesorach). A dwa tysiące lat później Isaac Newton uogólnił jej ideę na dowolne równanie — dając metodę, która podwaja liczbę poprawnych cyfr z każdym krokiem. Ta jednostka to spotkanie dwóch geniuszy przez cztery tysiąclecia i lekcja, że czasem sprytny pomysł bije systematyczne połowienie o rzędy wielkości. Rozszerzona podstawa wymienia przybliżony pierwiastek wprost.

✅ Czego się nauczysz

Po tej jednostce potrafisz:

  • policzyć pierwiastek metodą babilońską (średnia kolejnych przybliżeń) i wyjaśnić, czemu działa;
  • opisać ideę metody Newtona (stycznej) jako uogólnienie i porównać jej zbieżność z połowieniem;
  • dobrać warunek stopu dla metody iteracyjnej opartej na dokładności.

🔁 Przypomnij sobie

Z 7.5: szukamy $x$ z $f(x) = 0$; z 2.4: porównania ułamków przez próg (epsilon), nie przez ==; z 4.3: iteracja z „oknem" jednej wartości.

📘 Wyjaśnienie

Metoda babilońska. Chcesz $\sqrt{S}$. Zgadnij cokolwiek dodatniego, $x$. Jeśli $x$ jest za duże, to $S/x$ jest za małe (bo ich iloczyn to dokładnie $S$) — a prawdziwy pierwiastek leży między nimi. Weź więc ich średnią jako lepsze zgadnięcie i powtórz:

$$x_{\text{nowe}} = \frac{1}{2}\left(x + \frac{S}{x}\right)$$

def pierwiastek(S, eps=1e-12):
    x = S                            # dowolne dodatnie zgadnięcie
    while abs(x * x - S) > eps:      # aż x² będzie dość blisko S
        x = (x + S / x) / 2
    return x

Prześledź $\sqrt{2}$ startując od $x = 2$: $x_1 = \frac{1}{2}(2 + 1) = 1{,}5$; $x_2 = \frac{1}{2}(1{,}5 + 1{,}333) = 1{,}4167$; $x_3 = 1{,}41422$; $x_4 = 1{,}41421356$… Cztery kroki i mamy osiem cyfr! Porównaj z połowieniem: tam osiem cyfr kosztowało ~27 kroków. Skąd ta przepaść? Bo metoda babilońska podwaja liczbę poprawnych cyfr z każdym krokiem (2 → 4 → 8 → 16…), podczas gdy połowienie dokłada stałą liczbę cyfr (jedną co ~3,3 kroku). To jest różnica między zbieżnością liniową a kwadratową — i jedna z najważniejszych w metodach numerycznych.

Metoda Newtona. Babilończycy trafili na szczególny przypadek genialnej ogólnej idei. Newton spytał: mam funkcję $f$ i przybliżenie $x$ pierwiastka — jak je poprawić? Poprowadź styczną do wykresu w punkcie $x$ i zobacz, gdzie ta styczna przecina oś (to znacznie bliżej pierwiastka niż $x$). Wzór (używa pochodnej $f'$ z analizy):

$$x_{\text{nowe}} = x - \frac{f(x)}{f'(x)}$$

Dla $f(x) = x^2 - S$ mamy $f'(x) = 2x$, więc wzór Newtona to $x - \frac{x^2 - S}{2x} = \frac{1}{2}(x + \frac{S}{x})$ — dokładnie metoda babilońska! Babilończycy cztery tysiące lat temu wykonali metodę Newtona dla pierwiastka, nie wiedząc, czym jest styczna ani pochodna. Ich intuicja „średnia z za-dużo i za-mało" okazała się szczególnym przypadkiem uniwersalnej metody. Newton działa dla dowolnego równania (byle znać pochodną), z tą samą oszałamiającą, kwadratową zbieżnością.

💭 Pomyśl: Metoda Newtona jest zwykle znacznie szybsza od połowienia. Czemu więc połowienie nie odeszło do lamusa? Co połowienie ma, czego Newtonowi brakuje?

Sprawdź odpowiedź

Połowienie ma gwarancję: dopóki są różne znaki na końcach, ZAWSZE zbiegnie do pierwiastka, niezawodnie. Newton jest szybszy, ale kapryśny: przy złym punkcie startowym może odlecieć w nieskończoność, wpaść w cykl albo zbiegać do innego pierwiastka niż chciałeś (styczna potrafi „strzelić" daleko). Wymaga też pochodnej, której nie zawsze znasz. To znajomy handel z 6.7 (scalanie vs szybkie): niezawodna wolność kontra kapryśna szybkość. Praktyka często je łączy: kilka kroków połowienia, by bezpiecznie zbliżyć się do pierwiastka, potem Newton, by błyskawicznie dobić do dokładności. Inżynieria to portfel metod, nie jedna ulubiona.

⚠️ Uwaga, pułapka

Warunek stopu abs(x*x - S) > eps (albo abs(x_nowe - x) > eps) jest konieczny — i musi używać progu, nie równości. Napiszesz while x*x != S — i dla $S = 2$ pętla nigdy się nie skończy, bo $\sqrt{2}$ nie ma dokładnej reprezentacji zmiennoprzecinkowej (2.4!), więc $x^2$ nigdy nie będzie dokładnie 2. To ten sam błąd, co porównywanie ułamków przez == z jednostki 2.4 — tu w nowym kostiumie, ale równie zabójczy: metoda iteracyjna bez progowego warunku stopu to pętla nieskończona czekająca na dokładność, której arytmetyka komputera nie osiągnie.

🛠️ Teraz Ty

Bez komputera: policz metodą babilońską $\sqrt{10}$, startując od $x = 3$ — wykonaj trzy kroki i porównaj z prawdziwą wartością (~3,162). Ile cyfr masz po każdym kroku? Z komputerem: zaimplementuj pierwiastek, dołóż licznik iteracji i porównaj z liczbą kroków połowienia (7.5) dla tej samej dokładności. Na deser: zastosuj wzór Newtona do $f(x) = x^3 - S$ (pierwiastek sześcienny — jaka będzie pochodna i wzór iteracji?).

📐 Definicje tej lekcji

  • Metoda babilońska — $\sqrt{S}$ przez iterację $x \leftarrow \frac{1}{2}(x + S/x)$; kwadratowa zbieżność (podwaja cyfry).
  • Metoda Newtona (stycznej) — $x \leftarrow x - f(x)/f'(x)$; uogólnienie babilońskiej na dowolne równanie; szybka, ale bez gwarancji zbieżności.

📌 Najważniejsze w pigułce

  • Babilońska: średnia z „za dużo" i „za mało"; cztery kroki na osiem cyfr — bo podwaja cyfry co krok.
  • Newton to ta sama idea (styczna) dla dowolnego równania; babilońska to jego szczególny przypadek sprzed 4000 lat.
  • Szybkość Newtona kosztuje gwarancję — połowienie jest wolne, ale niezawodne; praktyka je łączy.

🎒 Zadania

  1. Policz metodą babilońską $\sqrt{7}$ startując od $x = 3$: wykonaj trzy iteracje i zapisz, ile cyfr się zgadza po każdej (prawdziwa wartość ~2,6458).
Wskazówka i odpowiedź

$x_0=3$; $x_1 = \frac{1}{2}(3 + 7/3) = \frac{1}{2}(3 + 2{,}333) = 2{,}6667$ (2 cyfry); $x_2 = \frac{1}{2}(2{,}6667 + 2{,}625) = 2{,}64583$ (4-5 cyfr); $x_3 = 2{,}6457513$ (8 cyfr). Podwajanie cyfr widać jak na dłoni: 2 → 4 → 8. Trzy iteracje wystarczyły na dokładność, którą połowienie osiągałoby po ~25 krokach.

  1. Wyjaśnij intuicyjnie (bez pochodnych), dlaczego uśrednianie $x$ i $S/x$ zbliża do pierwiastka. Co gwarantuje, że pierwiastek leży między nimi?
Wskazówka i odpowiedź

Iloczyn $x \cdot \frac{S}{x} = S$ jest stały. Jeśli $x > \sqrt{S}$, to żeby iloczyn wyniósł $S$, drugi czynnik $\frac{S}{x}$ musi być $< \sqrt{S}$ — więc pierwiastek jest między nimi (jeden za duży, drugi za mały). Średnia dwóch liczb otaczających cel jest bliżej celu niż gorsza z nich — i to za każdym razem, coraz bliżej. Piękno metody: nie potrzeba analizy, wystarczy obserwacja o stałym iloczynie. Babilończycy myśleli właśnie tak — geometrią prostokąta o polu $S$, który iteracyjnie „kwadratowieje".

  1. Metoda Newtona dla $f(x) = x^2 - 2$ startuje od $x_0 = 0{,}0001$ (bardzo blisko zera). Co się stanie w pierwszym kroku i czemu to ilustruje słabość Newtona?
Wskazówka i odpowiedź

Wzór: $x_1 = \frac{1}{2}(0{,}0001 + 2/0{,}0001) = \frac{1}{2}(0{,}0001 + 20000) \approx 10000$ — pierwszy krok strzela z okolic zera na dziesięć tysięcy! (Styczna w punkcie prawie płaskim jest niemal pozioma i przecina oś bardzo daleko.) Potem metoda wprawdzie wróci i zbiegnie do $\sqrt{2}$, ale ta gwałtowność ilustruje kapryśność: zły start = dziki skok. Dla pierwiastka babilońska/Newton i tak w końcu zbiega (funkcja jest łagodna), ale dla trudniejszych równań taki skok może wpaść w inny pierwiastek albo rozbiec się na zawsze. Dlatego dobiera się punkt startowy z głową — albo zaczyna połowieniem.

🔍 Sprawdź, czy umiesz

  • Wykonać kilka kroków metody babilońskiej i pokazać podwajanie cyfr.
  • Wyjaśnić związek metody babilońskiej z Newtonem i rolę stycznej.
  • Uzasadnić progowy warunek stopu i wskazać handel szybkość–gwarancja wobec połowienia.

Ucz się tej jednostki z asystentem