Un estudio unificado de la convergencia semilocal de métodos tipo Newton de dos puntos en espacios de Banach

XX Congreso de Ecuaciones Diferenciales y Aplicaciones X Congreso de Matem´ atica Aplicada Sevilla, 24-28 septiembre 2007 (pp. 1–8) Un estudio unificado de la convergencia semilocal de m´etodos tipo Newton de dos puntos en espacios de Banach M. J. Rubio1, M. A. Hern´ andez1 1Dpto. de Matem´aticas y Computaci´on, Universidad de La Rioja, C/ Luis de Ulloa s/n. 26004 Logro˜no. E-mails: [email protected], [email protected]. Palabras clave: M´etodos tipo Newton, operadores no diferenciables, espacios de Banach Resumen En este trabajo consideramos procesos iterativos tipo Newton de dos puntos para aproximar una soluci´on de una ecuaci´on no lineal en espacios de Banach. A partir de una expresi´on general que caracteriza estos procesos iterativos, obtenemos resultados de convergencia semilocal, estableciendo una teor´ıa unificada para el an´alisis de este tipo de procesos. 1. Introducci´on Uno de los procesos iterativos m´as utilizados para la aproximaci´on de una soluci´on de la ecuaci´on no lineal F(x) = 0,(1) es el m´etodo de Newton. Si consideramos Fun operador no lineal F: Ω ⊆X→Y, siendo XeYdos espacios de Banach y Ω un dominio abierto y convexo, el algoritmo que define el citado m´etodo viene dado por xn+1 =xn−F0(xn)−1F(xn), n ≥0, x0∈Ω.(2) Pese a ser un proceso iterativo eficiente, tiene el inconveniente de necesitar la evaluaci´on del operador F0en el punto xn. Un procedimiento para evitar este problema es aproximar este operador por una diferencia dividida. Recordemos que un operador lineal y acotado [x, y;F] : Ω ⊆X→Yse dice una diferencia dividida de primer orden para Fen los puntos distintos xeysi cumple [x, y;F] (x−y) = F(x)−F(y).(3) 1 M. J. Rubio, M. A. Hern´andez Entonces aproximamos F0(xn) por [xn−1, xn;F] y as´ı obtenemos el conocido m´etodo de la Secante [4]: xn+1 =xn−[xn−1, xn;F]−1F(xn), n ≥0, x−1, x0∈Ω dados.(4) ´ Este es un m´etodo de dos puntos, ya que cada paso del algoritmo necesita de dos puntos, y es el m´as conocido de los tipo Newton. Una generalizaci´on de este proceso iterativo la proporciona la familia uniparam´etrica de procesos iterativos tipo Secante [2], dada por    x−1, x0∈Ω yn=λxn+ (1 −λ)xn−1, λ ∈[0,1), xn+1 =xn−[yn, xn;F]−1F(xn), n ≥0. (5) que tambi´en es un m´etodo de dos puntos tipo Newton. Otra situaci´on de este tipo se presenta en el conocido m´etodo de Steffensen [3] (g, F : Ω ⊆X→X) xn+1 =xn−[xn, g(xn); F]−1F(xn), x0∈Ω, n ≥0,(6) Todos estos m´etodos de dos puntos tipo Newton no necesitan evaluar F0pero pierden velocidad de convergencia respecto de la convergencia cuadr´atica del m´etodo de Newton, aunque tienen convergencia superlineal. Al no necesitar de la existencia de F0,pueden ser utilizados para aproximar soluciones de operadores no diferenciables. Se han utilizado otros procesos iterativos de dos pasos tipo Newton, construidos a partir de la descomposici´on del operador no diferenciable Fcomo F(x) = G(x) + H(x), siendo G, H : Ω ⊆X→, Y , donde Ges un operador diferenciable y Hes continuo pero no diferenciable. As´ı, por ejemplo E. Catinas [1] propone el siguiente algoritmo xn+1 =xn−G0(xn)+[xn−1, xn;H]−1F(xn), n ≥0, x−1, x0∈Ω.(7) Pues bien, en este trabajo tratamos de conseguir una teor´ıa unificada para el estudio de todos estos procesos iterativos considerando el algoritmo xn+1 =xn−(A(xn−1, xn))−1F(xn), n ≥0, x−1, x0∈Ω (8) donde A(x, y) es un operador lineal y acotado de Ω ⊆Xen Y, es decir, A(x, y)∈ L(X, Y ) para x, y ∈Ω. Es claro que estos procesos iterativos dados en (8) generalizan los algoritmos (2), (4), (5), (6 ) y (7). As´ı, en la secci´on 2 estudiamos resultados de convergencia semilocal para (8) utilizando relaciones de recurrencia. En la secci´on 3, utilizando la descomposici´on en partes diferenciable y no diferenciable para el operador F, obtenemos otro resultado de convergencia semilocal, en esta ocasion aplicable al caso en que (1) represente una ecuaci´on no diferenciable. 2 M´etodos de tipo Newton de dos puntos 2. Relaciones de recurrencia. Convergencia semilocal En esta secci´on, haremos un estudio de la convergencia semilocal del algoritmo (8) considerando condiciones de tipo Lipschitz para los operadores involucrados. En primer lugar, suponemos que Fdiferenciable y se verifican las condiciones kF0(x)−F0(y)k ≤ k1kx−yk, kF0(x)−A(u, v)k ≤ k2(kx−uk+kx−vk); x, y, u, v ∈Ω (9) y consideramos k= max{k1, k2} A continuaci´on, estableceremos un conjunto de relaciones de recurrencia que nos permitir´an demostrar dicha convergencia. Sean x−1, x0∈Ω y suponemos que existe el inverso del operador lineal A0=A(x−1, x0) cumpli´endose las condiciones iniciales: (I)kA(x−1, x0)−1k ≤ β, kx−1−x0k=α, kA0−1F(x0)k ≤ η(10) Definimos a−1=η α+η, a0=βk(α+η) y la sucesi´on real {an}dada por an=f(an−1)2an−1an−2, n ≥1,(11) donde fes la funci´on f(x) = 1 1−x que es creciente y f(x)>1 para x∈(0,1). Como x1est´a bien definido por existir A0−1, se sigue kx1−x0k=kA0−1F(x0)k ≤ ηykA0−1kkkx1−x0k ≤ βkη =a0a−1. Probaremos por inducci´on sobre nlas siguientes relaciones para n≥1: (in)Existe An−1=A(xn−1, xn)−1tal que kAn−1k ≤ f(an−1)kAn−1−1k, (iin)kxn+1 −xnk ≤ f(an−1)an−1kxn−xn−1k, (iiin)kAn−1kkkxn−xn−1k ≤ f(an−1)an−1an−2, kAn−1kkkxn+1 −xnk ≤ anan−1. Suponiendo que a0<1, x1∈Ω y (9), tenemos kI−A0−1A1k ≤ kA0−1k kA0−A1k ≤ kA0−1kkA(x−1, x0)−F0(x0)k+kF0(x0)−A(x0, x1)k ≤βk(α+η) = a0<1, 3 M. J. Rubio, M. A. Hern´andez y por el lema de Banach existe A1−1y kA1−1k ≤ kA0−1k 1−kA0−1kk(kx−1−x0k+kx0−x1k)≤f(a0)kA0−1k lo que prueba (i1). Utilizando la formula de Taylor, tenemos F(x1) = (F0(x0)−A0)(x1−x0) + Z1 0F0x0+t(x1−x0)−F0(x0)(x1−x0)dt. Por (9) se sigue kF(x1)k ≤ kkx0−x−1k kx1−x0k+kkx1−x0k2≤k(α+η)kx1−x0k. Como x2est´a bien definido por estarlo A1−1, se obtiene kx2−x1k ≤ f(a0)kA0−1k kF(x1)k ≤ f(a0)a0kx1−x0k, y se cumple (ii1). Notar que, por (i1)y(ii1), se sigue kA1−1kkkx1−x0k ≤ f(a0)βkη =f(a0)a0a−1. Por otro lado, kA1−1kkkx2−x1k ≤ f(a0)βkf(a0)a0kx1−x0k ≤ a1a0. Suponiendo an<1 y xn∈Ω, para n≥1, se prueban de forma an´aloga (in+1)-(iiin+1). Para establecer la convergencia de la sucesi´on {xn}, ser´a suficiente probar que {an}es decreciente. Lema 2.1 Si (βkη)1/2< η/(α+η)<(3 −√5)/2, entonces la sucesi´on {an}dada por (11) es decreciente. Teorema 2.1 Supongamos que se satisfacen las condiciones (9), (10) y las hip´otesis del Lema 2.1. Si B(x0, r0)⊆Ω, donde r0=η 1−∆y∆ = a0 1−a0<1, entonces la sucesi´on {xn}dada por (8) est´a bien definida y converge a x∗soluci´on de (1). Adem´as la soluci´on x∗y las iteraciones xnpertenecen a B(x0, r0). Ahora nos planteamos generalizar al caso cuando el operador Fno sea diferenciable. Para ello hemos de sustituir las condiciones (9) dadas sobre F0. Esta generalizaci´on la llevamos a cabo considerando que para cada par de puntos distintos x, y ∈Ω, existe la diferencia dividida de primer orden en ellos [x, y;F]∈ L(X, Y ) y que se verifica: k[x, y;F]−A(u, v)k ≤ k(kx−uk+kx−vk); x, y, u, v ∈Ω,(12) Con esta nueva condici´on siguen cumpli´endose las relaciones de recurrencia planteadas al inicio de esta secci´on, obteni´endose la misma sucesi´on {an}. En efecto, lo comprobamos para el primer paso, ya que el proceso inductivo no ofrece dificultad. 4 M´etodos de tipo Newton de dos puntos Para la existencia del inverso A1−1, procedemos como sigue: kI−A0−1A1k ≤ kA0−1k kA0−A1k ≤ kA0−1k(kA(x−1, x0)−[x−1, x0;F]k+k[x−1, x0;F]−A(x0, x1)k) ≤βk(α+η) = a0<1, lo que demuestra (i1). Para comprobar (ii1), en lugar de utilizar la formula de Taylor, aplicamos (3) y (8) para expresar F(x1) de la siguiente forma: F(x1) = F(x0)−[x0, x1;F](x0−x1) = (A0−[x0, x1;F]) (x0−x1). Entonces, por (12), se obtiene kF(x1)k ≤ k[x0, x1;F]−A0k kx1−x0k ≤ k(kx0−x−1k+kx1−x0k)kx1−x0k ≤k(α+η)kx1−x0k y trivialmente se cumple (iii1). Estamos ya en condiciones de poder dar un nuevo teorema de convergencia semilocal, v´alido ahora para operadores no diferenciables Teorema 2.2 Supongamos que se satisfacen las condiciones (10), (12) y las hip´otesis del Lema 2.1. Si B(x0, r0)⊆Ω, donde r0=η 1−∆y∆ = βk(α+η) 1−βk(α+η), entonces la sucesi´on {xn}dada por (8) est´a bien definida y converge a x∗soluci´on de (1). Adem´as la soluci´on x∗y las iteraciones xnpertenecen a B(x0, r0). 3. Operadores no diferenciables De nuevo, en esta secci´on, analizaremos la convergencia semilocal de (8) en las condiciones iniciales consideradas en (10), dados x−1, x0∈Ω: (I)kA(x−1, x0)−1k ≤ β, kx−1−x0k=α, kA0−1F(x0)k ≤ η y supondremos adem´as (II) kG0(x)−G0(y)k ≤ ω1(kx−yk); x, y ∈Ω,siendo ω1:R+→R+continua y no decreciente, (III) Existe una funci´on continua y no decreciente h: [0,1] →R+, tal que ω1(tz)≤h(t)ω1(z), con t∈[0,1] y z∈[0,∞). Escribimos T=Z1 0 h(t)dt. (IV) kH(x)−H(y)k ≤ ckx−yk;x, y ∈Ω, (V) kG0(x)−A(y, z)k ≤ ω2(kx−yk,kx−zk); x, y, z ∈Ω,siendo ω2:R+×R+→R+ continua y no decreciente en ambas componentes 5 M. J. Rubio, M. A. Hern´andez Notar que la condici´on (III) no supone ninguna restricci´on porque siempre existe h tal que h(t) = 1, como consecuencia de ser ω1no decreciente. Teorema 3 En las condiciones (I)-(V), denotamos por m= max{β(ω2(α, 0) + Tω1(η) + c), β (ω2(η, 0) + Tω1(η) + c)} y suponemos que la ecuaci´on r1−m 1−β(ω2(α, 0) + ω2(r, r))−η= 0,(13) tiene al menos una soluci´on positiva. Sea Rla soluci´on positiva m´as peque˜na. Denotando por d=β(ω2(α, 0) + ω2(R, R)), si B(x0, R)⊂Ωym+d < 1, entonces, la sucesi´on {xn} dada por (8) est´a bien definida, pertenece a B(x0, R)y converge a una soluci´on x∗de la ecuaci´on F(x) = 0 en B(x0, R). Demostraci´on. Para simplificar la notaci´on, como hemos hecho antes, denotaremos A(xn−1, xn) = An. En primer lugar probaremos, por inducci´on, que la sucesi´on generada por (8) est´a bien definida, es decir, que en cada paso el operador Anposee inverso y el punto obtenido xn+1 est´a en Ω. De las hip´otesis iniciales se sigue que x1est´a bien definido y kx1−x0k ≤ η < R. Por tanto, x1∈B(x0, R)⊆Ω. Utilizando (V) y que ω2es no decrecientes, resulta kI−A0−1A1k ≤ kA0−1k kA0−A1k ≤ kA0−1k(kA(x−1, x0)−F0(x0)k+kF0(x0)−A(x0, x1)k ≤β(ω2(α, 0) + ω2(R, R)) <1, por el lema de Banach existe A1−1y adem´as kA1−1k ≤ β 1−β(ω2(α, 0) + ω2(R, R)) =β 1−d. Como Ges diferenciable, por la formula de Taylor, se tiene G(x1) = G(x0) + G0(x0)(x1−x0) + Z1 0G0(x0+t(x1−x0)) −G0(x0)(x1−x0)dt. Por otro lado, utilizando H(x1) = H(x0) + H(x1)−H(x0),podemos escribir F(x1) = G(x1) + H(x1) = F(x0) + G0(x0)(x1−x0) + H(x1)−H(x0) +Z1 0G0(x0+t(x1−x0)) −G0(x0)(x1−x0)dt. Entonces, por (8) F(x1) = G0(x0)−A(x−1, x0)(x1−x0)+Z1 0G0(x0+t(x1−x0)) −G0(x0)(x1−x0)dt+H(x1)−H(x0). Tomando normas y aplicando (II)-(V), se sigue que kF(x1)k ≤ (ω2(α, 0) + Tω1(η) + c)kx1−x0k, 6 M´etodos de tipo Newton de dos puntos entonces se obtiene que x2∈Ω considerando: kx2−x1k ≤ kA1−1k kF(x1)k ≤ m 1−dkx1−x0k=Mkx1−x0k< η, donde M=m 1−d. Por otro lado, teniendo en cuenta que Rsatisface (13), entonces kx2−x0k ≤ kx2−x1k+kx1−x0k ≤ (M+ 1)kx1−x0k ≤ (M+ 1)η < R. Es f´acil probar por inducci´on sobre nlas siguientes relaciones para n≥2: (in)∃An−1=A(xn−1, xn)−1tal que kAn−1k ≤ β 1−d, (iin)kxn+1 −xnk ≤ Mkxn−xn−1k ≤ Mnkx1−x0k ≤ ηyxn+1 ∈B(x0, R)⊆Ω. En segundo lugar, probaremos que {xn}es sucesi´on de Cauchy. Para k≥1 se tiene kxn+k−xnk ≤ kxn+k−xn+k−1k+kxn+k−1−xn+k−2k+···+kxn+1 −xnk ≤hMk−1+Mk−2+···+ 1ikxn+1 −xnk ≤ 1−Mk 1−Mkxn+1 −xnk<1 1−MMnkx1−x0k. en consecuencia, {xn}es una sucesi´on de Cauchy y converge a x∗∈B(x0, R). Por ´ultimo, veamos que x∗es una ra´ız de F. Como kF(xn)k ≤ (ω2(η, 0) + Tω1(η) + c)kxn−xn−1k ykxn−xn−1k → 0 cuando n→ ∞, se tiene F(x∗) = 0. 4. Aplicaci´on Sea el siguiente sistema      x3/2−y−3 4+1 9|x−1|= 0, y3/2+2 9x−3 8+1 9|y|= 0. (14) Por tanto, tenemos el operador F:R2→R2con F= (F1, F2). Para x= (x1, x2)∈R2 tomamos F1(x1, x2) = x13/2−x2−3 4+1 9|x1−1|,F2(x1, x2) = x23/2+2 9x1−3 8+1 9|x2| Aplicaremos el m´etodo de la Secante para aproximar F(x) = 0. Dados u, v ∈R2, tomamos [u, v;F]∈ L(R2,R2) como [u, v;F]i1=Fi(u1, v2)−Fi(v1, v2) u1−v1 ,[u, v;F]i2=Fi(u1, u2)−Fi(u1, v2) u2−v2 , i = 1,2. Luego [u, v;F] =   u3/2 1−v3/2 1 u1−v1−1 2 9 u3/2 2−v3/2 2 u2−v2  +1 9 |u1−1|−|v1−1| u1−v10 0|u2|−|v2| u2−v2! 7 M. J. Rubio, M. A. Hern´andez Entonces, con la norma del m´aximo, se sigue k[x, y;F]−[u, v;F]k ≤ kx−uk1/2+ky−vk1/2+2 9. Por tanto no se verifica la condici´on Lipschitz (12) y estamos en la situaci´on descrita en la secci´on 2. Establecemos la descomposici´on de Fen su parte diferenciable G= (G1, G2) y no diferenciable H= (H1, H2). Para x= (x1, x2)∈R2tenemos G1(x1, x2) = x13/2−x2−3 4, G2(x1, x2) = x23/2+2 9x1−3 8,H1(x1, x2) = 1 9|x1−1|,H2(x1, x2) = 1 9|x2|. Por tanto, se tiene G0(x) = 3 2x1/2 1−1 2 9 3 2x1/2 2!,kG0(x)−G0(y)k ≤ 3 2kx−yk1/2 As´ı como H(x) = 1 9|x1−1|0 0|x2|ykH(x)−H(y)k ≤ 1 9kx−yk Ahora aplicamos el m´etodo de la Secante para aproximar la soluci´on de (14). Elegimos z−1= (5,5) y z0= (1,0). Despu´es de tres iteraciones conseguimos z2= (1,06157,0,329438) y z3= (1,00309,0,253723) . Entonces, tomamos x−1=z2yx0=z3. y resulta α= 0,0757149, β = 1,15189, η = 0,00371354, T =2 3 Por tanto, la sucesi´on generada por el m´etodo dicho converge a una soluci´on x∗de la ecuaci´on F(x) = 0 en B(x0, R). Obtenemos el vector x∗= (1,0,25) como soluci´on del sistema (14). Agradecimientos Ayuda a la Investigaci´on del Ministerio de Educaci´on y Ciencia. Ref. MTM 2005-03091 Referencias [1] E. Catinas. On some iterative methods for solving nonlinear equations. Rev. Anal. Num´er. Th´eor. Approx., 23 (1994), 47–53. [2] M.A. Hern´andez, M.J. Rubio y J.A. Hezquerro. Solving a special case of conservative problems by secant-like methods. Appl. Math. Comput., 169, no. 2 (2005), 926–942. [3] L.W. Johnson y D.R. Scholz. On Steffensen’s Method. SIAM J. Numer. Anal., 5, no. 2 (1968), 296– 302. [4] J.W. Schmidt. Untere Fehlerschranken fur Regula-Falsi Verhafren. Period. Math. Hungar., 9 (1978), 241–247. 8