nth root algorithm

The principal nth root ${\sqrt[{n}]{A}}$ of a positive real number A, is the positive real solution of the equation $x^{n}=A$. For a positive integer n there are n distinct complex solutions to this equation if $A>0$, but only one is positive and real.

Using 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 $x_{0}$
2. Set $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

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

So the derivative is

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

and the iteration rule is

$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 {1}{n}}\left[-x_{k}+{\frac {A}{x_{k}^{n-1}}}\right]$

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

See also

• Recurrence relation
• Shifting nth root algorithm
• Halley's method
• Householder's method

References

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