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}$. For a positive integer n there are n distinct complex solutions to this equation if ${\displaystyle 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 ${\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 {1}{n}}\left[-x_{k}+{\frac {A}{x_{k}^{n-1}}}\right]}$ 

${\displaystyle ={\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.