Editing Nth root (section)

===Using Newton's method===

The {{mvar|n}}th root of a number {{math|''A''}} can be computed with [[Newton's method]], which starts with an initial guess {{math|''x''<sub>0</sub>}} and then iterates using the [[recurrence relation]]

<math display="block">x_{k+1} = x_k-\frac{x_k^n-A}{nx_k^{n-1}}</math>

until the desired precision is reached. For computational efficiency, the recurrence relation is commonly rewritten 

<math display="block">x_{k+1} = \frac{n-1}{n}\,x_k+\frac{A}{n}\,\frac 1{x_k^{n-1}}.</math>

This allows to have only one [[exponentiation]], and to compute once for all the first factor of each term.

For example, to find the fifth root of 34, we plug in {{math|1=''n'' = 5, ''A'' = 34}} and {{math|1=''x''<sub>0</sub> = 2}} (initial guess). The first 5 iterations are, approximately:

{{block indent|{{math|1=''x''<sub>0</sub> = 2}}}}
{{block indent|{{math|1=''x''<sub>1</sub> = 2.025}}}}
{{block indent|{{math|1=''x''<sub>2</sub> = 2.02439 7...}}}}
{{block indent|{{math|1=''x''<sub>3</sub> = 2.02439 7458...}}}}
{{block indent|{{math|1=''x''<sub>4</sub> = 2.02439 74584 99885 04251 08172...}}}}
{{block indent|{{math|1=''x''<sub>5</sub> = 2.02439 74584 99885 04251 08172 45541 93741 91146 21701 07311 8...}}}}

(All correct digits shown.)

The approximation {{math|''x''<sub>4</sub>}} is accurate to 25 decimal places and {{math|''x''<sub>5</sub>}} is good for 51.

Newton's method can be modified to produce various [[generalized continued fraction#Roots of positive numbers|generalized continued fractions]] for the ''n''th root. For example,

<math display="block">
  \sqrt[n]{z} = \sqrt[n]{x^n+y} = x+\cfrac{y} {nx^{n-1}+\cfrac{(n-1)y} {2x+\cfrac{(n+1)y} {3nx^{n-1}+\cfrac{(2n-1)y} {2x+\cfrac{(2n+1)y} {5nx^{n-1}+\cfrac{(3n-1)y} {2x+\ddots}}}}}}.
</math>