Nth root algorithm: Difference between revisions

Revision as of 12:10, 29 July 2020

Latest revision as of 14:36, 29 July 2020

(2 intermediate revisions by the same user not shown)

Line 1:

#REDIRECT [[Nth root#Computing principal roots]]

{{DISPLAYTITLE:''n''th root algorithm}}

{{Redirect category shell|

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 <math>x^n = a</math>. For a positive 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.

{{R to section}}

}}

==Using 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''^th 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{1}{n} \left[-x_k +\frac{a}{x_k^{n-1}}\right]</math>

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

==See also==

*[[Recurrence relation]]

*[[Shifting nth root algorithm|Shifting ''n''th root algorithm]]

*[[Halley's method]]

*[[Householder's method]]

==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]]