El método Newton

Hola, en el vídeo anterior introdujimos el Método de Newton, donde destacamos que sirve para calcular los ceros de funciones complejas, explicamos su funcionamiento de manera gráfica y dedujimos su fórmula general. Aun así, vimos que quedaban algunas cuestiones importantes por resolver, como, por ejemplo, cuántas iteraciones se deben realizar para obtener un buen resultado o qué valor de X0 debemos escoger. Pero antes de continuar con estas cuestiones, resolveremos las preguntas que resolvimos al final del apartado 1.

¿En qué consiste el Método Newton? Es un método numérico iterativo que aproxima las raíces de funciones complejas mediante la lineación de estas funciones en puntos cercanos a la raíz.

Dibujad una función compleja que corte el eje X en aproximadamente x=1 y, tomando x0=3, iterad el Método de Newton gráficamente tres veces. ¿Os ha quedado más cerca X3 de X* que X0?

Este es un ejemplo en que se puede ver como, a medida que iteramos el método, se aproxima cada vez mejor a la raíz. En este caso, confirmamos que X3 está más cerca de X*que X0. Pero puede ser que algunos de vosotros hayáis dibujado una función donde el Método de Newton no haya funcionado adecuadamente. No quiere decir que lo hayáis aplicado mal, en este caso, se dice que el Método de Newton diverge en el entorno cercano a la raíz y, en este caso, X0 está más cerca de X* que X3. Para que esto no suceda, existe una Condición de Convergencia que se debería de satisfacer si queremos que el Método de Newton funcione adecuadamente. Más adelante, en este vídeo, la explicaremos con más detalle.

Calcula tres iteraciones del Método de Newton (numéricamente) de la función f(x)=x^3+x+1 cogiendo x0=-0,5. En este caso la aplicación numérica sería la siguiente:

X1 = 2 – f(2)/f`(2) = 2,1000000

X2 = 2,1 – f(2,1)/f’(2,1) = 2,0945691211

X3 = 2,094551482

¿Qué creéis que pasaría si f’(x)=0 en alguna x?

Es como si hubiera un punto estacionario en el entorno cerca de la raíz. Como se ve en la fórmula general, la derivada se encuentra en el denominador y, por lo tanto, si fuera igual a 0, la Xk que se estuviera calculando no existiría y por lo tanto el Método de Newton dejaría de funcionar. Esta será otra situación que se tendrá que tener en cuenta a la hora de definir la Condición de Convergencia del Método.

Antes de entrar en detalle para explicar la Condición de Convergencia, vamos a ver cuáles son los Criterios de parada del Método. Es decir, como podemos definir cuántas veces se tendrá que iterar la fórmula general deducida del vídeo anterior. Ya hemos visto que si se hace manualmente, dejaremos de iterar cuando veamos que la Xk tiene la precisión deseada, por ejemplo, en función de los decimales que varíen entre xk y Xk-1. Pero el Método de Newton se suele programar en el ordenador y, por lo tanto, debemos tener alguna manera de limitar la recurrencia del método. Para ello debemos entender qué son el Error Relativo y el Error Absoluto.

Definición: el error absoluto y el error relativo entre dos iteraciones sucesivas Xk-1 y xk son, respectivamente:

ek = |xk-Xk-1| y Ek = ek/|xk| = | (xk-xk-1)/xk|

Que, para alguna de las iteraciones, Ek0 es una tolerancia prefijada por el usuario. Una alternativa de este criterio sería ek

Que, para alguna de las iteraciones, |f(Xk)|

Si, al fin y al cabo estamos buscando un cero de f, podemos detener los cálculos cuando f(Xk) esté bastante cercano a 0.

Que se haya llegado a K = Kmax, donde Kmax es un número de iteraciones máximo prefijado por el usuario. Este criterio se utiliza casi siempre al principio por si, en algún caso concreto, la recurrencia no convergiera a ninguna solución y por lo tanto el algoritmo entrase en un bucle infinito. Aun así, también se puede hacer sistemáticamente un número de iteraciones prefijado, sin tener que comprobar ningún otro criterio en cada iteración.

Ahora vamos a ver la parte del Método de Newton que nos produce más dolores de cabeza. Cómo escoger un X0 adecuadamente y qué condiciones se deben cumplir para que el Método de Newton converja en el intervalo de búsqueda [a, b].

Antes que nada, tenéis que entender que el intervalo de búsqueda [a,b] corresponde a todos los valores de x posible que pueden tener las Xk. Como ya hemos visto hasta ahora, a medida que aumentan las iteraciones, si el método funciona correctamente, las Xk se irán acercando a X* y, por lo tanto, X0 podría ser uno de los extremos de este intervalo. Revisad los gráficos anteriores si no entendéis este punto, ya que es bastante importante. Por otro lado, es importante tener en cuenta que si dentro del intervalo de búsqueda [a, b] ha de haber un cero, esto querrá decir que si f(a)>0 entonces f(b)<0 o de manera inversa si f(a) es negativo, f(b) tendrá que ser positivo. Gráficamente, para que haya un punto donde la función cruce el eje X, ha de haber un punto de la función por encima del eje X en un lado y un punto de la función por debajo del eje al otro lado. ¡Pensad en ello! En realidad, esta idea que puede parecer trivial, pero que a veces olvidamos tener en cuenta, es precisamente lo que anuncia el Teorema de Bolzano.

Sea f:[a,b] ? R continua tal que f(a)*f(b) < 0. Entonces, f tiene un cero en (a,b), es decir, existe x0 E (a,b) tal que f(x0) = 0.

Y es lo que aplicaremos al principio de cualquier aplicación del Método de Newton para definir el intervalo de búsqueda [a,b] donde se encuentra X*.

Si volvemos a la función que teníais como “deberes” del vídeo anterior, yo os dije que tomaseis X0=2, pero, ¿por qué? La función era f(x)= x^3-2x-5. Si os hubiera dado X0, tendríais que haber elegido una vosotros mismos, y si aplicamos Bolzano vemos que:

f(0)<0, f(1)<0, f(2)<0, i f(3)>0 Como entre x=2 y x=3 hay un cambio de signo en la función, podemos decir que [2,3] será nuestro intervalo de búsqueda. Es lógico tomar X0=2, pero también podríamos haber cogido cualquier otro valor entre 2 y 3.

Ahora supongamos que se quiere aproximar un cero de f(x)=6x^3 -2x^2 – 2x-1. Lo primero que hacemos es buscar el intervalo de búsqueda aplicando Bolzano como antes.

f(0)<0, y f(1)>1 por lo tanta podríamos decir que X* E [0,1]. En este caso si cogemos X0=0,5 (recordad que, si el intervalo está bien definido, x0 puede ser cualquier valor dentro de este intervalo) y calculamos X1

X1= 0,5 – f(0,5)/f’(0,5) = 4

En este caso, X1 nos queda fuera del intervalo de búsqueda y por tanto quiere decir que alguna cosa no va bien. De hecho, f(4)= 343, y por lo tanto está muy alejado de 0. Este ejemplo pone de manifiesto que aplicando solo el Teorema de Bolzano puede ser que el intervalo de búsqueda que nos definimos no sea suficientemente pequeño como para garantizar que el Método de Newton converja en todo él. Para que esto sea cierto se ha de cumplir lo siguiente: Sean [a,b] un intervalo de búsqueda de x* (típicamente un intervalo per el cual f(a)*f(b)<0) y f:[a,b] ? R una función derivable dos veces tal que f’(x)!= 0 para todo x E [a,b]. Si

|x*-x0| < 2/max |f’’(x)/f’x)| entonces lim k->inf Xk = x*

Esta fórmula se puede deducir a partir del residuo de Lagrange, pero como este curso se ha explicado en clase, aquellos que tengáis interés podéis encontrar de donde sale en los apuntes que hay colgados en el Moodle. Vamos a ver cómo aplicaríamos esta fórmula al ejemplo de antes que nos había dado problemas. Para empezar miraremos si hay algún punto en [0,1] que haga que la f’(x)=0.

F’(x)=18x^2- 4x-2 =0 si resolvemos la ecuación de segundo grado tendremos que f’(0,46) = 0 por lo tanto debemos definir un nuevo intervalo de búsqueda que no incluya este punto.

Recordemos que f(1)=1 y f(0)=-1, si hacemos x=0,5 tenemos que f(0,5)=-1,75 <0 por lo tanto nuestro nuevo intervalo podría ser [0,5 , 1]. Si aplicamos la fórmula de la Condición de Convergencia, tenemos que |X*-x0| < 2/f’’(1)/f’(0,5) Como f’ y f’’ son monótonas crecientes, el valor que maximiza la segunda derivada es el extremo superior del intervalo y el valor que minimiza la primera derivada es el extremo inferior del intervalo. Por lo tanto f’(x)= 18x^2-4x-2 y f’(0,5)= 0,5 y f’’(x)= 36x-4 y f’’(1)=32

Nos queda que el intervalo |x*-x0|< 0,03125 para garantizar la convergencia del método. Como nuestro intervalo es [0,5 , 1] se puede ver fácilmente que no se cumple la condición y que, por lo tanto, podría ser que si cogiéramos x0=0,5 os volviese a dar valores fuera del intervalo. Esto podría deberse a que 0,5 es demasiado cercano a x=0,46, donde la derivada se anulaba.

Intentemos ajustar mejor el intervalo. Si tomamos x=0,75, f(0,75) = -1,09 <0 sigue siendo menos a cero y por lo tanto un posible intervalo sería [0,75, 1]. En este casi si aplicáis la Condición de Convergencia veréis que sí que se cumple.

Recapitulando, en este vídeo hemos visto los tres criterios de parada más relevantes y hemos analizado cómo se elige el valor de x0 adecuadamente aplicando el Teorema de Bolzano y la fórmula de la Condición de Convergencia. En el próximo vídeo veremos otras aplicaciones del Método de Newton que estamos seguros de que os resultarán interesantes y sorprendentes.

Antes de visualizar el último de los tres vídeos que os hemos preparado, os pedimos que hagáis los siguientes ejercicios:

1. Realizad los cálculos que confirman que [0,75,1] es un intervalo de búsqueda que garantiza la convergencia del Método de Newton para la función f(x)= 6x^3-2x^2-2x-1 y escoged un posible valor de X0.

2. Encontrad un intervalo de búsqueda que garantice la convergencia del Método de Newton para la función

f(x)=x^3-2x-5.

3. Enumerad los tres criterios de parada que hemos explicado y definidlos con vuestras propias palabras.

4. Queremos utilizar el Método de Newton para resolver la raíz cuadrada de un número (que no sea trivial). ¿Cómo plantearíais la ecuación general? Y en caso de que ese número fuera pi, ¿sabríais escoger un x0 adecuado?