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 integer n there are n distinct complex solutions to this equation if $A>0$ , but only one is positive and real).

There is a very fast-converging nth root algorithm for finding ${\sqrt[{n}]{A}}$ :

Make an initial guess $x_{0}$
Set $x_{k+1}={\frac {1}{n}}\left[{(n-1)x_{k}+{\frac {A}{x_{k}^{n-1}}}}\right]$ . In practice we do $\Delta x_{k}={\frac {1}{n}}\left[{\frac {A}{x_{k}^{n-1}}}-x_{k}\right];x_{k+1}=x_{k}+\Delta x_{k}$ .
Repeat step 2 until the desired precision is reached, i.e. $|\Delta x_{k}|<\epsilon$ .

A special case is the familiar square-root algorithm. By setting n = 2, the iteration rule in step 2 becomes the square root iteration rule:

x_{k+1}={\frac {1}{2}}\left(x_{k}+{\frac {A}{x_{k}}}\right)

Several different derivations of this algorithm are possible. One derivation shows it is a special case of Newton's method (also called the Newton-Raphson method) for finding zeros of a function $f(x)$ beginning with an initial guess. Although Newton's method is iterative, meaning it approaches the solution through a series of increasingly accurate guesses, it converges very quickly. The rate of convergence is quadratic, meaning roughly that the number of bits of accuracy doubles on each iteration (so improving a guess from 1 bit to 64 bits of precision requires only 6 iterations). For this reason, this algorithm is often used in computers as a very fast method to calculate square roots.

For large n, the n^th root algorithm is somewhat less efficient since it requires the computation of $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:

Make an initial guess $x_{0}$
Set $x_{k+1}=x_{k}-{\frac {f(x_{k})}{f'(x_{k})}}$
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 {x_{k}}{n}}+{\frac {A}{nx_{k}^{n-1}}}

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

leading to the general n^th root algorithm.

References

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

This article is issued from Wikipedia - version of the 11/12/2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

nth root algorithm

Derivation from Newton's method

See also

References