nth root algorithm

The principal nth root ${\displaystyle {\sqrt[{n}]{A}}}$ of a positive real number A, is the positive real solution of the equation

${\displaystyle x^{n}=A</mathForlarge''n'',the''n''^throotalgorithmissomewhatlessefficientsinceitrequiresthecomputationof<math>x_{k}^{n-1}}$ at each step, but can be efficiently implemented with a good exponentiation algorithm.

Derivation from Newton's method

Newton's method is a method for finding a zero of a function f(x). The general iteration scheme is:

1. Make an initial guess ${\displaystyle x_{0}}$ 
2. Set ${\displaystyle x_{k+1}=x_{k}-{\frac {f(x_{k})}{f'(x_{k})}}}$ 
3. Repeat step 2 until the desired precision is reached.

The n^th root problem can be viewed as searching for a zero of the function

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

So the derivative is

${\displaystyle f^{\prime }(x)=nx^{n-1}}$ 

and the iteration rule is

${\displaystyle x_{k+1}=x_{k}-{\frac {f(x_{k})}{f'(x_{k})}}}$ 

${\displaystyle =x_{k}-{\frac {x_{k}^{n}-A}{nx_{k}^{n-1}}}}$ 

${\displaystyle =x_{k}-{\frac {x_{k}}{n}}+{\frac {A}{nx_{k}^{n-1}}}}$ 

${\displaystyle ={\frac {1}{n}}\left[{(n-1)x_{k}+{\frac {A}{x_{k}^{n-1}}}}\right]}$ 

leading to the general n^th root algorithm.

See also

• Recurrence relation

References

• Atkinson, Kendall E. (1989), An introduction to numerical analysis (2nd ed.), New York: Wiley, ISBN 0-471-62489-6.