Serwis Edukacyjny w I-LO w Tarnowie Materiały dla uczniów liceum |
Wyjście Spis treści Wstecz Dalej
Autor artykułu: mgr Jerzy Wałaszek |
©2024 mgr Jerzy Wałaszek |
SPIS TREŚCI |
|
Podrozdziały |
Metoda bisekcji ( ang. bisection method ), zwana również metodą połowienia lub wyszukiwaniem binarnym pozwala stosunkowo szybko znaleźć pierwiastek dowolnej funkcji w zadanym przedziale poszukiwań [a,b]. Aby można było zastosować metodę bisekcji, funkcja musi spełniać kilka warunków początkowych:
Metoda bisekcji stosowana jest do przybliżonego rozwiązywania równania f(x) = 0 w przedziale [a,b]. Funkcja f(x) musi być określona i ciągła w tym przedziale oraz musi posiadać różne znaki na krańcach przedziału [a,b], co gwarantuje istnienie przynajmniej jednego pierwiastka w tym przedziale. Rozwiązanie znajdowane jest za pomocą kolejnych przybliżeń. Z tego powodu należy określić dokładność, z którą chcemy otrzymać pierwiastek funkcji oraz dokładność wyznaczania samej funkcji.
W każdym przybliżeniu algorytm wyznacza środek x0 przedziału [a,b] jako średnią arytmetyczną krańców. Następnie sprawdzane jest, czy odległość tego środka od krańców przedziału jest mniejsza od założonej dokładności wyliczania pierwiastka. Jeśli tak, to algorytm kończy pracę z wynikiem w x0. Jeśli nie, to wyznaczana jest wartość funkcji w punkcie x0 i sprawdza się, czy odległość tej wartości od 0 jest mniejsza od założonej dokładności wyznaczania funkcji. Jeśli tak, to algorytm kończy pracę z wynikiem w x0.
W przeciwnym razie punkt x0 dzieli przedział [a,b] na dwie równe połowy: [a,x0] i [x0,b]. Algorytm za nowy przedział [a,b] przyjmuję tę połówkę, w której funkcja zmienia znak na krańcach i kontynuuje wyznaczanie pierwiastka funkcji.
Z opisu wynika, iż w każdym obiegu szerokość przedziału maleje dwukrotnie. Dzięki temu pierwiastek jest wyznaczany coraz bardziej dokładnie. Po dziesięciu obiegach szerokość przedziału maleje 210 = 1024 razy. Po 20 obiegach szerokość maleje 220 = 1048576 razy. Jest to postęp wykładniczy, zatem bardzo szybki.
εx | – | dokładność obliczania pierwiastka |
εy | – | dokładność obliczania funkcji |
a | – | początek przedziału poszukiwań pierwiastka |
b | – | koniec przedziału poszukiwań pierwiastka |
f() | – | funkcja, której pierwiastek będzie obliczany |
x0 | – | przybliżony pierwiastek funkcji |
fa | – | wartość funkcji w punkcie a |
fb | – | wartość funkcji w punkcie b |
K01: | fa ← f ( a ) fb ← f ( b ) |
Obliczamy wartości funkcji na krańcach przedziału [a,b]. |
K02: | Jeśli fa ·
fb > 0, to zakończ z błędem |
Funkcja nie ma różnych znaków na krańcach przedziału [a,b]. |
K03: | Wyznaczamy środek przedziału [a,b]. | |
K04: | Jeśli |a - x0| < εx, to zakończ |
Osiągnięto założoną dokładność. Wynik w x0. |
K05: | fx ← f ( x0 ) | Obliczamy wartość funkcji w środku przedziału |
K06: | Jeśli | fx | < εy, to zakończ |
Sprawdzamy, czy funkcja ma wartość 0 w środku przedziału. Wynik w x0. |
K07: | Jeśli fx ·
fa < 0, to b ← x0 inaczej a ← x0, fa ← fx |
Za nowy przedział [a,b]
przyjmujemy tę połówkę [a,x0], [x0,b], w której funkcja zmienia znak |
K08: | Idź do kroku K3 | Kontynuujemy obliczenia |
Poniższy program jest przykładową realizacją algorytmu bisekcji. Program oblicza pierwiastek funkcji:
Wykres tej funkcji w przedziale [-3,1] jest następujący:
Z wykresu wynika, iż pierwiastek znajduje się w przedziale [-1,1 , -1]. Taki więc przedział został przyjęty w programie.
Przykładowy program w języku C++
// Pierwiastek funkcji - metoda bisekcji // (C)2019 mgr Jerzy Wałaszek // Metody numeryczne //-------------------------------------- #include <iostream> #include <cmath> #include <iomanip> using namespace std; // Tutaj definiujemy funkcję, której pierwiastek jest wyliczany //------------------------------------------------------------- double f(double x) { return sin(x*x-x+1/3.0)+0.5*x; } // Tutaj definiujemy parametry początkowe double epsx = 1e-14; // Dokładność x double epsy = 1e-14; // Dokładność y double a = -1.1; // Początek przedziału poszukiwań pierwiastka double b = -1.0; // Koniec przedziału poszukiwań pierwiastka // Program główny //--------------- int main() { // Zmienne double fa,fb,fx,x0; // Licznik obiegów pętli int i = 0; // Zmienna informująca o znalezieniu wyniku bool result = false; setlocale(LC_ALL,""); cout << setprecision(15) << fixed; cout << "Obliczanie przybliżonego pierwiastka funkcji metodą bisekcji" << endl << "------------------------------------------------------------" << endl << endl; // Obliczamy i zapamiętujemy wartości funkcji na krańcach przedziału [a,b] fa = f(a); fb = f(b); //Sprawdzamy, czy na krańcach przedziału [a,b] wartości funkcji mają różne znaki if(fa * fb > 0) cout << "BŁĄD!!! Funkcja nie ma różnych znaków na krańcach przedziału"; else { result = true; // W pętli wyznaczamy kolejne przybliżenia pierwiastka while(true) { // Zwiększamy licznik obiegów pętli i++; // Wyznaczamy środek przedziału [a,b] x0 = (a + b) / 2; // Sprawdzamy, czy szerokość przedziału [a,b] jest mniejsza od dokładności if(fabs(a - x0) < epsx) break; // Jeśli tak, to kończymy // Obliczamy i zapamiętujemy wartość funkcji w punkcie x0 fx = f(x0); // Sprawdzamy, czy wartość funkcji jest dostatecznie bliska zeru if(fabs(fx) < epsy) break; // Jeśli tak, to kończymy // Za nowy przedział [a,b] przyjmujemy tą z połówek [a,x0], [x0,b], // w której funkcja ma różne znaki na krańcach if(fa * fx < 0) b = x0; else { a = x0; fa = fx; } } } if(result) cout << "Pierwiastek x0 = " << setw(18) << x0 << endl << "Wartość funkcji f(x0) = " << setw(18) << f(x0) << endl << "Dokładność dla x epsx = " << setw(18) << epsx << endl << "Dokładność dla y epsy = " << setw(18) << epsy << endl << "Liczba obiegów i = " << i; cout << endl << endl; return 0; } |
Wynik |
Obliczanie przybliżonego pierwiastka
funkcji metodą bisekcji ------------------------------------------------------------ Pierwiastek x0 = -1.077713513691339 Wartość funkcji f(x0) = 0.000000000000002 Dokładność dla x epsx = 0.000000000000010 Dokładność dla y epsy = 0.000000000000010 Liczba obiegów i = 44 |
Zespół Przedmiotowy Chemii-Fizyki-Informatyki w I Liceum Ogólnokształcącym im. Kazimierza Brodzińskiego w Tarnowie ul. Piłsudskiego 4 ©2024 mgr Jerzy Wałaszek |
Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email:
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.