|
#REDIRECT [[Nth root#Computing principal roots]]
{{DISPLAYTITLE:''n''th root algorithm}}
The [[Principal branch|principal]] [[nth root|''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 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.
==See also==
*[[Recurrence relation]]
==References==
*{{Citation |first=Kendall E. |last=Atkinson |title=An introduction to numerical analysis |___location=New York |publisher=Wiley |year=1989 |edition=2nd |isbn=0-471-62489-6 }}.
[[Category:Root-finding algorithms]]
| 