Convergencia y análisis numérico de un método de tercer orden para sistemas de ecuaciones no lineales

XX Congreso de Ecuaciones Diferenciales y Aplicaciones X Congreso de Matem´ atica Aplicada Sevilla, 24-28 septiembre 2007 (pp. 1–6) Convergencia y an´alisis num´erico de un m´etodo de tercer orden para sistemas de ecuaciones no lineales S. Amat1, C. Berm´ udez1, S. Busquier1, F. Manzano1, S. Plaza2 1Dpto. de Matem´atica Aplicada y Estad´ıstica, U.P. Cartagena. 30203 Cartagena (Murcia) E-mails: [email protected], [email protected], [email protected]. 2Dpto. de Matem´aticas, Facultad de Ciencias, Universidad de Santiago de Chile. E-mail: [email protected]. Palabras clave: M´etodos iterativos, sistemas de ecuaciones no lineales, orden de convergencia Resumen A lo largo de la Historia la resoluci´on de ecuaciones no lineales ha preocupado a gran cantidad de cient´ıficos. Hoy en d´ıa, con los adelantos tecnol´ogicos, estas ecuaciones son aproximadas de forma eficiente por medio de m´etodos iterativos. La idea es generar una sucesi´on de aproximaciones x0, x1, x2, ... que bajo ciertas condiciones converge a la ra´ız deseada. En este trabajo, presentamos una extensi´on a espacios de Banach de un m´etodo de tercer orden recientemente presentado en el caso escalar [6]. Se introducir´an varios teoremas de convergencia, modificaciones que no necesitan el c´omputo de derivadas y varios experimentos num´ericos. 1. Introducci´on En matem´aticas, uno de los problemas m´as habituales al que nos enfrentamos es la resoluci´on de ecuaciones. Cuando nos encontramos con la expresi´on F(x) = 0,cabe pensar en diferentes situaciones, resoluci´on de un sistema de ecuaciones, encontrar la soluci´on de una ecuaci´on diferencial o hallar las ra´ıces de un polinomio. Cuando la obtenci´on de la soluci´on no es posible (hecho que ocurre en numerosas ocasiones), nos debemos conformar con aproximaciones de las mismas. Este hecho da pie a los procesos num´ericos, dando vida a los m´etodos iterativos. Las ra´ıces de una ecuaci´on no lineal f(x) = 0 no puede expresarse en general de forma cerrada. As´ı para tratar ecuaciones no lineales, usualmente se debe utilizar m´etodos 1 S.Amat, C. Berm´udez, S. Busquier, F. Manzano, S. Plaza aproximados. Estos m´etodos normalmente se basan en la idea de aproximaci´on sucesiva o en linealizaci´on. Tales m´etodos son iterativos; es decir, a partir de una o m´as aproximaciones a la ra´ız, crean una sucesi´on x0, x1, x2, ... que bajo ciertas condiciones converge a la ra´ız deseada. Con ciertos m´etodos, es suficiente (para la convergencia) conocer un intervalo [a, b] que contenga a la ra´ız. Otros m´etodos requieren una aproximaci´on inicial que est´a cerca de la ra´ız deseada; a cambio, estos m´etodos convergen m´as r´apidamente. As´ı, a menudo es conveniente empezar con un m´etodo de orden bajo y luego cambiar a uno que converja m´as r´apido [3]. En general, un m´etodo iterativo xn+1 = Φ(xn) es de orden p-´esimo si la soluci´on x∗ de F(x) = 0 satisface x∗= Φ(x∗), Φ0(x∗) = · · · = Φ(p−1(x∗) = 0 y Φ(p(x∗)6= 0. Para este m´etodo, el error |x∗−xn+1|es proporcional a |x∗−xn|pcuando n→ ∞. Por ejemplo, el m´etodo de Newton xn+1 =xn−F0(xn)−1F(xn). tiene convergencia cuadr´atica (orden dos) para ra´ıces simples. En este trabajo, presentamos una extensi´on a espacios de Banach de un m´etodo de tercer orden recientemente presentado en el caso escalar [6]. Se introducir´an varios teoremas de convergencia, modificaciones que no necesitan el computo de derivadas y varios experimentos num´ericos. 2. Esquemas de tercer orden En [6] se introduce el siguiente m´etodo iterativo de orden 3 yn=xn−f(xn) f0(xn), zn=−(yn−xn)2 2f0(xn)f00 (xn) xn+1 =yn−(yn+zn−xn)2 2f0(xn)f00 (xn). En este trabajo estamos interesados en el caso de sistemas de ecuaciones o de forma m´as general de ecuaciones donde los operadores sean entre espacios de Banach. Sea F:D⊂X→Yun operador no lineal, entonces el m´etodo anterior se escribe como xn+1 =xn−(I+Tn+ 2T2 n+T3 n)Γn donde Tn:= 1 2F0(xn)−1F00 (xn)F0(xn)−1F(xn), y Γn:= F0(xn)−1F(xn). Usando diferencias divididas se pueden obtener esquemas que no necesitan que el operador sea diferenciable Fr´echet [2], [5]. 2 Sobre un m´etodo de tercer orden para sistemas de ecuaciones no lineales 3. Convergencia Los m´etodos introducidos en la secci´on anterior pueden escribirse como tn+1 =tn−¡1 + θn+O¡θ2 n¢¢ f(tn) f0(tn), donde θn:= 1 2 f00 (tn)f(tn) f0(tn)2. En particular, podemos aplicar la teor´ıa general desarrollada para este tipo de m´etodos [1], [4]. Para un operador entre espacios de Banach F:D⊂X→Y;F(x) = 0, se tiene xn+1 =xn−¡I+Tn+O¡T2 n¢¢Γn.(1) Consideraremos tn+1 =tn−¡1 + θn+O(θ2 n)¢f(tn) f0(tn),(2) donde O(θ2 n) tiene el mismo desarrollo de Taylor que O¡T2 n¢. Proposici´on 1 Sean a, b, c > 0n´umeros reales de forma que a≤¡b2+ 2c¢3 2−b¡b2+ 3c¢ 3c2.(3) Entonces, existe un polinomio de tercer grado f(t)verificando: (a) f(0) = 0 (b) f(t0) = a (c) f0(t0) = 1 (d) f00 (t0) = b (e) f000 (t) = −c, ∀treal. Demostraci´on Claramente, para f(t) := t³−c 6t2+βt +γ´ donde β:= b+ct0 2 y γ:= 1 −c 2t2 0−bt0 se verifican los resultados. ¤ 3 S.Amat, C. Berm´udez, S. Busquier, F. Manzano, S. Plaza Corolario 1 Si a, b, c verifican (3), entonces ab ≤1 2. Proposici´on 2 La sucesi´on {tn}n≥0converge mon´otonamente y su l´ımite es cero. Teorema 1 Supongamos que x0en Des tal que F0(x0)es invertible. Adem´as, a, b, c son n´umeros reales positivos verificando 3, y para todo x, y en D, ° ° °F0(x0)−1F(x0)° ° °≤a, (4) ° ° °F0(x0)−1F00 (x0)° ° °≤b, (5) ||F0(x0)−1(F00(x)−F00(y)|| ≤ ckx−yk.(6) Adem´as, como f(t), t0y{tn}n≥0son los definidos en la secci´on anterior, se tiene para todo n≥0, kxn+1 −xnk ≤ tn−tn+1. Corolario 2 Bajo las mismas hip´otesis del teorema 1, si B0:= {x∈X:kx−x0k ≤ t0} ⊂ D, entonces la sucesi´on {xn}n≥0converge a x∗en B0;x∗es la ´unica ra´ız de F(x) = 0 en B:= {x∈D:kx−x0k ≤ t2}. Adem´as, para todo n≥0, kxn−x∗k ≤ tn Corolario 3 Para todo a, b, c ≥0satisfaciendo (3), existe un operador F(x)y un pivote x0verificando la proposici´on 2 tal que: Si {xn}n≥0es la sucesi´on obtenida en (1) de x0,entonces ||xn+1 −xn|| =tn−tn+1;kx∗−xnk=tn (Es claro que f(t)yt0satisfacen el corolario) Lema 1 F0(x0)−1[x, y;F]es invertible, y ||F0(x0)−1[xn, x∗;F]|| ≤ 1 1− {b 2(||xn−x0|| +t0) + c 6(||xn−x0||2+t0||xn−x0|| +t02)}=: r Proposici´on 3 Sean b, c, t0, F, F 0, F 00, T, xn, x∗verificando las mismas condiciones que en el resto de la secci´on. Entonces, ||xn−x∗|| ≤ r||F0(x0)−1F(xn)|| 4 Sobre un m´etodo de tercer orden para sistemas de ecuaciones no lineales 4. Experimentos num´ericos Sea la ecuaci´on de Hammerstein x(s) = 1 −1 4Z1 0 s t+s 1 x(t)dt, s ∈[0,1].(7) Usando la regla de integraci´on de los trapecios con paso h=1 m, obtenemos el siguiente sistema de ecuaciones no lineales 0 = xi−1 + 1 4m(1 2 ti ti+t0 1 x0 n X k=0 ti ti+tk 1 xk+1 2 ti ti+tm 1 xm), i = 0,1, . . . , m, (8) donde tj=j m. En este caso, la segunda derivada Fr´echet es diagonal a bloques. Consideramos m= 100 y tomamos como soluci´on la computada num´ericemente por el m´etodo de Newton. (ver tabla 1). Newton Tercer Orden 4 3 Tabla 1: N´umero de iteraciones hasta la convergencia, x0= 1, discretizaci´on ecuaci´on tipo Hammerstein. Consideramos ecuaciones cuadr´aticas del tipo F(x) = x0Ax +Bx +C= 0 (9) donde dim(A) = (N×N×N,dim(B) = N×Nydim(C) = dim(x) = N. Sobre el tipo de ecuaciones, pueden venir de la discretizaci´on de problemas de equilibrio, donde interaccionan fuerzas entre part´ıculas que determinan el rendimiento. De cualquier modo, el caso que vamos a analizar est´a preparado para obtener una soluci´on exacta con el fin de facilitar la evaluaci´on de los errores. Generamos aleatoriamente AyB, y entonces determinamos Ctal que x∗(i) = 2, i = 1,2, . . . , n, es una soluci´on de (9). En la tabla 2 la dimensi´on utilizada es m= 100. Notar que, la segunda derivada Fr´echet es constante F00 (x) = A+A0. Newton Tercer Orden 5 4 Tabla 2: N´umero de iteraciones hasta la convergencia, x0= 1,8, ecuaci´on cuadr´atica. Finalmente, estudiamos el sistema de ecuaciones no diferenciable (ver tabla 3) 3x2+y2−1 + |x−1|= 0, x4+xy3−1 + |y|= 0. 5 S.Amat, C. Berm´udez, S. Busquier, F. Manzano, S. Plaza Secante Tercer Orden 8 3 Tabla 3: N´umero de iteraciones hasta la convergencia, (x−1, y−1) = (5,5), (x0, y0) = (1,0), sistema no diferenciable. La soluci´on considerada es (x∗, y∗) = (0,8946553733346867,0,3278265117462974). Se han utilizado como primera y segunda diferencia dividida [xn−γnF(xn), xn+γnF(xn); F] y [xn−γnF(xn), xn, xn+γnF(xn); F] donde γnes un par´ametro real verificando 10−16 << ||γnF(xn)|| ≤ 10−6, (ver [1], [2]). 5. Conclusiones Se han estudiado unos m´etodos iterativos de tercer orden para ecuaciones no lineales en espacios de Banach, construyendo teoremas de convergencia. Se han dado alternativas para prescindir del uso de derivadas. En diversos ejemplos de inter´es pr´actico hemos testado los distintos m´etodos. Los m´etodos introducidos son competitivos con respecto a los m´etodos cl´asicos ya conocidos. Agradecimientos La investigaci´on de los cuatro primeros autores ha sido en parte subvencionada por MTM2004-07114 y 00675/PI/04. La investigaci´on de Sergio Plaza ha sido subvencionada en parte por Fondecyt Grant #1020711 y Dicyt Grant #0433 Referencias [1] S. Amat, S. Busquier, Third-order iterative methods under Kantorovich conditions. J. Math. Anal. Appl., en prensa 2007. [2] S. Amat, S. Busquier, Convergence and numerical analysis of a family of two-step Steffensen’s methods. Comput. Math. Appl. 49 (1), 13–22, (2005). [3] S. Amat, S. Busquier and J.M. Guti´errez, Geometric constructions of iterative functions to solve nonlinear equations. J. Comput. Appl. Math. 157 (1), 197–205, (2003). [4] M.A. Hern´andez and N. Romero, On a characterization of some Newton-like methods of R-order at least three. J.Comput.Appl.Math. 183 (1), 53-66, (2005). [5] M.A. Hern´andez and M.J. Rubio, Semilocal convergence of the secant method under mild convergence conditions of differentiability. Comput. Math. Appl. 44 (3-4), 277-285, (2002). [6] M.A. Noor et al., An iterative method with cubic convergence for nonlinear equations, Appl. Math. Comp., 183, (2006), 1249-1255. 6