La solución acorralada. El método de la bisección

Comenzamos con los métodos de aproximación de raíces de funciones.  En este caso tomaremos como herramienta principal el teorema de Bolzano que podemos resumir en la siguiente imagen:

Es importante asegurar que en el interior del intervalo de trabajo, $[a,b]$, la primera derivada de la función no se anula en ningún punto. 

Así pues, cuando nos digan que tenemos que realizar el método de bisección en un intervalo $[a,b]$ comprobaremos los siguientes puntos:

1. Que se cumple el teorema de Bolzano en los extremos del intervalo.
2. Que la derivada de la función no se anula en ningún punto del interior del mismo.

Si alguno de estos puntos no se verifican tendremos que redefinir apropiada e inteligentemente el intervalo de inicio.  Esto es así porque la combinación de esos dos puntos nos asegura por un lado que existe la raíz y que es única.  De no ser así tendríamos que encontrar un nuevo intervalo en el que la raíz sea única y por lo tanto tenga sentido aplicar el método aproximado para encontrarla.

Método de la bisección

1. Supongamos que hemos llegado a la conclusión de que $f(x)$ tiene una raíz en el intervalo $[a,b]$.
2. Calculemos el punto medio del intervalo:  $m=\dfrac{a+b}{2}$
3. Calculamos lo que vale la función al sustituir $x$ por el valor $m$:  $f(m)$.
4. Definimos los intervalos $[a,m]$ y $[m,b]$ y nos quedaremos con el que se siga verificando el teorema de Bolzano desestimando el otro.
5. Volvemos a realizar el proceso con el nuevo intervalo.

En este método siempre nos quedamos con el intervalo que contiene la raíz, por lo tanto cualquiera de sus puntos sirve de aproximación a la misma.  Evidentemente estaremos cometiendo un error si comparamos la solución propuesta con la solución exacta ideal -- a la que no podemos acceder --.

El error en este método, en cada paso, es muy simple:

$\epsilon=\dfrac{b-a}{2}$,

es decir, como la solución estará en algún punto interior del intervalo considerado -- podéis tomar el que queráis del mismo -- a lo sumo, en el peor de los casos, la diferencia entre el punto aproximado propuesto y la solución exacta ideal $x^*$ será la mitad del intervalo en cuestión.

Si hacemos $n$ iteraciones del proceso habremos reducido la longitud del intervalo inicial en un factor $2^n$.  Por lo tanto, el error después de $n$ iteraciones será la longitud del intervalo de inicio dividida por $2^n$:

$\epsilon_n=\dfrac{b-a}{2^n}$

Ejemplo visual:

Criterio de parada

¿Cuándo pararemos el método?

Pues se pueden dar dos casos:

a)  Que en alguna iteración cuando calculemos el valor de la función para un $m_i$ obtengamos que $f(m_i)=0$.  Entonces habremos tenido la increíble suerte de que hemos dado con la solución exacta.

b)  Que el error cometido en una iteración esté por debajo de una determinada $K$ cantidad definida al principio:    $\epsilon_i<K$.  Usualmente $K$ se expresará como una potencia negativa de diez, indicando por tanto que tenemos un número dado de cifras decimales exactas.  Podesr ejemplo, si decimos que podemos parar el proceso cuando el error sea inferior a $10^{-4}$, lo que estamos expresando es que nos basta con dar la solución aproximada con cuatro cifras decimales exactas.

c)  Puede que haya veces en que nos digan que paremos el proceso cuando la longitud del intervalo en la iteración i-ésima esté por debajo de de una cantidad $K$ predefinida, usualmente también dada en potencias negativas de 10.

Número de iteraciones 

Este método tiene la gracia de que nos permite, una vez definida la cota del error prefijada, saber cuantas iteraciones necesitamos para alcanzarla.  Por ejemplo, podemos decir que queremos 14 cifras decimales exactas, por lo tanto se tiene que cumplir:

$\epsilon_n<10^{-14}$

Basta poner el error:   

$\dfrac{b-a}{2^n}<10^{-14}$

Y despejar de ahí $n$, que nos dará el número de iteraciones necesarias para que se cumpla esa condición.

Ale, a seguir estudiando...