algorytm.org

Obliczanie pierwiastka n-tego stopnia

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Obliczanie pierwiastka n-tego stopnia
Ocena użytkowników:***** / 9
SłabyŚwietny 
Wpisany przez Jan Wojciechowski, 25 września 2012 14:50

Chcemy policzyć pierwiastek stopnia n z liczby a:
x = \sqrt[n]{a} \text{ gdzie } a \in R+, n \in N.
Metoda polega na znajdowaniu kolejnych, coraz dokładniejszych przybliżeń pierwiastka. Najpierw przyjmujemy, że pierwszym przybliżeniem jest liczba pierwiastkowana.
x_0 = a
Następnie obliczamy kolejne przybliżenia stosując odpowiedni wzór:
x_{k+1}=\frac{1}{n}\left((n-1)x_k+\frac{a}{x^{n-1}_k}\right)\text{ dla } j=0,1,2,...
Jak stwierdzić, że osiągnęliśmy odpowiednią dokładność? Można wybrać jakąś bardzo małą liczbę – oznaczmy ją e – i przerwać przybliżanie pierwiastka gdy spełniony będzie warunek:
|a-x_k^n|<e
Warto zwrócić uwagę, że licząc przybliżenie musimy policzyć xkn-1, zatem obliczenie xkn to kwestia tylko jednego mnożenia: xkn = xkn-1 ∙ xk Przybliżanie można też przerwać gdy:
|x_k-x_{k+1}|<e
Przytoczony tutaj algorytm obliczania pierwiastka wynika bezpośrednio z metody Newtona:
x = \sqrt[n]{a}\\\\ x - \sqrt[n]{a} = 0\\\\ x^n - a = 0\\\\ x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)} = x_k - \frac{x_k^n - a}{n*x_k^{n-1}} =\\\\ x_k - \frac{x_k^n}{n*x^{n-1}_k} + \frac{a}{n*x^{n-1}_k} = \frac{n*x_k}{n} - \frac{x_k}{n} + \frac{a}{n*x^{n-1}_k} =\\\\ \frac{n*x_k - x_k}{n} + \frac{a}{n*x^{n-1}_k} = \frac{(n-1)*x_k}{n} + \frac{a}{n*x^{n-1}_k} =\\\\ \frac{1}{n}\left((n-1)x_k+\frac{a}{x^{n-1}_k}\right)

Przykład:
Obliczymy wartość pierwiastka kwadratowego z 5. Zatem n = 2, a = 5
Początkowe rozwiązanie x = a = 5
W tej chwili błąd przybliżenia wynosi |a - xn| = |5 - 52| = |5 - 25| = 20
Kolejne przybliżenie x = 0.5 * ((2-1)5 + 5/51) = 0.5(5 + 1) = 0.5*6 = 3
Teraz błąd przybliżenia wynosi |a - xn| = |5 - 32| = |5 - 9| = 4
Następne przybliżenie x = 0.5 * ((2-1)3 + 5/31) = 0.5(3 + 1.6666667) = 0.5*4.6666667 = 2.33333335
Teraz błąd przybliżenia wynosi |a - xn| = |5 - 2.333333352| = |5 - 5.4444445| = 0.4444445
Kolejne przybliżenie x = 0.5 * ((2-1)2.33333335 + 5/2.333333351) = 0.5(2.33333335 + 2.1428571) = 0.5*4.47619045 = 2.2380952
W tej chwili błąd przybliżenia wynosi |a - xn| = |5 - 2.23809522| = |5 - 5.0090701| = 0.0090701
Jak widać kolejne obliczenia bardzo szybko zbliżają nas do dokładnego wyniku.

Przykład w JavaScript:
Liczba pierwiastkowana (a)
Podstawa pierwiastka (n)
n
a
=
wynik

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Michał WitaszekC/C++C++
.cpp
.cpp
***** / 6
Tomasz LubińskiJavaScript
.js
.js
***** / 0
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 26 września 2012 19:29
Dodaj komentarz

Kod antysapmowy Odśwież