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

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.