2.1 Algoritmo de bisección
El algoritmo de bisección es un método sencillo para encontrar las raíces de funciones unidimensionales. El objetivo es encontrar una raíz \(x_0\in\) tal que \(f(x_0)=0\). El algoritmo comienza con un intervalo grande, que se sabe que contiene \(x_0\), y luego reduce sucesivamente el tamaño del intervalo hasta poner entre paréntesis la raíz. El fundamento teórico del algoritmo es el teorema del valor intermedio, que establece que si una función continua \(f\) toma los valores \(f(a)\) y \(f(b)\) en los puntos extremos del intervalo \(\), entonces \(f\) debe tomar todos los valores entre \(f(a)\) y \(f(b)\) en algún lugar del intervalo. Por lo tanto, si \(f(a) < \gamma < f(b)\), entonces existe un \(c\in\) tal que \(f(c)=\gamma\).
Usando esta información, podemos presentar el algoritmo de bisección. Primero debemos comprobar que \text(f(a)) \ne \text{signo}(f(b))\n). En caso contrario, el intervalo no contiene la raíz y podría ser necesario ampliarlo. Entonces podemos proceder:
-
Dejemos que \(c = \frac{a + b}{2}\).
-
Si \f(f(c) = 0\), detente y devuelve \f(c\).
-
Si \(\text{signo}(f(a))\netext{signo}(f(c))\Nse fija \N(b\leftarrow c\). Si no es así, si \(\text{sign}(f(b))\netexto{sign}(f(c))\Nse establece \(aflechaizquierda c\).
-
Se pasa al principio y se repite hasta la convergencia (ver más abajo).
Después de \(n\) iteraciones, el tamaño del intervalo que encierra la raíz será \(2^{n}(b-a)\N).
El algoritmo de bisección es útil, conceptualmente simple, y es fácil de implementar. En particular, no se necesita ninguna información especial sobre la función \(f\) excepto la capacidad de evaluarla en varios puntos del intervalo. Las desventajas son que sólo es útil en una dimensión y su convergencia es lineal, que es la tasa de convergencia más lenta para los algoritmos que vamos a discutir (más sobre esto más adelante).
El algoritmo de bisección puede tener problemas en situaciones en las que la función \(f\) no se comporta bien. La situación ideal para el algoritmo de bisección es algo así.
Situación ideal para el algoritmo de bisección.
Aquí, \(f(a)\Ny \N(f(b)\Nson de signos opuestos y la raíz está claramente entre \N(a\N) y \N(b\N).
En el escenario de abajo, el algoritmo no se iniciará porque \(f(a)>0\) y \(f(b)>0\).
La derivada de \(f\) en la raíz es \(0\).
En este siguiente escenario, hay dos raíces entre \(a\) y \(b\), además de tener \(f(a)>0\) y \(f(b)>0\). Habría que reducir la longitud del intervalo de partida para encontrar cualquiera de las dos raíces.
Dos raíces dentro del intervalo.
En el escenario de abajo, el algoritmo comenzará porque \(f(a)\Ny \Nf(b)\Nson de signo contrario, pero no hay raíz.
El intervalo contiene una asíntota pero no hay raíz.
La convergencia del algoritmo de bisección puede determinarse teniendo \(|b-a|<varepsilon\) para algún (\varepsilon\) pequeño o teniendo \(|f(b)-f(a)|<varepsilon\). El criterio que se utilice dependerá de la aplicación específica y de los tipos de tolerancias que se requieran.
2.1.1 Ejemplo: Cuantiles
Dada una función de distribución acumulativa \(F(x)\) y un número \(p\ en (0, 1)\), un cuantil de \(F\) es un número \(x\) tal que \(F(x) = p\). El algoritmo de bisección se puede utilizar para encontrar un cuantil \(x\) para un determinado \(p\) mediante la definición de la función \(g(x) = F(x) – p\) y la resolución del valor de \(x\) que logra \(g(x) = 0\).
Otra manera de poner esto es que estamos invirtiendo la CDF para calcular \(x = F^{-1}(p)\). Así que el algoritmo de bisección se puede utilizar para invertir funciones en estas situaciones.