Algorytm obliczania pierwiastka n-tego stopnia

Z testwiki
Przejdź do nawigacji Przejdź do wyszukiwania

Algorytm obliczania pierwiastka n-tego stopnia – metoda przybliżonego obliczania wartości pierwiastka arytmetycznego stopnia n z danej dodatniej liczby A. Algorytm ten charakteryzuje bardzo szybka zbieżność.

Działanie algorytmu:

  1. Jako pierwsze przybliżenie liczby An przyjmij dowolną liczbę x0. Może to być np. x0=[A].
  2. Za kolejne przybliżenie weź xk+1=1n((n−1)xk+Axkn−1).
  3. Powtarzaj 2 tak długo, aż otrzymasz wymaganą dokładność przybliżenia.

Algorytm obliczania pierwiastka wynika w prosty sposób z metody Newtona-Raphsona znajdowania miejsc zerowych funkcji. W typowych przypadkach metoda ta jest bardzo szybko zbieżna – błąd maleje jak funkcja kwadratowa, co w praktyce oznacza, że na każdym kroku podwaja się liczba dokładnych cyfr przybliżenia.

Dla dużych n algorytm może być niewygodny, wymaga bowiem obliczania na każdym kroku potęgi xkn−1. Częściowym rozwiązaniem tego problemu może być użycie algorytmu szybkiego potęgowania.

Uzasadnienie algorytmu

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

  1. Wybierz przybliżoną wartość x0.
  2. Za kolejne przybliżenia weź xk+1=xk−f(xk)f′(xk),k=0,1,…Po
  3. owtarzaj 2 tak długo, aż otrzymasz wymaganą dokładność przybliżenia.

Wyznaczanie pierwiastka n-tego stopnia z liczby A może być traktowane jako znajdowanie miejsc zerowych funkcji

f(x)=xn−A.

Pochodna jest równa f′(x)=nxn−1, a kolejne obliczenia dają xk+1=xk−f(xk)f′(xk)=xk−xkn−Anxkn−1=xk−xkn+Anxkn−1=1n((n−1)xk+Axkn−1), czyli właśnie algorytm wyznaczania pierwiastka.

Przykład

Za pomocą metody Newtona można obliczyć pierwiastek a dla każdej liczby a∈ℝ+:

a=x⟺a=x2⟺x2−a=0.

Funkcja f(x) ma postać:

f(x)=x2−a,
f′(x)=2x.

Rekurencyjny wzór wynosi:

xk+1=xk−xk2−a2xk,
xk+1=12(xk+axk).

Dla danych a=2 i x0=1,5 algorytm przebiega następująco:

x0=1,5.
x1=12(1,5+21,5)≈1,416666.
x2=12(1,416666+21,416666)≈1,414214.
Źródło: „https://pl.wiki.beta.math.wmflabs.org/w/index.php?title=Algorytm_obliczania_pierwiastka_n-tego_stopnia&oldid=4587”