Pierwiastek kwadratowy [m. połowienia]

Metoda połowienia jest najwolniej zbieżną metodą znajdowania przybliżonych pierwiastków funkcji w zadanym przedziale argumentów [a; b]. Metodę tę można zastosować, jeśli funkcja jest ciągła i ma przeciwne wartości w krańcach przedziału ( f(a) * f(b) < 0 ).

Aby wykorzystać tę metodę do wyznaczania wartości pierwiastków kwadratowych należy odpowiednio przygotować funkcję kwadratową:

f(x) = ax^2 + bx + c

Będziemy szukać miejsca zerowego (nieujemnego) funkcji

f(x) = x^2 - A

czyli

x^2 - A = 0

gdzie A jest liczbą, której pierwiastka będziemy szukać w określonym przedziale. Dla ułatwienia możemy przyjąć, że ten przedział będzie następujący: [0; A). 

W tej metodzie sprawdza się czy miejsce zerowe znajduje się na środku zadanego przedziału. Jeżeli sprawdzany element jest większy od poszukiwanego elementu to staje się on nowym końcem przedziału. W przeciwnym przypadku sprawdzany element staje się nowym początkiem przedziału.
Powyższe czynności powtarza się aż do znalezienia miejsca zerowego lub do znalezienia elementu, którego wartość będzie wystarczająco bliska poszukiwanej wartości.

Dla A = 2 i bezwzględnego błędu eps = 0,1 (zakładana dokładność obliczeń) graficzne przedstawienie opisywanej metody będzie wyglądało następująco:

W powyższym przykładzie ostatnim otrzymanym przedziałem jest [1,375; 1,4375). Jego średnica jest mniejsza niż 0,1. Poszukiwanym wynikiem może być, którakolwiek z liczb znajdujących się w tym przedziale. W realizacji komputerowej przyjąłem, że wyświetlę najmniejszy element ostatniego przedziału.

Realizacja komputerowa w języku C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#include <iostream>
#include <math.h>
 
using namespace std;
 
int main() {
    float A;
    float a, b;
    float srodek;
    float eps = 0.1;
    
    cin >> A;
    
    a = 0;
    b = A;
    
    while(fabs(a-b)>eps)
    {
        srodek = (a + b) / 2;
        if(srodek * srodek > A)
            b = srodek;
        else
            a = srodek;   
        cout <<"[" << a<< ", " << b <<")"<< endl;
    }
    cout << a;
    return 0;
}