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 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

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'(x)=nx^{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}{nx_{k}^{n-1}}}=x_{k}-{\frac {x_{k}}{n}}+{\frac {A}{nx_{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.

Przykład

Za pomocą metody Newtona można obliczyć pierwiastek ${\sqrt {a}}$ dla każdej liczby $a\in \mathbb {R} ^{+}{:}$

${\sqrt {a}}=x\iff a=x^{2}\iff x^{2}-a=0.$

Funkcja $f(x)$ ma postać:

$f(x)=x^{2}-a,$

$f'(x)=2x.$

Rekurencyjny wzór wynosi:

$x_{k+1}=x_{k}-{\frac {x_{k}^{2}-a}{2x_{k}}},$

$x_{k+1}={\frac {1}{2}}\left(x_{k}+{\frac {a}{x_{k}}}\right).$

Dla danych $a=2$ i $x_{0}=1{,}5$ algorytm przebiega następująco:

$x_{0}=1{,}5.$

$x_{1}={\frac {1}{2}}\left(1{,}5+{\frac {2}{1{,}5}}\right)\approx 1{,}416666.$

$x_{2}={\frac {1}{2}}\left(1{,}416666+{\frac {2}{1{,}416666}}\right)\approx 1{,}414214.$