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:

$$\epsilon=0.000001$$

Dla przykładu wyznaczymy:

$$\sqrt{3}$$

Liczbę, którą szukamy jest bokiem kwadratu o polu $$3$$:

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

Krok 1:

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

Krok 2:

$$a=\frac{a+b}{2}=\frac{1+3}{2}=2$$

natomiast bok $$b$$ dzieląc pole przez bok $$a$$:

$$b=\frac{P}{a}=\frac{3}{2}=1.5$$

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

$$|a-b|<\epsilon$$

Krok 3.

$$a=\frac{a+b}{2}=\frac{2+1.5}{2}=1.75$$

$$b=\frac{P}{a}=\frac{3}{1.75}=1.71$$

Krok 4:

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

$$b=\frac{P}{a}=\frac{3}{1.73}=1.73$$

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

$$|a-b|<\epsilon$$

Implementacja algorytmu 

//algorytm.edu.pl
#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+b)/2.; 
}
 
int main()
{
    double x;
    cout<<"Podaj liczbę, z której chcesz wyznaczyć pierwiastek: ";
    cin>>x;
 
    cout<<fixed<<pierwiastek(x, eps); 

    return 0;
}