Login lub e-mail Hasło   

Miejsca zerowe funkcji - Metoda połowienia

Odnośnik do oryginalnej publikacji: http://www.i-lo.tarnow.pl/edu/inf/alg/zm(...)ex.html
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 zastosow...
Wyświetlenia: 14.728 Zamieszczono 04/11/2006

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:

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:

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.

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 , fo R
εo - określa dokładność porównania z zerem. εo = 0.0000000001
εx - określa dokładność wyznaczania pierwiastka xo. εx = 0.0000000001
  krok 1: Odczytaj a i b
  krok 2: fa f(a) ;   fb f(b)
  krok 3: Jeśli fa 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:    
krok 6:     Jeśli | fo | < εo, to idź do kroku 8
krok 7:     Jeśli fa fo < 0, to  b xoinaczej  a xo;   fa fo
  krok 8: Pisz xo i zakończ algorytm

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.


   
   
   

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.

Podobne artykuły


8
komentarze: 79 | wyświetlenia: 1153
111
komentarze: 32 | wyświetlenia: 60725
54
komentarze: 56 | wyświetlenia: 32590
54
komentarze: 68 | wyświetlenia: 31291
50
komentarze: 27 | wyświetlenia: 63525
49
komentarze: 18 | wyświetlenia: 64976
39
komentarze: 50 | wyświetlenia: 23278
39
komentarze: 30 | wyświetlenia: 28845
37
komentarze: 9 | wyświetlenia: 28519
36
komentarze: 37 | wyświetlenia: 23497
34
komentarze: 21 | wyświetlenia: 26316
32
komentarze: 12 | wyświetlenia: 26675
 
Autor
Artykuł

Powiązane tematy






Brak wiadomości


Dodaj swoją opinię
W trosce o jakość komentarzy wymagamy od użytkowników, aby zalogowali się przed dodaniem komentarza. Jeżeli nie posiadasz jeszcze swojego konta, zarejestruj się. To tylko chwila, a uzyskasz dostęp do dodatkowych możliwości!
 

© 2005-2018 grupa EIOBA. Wrocław, Polska