JustPaste.it

Miejsca zerowe funkcji - Metoda połowienia

00fc718aabddac4826b9aff8239a68b6.gif

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ę:

7121a3c7955fe0a810b1c093248a85ea.gif

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ę:

8ff22c7fadf112a0690a6297674b7f79.gif

Funkcja w przedziale <-2,1> posiada następujący wykres:

3b3fba5d4fd02b2fe24e3b1e710a2802.gif

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 wymogiem, 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:

e99b803d1bc4f25f100e25908735c02b.gif

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:

14bd74d151c9d608acfb7fecf33d876a.gif

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.

015a282938dde72b420f8278e386df0b.gif

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 c5b7b306dc58af83b394462ad7502b7c.gif 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 , fo c5b7b306dc58af83b394462ad7502b7c.gif R
εo - określa dokładność porównania z zerem. εo = 0.0000000001
εx - określa dokładność wyznaczania pierwiastka xo. εx = 0.0000000001
5ce05843ac6186a9fcf07a9d04d3054c.gif
  krok 1: Odczytaj a i b
  krok 2: fa 56b14ee19440f1dd744f351b7c614062.gif f(a) ;   fb 56b14ee19440f1dd744f351b7c614062.gif f(b)
  krok 3: Jeśli fa 4825bc34d1100f0afa57e178b6906593.gif fb > 0, to pisz "Funkcja nie spełnia założeń" i zakończ algorytm
  krok 4: Dopóki | a - b | > εx wykonuj kroki 5..7
krok 5:     8530b3d2daaa74bf80187977bc90935a.gif
krok 6:     Jeśli | fo | < εo, to idź do kroku 8
krok 7:     Jeśli fa 4825bc34d1100f0afa57e178b6906593.gif fo < 0, to  b 56b14ee19440f1dd744f351b7c614062.gif xo,  inaczej  a 56b14ee19440f1dd744f351b7c614062.gif xo;   fa 56b14ee19440f1dd744f351b7c614062.gif fo
  krok 8: Pisz xo i zakończ algorytm

92ecc42cff074bdf940c2a705d497495.gif

 

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.


b127fa9bb931eace8b17db6705f1feb0.gif

50935f00685a4aa036f3e5aa7df9d431.gif    
   
   

91c495571638d61607fff8d388e24963.gif

Poniższe, przykładowe programy są praktyczną realizacją omawianego w tym rozdziale algorytmu. Zapewne można je napisać bardziej efektywnie. To już twoje zadanie. Dokładny opis stosowanych środowisk programowania znajdziesz we wstępie. Programy przed opublikowaniem w serwisie edukacyjnym zostały dokładnie przetestowane. Jeśli jednak znajdziesz jakąś usterkę (co zawsze może się zdarzyć), to prześlij o niej informację do autora. Pozwoli to ulepszyć nasze artykuły. Będziemy Ci za to wdzięczni.

  
       

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

Wydruk z uruchomionego 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...
Microsoft Visual Basic 2005 Express Edition

 

Borland
Delphi 7.0
Personal
Edition		 
// 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;

{$APPTYPE CONSOLE}

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) : real;
begin
  Result := x * x * x * (x + sin(x * x - 1) - 1) - 1;
end;

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

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

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.
Borland
C++ Builder
6.0
Personal
Edition		 
// 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 <math>

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(int argc, char* argv[])
{

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

  cout.precision(8);     // 8 cyfr po przecinku
  cout.setf(ios::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";
  system("pause");
  return 0;
}
Microsoft
Visual
Basic 2005
Express
Edition		 
' Program znajduje miejsce zerowe funkcji f(x)
' za pomocą algorytmu połowienia - bisekcji
'---------------------------------------------
' (C)2006 mgr J.Wałaszek       I LO w Tarnowie

Module Module1

  Const EPS0 = 0.0000000001 ' dokładność porównania z zerem
  Const 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(ByVal x As Double) As Double
    Return x * x * x * (x + Math.Sin(x * x - 1) - 1) - 1
  End Function

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

  Sub Main()

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

    Console.WriteLine("Obliczanie pierwiastka funkcji - metoda bisekcji")
    Console.WriteLine("f(x) = x^3*(x+sin(x^2-1)-1)-1")
    Console.WriteLine("------------------------------------------------")
    Console.WriteLine("(C)2006 mgr Jerzy Wałaszek       I LO w Tarnowie")
    Console.WriteLine()
    Console.WriteLine("Podaj zakres poszukiwań pierwiastka:")
    Console.WriteLine()
    Console.Write("a = ") : a = Val(Console.ReadLine)
    Console.Write("b = ") : b = Val(Console.ReadLine)
    Console.WriteLine()
    Console.WriteLine("------------------------------------------------")
    Console.WriteLine()
    Console.WriteLine("WYNIK:")
    Console.WriteLine()
    fa = f(a) : fb = f(b)
    If fa * fb > 0 Then
      Console.WriteLine("Funkcja nie spełnia założeń")
    Else
      While Math.Abs(a - b) > EPSX
        x0 = (a + b) / 2 : f0 = f(x0)
        If Math.Abs(f0) < EPS0 Then Exit While
        If fa * f0 < 0 Then
          b = x0
        Else
          a = x0 : fa = f0
        End If
      End While
      Console.WriteLine("x0 = {0,15:F8}", x0)
    End If
    Console.WriteLine()
    Console.WriteLine("------------------------------------------------")
    Console.WriteLine("Koniec. Naciśnij klawisz Enter...")
    Console.ReadLine()

  End Sub

End Module
Python 
# -*- coding: cp1250 -*-
# Program znajduje miejsce zerowe funkcji f(x)
# za pomocą algorytmu połowienia - bisekcji
#---------------------------------------------
# (C)2006 mgr J.Wałaszek       I LO w Tarnowie

import math

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>
#-----------------------------------------
def f(x):
  return x * x * x * (x + math.sin(x * x - 1) - 1) - 1

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

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
a = float(raw_input("a = "))
b = float(raw_input("b = "))
print
print "-------------------------------------------------"
print
print "WYNIK:"
print
fa, fb = f(a), f(b)
if fa * fb > 0: print "Funkcja nie spelnia zalozen"
else:
  while abs(a - b) > EPSX:
    x0 = (a + b) / 2
    f0 = f(x0)
    if abs(f0) < EPS0: break    
    if fa * f0 < 0: b = x0
    else: a, fa = x0, f0
  print "x0 = %15.8f" % x0
print
print "---------------------------------------------------------"
raw_input("Koniec. Nacisnij klawisz Enter...")
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>
 
 
Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

 

Źródło: mgr Jerzy Wałaszek

technologia programowanie