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 |
©2019 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ń
Metoda bisekcji stosowana jest do przybliżonego rozwiązywania
równania
W każdym przybliżeniu algorytm wyznacza
W przeciwnym razie punkt x0 dzieli przedział
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
ε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 błąd. Zakończ | 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
Z wykresu wynika, iż pierwiastek znajduje się w przedziale
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 |
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: i-lo@eduinf.waw.pl
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.