Algorytm obliczania pierwiastka n-tego stopnia

Algorytm obliczania pierwiastka n-tego stopnia – metoda przybliżonego obliczania wartości pierwiastka arytmetycznego stopnia n z danej dodatniej liczby A.

Algorytm ten charakteryzuje się niezwykle szybką zbieżnością.

Działanie algorytmu:

Na początku przyjmij jako pierwsze przybliżenie liczby A wartość x0, która może być dowolną liczbą, na przykład x0 = [A].

Kolejne przybliżenie xk+1 obliczysz według wzoru:

  • xk+1 = (1/n) * ((n-1) * xk + (A / xkn-1))

Powtarzaj ten krok, aż osiągniesz wymaganą dokładność przybliżenia.

Metoda ta opiera się na algorytmie Newtona-Raphsona, który służy do znajdowania miejsc zerowych funkcji. W typowych przypadkach, metoda ta zbiega się bardzo szybko – błąd maleje jak funkcja kwadratowa, co w praktyce oznacza, że przy każdym kroku liczba dokładnych cyfr przybliżenia jest podwajana.

Dla dużych wartości n algorytm może być niewygodny, ponieważ wymaga obliczania potęgi xkn-1 na każdym etapie. Częściowym rozwiązaniem tego problemu jest zastosowanie algorytmu szybkiego potęgowania.

Uzasadnienie algorytmu

Metoda Newtona-Raphsona służy do wyznaczania miejsc zerowych funkcji f(x). Jej działanie przebiega następująco:

Wybierz przybliżoną wartość x0. Następnie oblicz kolejne przybliżenia zgodnie z wzorem:

  • xk+1 = xk – (f(xk) / f'(xk)), k = 0, 1, …

Powtarzaj te kroki, aż uzyskasz żądaną dokładność przybliżenia.

Wyznaczanie pierwiastka n-tego stopnia z liczby A można traktować jako znajdowanie miejsc zerowych funkcji f(x) = xn – A. Pochodna tej funkcji to f'(x) = n * xn-1.

Rekurencyjny wzór daje w efekcie:

  • xk+1 = xk – (xkn – A) / (n * xkn-1)

Ostatecznie prowadzi to do wzoru:

  • xk+1 = (1/n) * ((n-1) * xk + (A / xkn-1))

Jest to właśnie algorytm wyznaczania pierwiastka.

Przykład

Za pomocą metody Newtona można obliczyć pierwiastek √a dla każdej liczby a ∈ R+. Możemy zapisać, że √a = x ⟺ a = x2 ⟺ x2 – a = 0.

Funkcja f(x) jest zdefiniowana jako:

  • f(x) = x2 – a

Pochodna tej funkcji to f'(x) = 2x.

Rekurencyjny wzór można zapisać jako:

  • xk+1 = xk – (xk2 – a) / (2xk)

Wynika z tego:

  • xk+1 = (1/2) * (xk + (a / xk))

Dla przykładowych danych a = 2 i x0 = 1.5 algorytm będzie wyglądał następująco:

x0 = 1.5.

Obliczamy następne wartości:

  • x1 ≈ 1.416666
  • x2 ≈ 1.414214
Przeczytaj u przyjaciół: