Algorytm obliczania pierwiastka n-tego stopnia

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

Działanie algorytmu:

1. Jako pierwsze przybliżenie liczby ${\displaystyle {\sqrt[{n}]{A}}}$ przyjmij dowolną liczbę ${\displaystyle x_{0}.}$ Może to być np. ${\displaystyle x_{0}=[A].}$
2. Za kolejne przybliżenie weź ${\displaystyle 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 ${\displaystyle n}$ algorytm może być niewygodny, wymaga bowiem obliczania na każdym kroku potęgi ${\displaystyle x_{k}^{n-1}.}$ Częściowym rozwiązaniem tego problemu może być użycie algorytmu szybkiego potęgowania.

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

1. Wybierz przybliżoną wartość ${\displaystyle x_{0}.}$
2. Za kolejne przybliżenia weź ${\displaystyle x_{k+1}=x_{k}-{\frac {f(x_{k})}{f'(x_{k})}},k=0,1,\dots }$Po
3. owtarzaj 2 tak długo, aż otrzymasz wymaganą dokładność przybliżenia.

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

${\displaystyle f(x)=x^{n}-A.}$

Pochodna jest równa ${\displaystyle f'(x)=nx^{n-1},}$ a kolejne obliczenia dają ${\displaystyle 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.

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

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

Funkcja ${\displaystyle f(x)}$ ma postać:

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

${\displaystyle f'(x)=2x.}$

Rekurencyjny wzór wynosi:

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

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

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

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

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

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