Algorytm obliczania pierwiastka n-tego stopnia

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Algorytm obliczania pierwiastka n-tego stopnia – to 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 \sqrt[n]{A}\, przyjmij dowolną liczbę x_0. Może to być np. x_0=[A]\,.
  2. Za kolejne przybliżenie weź x_{k+1} = \frac{1}{n} \left({(n-1)x_k +\frac{A}{x_k^{n-1}}}\right).
  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 x_k^{n-1}\,. Częściowym rozwiązaniem tego problemu może być użycie algorytmu szybkiego potęgowania.

Uzasadnienie algorytmu[edytuj | edytuj kod]

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ść x_0\,
  2. Za kolejne przybliżenie weź x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}.
  3. Powtarzaj 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) = x^n - A.

Pochodna jest równa f^\prime(x) = n x^{n-1},\, a kolejne obliczenia dają x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}= x_k - \frac{x_k^n - A}{n x_k^{n-1}}= x_k - \frac{x_k}{n}+\frac{A}{n x_k^{n-1}} = \frac{1}{n} \left({(n-1)x_k +\frac{A}{x_k^{n-1}}}\right), czyli właśnie algorytm wyznaczania pierwiastka.

Linki zewnętrzne[edytuj | edytuj kod]

Funkcje obliczające pierwiastek sześcienny (pol.)) - Gotowe algorytmy dla programistów.