Algorytm obliczania pierwiastka n-tego stopnia

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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

Działanie algorytmu:

  1. Jako pierwsze przybliżenie liczby przyjmij dowolną liczbę . Może to być np. .
  2. Za kolejne przybliżenie weź
  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 algorytm może być niewygodny, wymaga bowiem obliczania na każdym kroku potęgi . Częściowym rozwiązaniem tego problemu może być użycie algorytmu szybkiego potęgowania.

Uzasadnienie algorytmu[edytuj]

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

  1. Wybierz przybliżoną wartość
  2. Za kolejne przybliżenie weź
  3. Powtarzaj 2 tak długo, aż otrzymasz wymaganą dokładność przybliżenia.

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

Pochodna jest równa a kolejne obliczenia dają , czyli właśnie algorytm wyznaczania pierwiastka.

Przykład[edytuj]

Za pomocą metody Newtona można obliczyć pierwiastek dla każdej liczby

Funkcja f(x) ma postać:

Rekurencyjny wzór wynosi:

Dla danych i algorytm przebiega następująco: