Programowanie i algorytmy

KONKURS FRAKTAL

fraktal

VII edycja konkursu programistycznego

FRAKTAL

8-9 kwietnia 2017

czytaj więcej

Wyznaczanie pierwiastka arytmetycznego - metoda Newtona - Raphsona

powrót

Przedstawiony poniżej algorytm wyznacza pierwiastek arytmetyczny z liczby rzeczywistej nieujemnej. Opisywana metoda jest bardzo szybka i prosta w implementacji.

W pierwszym kroku ustalamy precyzję, z jaką chcemy wyznaczyć szukany pierwiastek, na przykład do sześciu miejsc po przecinku ustalamy epsilona:

{tex}\epsilon=0.000001{/tex}

Dla przykładu wyznaczymy:

{tex}\sqrt{3}{/tex}

Liczbę, którą szukamy jest bokiem kwadratu o polu {tex}3{/tex}:

newton-raphson

 Każdy krok będzie przybliżał nas do otrzymania takiego kwadratu. Zaczniemy od prostokąta o wymiarach {tex}1\ x\ 3{/tex}

Krok 1:

newton-raphson

W każdym kroku wyznaczamy bok {tex}a{/tex} ze średniej arytmetycznej długości boków {tex}a{/tex} i {tex}b{/tex} z poprzedniego kroku:

Krok 2:

{tex}a=\frac{a+b}{2}=\frac{1+3}{2}=2{/tex}

natomiast bok {tex}b{/tex} dzieląc pole przez bok {tex}a{/tex}:

{tex}b=\frac{P}{a}=\frac{3}{2}=1.5{/tex}

newton-raphson

Kroki te powtarzamy do momentu otrzymania zadanej precyzji, czyli uzyskania różnicy boków prostokąta mniejszej niż epsilon:

{tex}|a-b|<\epsilon{/tex}

Krok 3.

{tex}a=\frac{a+b}{2}=\frac{2+1.5}{2}=1.75{/tex}

{tex}b=\frac{P}{a}=\frac{3}{1.75}=1.71{/tex}

newton-raphson

Krok 4:

{tex}a=\frac{a+b}{2}=\frac{1.75+1.71}{2}=1.73{/tex}

{tex}b=\frac{P}{a}=\frac{3}{1.73}=1.73{/tex}

newton-raphson

 Każdy kolejny krok przybliża nas do spełnienia warunku:

{tex}|a-b|<\epsilon{/tex}

Implementacja algorytmu 

Funkcja fabs(liczba) wyznacza wartość bezwzględną z liczby rzeczywistej i zdefiniowana jest w bibliotece cmath

 

#include<iostream>
#include<cmath>
using namespace std;
 
//ustawienie prezycji pierwiastka
const double eps = 0.000001;
 
double pierwiastek(double P, double eps)
{
     double a = 1., b = P;
 
       //dopóki nie otrzymamy żądanej precyzji
       while(fabs(a-b)>=eps) 
       {
           a = (a+b)/2.;   
           b = P/a;
       }
 
       return a; 
}
 
int main()
{
    double x;
    cout<<"Podaj liczbę, z której chcesz wyznaczyć pierwiastek: ";
    cin>>x;
 
    cout<<fixed<<pierwiastek(x, eps); 
 
    cin.ignore();
    cin.get();
    return 0;
}