Miejsca Zerowe Funkcji - Metoda Połowienia

Mamy daną funkcję f(x) oraz przedział [a,b], w którym będziemy poszukiwali miejsca zerowego (czyli pierwiastka funkcji f(x)). Aby można było zastosować algorytm połowienia (zwany również algorytmem bisekcji), w przedziale [a,b] muszą być spełnione poniższe warunki:

Funkcja f(x) jest określona - uczniowie często nie rozumieją tego pojęcia. Określoność funkcji oznacza, iż dla każdej wartości argumentu x z przedziału [a,b] potrafimy policzyć wartość funkcji. W trakcie pracy algorytm połowienia oblicza wartości funkcji dla argumentów należących do tego przedziału [a,b]. Jeśli przypadkowo trafi na punkt, dla którego wartość funkcji jest nieokreślona, obliczenia się załamią. W praktyce konsekwencje mogą być tragiczne, np. zmiana lotu samolotu z poziomego na pionowy w kierunku ziemi...

Dla przykładu rozważmy prostą funkcję:

Ile wynosi wartość tej funkcji dla x = 1? Musimy dzielić przez 0, a jak wiadomo jest to zadanie niewykonalne. W punkcie x = 1 tak podana funkcja ma nieokreśloną wartość. Co gorsza punkt ten wypada akurat w środku przedziału [a,b] i algorytm bisekcji trafi na niego przy pierwszym obiegu.

Funkcja f(x) jest ciągła. Ciągłość funkcji oznacza z kolei, iż jej wartości nie "wykonują" nagłych skoków. Funkcja przebiega przez wszystkie wartości pośrednie - nie istnieją zatem przerwy w kolejnych wartościach funkcji. Dla przykładu rozważmy taką oto funkcję:

Funkcja w przedziale [-2,1] posiada następujący wykres:

obrazek

Nieciągłość występuje w punkcie x = 0, czyli w miejscu zmiany przepisu funkcji. Zwróć uwagę, iż funkcja jest określona w tym punkcie - nieciągłość i nieokreśloność to dwie różne sprawy - nie myl ich!!!

Funkcja f(x) na krańcach przedziału [a,b] przyjmuje różne znaki. Ponieważ funkcja, zgodnie z poprzednim podpunktem, jest ciągła, to przyjmuje w przedziale [a,b] wszystkie wartości pośrednie pomiędzy f(a) i f(b). Wartości te mają różne znaki (czyli leżą po różnych stronach osi OX), zatem musi być taki punkt x_o w przedziale [a,b], dla którego funkcja przyjmuje wartość pośrednią:

Gdy funkcja f(x) spełnia powyższe trzy warunki, to w przedziale [a,b] zagwarantowane jest istnienie pierwiastka i możemy go wyszukać algorytmem połowienia (bisekcji). Zasada jest następująca:

Wyznaczamy punkt x_o jako środek przedziału [a,b] zgodnie ze wzorem:

Obliczamy wartość funkcji w punkcie x_o. Jeśli długość przedziału jest mniejsza od założonej dokładności wyliczeń pierwiastka, to wartość x_o jest poszukiwanym przybliżeniem. Kończymy algorytm. W przeciwnym razie sprawdzamy, czy f(x_o) znajduje się dostatecznie blisko 0:

Jeśli nierówność jest spełniona, to x_o jest poszukiwaną wartością pierwiastka. Zwracamy wynik i kończymy algorytm. W przeciwnym razie za nowy przedział poszukiwań pierwiastka przyjmujemy tą połówkę [a,x_o] lub [x_o,b], w której funkcja zmienia znak na krańcach. Algorytm powtarzamy od początku dotąd, aż znajdziemy pierwiastek lub przedział [a,b] osiągnie założoną długość (może to być również epsilon). Wtedy kończymy zwracając ostatnio wyliczone x_o.

Na początek: podrozdziału strony

Specyfikacja problemu

Dane wejściowe

f(x)	–	funkcja, której pierwiastek liczymy. Musi być ciągła i określona w przedziale poszukiwań pierwiastka.
a,b	–	punkty krańcowe przedziału poszukiwań pierwiastka funkcji f(x). a,b ∈ R

Dane wyjściowe

x_o

–

pierwiastek funkcji f(x)

Zmienne pomocnicze i funkcje

f_a , f_b , f_o	– wartości funkcji odpowiednio w punktach a, b, x_o. f_a , f_b , f_o ∈ R
ε_o	– określa dokładność porównania z zerem.	ε_o = 0.0000000001
ε_x	– określa dokładność wyznaczania pierwiastka x_o.	ε_x = 0.0000000001

Lista kroków

	K01:	Czytaj a i b
	K02:	f_a ← f(a) ; f_b ← f(b)
	K03:	Jeśli f_a · f_b > 0, to pisz "Funkcja nie spełnia założeń" i zakończ
	K04:	Dopóki \| a - b \| > ε_x: wykonuj kroki K05...K07
	K05:
	K06:	Jeśli \| f_o \| < ε_o, to idź do kroku K08
	K07:	eśli f_a · f_o < 0, to b ← x_o inaczej a ← x_o; f_a ← f_o
	K08:	Pisz x_oi zakończ

Schemat blokowy

obrazek

Wykonanie algorytmu rozpoczynamy od odczytu zakresu poszukiwań pierwiastka danej funkcji. W zmiennych f_a i f_b umieszczamy wartość funkcji na krańcach tego zakresu

Pierwszy test ma na celu sprawdzenie warunku różnych znaków wartości funkcji na krańcach zakresu poszukiwań pierwiastka. Różne znaki gwarantują nam istnienie pierwiastka w danym zakresie. Zatem jeśli funkcja na krańcach nie przybiera różnych znaków, wypisujemy odpowiedni komunikat i kończymy algorytm.

Rozpoczynamy pętlę wyliczania kolejnych przybliżeń pierwiastka funkcji. Pętla wykonuje się do momentu, aż przedział poszukiwań pierwiastka osiągnie długość ε_x.

Wewnątrz pętli wyznaczamy punkt x_o leżący w środku przedziału [a,b] oraz obliczamy wartość funkcji w punkcie x_o i umieszczamy ją w zmiennej f_o. Jeśli wartość f_o jest dostatecznie bliska zeru (wpada w otoczenie zera o promieniu ε_o), przerywamy pętlę, wypisujemy x_o i kończymy algorytm.

W przeciwnym razie za nowy przedział [a,b] przyjmujemy połówkę wyznaczoną przez x_o, w której funkcja zmienia znak. Testujemy iloczyn f_a przez f_o. Jeśli iloczyn jest ujemny, to różne znaki funkcja przyjmuje w połówce [a,x_o]. Zatem za nowy koniec b przyjmujemy x_o i kontynuujemy pętlę. W przeciwnym razie zmiana znaku występuje w drugiej połówce przedziału - [x_o,b]. Za nowy początek a przyjmujemy x_o. Dodatkowo za f_a przyjmujemy f_o - zwolni nas to od konieczności ponownego wyliczania wartości funkcji w nowym punkcie a. Po tych czynnościach kontynuujemy pętlę wyznaczania kolejnych przybliżeń pierwiastka x_o.

Na początek: podrozdziału strony

Programy wyznaczają miejsce zerowe funkcji:

Pierwiastków należy poszukiwać w przedziałach [-1,0] i [1,2].

C++

// Program znajduje miejsce zerowe funkcji f(x)
// za pomocą algorytmu połowienia - bisekcji
//---------------------------------------------
// (C)2006 mgr J.Wałaszek       I LO w Tarnowie

#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstdlib>

using namespace std;

const double EPS0 = 0.0000000001; // dokładność porównania z zerem
const double EPSX = 0.0000000001; // dokładność wyznaczenia pierwiastka

// Funkcja, której miejsce zerowe obliczamy
// f(x) = x^3*(x+sin(x^2-1)-1)-1
// <-1,0> i <1,2>
//-----------------------------------------

double f(double x)
{
  return x * x * x * (x + sin(x * x - 1) - 1) - 1;
}

//-----------------------------------------------------
// Program główny
//-----------------------------------------------------

int main()
{

  double a,b,x0,fa,fb,f0;

  cout << setprecision(5)     // 5 cyfr po przecinku
       << fixed;              // format stałoprzecinkowy

  cout << "Obliczanie pierwiastka funkcji - metoda bisekcji\n"
          "f(x) = x^3*(x+sin(x^2-1)-1)-1\n"
          "------------------------------------------------\n"
          "(C)2006 mgr Jerzy Walaszek       I LO w Tarnowie\n\n"
          "Podaj zakres poszukiwan pierwiastka:\n\n";
  cout << "a = "; cin >> a;
  cout << "b = "; cin >> b;
  cout << "\n------------------------------------------------\n\n"
          "WYNIK:\n\n";
  fa = f(a); fb = f(b);
  if(fa * fb > 0)     cout << "Funkcja nie spelnia zalozen\n";
  else
  {
    while(fabs(a - b) > EPSX)
    {
      x0 = (a + b) / 2; f0 = f(x0);
      if(fabs(f0) < EPS0) break;
      if(fa * f0 < 0) b = x0;
      else
      {
        a = x0; fa = f0;
      }
    }
    cout << "x0 = " << setw(15) << x0 << endl;
  }
  cout << "\n------------------------------------------------\n\n";
  system("pause");
  return 0;
}

Pascal

// Program znajduje miejsce zerowe funkcji f(x)
// za pomocą algorytmu połowienia - bisekcji
//---------------------------------------------
// (C)2006 mgr J.Wałaszek       I LO w Tarnowie

program mzf1;

uses math;

const
  EPS0 = 0.0000000001; // dokładność porównania z zerem
  EPSX = 0.0000000001; // dokładność wyznaczenia pierwiastka

// Funkcja, której miejsce zerowe obliczamy
// f(x) = x^3*(x+sin(x^2-1)-1)-1
// <-1,0> i <1,2>
//-----------------------------------------

function f(x : real) : double;
begin
  Result := x * x * x * (x + sin(x * x - 1) - 1) - 1;
end;

//-----------------------------------------------------
// Program główny
//-----------------------------------------------------

var
  a,b,x0,fa,fb,f0 : double;

begin
  writeln('Obliczanie pierwiastka funkcji - metoda bisekcji');
  writeln('f(x) = x^3*(x+sin(x^2-1)-1)-1');
  writeln('------------------------------------------------');
  writeln('(C)2006 mgr Jerzy Walaszek       I LO w Tarnowie');
  writeln;
  writeln('Podaj zakres poszukiwan pierwiastka:');
  writeln;
  write('a = '); readln(a);
  write('b = '); readln(b);
  writeln;
  writeln('------------------------------------------------');
  writeln('WYNIK:');
  writeln;
  fa := f(a); fb := f(b);
  if fa * fb > 0 then writeln('Funkcja nie spelnia zalozen')
  else
  begin
    while abs(a - b) > EPSX do
    begin
      x0 := (a + b) / 2; f0 := f(x0);
      if abs(f0) < EPS0 then break;
      if fa * f0 < 0 then b := x0
      else
      begin
        a := x0; fa := f0;
      end;
    end;
    writeln('x0 = ',x0:15:8);
  end;
  writeln;
  writeln('------------------------------------------------');
  writeln('Koniec. Nacisnij klawisz Enter...');
  readln;
end.

Basic

' Program znajduje miejsce zerowe funkcji f(x)
' za pomocą algorytmu połowienia - bisekcji
'---------------------------------------------
' (C)2006 mgr J.Wałaszek       I LO w Tarnowie

Declare Function f(x As Double) As Double

Const EPS0 As Double = 0.0000000001 ' dokładność porównania z zerem
Const EPSX As Double = 0.0000000001 ' dokładność wyznaczenia pierwiastka

'-----------------------------------------------------
' Program główny
'-----------------------------------------------------

Dim As double a, b, x0, fa, fb, f0

Print "Obliczanie pierwiastka funkcji - metoda bisekcji"
Print "f(x) = x^3*(x+sin(x^2-1)-1)-1"
Print "------------------------------------------------"
Print "(C)2006 mgr Jerzy Walaszek       I LO w Tarnowie"
Print
Print "Podaj zakres poszukiwan pierwiastka:"
Print
Input "a = ", a
Input "b = ", b
Print
Print "------------------------------------------------"
Print
Print "WYNIK:"
Print
fa = f(a) : fb = f(b)
If fa * fb > 0 Then
   Print "Funkcja nie spelnia zalozen"
Else
   While Abs(a - b) > EPSX
      x0 = (a + b) / 2 : f0 = f(x0)
      If Abs(f0) < EPS0 Then Exit While
      If fa * f0 < 0 Then
         b = x0
      Else
         a = x0 : fa = f0
      End If
   Wend
   
   Print Using "x0 = ######.########"; x0
End If

Print
Print "------------------------------------------------"
Print
Print "Koniec. Nacisnij klawisz Enter..."

Sleep

End

' Funkcja, której miejsce zerowe obliczamy
' f(x) = x^3*(x+sin(x^2-1)-1)-1
' <-1,0> i <1,2>
'-----------------------------------------

Function f(x As Double) As Double
  Return x * x * x * (x + Sin(x * x - 1) - 1) - 1
End Function

JavaScript

<html>
  <head>
  </head>
  <body>
    <div align="center">
      <form style="BORDER-RIGHT: #ff9933 1px outset; PADDING-RIGHT: 4px;
                   BORDER-TOP: #ff9933 1px outset; PADDING-LEFT: 4px;
                   PADDING-BOTTOM: 1px; BORDER-LEFT: #ff9933 1px outset;
                   PADDING-TOP: 1px; BORDER-BOTTOM: #ff9933 1px outset;
                   BACKGROUND-COLOR: #ffcc66" name="frmbincode">
        <h3 style="TEXT-ALIGN: center">
          Obliczanie pierwiastka funkcji metodą bisekcji
        </h3>
        <p style="TEXT-ALIGN: center">
          <i>f(x) = x<sup>3</sup>(x + sin(x<sup>2</sup> - 1) - 1) - 1</i>
        </p>
        <p style="TEXT-ALIGN: center">
          (C)2006 mgr Jerzy Wałaszek I LO w Tarnowie
        </p>
        <hr>
        <p style="text-align: center">
          Wpisz do pól edycyjnych zakres przedziału poszukiwań pierwiastka
        </p>
        <div align="center">
          <table border="0" id="table144" cellpadding="8"
                 style="border-collapse: collapse">
            <tr>
              <td>
                a = <input type="text" name="wsp_a" size="20" value="1"
                           style="text-align: right">
              </td>
              <td>
                b = <input type="text" name="wsp_b" size="20" value="2"
                           style="text-align: right">
              </td>
              <td>
                <input type="button" value="Szukaj pierwiastka" name="B1"
                       onclick="main()">
              </td>
            </tr>
          </table>
        </div>
        <div id="out" align=center>...</div>
      </form> 

<script language=javascript>

// Program znajduje miejsce zerowe funkcji f(x)
// za pomocą algorytmu połowienia - bisekcji
//---------------------------------------------
// (C)2006 mgr J.Wałaszek       I LO w Tarnowie

var EPS0 = 0.0000000001; // dokładność porównania z zerem
var EPSX = 0.0000000001; // dokładność wyznaczenia pierwiastka

// Funkcja, której miejsce zerowe obliczamy
// f(x) = x^3*(x+sin(x^2-1)-1)-1
// <-1,0> i <1,2>
//-----------------------------------------

function f(x)
{
  return x * x * x * (x + Math.sin(x * x - 1) - 1) - 1;
}

//-----------------------------------------------------
// Program główny
//-----------------------------------------------------

function main()
{
  var a,b,x0,fa,fb,f0,t;

  a = parseFloat(document.frmbincode.wsp_a.value);
  b = parseFloat(document.frmbincode.wsp_b.value);
  if(isNaN(a) || isNaN(b))
    t = "<font color=red><b>Złe krańce zakresu poszukiwań pierwiastka!</b></font>";
  else
  {
    t  = "x<sub>o</sub> = ";
    fa = f(a); fb = f(b);
    if(fa * fb > 0)
      t = "<font color=red><b>Funkcja nie spelnia zalozen</b></font>";
    else
    {
      while(Math.abs(a - b) > EPSX)
      {
        x0 = (a + b) / 2; f0 = f(x0);
        if(Math.abs(f0) < EPS0) break;
        if(fa * f0 < 0) b = x0;
        else
        {
          a = x0; fa = f0;
        }
      }
      t += x0;
    }
  }
  document.getElementById("out").innerHTML = t;
}

</script>
    </div>
  </body>
</html>

Wynik:

Obliczanie pierwiastka funkcji - metoda bisekcji
f(x) = x^3*(x+sin(x^2-1)-1)-1
------------------------------------------------
(C)2006 mgr Jerzy Wałaszek I LO w Tarnowie

Podaj zakres poszukiwań pierwiastka:

a = 1
b = 2

------------------------------------------------

WYNIK:

x0 = 1,18983299

------------------------------------------------
Koniec. Naciśnij klawisz Enter...

Tutaj możesz przetestować działanie prezentowanego skryptu. Przykładowa funkcja posiada pierwiastki w przedziałach [-1,0] oraz [1,2].

Na początek: podrozdziału strony

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.

Metoda połowienia

Algorytm

Opis algorytmu

Specyfikacja problemu

Dane wejściowe

Dane wyjściowe

Zmienne pomocnicze i funkcje

Lista kroków

Schemat blokowy

Programy

Obliczanie pierwiastka funkcji metodą bisekcji