|
#REDIRECT [[Nth root#Computing principal roots]]
{{lowercase}}
{{Redirect category shell|
The 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
{{R to section}}
}}
:<math>x^n = A</math>
(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-[[Limit of a sequence|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>
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.
== N-th perfect root comes from Tartaglia's triangle and "Complicate Modulus" Method ==
Given C and n as integer, is possible to write that:
:<math>C^n =\sum_{x=1}^{C}[x^n-(x-1)^n]</math>.
Since this sum can be used for any integer C and n, we call M(n) Complicate modulus:
:<math> M(n)=[x^n -(x-1)^n] </math>.
How to have the Complicate modulus M(n):
M(n) comes from Tartaglia's envelope of <math>(x-1)^n</math> in this way:
Remembering Tartaglia's triange:
n=0 1
n=1 1 1
n=2 1 2 1 M(2) = (2x-1)
n=3 1 3 3 1 M(3) = (3x^2-3x+1) etc...
n=4 1 4 6 4 1 M(4) = (4x^3-6x^2+4x-1) etc...
So our complicate modulus M(n) is the n row, less first element, changing all the signs.
Example if n=2 :
:<math>C^2 =\sum_{x=1}^{C}[x^2-(x-1)^2]</math>.
That is the very well known odds sum:
:<math> C^2 = 1+3+5+7+9+ ... +[C^2-(C-1)^2)</math>.
Example if n=3 :
:<math>C^3 =\sum_{x=1}^{C}[x^3-(x-1)^3]</math>.
Or special odds sum:
:<math> C^3 = 1+7+19... +[x^3-(x-1)^3)</math>.
etc...
=== Why "Complicate Modulus" ? ===
Because this is a special clock characterized by:
- 2 hands: the shortest one show the Numbers of Turns, the longer one the Rest
- at each turn the numbers of division of the clock turn change by the complicate modulus that is the known function.
- The complicate modulus must be declared onto the clock to understand which function we are using.
=== How to make the n-th root: ===
If we want to make the 3-th root of 27 we:
1) From Tartaglia's envelope of (x-1)^n we keep n=3 row,
n=3 1 -3 +3 -1
- we ellimiate the first value
-3 3 -1
- we change all the signs:
3 -3 1
So we have the complicate modulus M(3):
:<math> M(3)= 3x^2 - 3x + 1 </math>.
We call X the numbers of complete turns of the short hand and
M(3)x [or M(3) calculated in x], is the number of division we will see onto the clock
So at the 1st turn we will see:
turn: x=1
M(3)x = 3x^2 - 3x + 1 = 1 division
at the 2th we will see:
turn: x=2
M(3)x = 3x^2 - 3x + 1 = 7 division
at the 3th we will see:
turn: x=3
M(3)x = 3x^2 - 3x + 1 = 19 division etc...
=== To make the 3rd root of 27 so we have to tabulate: ===
x <math> M(3)= 3x^2 - 3x + 1 </math> 27
1 1 27-1 = 26
2 7 26-7 = 19
3 19 19-19 = 0 <- REST
So the 3th root of 27 is 3 and since the rest is zero this is a perfect cube.
So we can wrote
<math> 27 = 3M(3)+ 0 </math> or <math> 27= 3^3</math>
In case we have the 3rd root of 28 without make other calculation we can say that will be:
<math> 31 = 3m(3) + 1 </math> or <math> 31 = 3^3 +1 </math> etc….
To confirm we can just tabulate again:
x <math> M(3)= 3x^2 - 3x + 1 </math> 28
1 1 28-1 = 27
2 7 27-7 = 20
3 19 20-19 = 1 <- REST
So:
<math> 28 = 3m(3) + 1 </math> or <math> 28 = 3^3 +1 </math> etc….
Was clear that this method is intriguing since in case we have to make a very long series of root calculation we never loose of precision during the calculation...
=== Note ===
We also note that M(n-1)= n* derivative of (M(n)
Example:
M(2) = 3 * derivative of M(3) = 3* derivative (3x^2 - 3x + 1) = 3* (2x-1)
In fact M(2) = (2x-1)
==References==
*{{Citation |first=Kendall E. |last=Atkinson |title=An introduction to numerical analysis |___location=New York |publisher=Wiley |year=1989 |edition=2nd |isbn=0471624896 }}.
[[Category:Root-finding algorithms]]
[[fr:Algorithme de calcul de la racine n-ième]]
[[pl:Algorytm obliczania pierwiastka n-tego stopnia]]
| 