nth root algorithm

The principal nth root [math]\displaystyle{ \sqrt[n]{A} }[/math] of a positive real number A, is the positive real solution of the equation [math]\displaystyle{ x^n = A }[/math]. For a positive integer n there are n distinct complex solutions to this equation if [math]\displaystyle{ A \gt 0 }[/math], 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 [math]\displaystyle{ x_0 }[/math]
2. Set [math]\displaystyle{ x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)} }[/math]
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

[math]\displaystyle{ f(x) = x^n - A }[/math]

So the derivative is

[math]\displaystyle{ f^\prime(x) = n x^{n-1} }[/math]

and the iteration rule is

[math]\displaystyle{ x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)} }[/math]

[math]\displaystyle{ = x_k - \frac{x_k^n - A}{n x_k^{n-1}} }[/math]

[math]\displaystyle{ = x_k + \frac{1}{n} \left[-x_k +\frac{A}{x_k^{n-1}}\right] }[/math]

[math]\displaystyle{ = \frac{1}{n} \left[{(n-1)x_k +\frac{A}{x_k^{n-1}}}\right]\,. }[/math]

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 .