Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

obrazek

Autor artykułu: mgr Jerzy Wałaszek

©2019 mgr Jerzy Wałaszek
I LO w Tarnowie

obrazek

Pierwiastki funkcji

Metoda bisekcji

SPIS TREŚCI
Podrozdziały

Warunki początkowe

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:

Funkcja musi być określona w przedziale [a,b]

Określoność funkcji oznacza, że dla każdego argumentu x z przedziału [a,b] istnieje wartość funkcji. Warunek ten jest konieczny, ponieważ algorytm bisekcji wybiera punkty w przedziale [a,b] i oblicza dla nich wartość funkcji. Jeśli trafi na punkt nieokreśloności, w którym nie można policzyć wartości funkcji, to cała metoda załamie się.

Funkcja musi być ciągła w przedziale [a,b]

Ciągłość funkcji gwarantuje, iż jej wartości nie wykonują nagłych skoków i dla dowolnych dwóch wartości funkcji w tym przedziale znajdziemy wszystkie wartości pośrednie.

Na krańcach przedziału [a,b] funkcja musi mieć różne znaki

Ten warunek wraz z poprzednim gwarantuje, że w przedziale [a,b] istnieje taki argument x0, dla którego funkcja ma wartość 0, która to wartość jest wartością pośrednią pomiędzy wartościami funkcji na krańcach przedziału [a,b]:

Na początek:  podrozdziału   strony 

Algorytm i program

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.

Algorytm bisekcji

Dane wejściowe:

ε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

Dane wyjściowe

x0 przybliżony pierwiastek funkcji

Zmienne pomocnicze

fa wartość funkcji w punkcie a
fb wartość funkcji w punkcie b

Lista kroków

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 [-3,1] jest następujący:

obrazek

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
Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2019 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: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.