http://uva.onlinejudge.org/external/103/10341.pdf
Método de Biseccion
Hay que observar que para que la función contenga una raíz en el intervalo [0, 1], los signos de f(0) y f(1) tienen que ser opuestos. Esta propiedad se puede aplicar para buscar el valor de la x. Dado un intervalo [l, r] podemos aplicar el siguiente método de bisección:
- Tomamos el valor medio entre [l, r] y lo denotamos por m.
- Calculamos f(l) y f(m). Si el signo de estos es opuestos, la raíz se encuentra en el intervalo [l, m], y podemos descartar el intervalo [m, r].
- De lo contrario, la raíz se encuentra en el intervalo [m, r] y descartamos [l, m] de la búsqueda.
Este método es muy eficiente, pero existen otras formas de calcular las raíces de una función que podemos aplicar a este problema. Tales métodos son el método de las secantes, y el método de Newton. Vamos a ver las soluciones con estos métodos:
Método de la Secante
La aplicacion de este metodo consiste en aproximar sucesivamente la pendiente de una recta a la pendiente de la funcion en un punto dado. El metodo esta dado por la relacion de recurrencia:
Lo podemos calcular iterativamente, calculando en cada paso la x actual, y cuando el valor de f(x) sea lo suficientemente aproximado a 0, termina la funcion. Una posible implementacion seria la siguiente:
public double secant(double x0, double x1, double precision)
{
while(true)
{
double delta = f(x1)*(x1 - x0) / (f(x1) - f(x0));
if (abs(delta) < precision) return x1;
x0 = x1;
x1 = x1 - delta;
}
}
Metodo de Newton
El metodo de Newton es otra forma de calcular la raiz de una funcion. Este metodo funciona de manera muy similar al metodo de la secante, pero es mas «inteligente» al aproximarse a la raiz, ya que utiliza la recta tangente a la curva, y no una aproximacion a ella. Este metodo es sumamente eficiente cuando podemos calcular la derivada de la funcion original. El metodo esta definido por la relacion
Dada la funcion f y su derivada fd, podemos calcular los valores de x iterativamente como en el metodo de la secante:
public double secant(double x, double precision)
{
while(true)
{
double delta = f(x) / fd(x);
if (abs(delta) < precision) return x;
x = x - delta;
}
}
De los tres métodos presentados, el método de Newton es el mas eficiente, ya que se acerca a la raíz de forma mas inteligente que los anteriores, sin embargo para usarlo, es necesario calcular la derivada de la función. En los casos en que no se pueda calcular, podemos usar cualquiera de los dos anteriores.
Referencias
http://es.wikipedia.org/wiki/M%C3%A9todo_de_la_secante
http://es.wikipedia.org/wiki/M%C3%A9todo_de_Newton-Raphson
http://www.algorithmist.com/index.php/UVa_10341
Programacion Deportiva 