Métodos numéricos y optimización: Método de bisección

Método de bisección

En este método, la mitad del intervalo de incertidumbre es eliminado en cada iteración o paso. Se requieren 3 experimentos en el primer paso o iteración y 2 experimentos en pasos subsiguientes. Para desarrollar este método se tienen los siguientes pasos a continuación:

1. Dividir el intervalo inicial Lo=[a,b] en 4 partes iguales. Donde X0 es el punto medio y X1 y X2 son puntos de ese cuarto.

2. Evaluar la función f(x) en los 3 puntos interiores del intervalo X1, X0 y X2, es decir:

• f1=f(X1)
• f0=f(X0)
• f2=f(X2)

3. Se deben evaluar los siguientes casos en los cuales se debe decidir que parte del intervalo se eliminara:

• Si f2>f0>f1 entonces se elimina el intervalo [X0, b], por lo tanto X1=X0 y X0=b
• Si f2<f0<f1 entonces se elimina el intervalo [a,X0], por lo tanto X0=a y X2=X0
• Si f1>f0 y f2>f0 entonces se eliminan los intervalos [a,X1] y [X2,b] entonces X1=a y X2=b

4. Probar el nuevo intervalo L=b-a que satisfaga el criterio de convergencia L<=Error, si converge se detiene el procedimiento, de lo contrario L=Lo y se regresa al paso 1 del procedimiento.

El siguiente es un ejercicio de ejemplo, que ayudará a entender mejor la aplicación de el método:

Hallar el mínimo de la función objetivo f(x)=x(x-1.5) en el intervalo [0,1], con un 10% de exactitud del valor.

El método de bisección es un método más complejo que la búsqueda exhaustiva, requiere un conjunto más amplio de pruebas y cálculos más extensos. Por lo tanto, para estructurar una base para el algoritmo, se trazará un plan de posición de todas las variables respectivas en la hoja de calculo de EXCEL.
Este plan se compone de los siguientes elementos:
las variables a,b y error están en las celdas B2, B3 y B4 respectivamente y son las celdas de entrada del sistema.
En la fila 5 se tienen las etiquetas de resultados:
Valor puntos: es el valor de la partición del intervalo en 4 partes.
Iteración: cada paso que realiza el algoritmo.
a, x1, x0, x2 y b son los puntos x del intervalo de evaluación del óptimo.
F(x1), F(x2) y F(x0) es la función objetivo evaluada en cada punto del intervalo.
Decisión: evalúa el criterio de convergencia.
Caso: es cada opción para la eliminación de una parte del intervalo (ver paso 3 del procedimiento).

El algoritmo en VBA es el siguiente, nótese que se definen 4 variables y se les asigna una posición en la hoja. La fila 6 se programa por fuera del ciclo FOR_NEXT.

El resultado una vez implementado el algoritmo es el siguiente: