El método de la bisección e implementación en Python

Uno de los métodos numéricos para buscar la raíz de una función más sencillo es el de la bisección. Siendo también uno de los más fáciles de implementar en un programa. El método de la bisección se puede utilizar en funciones continuas que cambian de signo en un rango de valores y solamente tienen una raíz en el mismo. Basándose para ello en una idea sencilla: dividir el rango original el dos y seleccionar aquel en el que la función cambia de signo. La raíz debe estar en este. Por lo que al repetir el proceso se puede acotar la posición de la raíz con la precisión que sea necesaria.

Este método también se puede utilizar para buscar la posición tanto de los máximos como los mínimos de funciones en un rango. Usando para ello el hecho de que la raíz de la derivada indica la posición de valores extremos.

El algoritmo para implementar el método de la bisección

El procedimiento para implementar el método de la bisección se puede dividir en los siguientes pasos:

1. Seleccionar un intervalo inicial [a_0, b_0]en que que el valor de la función cambia de signo (f(a_0)f(b_0)<0)
2. Calcular el punto intermedio del intervalo m_0 = \frac{a_0 + b_0}{2} y evaluar la función en este f(m_0).
3. Si f(m_0) = 0 se ha encontrado la raíz y finaliza el proceso. En caso contrario se debe seleccionar el nuevo subintervalo como aquel en el que la función cambia de signo. Así, en el caso de que se tenga f(a_0)f(m_0)<0 el nuevo intervalo será [a_0, m_0], mientras si se da que f(m_0)f(m_0)<0 el nuevo intervalo será [m_0, b_0].
4. Repetir los pasos 2 y 3 hasta que el intervalo sea tan pequeño como se desee.
5. La posición de la raíz, en el caso de que no se hubiese enocntardo, se puede estimar con m_N = \frac{a_N + b_N}{2}.

Estimación del error cometido

Si la función evaluada es continua y esta cambia de signo en un rango, entonces debe existir al menos una raíz en este. Por lo tanto, si se toma el punto medio como solución, el error que se comente es inferior a la mitad del rango. Esto es

\varepsilon = \left| x_{true} - x_N \right| \le \frac{b_N - a_N}{2} = \frac{b_0-a_0}{2^{N+1}}

donde x_{true} indica la posición real de la raíz. De este modo, si se conoce el error máximo deseado \varepsilon se puede saber cual es el número máximo de pasos necesarios para alcanzarla. Simplemente se debe despejar el valor de N

N = \left\lceil \frac{\ln\left|\frac{b_0-a_0}{\varepsilon}\right|}{\ln|2|} \right\rceil

Implementación en Python del método de la bisección

Con esto es relativamente sencillo implementar el método de la bisección en Python, por ejemplo, con el siguiente código:

import math


def bisection(fun, x_a, x_b, eps=None, steps=10):
    # The bisection method cannot be applied
    if fun(x_a) * fun(x_b) >= 0:
        print("The bisection method cannot be applied")
        return None
    
    # Calculate number of stepds base on eps
    if eps is not None:
        steps = math.ceil(math.log((x_b - x_a) / eps) / math.log(2))
    
    # The bisection method
    for n in range(steps + 1):
        x_m = (x_a + x_b) / 2
        
        if f(x_m) == 0:
            return x_m
        
        if f(x_a) * f(x_m) < 0:
            x_b = x_m
        else:
            x_a = x_m
    
    return (x_a + x_b) / 2

Una función que tiene como entrada la función y los puntos iniciales e intermedios del rango. Adicionalmente tiene dos parámetros opcionales, el error ( eps) que se desee tener en el resultado y el número máximo de iteraciones ( steps). En el caso de que no se indique nada, se itera 10 veces, en el caso contrario se calcula el número de iteraciones a partir de valores del error o la cantidad introducida.

Nada más comenzar se comprueba que la función cumpla la condición de cambiar de signo en el rango, si no es así se sale de la función sin un resultado. Posteriormente, en el caso de que se indique un valor para el error, se usará esta para obtener el número de iteraciones. En caso contrario se usará el valor de steps. Finalmente se implementa el algoritmo siguiendo los pasos indicados anteriormente.

Validación de la función

Ahora se puede probar el correcto funcionamiento de la función con un polinomio tal como x^2 + 2 x - 8, que tiene una raíz en -4 y otra en 2. Llamando a la función con diferentes márgenes de error vemos cómo se puede controlar la precisión del resultado fácilmente.

f = lambda x: x**2 + 2*x - 8

bisection(f, 0, 5, 1e-2)  # 1.99951171875
bisection(f, 0, 5, 1e-6)  # 2.0000000298023224
bisection(f, 0, 5, 1e-12) # 2.0000000000000284
bisection(f, 0, 5, 1e-16) # 2.0

Conclusiones

En esta ocasión hemos visto cómo con una idea tan sencilla como la que se encuentra detrás del método de la bisección se puede obtener la posición de la raíz de una función. Pudiendo conocer con antelación la precisión del resultado.