Método de bisección

En matemáticas, el método de bisección , también llamado dicotomía, 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.

Unas cuantas iteraciones del método de bisección aplicadas en un intervalo [a1;b1]. El punto rojo es la raíz de la función.

Introducción

editar

Este es uno de los métodos más sencillos y de fácil intuición para resolver ecuaciones de una variable, también conocido como Método de Intervalo Medio.[1]​ Se basa en el teorema del valor intermedio (TVI), el cual establece que toda función continua   en un intervalo cerrado   toma todos los valores que se hallan entre   y  . Esto es que todo valor entre   y   es la imagen de al menos un valor en el intervalo  . En caso de que   y   tengan signos opuestos, el valor cero sería un valor intermedio entre   y  , por lo que con certeza existe un   que cumple  . De esta forma, se asegura la existencia de al menos una solución de la ecuación  .

El método consiste en lo siguiente:

  • Debe existir seguridad sobre la continuidad de la función   en el intervalo  
  • A continuación se verifica que  
  • Se calcula el punto medio   del intervalo   y se evalúa   si ese valor es igual a cero, ya hemos encontrado la raíz buscada
  • En caso de que no lo sea, verificamos si   tiene signo opuesto con   o con  
  • Se redefine el intervalo   como   o   según se haya determinado en cuál de estos intervalos ocurre un cambio de signo
  • Con este nuevo intervalo se continúa sucesivamente encerrando la solución en un intervalo cada vez más pequeño, hasta alcanzar la precisión deseada

En la siguiente figura se ilustra el procedimiento descrito.

El método de bisección es menos eficiente que el método de Newton, pero es mucho más seguro para garantizar la convergencia. Si   es una función continua en el intervalo   y  , entonces este método converge a la raíz de  . De hecho, una cota del error absoluto es:

 

en la n-ésima iteración. La bisección converge linealmente, por lo cual es un poco lento. Sin embargo, se garantiza la convergencia si   y   tienen distinto signo.

Si existieran más de una raíz en el intervalo entonces el método sigue siendo convergente pero no resulta tan fácil caracterizar hacia qué raíz converge el método.

Algoritmo

editar

Para aplicar el método consideremos tres sucesiones   definidas por las siguientes relaciones:

 

Donde los valores iniciales vienen dados por:

 

Se puede probar que las tres sucesiones convergen al valor de la única raíz del intervalo:

 

Implementación en Python

editar
from typing import Callable, Tuple

def bisection(f: Callable, a: float, b: float, xtol=0.001, maxiter=100) -> Tuple[float, int]:
    """
    Encuentra una raíz de la función f en el intervalo [a, b] utilizando el método de la bisección.

    :param f: La función cuya raíz se busca.
    :param a: Extremo izquierdo del intervalo.
    :param b: Extremo derecho del intervalo.
    :param xtol: Tolerancia de error en la raíz (diferencia mínima entre a y b).
    :param maxiter: Número máximo de iteraciones permitidas.
    :return: Una tupla que contiene la aproximación de la raíz y el número de iteraciones realizadas.
    :raise ValueError: Si f(a) y f(b) tienen el mismo signo, lo que significa que no hay una raíz en el intervalo.
    :raise Exception: Si se excede el número máximo de iteraciones permitidas.
    """

    if f(b) * f(a) > 0:
        raise ValueError('No existe raíz en el intervalo dado')

    nit = 0
    while nit <= maxiter:
        nit += 1
        c = (a + b) / 2
        if abs(f(c)) <= xtol:
            return c, nit
        elif f(c) * f(a) < 0:
            b = c
        else:
            a = c

    raise Exception("El número máximo de iteraciones permitidas ha sido excedido.")

Demostración de la convergencia

editar

Suponiendo que se cumplen las condiciones iniciales para la puesta en práctica del algoritmo, definimos r como una raíz dentro del intervalo [a, b]. El intervalo de búsqueda en el n-ésimo paso tiene longitud:

 

Como  , que es la raíz n-ésima calculada, se encuentra siempre dentro del intervalo de búsqueda, tenemos entonces que:

 

Tomando límites,

 

Queda demostrado entonces, que si se cumplen las condiciones iniciales del problema, el método de bisección converge al menos, a una de las raíces que se encuentran en el intervalo señalado.

Cota de error

editar

El error cometido tras realizar   iteraciones del método de bisección es[2]

 

Para lograr un error inferior a  , el número de iteraciones   a realizar debe ser

 

Bibliografía

editar
  • Richard L Burden, J. Douglas Faires (2000), "Numerical Analysis, (7th Ed)", Brooks/Cole. ISBN 0-534-38216-9.
  • Corliss, George (1977), «Which root does the bisection algorithm find?», SIAM Review 19 (2): 325-327, ISSN 1095-7200, doi:10.1137/1019044 .

Referencias

editar
  1. «Copia archivada». Archivado desde el original el 20 de julio de 2014. Consultado el 10 de febrero de 2014. 
  2. «Método de bisección». www.matesfacil.com. Consultado el 22 de febrero de 2019.