Metoda połowienia


Tematy pokrewne Podrozdziały  

 

Algorytm

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:

 

1. 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.

 

2. 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:

 

 

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!!!

3. 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 xo w przedziale <a,b>, dla którego funkcja przyjmuje wartość pośrednią:

 

f(a) < f(xo) = 0 < f(b lub   f(a) > f(xo) = 0 > f(b)

 

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 xo jako środek przedziału <a,b> zgodnie ze wzorem:

 

 

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

 

 

Jeśli nierówność jest spełniona, to xo jest poszukiwaną wartością pierwiastka. Zwracamy wynik i kończymy algorytm. W przeciwnym razie za nowy przedział poszukiwań pierwiastka przyjmujemy tą połówkę <a,xo> lub <xo,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 xo.

 

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

xo - pierwiastek funkcji f(x)

Zmienne pomocnicze i funkcje

fa , fb , fo - wartości funkcji odpowiednio w punktach a, b, xo.   fa , fb , foR
εo - określa dokładność porównania z zerem. εo = 0.0000000001
εx - określa dokładność wyznaczania pierwiastka xo.    εx = 0.0000000001

 

Lista kroków

  K01: Czytaj a i b
  K02: faf(a) ;   fbf(b)
  K03: Jeśli fa × fb > 0, to pisz "Funkcja nie spełnia założeń" i zakończ
  K04: Dopóki | a - b | > εx wykonuj K05...K07
K05:
    xo  a + b ;    fof(xo)
2
K06:     Jeśli | fo | < εo, to idź do K08
K07:     Jeśli fafo < 0, to  b ← xoinaczej  a ← xo;   fafo
  K08: Pisz xo i zakończ

 

Schemat blokowy

Wykonanie algorytmu rozpoczynamy od odczytu zakresu poszukiwań pierwiastka danej funkcji. W zmiennych fa i fb 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 xo leżący w środku przedziału <a,b> oraz obliczamy wartość funkcji w punkcie xo i umieszczamy ją w zmiennej fo. Jeśli wartość fo jest dostatecznie bliska zeru (wpada w otoczenie zera o promieniu εo), przerywamy pętlę, wypisujemy xo i kończymy algorytm.

W przeciwnym razie za nowy przedział <a,b> przyjmujemy połówkę wyznaczoną przez xo, w której funkcja zmienia znak. Testujemy iloczyn fa przez fo. Jeśli iloczyn jest ujemny, to różne znaki funkcja przyjmuje w połówce <a,xo>. Zatem za nowy koniec b przyjmujemy xo i kontynuujemy pętlę. W przeciwnym razie zmiana znaku występuje w drugiej połówce przedziału - <xo,b>. Za nowy początek a przyjmujemy xo. Dodatkowo za fa przyjmujemy fo - 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 xo.


 

Programy

Programy wyznaczają miejsce zerowe funkcji:

 

f(x) = x3(x + sin(x2 - 1) - 1) - 1

 

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

 

Efekt uruchomienia programu
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...

 

Free 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.
Code::Blocks
// 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;
}
FreeBASIC
' 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>

 

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

Obliczanie pierwiastka funkcji metodą bisekcji

f(x) = x3(x + sin(x2 - 1) - 1) - 1

(C)2006 mgr Jerzy Wałaszek I LO w Tarnowie


Wpisz do pól edycyjnych zakres przedziału poszukiwań pierwiastka

a = b =
...


List do administratora Serwisu Edukacyjnego I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo  , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

(C)2014 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.