Método de Bisección

El método de bisección es un algoritmo de búsqueda de raíces que trabaja dividiendo el intervalo a la mitad y seleccionando el subintervalo que tiene la raíz. Se basa en el Teorema de Bolzano:

Sea $f$ una función real continua en un intervalo cerrado $[a,b]$ con $f(a)$ y $f(b)$ de signos contrarios. Entonces existe al menos un punto $c$ del intervalo abierto $(a,b)$ con $f(c)=0$.

Bajo las condiciones del teorema el algoritmo siempre converge. Si deseamos una tolerancia de error absoluto $\epsilon$ necesitamos $n\geq \frac{\log\left(\frac{b-a}{\epsilon}\right)}{\log{2}}$ iteraciones.

Diagrama de flujo

Inicio
Inicio
Los datos
ingresados son
correctos?
Los datos...
Entrada: a, b, 
error, max. iteraciones
Entrada: a, b,...
k=0
k=0
f(a)*f(x)>0?
f(a)*f(x)>0?
f(x)=0
f(x)=0
No
No
a=x
a=x
b=x
b=x
No
No
k+1
k+1
k<kmax
k<kmax
Fin
Fin
No
No
x=(a+b)/2
x=(a+b)/2
El cero de la
función es x
El cero de la...
No
No
Viewer does not support full SVG 1.1

Código

Considerarémos el siguiente codigo en C++:

///////////////////////////////////////////////////////////////////////////////////
// Programa para aproximar la raiz de una funcion f entre a y b.		 //
// El programa requiere un subprograma para la función f, los puntos 		 //	
// a y b, la tolerancia de convergencia eps, y el máximo número 		 //
// de bisecciones permitidas, kmax. 						 //
// El programa muestra una tabla con los intervalos elegidos y sus puntos medios //
// como lo hace el algoritmo de la bisección					 //
///////////////////////////////////////////////////////////////////////////////////
# include <iostream>
# include <iomanip>
# include <math.h> // para log x
using namespace std; // Para usar cout


long double f(long double x); // Declara la función f

int main(){
	int kmax;
	long double a, b, eps;
	cout << "Ingrese a, b, eps, kmax\n";
	cin >> a >> b >> eps >> kmax;				
	// Verificamos que los valores ingresados permitan usar el algoritmo
	while(b<a || isnan(f(a)) || isnan(f(b)) || f(a)*f(b)>0){
		if(b<a)
			cout << "Ingrese un intervalo de la forma (a,b) con a<b\n";
		else if(isnan(f(a)))
			cout << "La evaluacion en " << a << " no esta definida\n";	
		else if(isnan(f(b)))
			cout << "La evaluacion en " << b << " no esta definida\n";
		else if(f(a)*f(b)>0)
			cout << "La funcion tiene el mismo signo en a y en b\n";	
	cout << "Ingrese nuevamente valores para a y b\n";
	cin >> a >> b;		
	}
	cout << "Los valores ingresados son \n";
	cout << "a= " << a << "  b= " << b;
	cout << " eps = " << eps << "  kmax = " << kmax << endl;
	cout << "Los resultados son\n"; // Muestra el encabezado de la tabla
	cout << "k" << setw(7) << "x" << setw(11) << "f(x)" << setw(8) << "a" << setw(9) <<  "b\n";
	int k=1;
	cout.setf(ios::fixed);
	float x=0.5*(a+b); // Primera bisección
	cout << 0 << setprecision(6) << setw(10) << x << setw(10) << f(x)
		 << setprecision(4) << setw(8) << a << setw(8) << b << endl;
	while ((k<=kmax) && ((b-a)/2>eps)){
		if(f(x)*f(a)>0)  	 // Compara para
			a=x;			 // elegir el
		else if(f(x)*f(b)>0) // intervalo
			b=x;			 // correcto
		else{
			cout << "El cero de la funcion es " << x; 
			exit(0);
		} 
	x=0.5*(a+b); // Siguiente bisección
	// Muestra los valores de k, x, y, a, b
	cout << k << setprecision(6) << setw(10) << x << setw(10) << f(x)
		 << setprecision(4) << setw(8) << a << setw(8) << b << endl;
	k++; // incrementa el contador del ciclo
	}
	if (k>kmax) cout << "El algoritmo no converge en menos de " << kmax << "pasos";
	else cout << "El cero de la funcion es " << setprecision(6) << x;
	return 0;
}
// El subprograma para ingresar la función f
long double f(long double x){
	return pow(x,3)-sin(x);
}
José Luis León Medina
José Luis León Medina
Investigador Posdoctoral CONAHCYT

Mis intereses en investigación se centran en el campo de la topología algebraica, en particular propiedades homotópicas como la complejidad topológica.