|
#REDIRECT [[Nth root#Computing principal roots]]
The principal ''n''th root <math>\sqrt[n]{A}</math> of a [[negative and positive numbers|positive]] [[real number]] ''A'', is the positive real solution of the equation
{{Redirect category shell|
:<math>x^n = A</math>
{{R to section}}
}}
(for integer ''n'' there are ''n'' distinct [[complex number|complex]] solutions to this equation if <math>A > 0</math>, but only one is positive and real).
There is a very fast-[[convergence|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}{n} \left[{(n-1)x_k +\frac{A}{x_k^{n-1}}}\right]</math>
#Repeat step 2 until the desired precision is reached.
A special case is the familiar [[Methods_of_computing_square_roots#Babylonian_method|square-root algorithm]]. By setting ''n'' = 2, the ''iteration rule'' in step 2 becomes the square root iteration rule:
:<math>x_{k+1} = \frac{1}{2}\left(x_k + \frac{A}{x_k}\right)</math>
In the case of ''n'' = 1/2 the rule also simplifies and becomes:
:<math>x_{k+1} = \frac{2 x_k} {1 + A x^2_k}</math>
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 <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, this algorithm is often used in computers as a very fast method to calculate square roots.
For large ''n'', the ''n''<sup>th</sup> root algorithm is somewhat less efficient since it requires the computation of <math>x_k^{n-1}</math> 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 <math>x_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.
The ''n''<sup>th</sup> root problem can be viewed as searching for a zero of the function
:<math>f(x) = x^n - A</math>
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)}{f'(x_k)}</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''<sup>th</sup> root algorithm.
== MANUAL NTH ROOT APPROXIMATION METHOD ==
Approximation of the nth root of a positive number may be done with the following method:
<math>X<sup>1/n</sup> = (A+B)<sup>1/n</sup>= A<sup>1/n</sup>+ B/(n(A<sup>1/n</sup>)<sup>n-1</sup></math>
where A is the n expansion of a trial root, which is close to X, and B is the complement of A to complete X.
Example; find the 5th root of 34.
Solution; 2<sup>5</sup> = 32 hence; 34<sup>1/5</sup> = (32 + 2)<sup>1/5</sup> = 2 + 2/(5x16) = 2 + 0.025 =2.025
The error in the approximation is only about 0.06 %
[[Category:Root-finding algorithms]]
[[fr:Algorithme de calcul de la racine n-ième]]
[[pl:Algorytm obliczania pierwiastka n-tego stopnia]]
| 