Znajdowanie miejsca zerowego metodą połowienia przedziałów

powrót

Omawiany algorytm wyznacza miejsce zerowe z dokładnością do pewnego $$\epsilon$$ (dokładność tą ustalamy na początku programu) w przedziale obustronnie domkniętym $$[a,\ b]$$ przy następujących założeniach:

1. Funkcja jest ciągła (oznacza to, że jej wykres narysujemy nie odrywając ołówka, chodź definicja funkcji ciągłej jest znacznie bardziej złożona)
2. W przedziale $$[a,\ b]$$ funkcja ma dokładnie jedno miejsce zerowe.

 Przyjrzyjmy się poniższemu rysunkowi spełniającemu powyższe założenia:

Dla każdej takiej funkcji będzie zachodził warunek:

$$f(a)\cdot f(b)<0$$

ponieważ wartości na krańcach przedziałów będą zawsze przeciwnych znaków (chyba, że miejsce zerowe znajduje się w jednym z krańców).

W pierwszym kroku wyznaczamy środek przedziału i sprawdzamy, czy nie jest on już miejscem zerowym. Jeśli nie to sprawdzamy czy 

$$f(a)\cdot f(srodek)<0$$

Jeśli tak, to miejsce zerowe musi znajdować się w przedziale $$[a,\ srodek)$$, w przeciwnym razie w przedziale $$(srodek,\ b]$$. W pierwszej sytuacji wartość $$b$$ zostanie zastąpiona wartością środka, w drugiej wartość $$a$$. W omawianym przykładzie zachodzi sytuacja pierwsza:

Czynności dzielenia przedziału $$[a,\ b]$$ powtarzamy do momentu, aż nie będzie spełniony warunek $$\epsilon < a-b$$:

Gdy osiągniemy szukaną dokładność, tzn. $$b-a<=\epsilon$$, możemy wypisać miejsce zerowe, które przyjmuje wartość $$\frac{b-a}{2}$$.

Przedstawione poniżej rozwiązanie szuka miejsca zerowego dla wielomianu:

$$f(x)=x^3-3x^2+2x-6$$,

który spełnia podane na początku artykułu założenia. Program wyznacza miejsce zerowe z dokładnością do pięciu miejsc po przecinku. Funkcję

double f(double a, double b, double epsilon)

możemy dowolnie zmieniać, tak samo przedział $$[a,\ b]$$ oraz $$\epsilon$$ pamiętając o założeniach. 

Rozwiązanie w C++:

//algorytm.edu.pl
#include<iostream>
#include<iomanip>
using namespace std;

double f(double x)
{
	//rozpatrujemy wielomian f(x) = x^3 - 3x^2 + 2x - 6 
	return x*(x*(x-3)+2)-6; //rozbijam schematem Hornera
}

double polowienie_przedzialow(double a, double b, double epsilon)
{
	if(f(a)==0.0)return a;
	if(f(b)==0.0)return b;
	
	double srodek;
	
	while(b-a > epsilon)
	{
		srodek = (a+b)/2;
		
		if(f(srodek) == 0.0) //jesli miejsce zerowe jest w srodku 
			return srodek;
		
		if(f(a)*f(srodek)<0) 
			b = srodek;
		else
			a = srodek;
	}
	return (a+b)/2;
}

int main()
{
	double a = -10, b = 10, epsilon = 0.00001;
	
	cout<<"Znalezione miejsce zerowe wynosi: ";
	cout<<fixed<<setprecision(5)<<polowienie_przedzialow(a, b, epsilon);

	return 0;
}

Rozwiązanie rekurencyjne:

double polowienie_przedzialow(double a, double b, double epsilon)
{
	if(f(a)==0.0)return a;
	if(f(b)==0.0)return b;
	
	double srodek = (a+b)/2;
	
	if(b-a <= epsilon) return srodek;
		
	if(f(a)*f(srodek)<0) 
		return polowienie_przedzialow(a, srodek, epsilon);
		
	return polowienie_przedzialow(srodek, b, epsilon);
}