Algoritmus pro nalezení kořene n-tého stupně

Aritmetický kořen --tého stupně $n$ kladného reálného čísla je kladné reálné řešení rovnice (pro celou rovnici existují komplexní řešení, jestliže , ale pouze jedno je kladné reálné). ${\sqrt[{n}]{A))$ $A$ $x^{n}=A$ $n$ $n$ $A>0$

Existuje rychlý konvergentní algoritmus pro nalezení kořene -tého stupně $n$ :

Proveďte počáteční odhad ; $x_{0}$
Set ; $x_{k+1}={\frac {1}{n}}\left({(n-1)x_{k}+{\frac {A}{x_{k}^{n-1 }}}}\že jo)$
Opakujte krok 2, dokud nedosáhnete požadované přesnosti.

Speciálním případem je Heronův iterační vzorec pro nalezení druhé odmocniny , který získáme dosazením do kroku 2: . $n=2$ $x_{k+1}=(x_{k}+A/x_{k})/2$

Tento algoritmus má několik důsledků. Jeden z nich považuje algoritmus za speciální případ Newtonovy metody (také známé jako metoda tečny ) pro nalezení nul funkce , daný počáteční odhad. Přestože je Newtonova metoda iterativní, velmi rychle konverguje. Metoda má kvadratickou míru konvergence - to znamená, že počet správných bitů v odpovědi se s každou iterací zdvojnásobuje (to znamená, že zvýšení přesnosti nalezení odpovědi z 1 na 64 bitů vyžaduje pouze 6 iterací, ale nezapomeňte na stroj přesnost ). Z tohoto důvodu se tento algoritmus používá v počítačích jako velmi rychlá metoda pro hledání odmocnin. $f(x)$

Pro velké hodnoty se tento algoritmus stává méně účinným, protože v každém kroku je vyžadován výpočet, který však lze provést pomocí algoritmu rychlého umocňování . $n$ $x_{k}^{{n-1}}$

Odvození z Newtonovy metody

Newtonova metoda je metoda pro nalezení nul funkce . Obecné iterační schéma: $f(x)$

Proveďte počáteční odhad $x_{0};$
Set ; $x_{k+1}=x_{k}-{\frac {f(x_{k})}{f'(x_{k)))))$
Opakujte krok 2, dokud nedosáhnete požadované přesnosti.

Problém nalezení kořene tého stupně lze považovat za nalezení nuly funkce, jejíž derivace je rovna . $n$ $f(x)=x^{n}-A$ ${\displaystyle f'(x)=nx^{n-1))$

Pak má formu druhý krok Newtonovy metody

{\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))

Odkazy

Atkinson, Kendall E. (1989), Úvod do numerické analýzy (2. vyd.), New York: Wiley, ISBN 0471624896 .