Nth root algorithm: Difference between revisions

Revision as of 08:28, 19 March 2005

Revision as of 03:25, 20 March 2005

Line 1:

ThereThe isprincipal a''n''-th very well knownroot <math>\sqrt[[Square_root#Square_roots_using_Newton_iteration|algorithm]] for calculating the [[square root]n]{A}</math> of a positive real number A, i.e.,is the positive real solution of the equation:

:<math>x^2n = A</math>

The algorithm is derived from [[Newton's method]] (also called the Newton-Raphson method) for finding zeros of a function <math>f(x)</math> 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, some variant of Newton's method is often used in computers to calculate square roots.

(For integer ''n'' there are ''n'' distinct complex solutions to this equation if <math>A > 0</math>, but only one is positive).

The Newton's method square root algorithm is:

There is a very fast-converging '''n-th root algorithm''' for finding <math>\sqrt[n]{A}</math>:

#Make an initial guess <math>x_0</math>

#Set <math>x_{k+1} = \frac{1}{2n} \left[{(n-1)x_k + \frac{A}{x_k^{n-1}}}\right)]</math>

#Repeat step 2 until the desired precision is reached.

This is a generalization of the well-known [[Square_root#Square_roots_using_Newton_iteration|square-root algorithm]]. By setting ''n'' = 2, the ''iteration rule'' in step 2 becomes the more familiar square root iteration rule:

This is derived from the general Newton's method for finding a zero of <math>f(x)</math> which uses the iteration rule

#Set :<math>x_{k+1} = \frac{1}{n2} \left[{(n-1)x_k + \frac{A}{x_k^{n-1}}}\right])</math>

TheSeveral different derivations of this algorithm isare derivedpossible. One [[N-th root algorithm#Derivation from Newton's method|derivation]] shows it is a special case of [[Newton's method]] (also called the Newton-Raphson method) for finding zeros of a function <math>f(x)</math> 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, somethis variant of Newton's methodalgorithm is often used in computers as a very fast method to calculate square roots.

:<math>x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}</math>

For large ''n'', the ''n''-th root algorithm is somewhat less efficient since it requires the computation of <math>x_k^n</math> at each step, but can be efficiently implemented with a good exponentiation algorithm.

with

:<math>f(x) = x^2 - A</math>

== Derivation from Newton's Method ==

as the function whose zero we are trying to find.

[[Newton's method]] is a method for finding a zero of a function ''f(x)''. The general iteration scheme is:

This is easily generalized to derive a fast-converging '''n-th root algorithm'''. The ''n''-th root of A is the solution of the equation

:#Make an initial guess <math>x^n = Ax_0</math>

:#Set <math>x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}</math>

#Repeat step 2 until the desired precision is reached.

andThe it''n''-th isroot problem can be viewed as searching for a zero of the function

:<math>f(x) = x^n - A</math>

Line 30 ⟶ 31:

So the derivative is

:<math>f'^\prime(x) = n x^{n-1}</math>

and the iteration rule is

:<math>x_{k+1} = x_k - \frac{f(x_k^n - A)}{n f'(x_k^{n-1})}</math>

:<math> = x_k - \frac{x_k^n - A}{n x_k^{n-1}}</math>

:<math> = x_k - \frac{x_k}{n}+\frac{A}{n x_k^{n-1}}</math>

:<math> = \frac{1}{n} \left[{(n-1)x_k +\frac{A}{x_k^{n-1}}}\right]</math>

Leading to the general ''n''-th root algorithm:

#Make an initial guess <math>x_0</math>

#Set <math>x_{k+1} = \frac{1}{n} \left[{(n-1)x_k +\frac{A}{x_k^{n-1}}}\right]</math>

#Repeat step 2 until the desired precision is reached.

Note that this requires a computation of <math>x_n^{n-1}</math> on each step, which for large ''n'' should be done with an exponentiation algorithm rather than repeated multiplication.

[[Category:Root-finding algorithms, Numerical analysis]]