Przejdź do głównej zawartości

Pierwiastek kwadratowy [m. Newtona-Raphsona]

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++


#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.


Popularne posty z tego bloga

[C++]Konwersja systemu dziesiętnego na binarny [dec2bin, dec2u2]

Konwersja między systemami liczbowymi była już poruszana w tym serwisie tym razem zajmę się kodem U2. Inaczej zwany uzupełnieniem do 2. Opis tego systemu pojawił się w kontekście wstępu do programowania w języku Python [ tutaj ]. Prosty program tzw. szkolny zamiany nieujemnej liczby dziesiętnej na jej postać binarną: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 #include <iostream> using namespace std; int main () { int liczba; cin >> liczba; string wynik; while (liczba){ wynik = (liczba % 2 ? "1" : "0" ) + wynik; liczba /= 2 ; } cout << wynik; return 0 ; } Poniżej prezentuję kod programu, który zawiera trzy metody rozwiązania problemu jakim jest wyświetlenie użytkownikowi reprezentacji u2 podanej przez niego liczby dziesiętnej. Pierwsza z nich wywodzi się z typowego algorytmu konwersji systemu dec do u2: 1. przedstaw bezwzględną wartość liczby dziesiętnej w postaci binarnej, 2. dodaj na początek

Python - lekcja 005

Spis treści - zamiana całkowitych liczb dziesiętnych na ich odpowiedniki w innych systemach liczbowych (algorytm), - ujemne liczby całkowite w systemie binarnym (ZM, U1, U2, algorytm, formatowanie stringów, rzutowanie ze zmianą systemu liczbowego) [dec2bin, dec2ZM, dec2U1, dec2U2] - zadania.