Wyznaczanie miejsc zerowych funkcji metodą połowienia przedziałów
Kolejnym algorytmem wykorzystującym metodę binarną (tu połowienie na dwa podzbiory) poszukiwania elementu w uporządkowanym ciągu (a tym są kolejne argumenty funkcji z przedziału [a,b]) jest wyznaczanie miejsc zerowych funkcji ciągłych.
Omawiany przykład bazuje na funkcji f(x)=x2-2
Kroki algorytmu wyznaczania miejsc zerowych
Podstawowe kroki algorytmu można zapisać jak poniżej:
- znajdź środek przedziału
- oblicz wartość funkcji dla wyznaczonego środka
- z dwóch przedziałów wybierz ten, na którego końcach wartość badanej funkcji ma przeciwne znaki (czyli iloczyn fa⋅fs<0, w takim przedziale dla funkcji ciągłej jest miejsce zerowe)
Powyższe kroki powtarzaj dopóki różnica granic przedziałów jest większa od zadanej dokładności.
Schemat algorytmu wyznaczania miejsc zerowych metoda połowienia przedziałów
W algorytmie tym występuje instrukcja obliczająca wartość badanej funkcji dla podanego argumentu (badanaFunkcja(x)). Funkcję tę należy wcześniej zaimplementować.
Przykładowy kod funkcji realizujący podany algorytm wyznaczani miejsc zerowych metodą połowienia przedziałów
Wskazówka:
float miejscaZerowe(float a,float b,float dokladnosc)
{
float fa,fs,//posrednie wartości dla funkcji f(a) i f(sr)
sr=0;//srodek przedzialu
fa = badanaFunkcja(a);
while (b - a > dokladnosc)
{
sr=(a+b)/ 2;
fs = badanaFunkcja(sr);
if (fa * fs < 0){
a = a - dokladnosc;
b = sr;
}
else
{
a = sr;
b = b - dokladnosc;
fa = fs;
}
}
return sr;
}
Przykład aplikacji obliczającej miejsca zerowe funkcji f(x)=x2-2
Pełny kod klasy Form utworzonej formatki aplikacji liczącej miejsca zerowe
Wskazówka:
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;
namespace _19AlgMiejscaZerowe
{
public partial class Form1 : Form
{
float badanaFunkcja(float x)
{
//postac x^2-2
return x*x-2;
}
float miejscaZerowe(float a,float b,float dokladnosc)
{
float fa,fs,//posrednie wartości dla funkcji f(a) i f(sr)
sr=0;//srodek przedzialu
fa = badanaFunkcja(a);
while (b - a > dokladnosc)
{
sr=(a+b)/ 2;
fs = badanaFunkcja(sr);
if (fa * fs < 0){
a = a - dokladnosc;
b = sr;
}
else
{
a = sr;
b = b - dokladnosc;
fa = fs;
}
}
return sr;
}
public Form1()
{
InitializeComponent();
}
private void textBox1_KeyPress(object sender, KeyPressEventArgs e)
{
//wyskocz na BackSpcae, Enter lub minus
if (e.KeyChar == 8 || e.KeyChar == 13 || e.KeyChar == '-') return;
if (e.KeyChar < '0' || e.KeyChar > '9') e.Handled = true;//blokuj nienumeryczne
}
private void textBox4_KeyPress(object sender, KeyPressEventArgs e)
{
//zamień kropkę na przecinek (seperator dziesiętny)
//przecinek jest ustawiony jako znak separatora na Polskę
if (e.KeyChar == '.' || e.KeyChar == ',') { e.KeyChar = ','; return; }
//wyskocz na BackSpcae
if (e.KeyChar == 8) return;
if (e.KeyChar < '0' || e.KeyChar > '9') e.Handled = true;//blokuj nienumeryczne
}
private void button1_Click(object sender, EventArgs e)
{
if (textBox1.Text.Length < 1
|| textBox2.Text.Length < 1
|| textBox3.Text.Length < 1) return;
float a = float.Parse(textBox1.Text),
b = float.Parse(textBox2.Text),
d = float.Parse(textBox3.Text),
sAB=(a+b)/2;
//szukaj pierwszego miejsca zerowego
float x1 = miejscaZerowe(a, sAB, d);
//szukaj drugiego miejsca zerowego
float x2 = miejscaZerowe(sAB, b, d);
//wyswietl wynik z dokladnoscia do n miejsc po przecinku
int n = textBox3.Text.Length - 2;//bo zapis 0,001
MessageBox.Show("x1=" + x1.ToString("F" + n.ToString())
+ ", x2=" + x2.ToString("F" + n.ToString()),
"Szukane miejsca zerowe:",
MessageBoxButtons.OK,
MessageBoxIcon.Information
);
}
}
}
