Wpisany przez Jan Wojciechowski,
25 września 2012 14:50
Chcemy policzyć pierwiastek stopnia n z liczby a:
Przytoczony tutaj algorytm obliczania pierwiastka wynika bezpośrednio z metody Newtona:
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.
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 } k=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
Ustawiając w tym przypadku e na zero, obliczymy wynik z makmsymalną możliwą dokładnością - kolejne przybliżenie jest tak blisko poprzedniego, że jest reprezentowane przez tą samą wartość.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 = 5Począ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:
n
√
a
= wynik
Implementacje
| Autor | Język programowania | Komentarz | Otwórz | Pobierz | Ocena |
| Michał Witaszek | C/C++ | C++ | .cpp | .cpp | ***** / 24 |
| Tomasz Lubiński | JavaScript | .js | .js | ***** / 7 |
Poprawiony: 02 października 2019 12:19
