Métodos iterativos multi-punto para ecuaciones no lineales

XX Congreso de Ecuaciones Diferenciales y Aplicaciones X Congreso de Matem´ atica Aplicada Sevilla, 24-28 septiembre 2007 (pp. 1–8) M´etodos iterativos multi-punto para ecuaciones no lineales Juan R. Torregrosa 1, A. Cordero 1 1Dpto. Matem´atica Aplicada, Universidad Polit´ecnica de Valencia, Camino de Vera, s/n, 46022 Valencia. E-mails: [email protected], [email protected]. Palabras clave: Ecuaci´on no lineal, m´etodo de Newton, m´etodo de punto fijo, orden de convergencia Resumen En este trabajo presentamos una familia de m´etodos iterativos multi-punto para resolver ecuaciones no lineales. Hacemos un an´alisis general del error y obtenemos el orden de convergencia y el ´ındice de eficiencia de algunos elementos de la citada familia. Adem´as, presentamos diferentes tests num´ericos que nos permiten comprobar (en algunos casos mejorar) los resultados te´oricos y comparar entre s´ı algunos m´etodos de esta familia. 1. Introducci´on En este trabajo abordamos el problema de encontrar las ra´ıces de la ecuaci´on f(x) = 0, donde fes una funci´on real de variable real. Estas ra´ıces pueden ser obtenidas como puntos fijos de una cierta funci´on g:R−→ R, mediante el m´etodo iterativo de punto fijo xk+1 =g(xk), k = 0,1, . . . , donde x0es la estimaci´on inicial. El m´etodo m´as conocido de este tipo es el m´etodo de Newton, xk+1 =xk−f(xk) f0(xk), k = 0,1, . . . , donde f0(xk) es la derivada de fevaluada en la k-´esima iteraci´on xk. La construcci´on de m´etodos num´ericos para la aproximaci´on de la soluci´on de una ecuaci´on no lineal es una tarea interesante en an´alisis num´erico y otras ciencias aplicadas. En los ´ultimos a˜nos han aparecido numerosos trabajos describiendo m´etodos iterativos de resoluci´on de ecuaciones no lineales. Entre ellos, cabe destacar los relacionados con 1 Juan R. Torregrosa, A. Cordero los m´etodos iterativos multi-punto. Por ejemplo, en [2], Frontini y Sormani describen una familia de variantes del m´etodo de Newton, obtenida aproximando la integral f(x) = f(xk) + Zx xk f0(t)dt por una f´ormula de cuadratura interpolatoria. La f´ormula general que resulta es xk+1 =xk−f(xk) m X j=1 Ajf0(ηj(xk)) ,(1) con ηj(xk) = xk−τj f(xk) f0(xk), donde τjson los nodos, en [0,1], y Ajlos pesos de la f´ormula de interpolaci´on. Es sencillo observar que el m´etodo de Newton, el m´etodo de Weerakoon y Fernando (ver [5]), el m´etodo de Newton-Simpson (ver [1]), etc., pueden obtenerse de la f´ormula general (1) eligiendo determinados valores de los par´ametros τjyAj. El m´etodo general (1) se obtiene, a partir del m´etodo de Newton, reemplazando f0(xk) por una combinaci´on lineal de valores de f0(x) en diferentes puntos. En este trabajo analizamos una colecci´on de m´etodos iterativos multi-punto, obtenidos a partir del m´etodo de Newton, reemplazando f(xk) por una combinaci´on lineal de valores de f(x) en diferentes puntos. Concretamente, el m´etodo general es xk+1 =xk−1 f0(xk) m X j=1 Ajf(ηj(xk)),(2) con ηj(xk) = xk−τj f(xk) f0(xk), donde τjyAjson par´ametros a elegir en [0,1] y R, respectivamente. Como veremos m´as adelante, el valor de estos par´ametros juega un papel importante en el orden de convergencia del m´etodo. Vamos a recordar los conceptos b´asicos sobre la convergencia de un m´etodo iterativo. Definici´on 1.1 Sea {xk}k≥0una sucesi´on en Rque converge a α. Entonces, se dice que la convergencia es (a) lineal, si existe M,0< M < 1, y k0tal que |xk+1 −α| ≤ M|xk−α|,∀k≥k0. (b) de orden p,p≥2, si existe M,M > 0, y k0tal que |xk+1 −α| ≤ M|xk−α|p,∀k≥k0. 2 M´etodos iterativos multi-punto Definici´on 1.2 (ver [5]) Sea αun cero de la funci´on fy supongamos que xk−1,xky xk+1 son tres iteraciones consecutivas pr´oximas a α. Entonces, el orden computacional de convergencia ρpuede ser aproximado mediante la f´ormula ρ≈ln(|xk+1 −α|/|xk−α|) ln(|xk−α|/|xk−1−α|).(3) Por otra parte, para comparar los diferentes m´etodos, consideramos tambi´en el concepto de ´ındice de eficiencia (ver [3]) definido como p1/d, donde pes el orden de convergencia ydes el n´umero total de nuevas evaluaciones funcionales (por iteraci´on) requeridas por el m´etodo. Teniendo en cuenta que (2) puede ser considerada como una f´ormula iterativa de punto fijo, estudiamos la convergencia de los diferentes m´etodos utilizando el siguiente resultado (ver [4]): Teorema 1.1 Sea guna funci´on de punto fijo tal que g(p)es continua en un entorno de α. El m´etodo iterativo xk+1 =g(xk)es de orden psi y s´olo si g(α) = α;g(k)(α) = 0, k = 1,2, . . . , p −1; g(p)(α)6= 0. En la Secci´on 2, analizamos la f´ormula general (2) para una ecuaci´on no lineal f(x) = 0 y estudiamos las condiciones que los par´ametros τjyAjdeben verificar para obtener un m´etodo con un particular orden de convergencia. Hemos dedicado la ´ultima secci´on a los resultados num´ericos obtenidos al aplicar algunos m´etodos incluidos en (2) a diferentes ecuaciones no lineales. Estos resultados nos permiten comparar los diferentes m´etodos, confirmar los resultados te´oricos y extraer conclusiones. 2. Descripci´on y convergencia de los m´etodos Sea f:I⊆R−→ R, una funci´on suficientemente diferenciable y α∈Iuna ra´ız simple de la ecuaci´on no lineal f(x) = 0. Sea gla funci´on de punto fijo que nos permite describir (2) g(x) = x−1 f0(x) m X j=1 Ajf(ηj(x)),con ηj(x) = x−τj f(x) f0(x). Si calculamos la primera derivada de g, obtenemos g0(α) = 1 − m X j=1 Aj(1 −τj), y entonces podemos establecer el siguiente resultado: Proposici´on 2.1 Si los par´ametros Ajyτjsatisfacen m X j=1 Aj(1 −τj) = 1, entonces el m´etodo iterativo (2) tiene, al menos, orden 2. 3 Juan R. Torregrosa, A. Cordero Si tomamos A1yτ1tal que A1(1 −τ1) = 1 obtenemos m´etodos cuyo orden de convergencia es, al menos, 2. Por ejemplo, utilizando A1= 1 y τ1= 0 obtenemos el m´etodo de Newton, y con A1= 2 y τ1= 1/2 tenemos el m´etodo iterativo xk+1 =xk−2f(η1(xk)) f0(xk),donde η1(xk) = xk−1 2 f(xk) f0(xk). En este caso, no es interesante tomar m > 1, puesto que obtenemos m´etodos iterativos con orden de convergencia 2 pero un ´ındice de eficiencia inferior al del m´etodo de Newton. Ahora, para la segunda derivada de g, tenemos g00(α) = f00(α) f0(α)(1 − m X j=1 Ajτ2 j). Por tanto, podemos afirmar: Proposici´on 2.2 Si los par´ametros Ajyτjsatisfacen m X j=1 Aj(1 −τj) = 1 y m X j=1 Ajτ2 j= 1,(4) entonces el m´etodo iterativo (2) tiene, al menos, orden 3. En este caso, para m= 1, tenemos el sistema A1(1 −τ1) = 1 A1τ2 1= 1 ¾ Este sistema s´olo tiene la soluci´on real A1= (3 + √5)/2 y τ1= (√5−1)/2. Con estos valores obtenemos el m´etodo iterativo xk+1 =xk−3 + √5 2 f(η1(xk)) f0(xk),donde η1(xk) = xk−√5−1 2 f(xk) f0(xk),(5) de orden 3 e ´ındice de eficiencia 31/3. Notemos que este ´ındice es m´as grande que el del m´etodo de Newton, cuyo valor es 21/2. Para m= 2, los par´ametros Ajyτjdeben verificar el sistema A1(1 −τ1) + A2(1 −τ2) = 1 A1τ2 1+A2τ2 2= 1 ¾ Este sistema tiene infinitas soluciones. Una de ellas, A1=A2= 1, τ1= 0 y τ2= 1 nos da el m´etodo: xk+1 =xk−f(xk) + f(η2(xk)) f0(xk),donde η2(xk) = xk−f(xk) f0(xk).(6) Aplicando las condiciones (4), la expresi´on de la tercera derivada de gen αes g000(α) = f000(α) f0(α)(−1 + m X j=1 Ajτ3 j)+3f002(α) f02(α). 4 M´etodos iterativos multi-punto Para garantizar g000(α) = 0 necesitamos m X j=1 Ajτ3 j= 1 y f00(α) = 0. Por tanto, podemos establecer el siguiente resultado: Proposici´on 2.3 Si los par´ametros Ajyτjsatisfacen m X j=1 Aj(1 −τj) = 1, m X j=1 Ajτ2 j= 1 y m X j=1 Ajτ3 j= 1,(7) yf00(α) = 0, entonces el m´etodo iterativo (2) tiene, al menos, orden 4. En este caso, para m= 1, las ecuaciones (7) no tienen soluci´on. Para m= 2 el sistema que deben verificar los par´ametros es: A1(1 −τ1) + A2(1 −τ2) = 1 A1τ2 1+A2τ2 2= 1 A1τ3 1+A2τ3 2= 1    Por ejemplo, los valores A1=A2= 1, τ1= 0, τ2= 1 o bien A1=10 13 A2=22 13, τ1= 1/4, τ2= 3/4 son dos soluciones del sistema anterior que nos proporcionan sendos m´etodos iterativos. Para m= 3 debemos resolver el sistema A1(1 −τ1) + A2(1 −τ2) + A3(1 −τ3) = 1 A1τ2 1+A2τ2 2+A3τ2 3= 1 A1τ3 1+A2τ3 2+A3τ3 3= 1    que tiene infinitas soluciones. Por ejemplo, A1=A3= 4, A2=−6, τ1= 1/4, τ2= 1/2 and τ3= 3/4 es una de ellas, que nos proporciona el m´etodo iterativo xk+1 =xk−1 f0(xk)[4f(η1(xk)) −6f(η2(xk)) + 4f(η3(xk))] ,(8) donde ηi(xk) = xk−τi f(xk) f0(xk), i = 1,2,3. Este m´etodo tiene orden 4 e ´ındice de eficiencia 41/5. Ahora, utilizando las condiciones (7), la derivada cuarta de gen αresulta g(iv)(α) = f(iv)(α) f0(α)(1 − m X j=1 Ajτ4 j). Por tanto, podemos establecer un resultado an´alogo al anterior. Proposici´on 2.4 Si los par´ametros Ajyτjverifican m X j=1 Aj(1 −τj) = 1, m X j=1 Ajτ2 j= 1, m X j=1 Ajτ3 j= 1 y m X j=1 Ajτ4 j= 1 (9) yf00(α) = 0, entonces el m´etodo iterativo (2) tiene, al menos, orden 5. 5 Juan R. Torregrosa, A. Cordero En este caso, por ejemplo para m= 4, los par´ametros deben verificar A1(1 −τ1) + A2(1 −τ2) + A3(1 −τ3) + A4(1 −τ4) = 1 A1τ2 1+A2τ2 2+A3τ2 3+A4τ2 4= 1 A1τ3 1+A2τ3 2+A3τ3 3+A4τ3 4= 1 A1τ4 1+A2τ4 2+A3τ4 3+A4τ4 4= 1        Este sistema tiene infinitas soluciones. Por ejemplo, la soluci´on A1= 24/11, A2=−18/11, A3= 8/11, A4= 19/22, τ1= 1/4, τ2= 1/2, τ3= 3/4 y τ4= 1, nos permite describir el siguiente m´etodo iterativo de orden 5 (cuando f00(α) = 0) e ´ındice de eficiencia 51/6. xk+1 =xk−1 f0(xk)[A1f(η1(xk)) + A2f(η2(xk)) + A3f(η3(xk)) + A4f(η4(xk))] ,(10) donde ηi(xk) = xk−τi f(xk) f0(xk), i = 1,2,3,4. De forma an´aloga, utilizando (9), la expresi´on de la quinta derivada de gen αes g(v)(α) = f(v)(α) f0(α)(−1 + m X j=1 Ajτ5 j) + 20f0002(α) f02(α). Por tanto, podemos asegurar: Proposici´on 2.5 Si los par´ametros Ajyτjverifican m X j=1 Aj(1 −τj) = 1,y m X j=1 Ajτp j= 1, p = 2,3,4,5,(11) yf00(α) = f000(α) = 0, entonces el m´etodo iterativo (2) tiene, al menos, orden 6. En general, aplicando las condiciones m X j=1 Aj(1 −τj) = 1 y m X j=1 Ajτp j= 1, p = 2,3, . . . , 2d−1, tenemos g(2d)(α) = f(2d)(α) f0(α)(−1 + m X j=1 Ajτ2d j). Adem´as, si exigimos m X j=1 Ajτ2d j= 1, obtenemos g(2d+1)(α) = f(2d+1)(α) f0(α)(−1 + m X j=1 Ajτ2d+1 j) + M(f(d+1))2(α) f02(α), donde Mes un n´umero real. Por tanto, podemos enunciar el siguiente resultado general: 6 M´etodos iterativos multi-punto Teorema 2.1 a) Si los par´ametros Ajyτjverifican m X j=1 Aj(1 −τj) = 1, m X j=1 Ajτp j= 1, p = 2,3, . . . , 2d−1, yf00(α) = f000(α) = ··· =f(d)(α)=0, entonces el m´etodo iterativo (2) tiene, al menos, orden 2d. b) Si los par´ametros Ajyτjverifican m X j=1 Aj(1 −τj) = 1, m X j=1 Ajτp j= 1, p = 2,3, . . . , 2d, yf00(α) = f000(α) = ··· =f(d)(α)=0, entonces el m´etodo iterativo (2) tiene, al menos, orden 2d+ 1. 3. Resultados num´ericos En esta secci´on presentamos ejemplos num´ericos y comparamos la eficiencia de diferentes m´etodos iterativos, obtenidos de (2) para valores particulares de los par´ametros Aj yτj. Concretamente, comparamos el m´etodo de Newton (CN), y los m´etodos descritos por (5), (6), (8) and (10) a los que denotamos en la Tabla 1 por M2, M3, M4 y M5, respectivamente. Utilizamos las siguientes funciones, algunas de las cuales aparecen en [5]. (a) f(x) = x3−9x2+ 28x−30, α= 3. (b) f(x) = cos (x)−x,α= 0,739085133214758. (c) f(x) = (x−1)6−1, cuyas ra´ıces reales son α1= 0 y α2= 2. (d) f(x) = xex2−sin2(x) + 3 cos (x) + 5, α=−1,20764782713013. (e) f(x) = arctan (x), α= 0. (f) f(x) = sin (x) + xcos (x), α= 0. Los resultados num´ericos han sido obtenidos con MATLAB (MATrix LABoratory), trabajando con 16 d´ıgitos decimales. El criterio de parada utilizado es |xk+1 −xk|+|f(xk)|< tol, donde tol = 10−12, con lo que nos aseguramos, por un lado la convergencia de los iterados a un cierto valor y, por otro, que ese valor es soluci´on de la ecuaci´on no lineal. Para cada m´etodo, estudiamos el n´umero de iteraciones y el orden computacional de convergencia ρ, aproximado por (3). El valor de ρque aparece en la Tabla 1 es la menor coordenada del vector ρcuando la variaci´on entre sus coordenadas es peque˜na. En la Tabla 1 podemos observar los resultados num´ericos obtenidos al utilizar el m´etodo de Newton y los m´etodos M2, M3, M4 y M5, para estimar los zeros de las funciones de (a) a (f). Para cada funci´on indicamos la estimaci´on inicial x0, la soluci´on y, para cada 7 Juan R. Torregrosa, A. Cordero m´etodo, el n´umero de iteraciones y el orden computacional de convergencia. En algunos casos este orden no es estable y lo consideramos no concluyente. Cuando f00(α) = 0, como ocurre en las funciones (a), (e) y (f), observamos que la convergencia del m´etodo de Newton tiene orden 3, mientras que los m´etodos M4 y M5 tienen orden computacional de convergencia pr´oximo a 5. Adem´as, cuando f00(α)6= 0, los m´etodos M2, M4 y M5 tienen orden 3, mientras que el orden de convergencia del m´etodo de Newton es 2. f(x)x0Soluci´on Iteraciones ρ CN M2 M3 M4 M5 CN M2 M3 M4 M5 (a) 2 α6 5 5 5 5 3.0 2.8 4.8 4.8 4.8 0α8 7 6 6 6 3.0 2.9 5.0 4.6 4.7 (b) 0 α6 5 5 5 5 2.0 3.1 3.1 3.1 3.1 1α5 4 4 4 4 2.0 2.9 2.9 2.9 2.9 (c) -0.9 α19 7 7 7 7 1.9 3.0 3.0 3.0 3.0 3α29 7 7 7 7 2.0 2.9 2.9 2.9 2.9 (d) -0.5 α10 32 - - - 2.0 - - - - 1α8 13 7 6 7 2.0 - 3.0 2.8 2.9 (e) -1 α6 6 5 5 5 3.0 3.0 5.0 5.0 5.0 0.7 α5 5 4 4 4 3.0 - 4.9 4.0 3.8 2α10 - 10 4 - 2.0 - 2.0 5.0 (f) 0.5 α5 4 4 4 4 3.0 3.0 5.2 - - -0.7 α5 6 4 4 4 3.0 - 5.0 5.0 5.0 Tabla 1: Resultados num´ericos para distintos m´etodos iterativos. Terminamos el trabajo indicando que la f´ormula iterativa (2) y los resultados descritos en la Secci´on 2, se pueden extender a funciones de varias variables, con lo que obtendr´ıamos m´etodos iterativos de resoluci´on de sistemas no lineales. Referencias [1] A. Cordero, J.R. Torregrosa, Variants of Newton’s Method using 5th order quadrature formulas. Applied Mathematics and Computation. DOI: 10.1016/j.amc.2007.01.062 [2] M. Frontini, E. Sormani, Some variant of Newton’s method with third-order convergence. Applied Mathematics and Computation, 140 (2003) 419–426. [3] A.M. Ostrowski, Solutions of equations and systems of equations, Academic Press, New York-London, 1966. [4] J.F. Traub, Iterative methods for the solution of equations, Chelsea Publishing Company, New York, 1982. [5] S. Weerakoon, T.G.I. Fernando, A variant of Newton’s method with accelerated third-order convergence. Applied Mathematics Letters, 13 (8) (2000) 87–93. 8