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
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);
}