Algoritm pentru găsirea rădăcinii gradului al n-lea

Rădăcina aritmetică a gradului - al unui $n$ număr real pozitiv este o soluție reală pozitivă a ecuației (pentru întregul , există soluții complexe ale acestei ecuații dacă , dar numai una este reală pozitivă). ${\sqrt[{n}]{A))$ $A$ $x^{n}=A$ $n$ $n$ $A>0$

Există un algoritm rapid convergent pentru găsirea rădăcinii gradului --lea $n$ :

Faceți o presupunere inițială ; $x_{0}$
Set ; $x_{k+1}={\frac {1}{n}}\left({(n-1)x_{k}+{\frac {A}{x_{k}^{n-1 }}}}\dreapta)$
Repetați pasul 2 până când se obține precizia dorită.

Un caz special este formula iterativă a lui Heron pentru găsirea rădăcinii pătrate , care se obține prin înlocuirea în pasul 2: . $n=2$ $x_{k+1}=(x_{k}+A/x_{k})/2$

Există mai multe implicații ale acestui algoritm. Unul dintre ele tratează algoritmul ca un caz special al metodei lui Newton (cunoscută și ca metoda tangentei ) pentru găsirea zerourilor unei funcții , având în vedere o estimare inițială. Deși metoda lui Newton este iterativă, ea converge foarte repede. Metoda are o rată de convergență pătratică - aceasta înseamnă că numărul de biți corecti din răspuns se dublează cu fiecare iterație (adică, creșterea preciziei de găsire a răspunsului de la 1 la 64 de biți necesită doar 6 iterații, dar nu uitați de mașină) . precizie ). Din acest motiv, acest algoritm este folosit în computere ca o metodă foarte rapidă de găsire a rădăcinilor pătrate. $f(x)$

Pentru valori mari , acest algoritm devine mai puțin eficient, deoarece este necesar un calcul la fiecare pas, care, totuși, poate fi efectuat folosind algoritmul de exponențiere rapidă . $n$ $x_{k}^{{n-1}}$

Derivarea din metoda lui Newton

Metoda lui Newton este o metodă de găsire a zerourilor unei funcții . Schema generală iterativă: $f(x)$

Faceți o ghicire inițială $x_{0};$
Set ; $x_{k+1}=x_{k}-{\frac {f(x_{k})}{f'(x_{k))))}$
Repetați pasul 2 până când se obține precizia dorită.

Problema găsirii rădăcinii gradului al-lea poate fi considerată ca găsirea zeroului funcției a cărei derivată este egală cu . $n$ $f(x)=x^{n}-A$ $f'(x)=nx^{n-1)$

Apoi, al doilea pas al metodei lui Newton ia forma

{\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))))\dreapta].\end{aliniat))

Link -uri

Atkinson, Kendall E. (1989), O introducere în analiza numerică (ed. a doua), New York: Wiley, ISBN 0471624896 .