Do wyznaczania pierwiastka kwadratowego liczby dodatniej można wykorzystać m.in. metodę Newtona-Raphsona. Zakłada ona, że postawiony problem jest identyczny z problemem, w którym należy szukać długości boku kwadratu o znanym polu powierzchni.
Pole kwadratu wyraża się wzorem:
A = a * a
co daje
a = A/a
i w konsekwencji
A/a - a = 0.
W ten sposób otrzymano test, który pozwala sprawdzić czy bok o długości a jest bokiem kwadratu o polu A.
Na początku niech a stanie się A/2. Jeżeli ta wartość nie przejdzie testu należy wyznaczyć kolejną długość boku a. Czynność tę będziemy powtarzać aż w końcu a będzie równe A/a.
Metoda NR zakłada, że kolejne przybliżenia długości a będą wyznaczane przez średnia arytmetyczną aktualnej długości boku a i długości drugiego boku A/a. Dzięki temu w każdym kroku kształt prostokąta o długościach boków a i A/a będzie coraz bardziej przypominał kwadrat.
Jak już wcześniej wspomniałem przybliżenia będą trwały tak długo, jak długo A/a nie będzie równe a. W metodach numerycznych zakłada się oczekiwaną dokładność wyniku. Zazwyczaj oznacza się ją litrą ε (epsilon). Mówi ona kiedy otrzymany wynik nas satysfakcjonuje (nie potrzebny nam dokładniejszy wynik). W związku z tym w kodzie programu, który znajduje się poniżej, test
A/a - a = 0
został zamieniony na
|A/a - a| < eps
Nowy test sprawdza czy długości dwóch boków prostokąta różnią się o wartość mniejszą niż założony błąd bezwzględny (epsion).
Przykład dla liczby 9 i dokładności 0,5
a = 9/2 = 4,5,
|4,5 - 2| > 0,5
a = (9/4,5 +4,5)/2 = 6,5/2 = 3,25,
|3,25 - 4,5| > 0,5
a = (9/3,25 + 3,25)/2 = 3,009615,
|3,009615 - 3.25| <0,5
w tym momencie różnica między poprzednim wynikiem a aktualnym mieści się w założonej dokładności. Tu przerywamy obliczenia. Naszym wynikiem jest 3,009615. Przy tak dużym błędzie jaki sobie założyłem to i tak wynik jest przyzwoity.
Realizacja w języku C++
Kolejny przykład - tym razem dla liczby 15 (pierwiastek z liczby 15)
15/2 -> 7,5
(15/7,5+7,5)/2 -> 4,75
(15/4,75+4,75)/2 -> 3,954
(15/3,954+3,954)/2 -> 3,874
wg WolframAlpha pierwiastek drugiego stopnia z 15 to 3.8729833462074168851792653997823996108329217052915908
Czyli stosując w 3 i 4 kroku zaokrąglenie do 3. miejsca po przecinku uzyskałem całkiem przyzwoity wynik po czterech przybliżeniach.
Pole kwadratu wyraża się wzorem:
A = a * a
co daje
a = A/a
i w konsekwencji
A/a - a = 0.
W ten sposób otrzymano test, który pozwala sprawdzić czy bok o długości a jest bokiem kwadratu o polu A.
Na początku niech a stanie się A/2. Jeżeli ta wartość nie przejdzie testu należy wyznaczyć kolejną długość boku a. Czynność tę będziemy powtarzać aż w końcu a będzie równe A/a.
Metoda NR zakłada, że kolejne przybliżenia długości a będą wyznaczane przez średnia arytmetyczną aktualnej długości boku a i długości drugiego boku A/a. Dzięki temu w każdym kroku kształt prostokąta o długościach boków a i A/a będzie coraz bardziej przypominał kwadrat.
Jak już wcześniej wspomniałem przybliżenia będą trwały tak długo, jak długo A/a nie będzie równe a. W metodach numerycznych zakłada się oczekiwaną dokładność wyniku. Zazwyczaj oznacza się ją litrą ε (epsilon). Mówi ona kiedy otrzymany wynik nas satysfakcjonuje (nie potrzebny nam dokładniejszy wynik). W związku z tym w kodzie programu, który znajduje się poniżej, test
A/a - a = 0
został zamieniony na
|A/a - a| < eps
Nowy test sprawdza czy długości dwóch boków prostokąta różnią się o wartość mniejszą niż założony błąd bezwzględny (epsion).
Przykład dla liczby 9 i dokładności 0,5
a = 9/2 = 4,5,
|4,5 - 2| > 0,5
a = (9/4,5 +4,5)/2 = 6,5/2 = 3,25,
|3,25 - 4,5| > 0,5
a = (9/3,25 + 3,25)/2 = 3,009615,
|3,009615 - 3.25| <0,5
w tym momencie różnica między poprzednim wynikiem a aktualnym mieści się w założonej dokładności. Tu przerywamy obliczenia. Naszym wynikiem jest 3,009615. Przy tak dużym błędzie jaki sobie założyłem to i tak wynik jest przyzwoity.
Realizacja w języku C++
#include <iostream> #include <math.h> using namespace std; int main() { float A,a; float eps = 0.0001; cin >> A; a = A/2; while(fabs(A/a-a)>eps) { a = (A/a+a)/2; } cout << a; return 0; }
Kolejny przykład - tym razem dla liczby 15 (pierwiastek z liczby 15)
15/2 -> 7,5
(15/7,5+7,5)/2 -> 4,75
(15/4,75+4,75)/2 -> 3,954
(15/3,954+3,954)/2 -> 3,874
wg WolframAlpha pierwiastek drugiego stopnia z 15 to 3.8729833462074168851792653997823996108329217052915908
Czyli stosując w 3 i 4 kroku zaokrąglenie do 3. miejsca po przecinku uzyskałem całkiem przyzwoity wynik po czterech przybliżeniach.