Metoda bisecției

Aproximarea numerică a zerourilor unei funcții continue folosind metoda bisecției.

Aspecte teoretice:

O ecuație de forma ax+b=0 se numește liniară. Orice ecuație care nu are această formă se numește neliniară, putând fi scrisă sub forma f(x)=0. Dacă funcția f(x) are forma unui polinom sau poate fi adusă la această formă, ecuația se numește algebrică. În caz contrar (f(x) are o formă oarecare) ecuația se numește transcendentă. De exemplu, ecuațiile.

sunt ecuații algebrice, iar ecuațiile:

sunt transcendente.

Un punct eps din intervalul de definiție al lui f cu proprietatea că f(eps) = 0 se numește zerou al funcției f sau rădăcină a ecuației f(x) = 0. Metodele de rezolvare a ecuațiilor neliniare se împart în două mari categorii: metode de partiționare și metode de aproximații succesive.
În cazul metodelor de partiționare, intervalul de lucru este micșorat progresiv, până când lungimea intervalului este suficient de mică pentru a satisface o anumită precizie impusă. Dintre aceste metode amintim: metoda bisecției (sau a înjumătățirii intervalului) și metoda secantei. Acestea se caracterizează printr-o convergență lentă, dar rădăcina este întotdeauna izolată într-un interval de lungime suficient de mică. Metodele de aproximații succesive pornesc de la o aproximație inițială, care este apoi îmbunătățită în pași succesivi și, în anumite condiții, converge către soluția exactă. Aceste metode sunt, de regulă, mai rapide decât metodele de partiționare, dar, în anumite situații, pot fi divergente.
Metodele de partiționare se pretează utilizării tehnicii Divide et Impera pentru implementare.
Pentru exemplificare, ne oprim asupra metodei bisecției, cea mai simplă metodă de rezolvare a ecuațiilor algebrice și transcendente. Presupunem că rădăcina exactă a ecuației f(x) = 0, eps, aparține intervalului [a; b]. Dacă funcția f este continuă, iar rădăcina eps este singurul zerou al lui f în intervalul [a; b], atunci în extremitățile intervalului funcția ia valori de semne contrare, f(a)f(b) < 0. Determinarea aproximației epsaprox a rădăcinii exacte cu o precizie eps > 0, folosind metoda bisecției, presupune: intervalul [a; b] se înjumătățește – se calculează c = (a + b)/2, mijlocul intervalului; dacă produsul f(a)f(c) < 0 atunci rădăcina se găsește între a și c. Astfel, c devine extremitatea dreaptă a intervalului și procedeul se reia; dacă f(c)f(b) < 0, rădăcina se găsește între c și b. În acest caz, c devine extremitatea stângă a intervalului și se reia procedeul.
Această schemă se aplică în mod repetitiv până cand lungimea intervalului [a; b] este suficient de mică sau |f(c)| < eps, caz în care soluția aproximativă este c.
Implementarea algoritmului se va realiza atât recursiv, cât și iterativ.

Cod Sursa C++

// MetodaBisectieiCPP.cpp : Defines the entry point for the console application.
//
 
#include "stdafx.h"
#include 
#define eps 0.1e-10
 
using namespace std;
 
double func1(double x)
{
	//o radacina in intervalul [1 2]
	return x*x - 2;
}
 
double func2(double x)
{
	//o radacina in intervalul [0 1]
	return x*x*x - 2 * x*x + 3 * x - 1;
}
 
double func3(double x)
{
	//o radacina in intervalul [2 4]
	return 4.5*cos(x / 3)*cos(x / 3) - x / 4;
}
 
double func4(double x)
{
	//o radacina in intervalul [-1 1]
	return exp(x) - 1;
}
 
double func5(double x)
{
	//o radacina in intervalul [-2 -1]
	return x*x*x - x*x - 3 * atan(x) + 1;
}
 
void validareDate(double a, double b, double(*f)(double))
{
	if ((*f)(a) == 0)
	{
		cout << a << " este solutie" << endl;
		exit(1);
	}
	if ((*f)(b) == 0)
	{
		cout << b << " este solutie" << endl;
		exit(1);
	}
	if ((*f)(a)*(*f)(b) > 0)
	{
		cout << "Nu exista solutie sau exista solutii multiple" << endl;
		exit(1);
	}
}
 
double bisectieRec(double a, double b, double(*f)(double))
{
	double c = (a + b) / 2;
	if (abs((*f)(c)) < eps || abs(a - b) < eps)
		return c;
	if ((*f)(a)*(*f)(c) < 0)
		return bisectieRec(a, c, f);
	else
		return bisectieRec(c, b, f);
}
 
double bisectieIter(double a, double b, double(*f)(double))
{
	double c;
	do
	{
		c = (a + b) / 2.0;
		if (abs((*f)(c)) < eps)
			return c;
		if ((*f)(a)*(*f)(c) < 0)
			b = c;
		else
			a = c;
	} while (abs(b - a) >= eps); //conditia de oprire
	return c;
}
 
int main()
{
	double s;
	double a, b;
	cout << "a= ";
	cin >> a;
	cout << "b= ";
	cin >> b;
	cout.precision(10);
	validareDate(a, b, &func5); //func1, func2, func3, func4
	s = bisectieRec(a, b, &func5); //func1, func2, func3, func4
	cout << "\nSolutia obtinuta cu algoritmul recursiv, s = " << s << endl;
	s = bisectieIter(a, b, &func5); //func1, func2, func3, func4
	cout << "\nSolutia obtinuta cu algoritmul iterativ, s = " << s << endl;
	system("pause");
}

Rezultat