Metody Numeryczne - Pierwiastki funkcji: metoda bisekcji

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 \(x_0\), 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]}\):

\[\begin{gathered}
f\left( {{x_0}} \right) = 0 \hfill \\
f\left( a \right) < 0 < f\left( b \right) \Rightarrow f\left( a \right) < f\left( {{x_0}} \right) < f\left( b \right) \hfill \\
f\left( a \right) > 0 > f\left( b \right) \Rightarrow f\left( a \right) > f\left( {{x_0}} \right) > f\left( b \right) \hfill \\
\end{gathered} \]

do podrozdziału do strony

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 \(x_0\) 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 \(x_0\). Jeśli nie, to wyznaczana jest wartość funkcji w punkcie \(x_0\) 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 \(x_0\).

W przeciwnym razie punkt \(x_0\) dzieli przedział na dwie równe połowy: \([a;x_0]\)) i \([x_0;b]\). Algorytm za nowy przedział 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 dokładniej. Po dziesięciu obiegach szerokość przedziału maleje 2¹⁰ = 1024 razy. Po 20 obiegach szerokość maleje 2²⁰ = 1048576 razy. Jest to postęp wykładniczy, zatem bardzo szybki.

Algorytm bisekcji

Dane wejściowe:

\(\varepsilon_x\)	–	dokładność obliczania pierwiastka
\(\varepsilon_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

\(x_0\)

–

przybliżony pierwiastek funkcji

Zmienne pomocnicze

\(f_a\)	–	wartość funkcji w punkcie \(a\)
\(f_b\)	–	wartość funkcji w punkcie \(b\)

Lista kroków

K01:	\(f_a \leftarrow f(a) \quad f_b \leftarrow f(b)\)	Obliczamy wartości funkcji na krańcach przedziału .
K02:	Jeśli \(f_a \cdot f_b > 0\), to zakończ z błędem	Funkcja nie ma różnych znaków na krańcach przedziału .
K03:	\(x_0 \leftarrow \dfrac{a + b}{2}\)	Wyznaczamy środek przedziału .
K04:	Jeśli \(\|a - x_0\| < \varepsilon_x\), to zakończ	Osiągnięto założoną dokładność. Wynik w x₀.
K05:	\(f_x \leftarrow f(x_0)\)	Obliczamy wartość funkcji w środku przedziału.
K06:	Jeśli \(\|f_x\| < \varepsilon_y\), to zakończ	Sprawdzamy, czy funkcja ma wartość 0 w środku przedziału. Wynik w x₀.
K07:	Jeśli \(f_x \cdot f_a < 0\), to \(b \leftarrow x_0\)inaczej \(a \leftarrow x_0 \quad f_a \leftarrow f_x\)	Za nowy przedział przyjmujemy tę połówkę <a;x₀>, <x₀;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:

\[f(x) = \sin \left( {{x^2} - x + \frac{1}{3}} \right) + \frac{x}{2}\]

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.

// Pierwiastek funkcji - metoda bisekcji
// (C)2019 mgr Jerzy Wałaszek
// Metody numeryczne 0032
//--------------------------------------

#include <iostream>
#include <windows.h>
#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

// Dokładność x
double EPSX = 1e-14;
// Dokładność y
double EPSY = 1e-14;
// Początek przedziału
// poszukiwań pierwiastka
double a = -1.1;
// Koniec przedziału
// poszukiwań pierwiastka
double b = -1.0;

// 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;

  SetConsoleOutputCP(CP_UTF8); 
  SetConsoleCP(CP_UTF8);

  cout << setprecision(15)
       << fixed;
  cout <<
  "Obliczanie przybliżonego pierwiastka "
  "funkcji metodą bisekcji\n"
  "-------------------------------------"
  "-----------------------\n\n";

  // Obliczamy i zapamiętujemy
  // wartości funkcji
  // na krańcach przedziału
  fa = f(a);
  fb = f(b);

  // Sprawdzamy, czy na krańcach
  // przedziału 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
      x0 = (a + b) / 2;

      // Sprawdzamy, czy szerokość
      // przedziału jest mniejsza
      // od zadanej 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ł 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(20) << x0 << endl
    << "Wartość funkcji f(x0) = "
    << setw(20) << f(x0) << endl
    << "Dokładność dla x EPSX = "
    << setw(20) << EPSX << endl
    << "Dokładność dla y EPSY = "
    << setw(20) << EPSY << endl
    << "Liczba obiegów      i = "
    << setw(4) << i;

  cout << endl << endl;
  system("pause");
  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

Python (dodatek)

from math import sin

# Pierwiastek funkcji - metoda bisekcji
# (C)2026 mgr Jerzy Wałaszek
# Metody numeryczne 0032
#--------------------------------------

# Tutaj definiujemy funkcję,
# której pierwiastek jest wyliczany
#----------------------------------
def f(x):
    return (sin(x * x - x + 1 / 3.0)
            + 0.5 * x)

# Tutaj definiujemy parametry początkowe

# Dokładność x
EPSX = 1e-14
# Dokładność y
EPSY = 1e-14
# Początek przedziału
# poszukiwań pierwiastka
a = -1.1
# Koniec przedziału
# poszukiwań pierwiastka
b = -1.0

# Program główny
#---------------

# Licznik obiegów pętli
i = 0

# Zmienna informująca
# o znalezieniu wyniku
result = False

print(
  "Obliczanie przybliżonego pierwiastka "
  "funkcji metodą bisekcji\n"
  "-------------------------------------"
  "-----------------------\n")

# Obliczamy i zapamiętujemy
# wartości funkcji
# na krańcach przedziału
fa = f(a)
fb = f(b)

# Sprawdzamy, czy na krańcach
# przedziału wartości funkcji
# mają różne znaki
if fa * fb > 0:
    print(
      "BŁĄD!!! Funkcja nie ma różnych "
      "znaków na krańcach przedziału.")
else:
    result = True
    x0 = 0.0

    # W pętli wyznaczamy kolejne
    # przybliżenia pierwiastka
    while True:

        # Zwiększamy licznik
        # obiegów pętli
        i += 1

        # Wyznaczamy środek przedziału
        x0 = (a + b) / 2

        # Sprawdzamy, czy szerokość
        # przedziału jest mniejsza
        # od zadanej dokładności
        if abs(a - x0) < EPSX:
            break

        # Obliczamy i zapamiętujemy
        # wartość funkcji w punkcie x0
        fx = f(x0)

        # Sprawdzamy, czy wartość
        # funkcji jest dostatecznie
        # bliska zeru
        if abs(fx) < EPSY:
            break

        # Za nowy przedział 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:
    print(
  f"Pierwiastek        x0 = {x0:20.15f}\n"
  f"Wartość funkcji f(x0) = {f(x0):20.15f}\n"
  f"Dokładność dla x EPSX = {EPSX:20.15f}\n"
  f"Dokładność dla y EPSY = {EPSY:20.15f}\n"
  f"Liczba obiegów      i = {i:4}\n")

print("\n")
input("Naciśnij Enter...")

do podrozdziału do strony

Pierwiastki funkcji

Metoda bisekcji

Warunki początkowe