El método de bisección

Basado en el teorema de valor intermedio, recibe el nombre de bisección, o método de la búsqueda binaria.

Suponga que $f$ es una función continua definida dentro del intervalo $[a, b]$ con $f(a)$ y $f(b)$ de signos opuestos. El teorema del valor intermedio inplica que existe un número $p$ en $(a, b)$ con $f(p) = 0$.

El método realiza repetidamente una reducción a la mitad (o bisección) de los subintervalos $[a, b]$ y, en cada paso, localizar la mitad que contiene $p$.

Procedimiento

Para comenzar, sea $a_{1} = a$ , $b_{1} = b$ y sea $p_{1}$ el punto medio de $[a, b]$, es decir $p_{1} = a_{1} + \frac{(b_{1} - a_{1})}{2} = \frac{a_{1} + b_{1}}{2}$

• Si $f({p_1}) = 0$ , entonces $p = p_{1}$
• Si $f({p_1}) \neq 0$, entonces $p_{1}$ tiene el mismo signo que $f(a_{1})$ o $f(b_{1})$
  • Si $f(a_{1})$ y $f(b_{1})$ tienen el mismo signo, $p \in (p_{1}, b_{1})$. Sea $a_{2} = p_{1}$ y $b_{2} = b_{1}$
  • Si $f(a_{1})$ y $f(b_{1})$ tienen signos opuestos, $p \in (a_{1}, p_{1})$. Sea $a_{2} = a_{1}$ y $b_{2} = p_{1}$

Entonces, volvemos a aplicar el proceso al interalo $[a_{2}, b_{2}]$ , hasta encontrar una aproximación a la raíz.

Convergencia y cota de error

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:

$l_{n} = \frac{b_{n}- a_{n}}{2} = \frac{|b-a|}{2^n}$

Como $r_{n}$, que es la raiz n-ésima cualculada, se encuentra siempre dentro del intervalo de búsqueda, tenemos entonces que:

$|r - r_{n}| \leq \frac{b-a}{2^n}$

Tomando limites,

$\lim_{n \to \infty}|r - r_{n}| = 0 \to \lim_{n \to \infty} r_{n} = r$

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.

El error cometido tras realizar $n \geq 0$ iteraciones del método de bisección es

$\varepsilon :=|r - r_{n}| < \frac{b-a}{2^{n+1}}$

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

$n > \frac{ln(b-a) - ln(\varepsilon)}{ln(2)} - 1$

Conclusión

El método de bisección, a pesar de que está conceptualmente claro, tiene desventajas significativas. Su velocidad de convergencia es más lenta y se podria descartar una aproximación intermedia inadvertidamente.

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.

Sin embargo, el método tiene la importante propiedad de que siempre converge a una solución y por esta razón con frecuencia se utiliza como iniciador para los métodos más eficientes.