Algoritm för att hitta roten till den n:e graden

Den aritmetiska roten av den -e graden av ett $n$ positivt reellt tal är en positiv reell lösning på ekvationen (för helheten finns det komplexa lösningar på denna ekvation om , men bara en är positiv reell). ${\sqrt[{n}]{A))$ $A$ $x^{n}=A$ $n$ $n$ $A>0$

Det finns en snabb konvergent algoritm för att hitta roten till den -e graden $n$ :

Gör en första gissning ; $x_{0}$
Set ; $x_{k+1}={\frac {1}{n}}\left({(n-1)x_{k}+{\frac {A}{x_{k}^{n-1 }}}}\höger)$
Upprepa steg 2 tills önskad noggrannhet uppnås.

Ett specialfall är Herons iterativa formel för att hitta kvadratroten , som erhålls genom att ersätta i steg 2: . $n=2$ $x_{k+1}=(x_{k}+A/x_{k})/2$

Det finns flera implikationer av denna algoritm. En av dem behandlar algoritmen som ett specialfall av Newtons metod (även känd som tangentmetoden ) för att hitta nollorna i en funktion , givet en första gissning. Även om Newtons metod är iterativ, konvergerar den väldigt snabbt. Metoden har en kvadratisk konvergenshastighet - detta betyder att antalet korrekta bitar i svaret fördubblas med varje iteration (det vill säga att öka noggrannheten för att hitta svaret från 1 till 64 bitar kräver bara 6 iterationer, men glöm inte maskinen noggrannhet ). Av denna anledning används denna algoritm i datorer som en mycket snabb metod för att hitta kvadratrötter. $f(x)$

För stora värden blir denna algoritm mindre effektiv, eftersom en beräkning krävs vid varje steg, som dock kan utföras med den snabba exponentieringsalgoritmen . $n$ $x_{k}^{{n-1}}$

Härledning från Newtons metod

Newtons metod är en metod för att hitta nollorna i en funktion . Allmänt iterativt schema: $f(x)$

Gör en första gissning $x_{0};$
Set ; $x_{k+1}=x_{k}-{\frac {f(x_{k})}{f'(x_{k)))))$
Upprepa steg 2 tills önskad noggrannhet uppnås.

Problemet med att hitta roten till den e graden kan betraktas som att hitta nollpunkten för den funktion vars derivata är lika med . $n$ $f(x)=x^{n}-A$ ${\displaystyle f'(x)=nx^{n-1))$

Sedan tar det andra steget av Newtons metod formen

{\begin{aligned}x_{k+1}&=x_{k}-{\frac {f(x_{k})}{f'(x_{k)))))\\&= x_ {k}-{\frac {x_{k}^{n}-A}{nx_{k}^{n-1))}\\&=x_{k}+{\frac {1}{n } }\left[{\frac {A}{x_{k}^{n-1}}}-x_{k}\right]\\&={\frac {1}{n}}\left[{ ( n-1)x_{k}+{\frac {A}{x_{k}^{n-1))))\right].\end{aligned))

Länkar

Atkinson, Kendall E. (1989), An introduction to numerical analysis (2nd ed.), New York: Wiley, ISBN 0471624896 .