31 may 2015

Método de Newton-Raphson






El método de Newton-Raphson es un método abierto, en el sentido de que no está garantizada su convergencia global. La única manera de alcanzar la convergencia es seleccionar un valor inicial lo suficientemente cercano a la raíz buscada. Así, se ha de comenzar la iteración con un valor razonablemente cercano al cero (denominado punto de arranque o valor supuesto). La relativa cercanía del punto inicial a la raíz depende mucho de la naturaleza de la propia función; si ésta presenta múltiples puntos de inflexión o pendientes grandes en el entorno de la raíz, entonces las probabilidades de que el algoritmo diverja aumentan, lo cual exige seleccionar un valor puesto cercano a la raíz. Una vez que se ha hecho esto, el método linealiza la función por la recta tangente en ese valor supuesto. La abscisa en el origen de dicha recta será, según el método, una mejor aproximación de la raíz que el valor anterior. Se realizarán sucesivas iteraciones hasta que el método haya convergido lo suficiente.

 
La función ƒ es mostrada en azul y la línea tangente en rojo. Vemos que xn+1 es una mejor aproximación que xn para la raíz x de la función f.
 

Sea f: [a, b] -> R función derivable definida en el intervalo real [a, b]. Empezamos con un valor inicial x0 y definimos para cada número natural



                                                       x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}.



Donde f ' denota la derivada de f.

El orden de convergencia de este método es, por lo menos, cuadrático.
Existen numerosas formas de evitar este problema, como pudieran ser los métodos de aceleración de la convergencia tipo Δ² de Aitken o el método de Steffensen.
x_{n+1} = x_n - m \frac{f(x_n)}{f'(x_n)}.
Evidentemente, este método exige conocer de antemano la multiplicidad de la raíz, lo cual no siempre es posible. Por ello también se puede modificar el algoritmo tomando una función auxiliar g(x) = f(x)/f'(x), resultando:
                                           x_{n+1} = x_n - \frac{g(x_n)}{g'(x_n)}.
Su principal desventaja en este caso sería lo costoso que pudiera ser hallar g(x) y g'(x) si f(x) no es fácilmente derivable.
Por otro lado, la convergencia del método se demuestra cuadrática para el caso más habitual en base a tratar el método como uno de punto fijo: si g '(r)=0, y g''(r) es distinto de 0, entonces la convergencia es cuadrática. Sin embargo, está sujeto a las particularidades de estos métodos.
Nótese de todas formas que el método de Newton-Raphson es un método abierto: la convergencia no está garantizada por un teorema de convergencia global como podría estarlo en los métodos de falsa posición o de bisección. Así, es necesario partir de una aproximación inicial próxima a la raíz buscada para que el método converja y cumpla el teorema de convergencia local.


Sea f\in{\mathcal{C}^2[a,b]} verificando:
  1. f(a) f(b)<0
  2. f'(x)\neq0 para todo x\in{[a,b]}
  3. f''(x) f''(y)\geq 0 para todo x,y\in{[a,b]}
  4. \max\left\{{\frac{\left |{f(a)}\right |}{\left |{f'(a)}\right |},\frac{\left |{f(b)}\right |}{\left |{f'(b)}\right |}}\right\}\leq b-a
Entonces existe un único s\in{[a,b]} tal que f(s)=0 por lo que la sucesión converge a s.

Se puede demostrar que el método de Newton-Raphson tiene convergencia cuadrática: si \alpha es raíz, entonces:
|x_{k+1}-\alpha|\leq C|x_k-\alpha|^2
para una cierta constante C. Esto significa que si en algún momento el error es menor o igual a 0,1, a cada nueva iteración doblamos (aproximadamente) el número de decimales exactos. En la práctica puede servir para hacer una estimación aproximada del error:
Error relativo entre dos aproximaciones sucesivas:
E = \frac{|x_{k+1}-x_k|}{|x_{k+1}|}
Con lo cual se toma el error relativo como si la última aproximación fuera el valor exacto. Se detiene el proceso iterativo cuando este error relativo es aproximadamente menor que una cantidad fijada previamente

Ejemplo

Consideremos el problema de encontrar un número positivo x tal que cos(x) = x3. Podríamos tratar de encontrar el cero de f(x) = cos(x) - x3.
Sabemos que f '(x) = -sin(x) - 3x2. Ya que cos(x) ≤ 1 para todo x y x3 > 1 para x>1, deducimos que nuestro cero está entre 0 y 1. Comenzaremos probando con el valor inicial x0 = 0,5
\begin{matrix} x_1 & = & x_0 - \frac{f(x_0)}{f'(x_0)} & = & 0,5 - \frac{\cos(0,5) - 0,5^3}{-\sin(0,5) - 3 \times 0,5^2} & = & 1,112141637097 \\ x_2 & = & x_1 - \frac{f(x_1)}{f'(x_1)} & & \vdots & = & \underline{0},909672693736 \\ x_3 & & \vdots & & \vdots & = & \underline{0,86}7263818209 \\ x_4 & & \vdots & & \vdots & = & \underline{0,86547}7135298 \\ x_5 & & \vdots & & \vdots & = & \underline{0,8654740331}11 \\ x_6 & & \vdots & & \vdots & = & \underline{0,865474033102} \end{matrix}
Los dígitos correctos están subrayados. En particular, x6 es correcto para el número de decimales pedidos. Podemos ver que el número de dígitos correctos después de la coma se incrementa desde 2 (para x3) a 5 y 10, ilustrando la convergencia cuadrática.



Publicado por en