Metoda Połowienia Przedziałów

Wstęp

Metoda Połowienia Przedziałów służy do znajdowania miejsca zerowego pewnej ciągłej funkcji f ograniczonej do pewnego przedziału [a, b]. Innymi słowy szukana jest taka wartość x, aby f(x) = 0.

Algorytm polega na wyliczeniu wartości funkcji na końcach przedziałów a i b. Jeśli są różnych znaków to znaczy, że musi istnieć miejsce zerowe. (Dla wartości o tym samym znaku nie jest to pewne.) W każdej iteracji obliczana jest wartość pośrodku przedziału. Jeśli wartość jest różna od 0 (i pewnej tolerancji błędu) to należy ograniczyć przedział z odpowiedniej strony.

Zwykle tego algorytmu używa się jedynie do wyliczania konkretnej wartości miejsca zerowego. Do poszukiwania miejsc zerowych jest on bardzo wolny i nie zawsze gwarantuje znalezienie tj. kiedy wartości na obu końcach przedziałów są tego samego znaku.

Przykład

Wykres funkcji f(x) = x³ + x² - 1

Weźmy przykładowo funkcję f(x) = x³ + x² - 1. Będziemy szukać jej miejsca zerowego na przedziale [0, 2]. Jak widać na zamieszczonym po prawej stronie obrazku miejsce zerowe powinno znajdować się w pobliżu wartości x₀ = 0.75. Poniżej zostały przedstawione kolejne iteracje wyliczania wyniku. Przyjmujemy, że wykonujemy, aż f(c) będzie mniejsze niż 0.01. c oznacza wartość środkową aktualnego przedziału c = (a + b) / 2. Wartości zostały przedstawione z dokładnością do czterech miejsc po przecinku.

W celu popełnienia jak najmniejszego błędu przyjmujemy, że punkt x leży pośrodku przedziału [a, b], więc x = 0.765625, a jego dokładna wartość to 0.00947618... Nie jest to, więc miejsce zerowe, ale dla mniejszej tolerancji np. 0.0001 wynik byłby zdecydowanie bliższy zeru. Algorytm znajduje wtedy pierwiastek x = 0.754878, gdzie funkcja przyjmuje wartość 0.00000006 co jest już znacznie bliżej wartości 0.

Implementacja

Podczas implementowania tego algorytmu należy mieć na względzie fakt, że komputery nie przechowują liczb z nieskończoną precyzją. Z tego względu należy przyjąć pewien błąd, który komputer może popełnić podczas wyszukiwania miejsca zerowego. Dodatkowym ograniczeniem może być ustalenie odgórne maksymalnej liczby iteracji, które program może wykonać.

Założenia

Podczas implementowania zadania przyda się wczytać funkcję od użytkownika. Skorzystam tutaj z własnej biblioteki wielomian.h, która umożliwia wczytywanie wielomianu, jego wypisanie czy obliczenie wartości w konkretnym punkcie. Szerzej o bibliotece można znaleźć w artykule o Schemacie Hornera.

Algorytm

Funkcja szukajMiejscaZerowego() przyjmuje cztery argumenty: w - wskaźnik na wielomian wczytany od użytkownika, a i b kolejno dolny i górny zakres przedziału oraz p - precyzja obliczeń tj. z jakim błędem może zostać podana przybliżona wartość argumentu x.

1. double szukajMiejscaZerowego(wielomian* w, double a, double b, double p = 0.0000001) {
2.   double fa = wartosc_wielomianu(w, a);
3.   if (fa == 0) return a;
4.   double fb = wartosc_wielomianu(w, b);
5.   if (fb == 0) return b;
6.   if (fa * fb > 0)
7.     return NULL;
8.   double c, fc;
9.   do {
10.     c = (a + b) / 2;
11.     fc = wartosc_wielomianu(w, c);
12.     if (fc == 0) return c;
13.     if (fc * fa > 0) {
14.       a = c;
15.       fa = fc;
16.     } else {
17.       b = c;
18.       fb = fc;
19.     }
20.   } while (abs(fc) > p);
21.   return c;
22. }

(2. - 5.) Na początku liczymy skrajne wartości i sprawdzamy czy na końcach nie ma miejsca zerowego. Jeśli nie to (6.) należy upewnić się, że wartości na końcach przedziału mają przeciwne znaki i jeśli tak nie jest to (7.) należy zwrócić błąd (tutaj zawracana jest wartość NULL). Jeśli jednak poszukiwania mogą zostać rozpoczęte to (8.) inicjalizujemy zmienne pod wartość środkową. W pętli (10.) obliczamy środek przedziału i (11.) wartość dla tego argumentu c. Jeśli (12.) wartość wynosi 0 to zwracamy argument c. W przeciwnym wypadku (13. - 19.) odpowiednio zawężamy przedział i (20.) kontynuujemy iterację, aż do zwrócenia wyniku lub do spełnienia precyzji.

Implementacja

W celu przetestowania napisanej funkcji można skorzystać z poniższego fragmentu kodu:

1. int main() {
2.   cout << "Podaj wzor funkcji (tylko wielomian):\n";
3.   wielomian* w = wczytajWieloman();
4.   cout << "f(x) = ";
5.   wypiszWieloman(w);
6.   double a, b;
7.   cout << "Podaj przedzial [a, b]\na = ";
8.   cin >> a;
9.   cout << "b = ";
10.   cin >> b;
11.   cout << "Szukany x to " << szukajMiejscaZerowego(w, a, b) << endl;
12.   system("pause");
13.   return 0;
14. }

Po uruchomieniu program poprosi użytkownika o wprowadzenie danych: wielomianu oraz przedziału. Następnie na ekran zostaje wypisany wynik.

• Kod źródłowy Implementacja

Zadania

Zadanie 1

Warto zauważyć, że w każdym przedziale długość przedziału zmniejsza się dwukrotnie. Z tego powodu istnieje możliwość oszacowania ile należy wykonać iteracji, aby uzyskać wynik z daną precyzją. W poniższym przykładzie p - precyzja, [a, b] - przedział poszukiwań i n - ilość potrzebnych iteracji.

Napisz program, który najpierw obliczy ile (n) potrzebuje wykonać iteracji, a następnie niech wykona maksymalnie n iteracji podczas wyszukiwania miejsca zerowego.

• Kod źródłowy Zadanie 1