Iteracyjna metoda obliczania pierwiastka kwadratowego – metoda Herona, znana od starożytności.
Metoda Babilońska (zwana też metodą Herona) to bardzo szybki algorytm numeryczny do przybliżonego obliczania pierwiastka kwadratowego liczby S.
Idea: zaczynamy od dowolnego początkowego przybliżenia x (najczęściej x = S). Następnie wielokrotnie aplikujemy wzór:
x_{n+1} = (x_n + S/x_n) / 2
Jest to średnia arytmetyczna liczby x i S/x. Geometrycznie: jeśli x jest za duże, to S/x jest za małe (i odwrotnie). Ich średnia daje znacznie lepsze przybliżenie. Iterujemy dopóki różnica między x² a S nie zejdzie poniżej zadanej dokładności eps.
Wyjątkowa szybkość zbieżności: liczba poprawnych cyfr podwaja się w każdej iteracji. Dla S = 2 już po 5 iteracjach mamy dokładność 10⁻¹⁵. Dlatego O(log n) jest złożonością "po liczbie cyfr dokładności" – w praktyce wystarcza kilka iteracji.
Powiązanie z metodą Newtona: metoda Babilońska to szczególny przypadek metody Newtona zastosowanej do funkcji f(x) = x² - S.
funkcja pierwiastek_babilonski(S, eps): jeżeli S < 0: zwróć błąd jeżeli S = 0: zwróć 0 // początkowe przybliżenie x ← S dopóki |x * x - S| > eps: x ← (x + S / x) / 2 zwróć x
def pierwiastek_babilonski(s, eps=1e-9):
if s < 0:
raise ValueError("Liczba musi być nieujemna")
if s == 0:
return 0
x = s
while abs(x * x - s) > eps:
x = (x + s / x) / 2
return x
# Przykład użycia
print(pierwiastek_babilonski(2))
# Wynik: 1.4142135623746899
print(pierwiastek_babilonski(144))
# Wynik: 12.0O(log n)O(1)Zagadnienia z tego samego obszaru matury – warto je powtórzyć razem: