This is page iPrinter: Opaque this

Metodos Iterativos para Ecuaciones no

Lineales

Oldemar Rodrguez Rojas

Septiembre 2008

ii

This is page iiiPrinter: Opaque this

Contents

1 Metodos iterativos para ecuaciones no lineales v1 El metodo de aproximaciones sucesivas . . . . . . . . . . . . v

1.1 Teoremas de convergencia y del error . . . . . . . . . v1.2 El metodo de punto fijo para resolver ecuaciones de

una variable . . . . . . . . . . . . . . . . . . . . . . . xi2 Metodo de la Biseccion . . . . . . . . . . . . . . . . . . . . . xiv

2.1 Estudio del error en el metodo de la biseccion . . . . xvii3 Metodo de NewtonRaphson . . . . . . . . . . . . . . . . . xviii4 Metodo de la Secante . . . . . . . . . . . . . . . . . . . . . . xxii5 Orden de convergencia . . . . . . . . . . . . . . . . . . . . . xxv6 Convergencia acelerada y el metodo de Steffensen . . . . . . xxx

6.1 El metodo 42 de Aitken . . . . . . . . . . . . . . . . xxx6.2 El metodo de Steffensen . . . . . . . . . . . . . . . . xxxi

iv

This is page vPrinter: Opaque this

Metodos iterativos paraecuaciones no lineales

1 El metodo de aproximaciones sucesivas

1.1 Teoremas de convergencia y del error

Teorema 1 Sea U un subconjunto completo de un espacio normado X yA : U U una contraccion. Entonces las aproximaciones sucesivas:

xn+1 = Axn, para n = 0, 1, 2, . . . ,

con x0 arbitrario en U, convergen al punto fijo unico x de A.

Prueba Sea x0 U entonces definimos recursivamente la siguiente sucesionen U :

xn+1 := Axn, para n = 0, 1, 2, . . . .

De donde se tiene que:

xn+1 xn = Axn Axn1 q xn xn1 ,

luego por induccion se deduce que:

xn+1 xn qn x1 x0 , para n = 0, 1, 2, . . . .

Por lo tanto para m > n se tiene que:

xn xm xn xn+1+ xn+1 xn+2+ + xm1 xm (1.1)

(qn + qn+1 + + qm1

)x1 x0

qn

1 qx1 x0 .

Como qn 0 cuando n, entonces (xn) es una sucesion de Cauchy ycomo U es completo existe x U tal que xn x cuando n.

Corolario 1 [Cota del Error a Priori] Con las mismas hipotesis del Teo-rema 1 se tiene el siguiente estimado para el error a priori:

xn x qn

1 qx1 x0 .

Prueba Es evidente de la desigualdad (1.1).

vi 1. Metodos iterativos para ecuaciones no lineales

Corolario 2 [Cota del Error a Posteriori] Con las mismas hipotesis delTeorema 1 se tiene el siguiente estimado para el error a posteriori:

xn x q

1 qxn xn1 .

Prueba Se deduce del error a priori iniciando con x0 = xn1.

Teorema 2 [Version 1] Sea D R un cerrado y sea g : D D unafuncion continuamente diferenciable con la siguiente propiedad:

q := supxD|g(x)| < 1.

Entonces la ecuacion g(x) = x tiene solucion unica x D y la sucesion deaproximaciones sucesivas:

xn+1 := g(xn), para n = 0, 1, 2, . . .

con x0 arbitrario en D converge a esta solucion. Ademas se tiene el siguienteestimado para el error a priori:

|xn x| qn

1 q|x1 x0| , (1.2)

y el siguiente estimado para el error a posteriori:

|xn x| q

1 q|xn xn1| . (1.3)

Ademas si D = [a, b] entonces se tiene tambien la siguiente cota del error:

|xn x| qn max{x0 a, b x0}. (1.4)

Prueba El espacio R equipado de la norma valor absoluto | | es un espaciode Banach. Por el teorema del valor medio, para todo x, y D con x < yse tiene que:

g(x) g(y) = g()(x y)para algun punto ]x, y[. Por lo tanto:

|g(x) g(y)| supD|g()| |x y| = q |x y| ,

lo cual tambien es valido para x, y D con x y. Por lo tanto g es unacontraccion, luego aplicando el Teorema de Banach o el Teorema 1 se tienela existencia y unicidad del punto fijo. De los corolarios 1 y 2 se tienenobviamente las desigualdades (1.2) y (1.3). Para probar la cota del error(1.4) note que:

|xn x| = |g(xn1) g(x)| = |g(1)| |xn1 x| q |xn1 x|= q |g(xn2) g(x)| = q |g(2)| |xn2 x| q2 |xn2 x| qn |x0 x| qn max{x0 a, b x0}.

1. Metodos iterativos para ecuaciones no lineales vii

Teorema 3 [Version 2] Sea g C[a, b], con g : [a, b] [a, b]. Entonces:

1. g tiene un punto fijo en [a, b].

2. Ademas si g(x) existe en ]a, b[ y |g(x)| q < 1, para todo x ]a, b[entonces g tiene un punto fijo unico en [a, b].

Prueba

1. I Caso: Si g(a) = a o g(b) = b se tiene la prueba.

II Caso: Si g(a) 6= a y g(b) 6= b g(a) > a y g(b) < bTome h(x) = g(x) x, note que:

h es continua en [a, b],

h(a) = g(a) a > 0,h(b) = g(b) b < 0,

luego h(a) y h(b) tienen signos opuestos, usando el teorema de losvalores intermedios, se tiene que existe x [a, b] tal que h(x) = 0g(x) x = 0 g(x) = x, por lo x es el punto fijo de g.

2. Suponga que g tiene dos puntos fijos en [a, b], sean estos x y y, conx 6= y, entonces por el Teorema del Valor Medio existe ]a, b[ talque:

|x y| = |g(x) g(y)| = g() |x y| q |x y| < |x y|

de donde |x y| < |x y| , lo cual es una contradiccion, luego setiene que x = y.

Ejemplo 1 Pruebe que f(x) =x2 2x

6, x [1, 1] tiene un punto fijo en

[1, 1].

Solucion: Se debe probar que f(x) [1, 1] para todo x [1, 1]. Comof (x) =

16(2x 2) = x 1

3= 0 x = 1 entonces los maximos o mnimos

posibles estan en x = 1 o x = 1. Como f(1) = 12

es maximo y f(1) =

16

es mnimo entonces para todo x [1, 1] se tiene que f(x) [1, 1],de donde f tiene un punto fijo en [1, 1]. Solo se ha probado que existe porlo menos un punto fijo, ahora tenemos que probar que es unico. Se debeprobar que existe q < 1 tal que |f (x)| q < 1, para todo x ] 1, 1[.Note que:

viii 1. Metodos iterativos para ecuaciones no lineales

| f (x)| = x 13

1 13 = 23 < 1, para todo x ] 1, 1[,

Luego f(x) tiene un punto fijo unico en [1, 1].

Teorema 4 Sea x un punto fijo de una funcion continuamente diferen-ciable g tal que |g(x)| < 1. Entonces el metodo de la aproximacionessucesivas xn+1 := g(xn), para n = 0, 1, 2, . . . es localmente convergente,es decir existe un vecindario B del punto fijo x de g tal que el metodo deaproximaciones sucesivas converge a x, para x0 B.

Prueba Como g es continua y |g(x)| < 1 entonces existe una constante0 < q < 1 y > 0 tal que |g(y)| < q para todo y B := [x , x + ].Entonces se tiene que:

|g(y) x| = |g(y) g(x)| q |y x| < |y x|

para todo y B, por lo que se deduce que g mapea B en si mismo, o sea queg : B B es una contraccion, por lo que el resultado se tiene del Teorema1.El Teorema 4 se ilustra en la Figura 1.

FIGURE 1. El metodo de aproximaciones sucesivas.

Seguidamente se presenta un algoritmo en seudocodigo para el metodo delas aproximaciones sucesivas.

Algoritmo 1 [Para encontrar puntos fijos]Entrada: x0 (aproximacion inicial), Tol,N, g(x)

1. Metodos iterativos para ecuaciones no lineales ix

Salida: x (punto fijo aproximado) o mensaje de errorPaso 1. i 1Paso 2. Mientras i N siga los pasos 36

Paso 3. x g(x0)Paso 4. Si |x x0| < Tol

Salida xParar

Paso 5. i i + 1Paso 6 x0 x

Paso 7. Mensaje de error (Numero maximo de iteraciones excedido)Parar

Una implementacion iterativa en Mathematica es la siguiente:

PuntoFijo[X0 ,Tol , n , G ]:=Module[{i=1,X0Tem=X0,X},

While[i

x 1. Metodos iterativos para ecuaciones no lineales

Ejemplo 2 Sea f(x) = ex, es facil probar que f(x) mapea A = [0.5, 0.69]en si mismo (ejercicio). Como f es continuamente diferenciable tome

q = maxxA| f (x)| = max

xA

ex 0.606531 < 1Si se ejecuta el programa iterativo en Mathematica como sigue:

In[1]:=[PuntoFijo[0.55, 0.000001, 30, G], 15]

es decir, tomando x0 = 0.55 como aproximacion inicial, con = Tol =106 para el algoritmo anterior obtenemos que el punto fijo de F es x =x19 = 0.567143650676, pues en x19 se termino la ejecucion del programa,como se aprecia en la salida del programa:

En la iteracion 1 el valor de X es 0.576949810380487En la iteracion 2 el valor de X es 0.561608769952327En la iteracion 3 el valor de X es 0.570290858658895En la iteracion 4 el valor de X es 0.565360974647922En la iteracion 5 el valor de X es 0.568155020178646En la iteracion 6 el valor de X es 0.566569784824922En la iteracion 7 el valor de X es 0.567468643541252En la iteracion 8 el valor de X es 0.566958798578383En la iteracion 9 el valor de X es 0.567247933366687En la iteracion 10 el valor de X es 0.567083945963931En la iteracion 11 el valor de X es 0.567176948212764En la iteracion 12 el valor de X es 0.567124201933893En la iteracion 13 el valor de X es 0.567154116414135En la iteracion 14 el valor de X es 0.567137150547289En la iteracion 15 el valor de X es 0.567146772602292En la iteracion 16 el valor de X es 0.567141315511106En la iteracion 17 el valor de X es 0.567141315511106En la iteracion 18 el valor de X es 0.567142655180367En la iteracion 19 el valor de X es 0.567143650676Out[1]:=0.567143650676

Por otro lado el error absoluto al calcular x12 = 0.567124201933893 iguala:

|x x12| 1.91 105,

mientras que usando el error a priori se obtiene:

|x x12| q12

1 q|x1 x0| = 1.70 104

y usando el error a posteriori se obtiene que:

|x x12| q

1 q|x12 x11| = 8.13 105

1. Metodos iterativos para ecuaciones no lineales xi

que es una mejor estimacion del verdadero error. Usando el error a priori sededuce que para obtener una precision de = 106 se requieren al menosde:

n log(

(1 q)|x1 x0|

)/ log(q) 22.3 23 iteraciones,

pero se observa que el programa requirio de 19 iteraciones.Ejecutando la version recursiva se obtiene el mismo resultado:

N[PuntoFijoRe cursivo[0.55, 0.000001, 30, G], 15]

es decir, x = 0.567143650676.

1.2 El metodo de punto fijo para resolver ecuaciones de unavariable

Ejemplo 3 Resuelva la ecuacion x3 x 1 = 0 en el intervalo [1, 2].

Solucion: Se debe plantear un problema de encontrar los puntos fijos deuna funcion g(x) que sea equivalente a resolver la ecuacion x3 x 1 = 0.Resolver x3 x 1 = 0 es equivalente a resolver la ecuacion x3 1 = x,entonces se puede tratar de encontrar los puntos de g(x) := x3 1. Perog(x) no cumple las hipotesis del Teorema de Punto Fijo de Banach, puesg(x) = 3x2 > 0 g(x) es creciente en [1, 2], luego g(1) = 0 y g(2) = 7 sonel mnimo y el maximo de g(x) en el intervalo [1, 2] respectivamente, por loque g(x) / [1, 2] x [1, 2]. Otro intento se puede hacer usando el hechode que:

x3 x 1 = 0 x =

1 +1x

,

luego tome g(x) :=

1 +1x

, g(x) = 1

2x2

1 + 1x< 0 en [1, 2], esto

implica que g(x) es decreciente en [1, 2], luego g(1) =

2 1.41, g(2) =32 1.22 son el maximo y el mnimo respectivamente de g(x) en [1, 2],

por lo que g(x) [1, 2] x [1, 2], luego la funcion g(x) tiene al menos unpunto fijo en [1, 2].Se probo que g : [1, 2] [1, 2], falta probar que g es una contraccion en elintervalo [1, 2]. Veamos

g(x) = 1

2x2

1 + 1x |g(x)| = 1

2x2

1 + 1x 1

2:= q < 1

de donde se puede tomar q :=12.

Ejecutando el programa de punto fijo con x0 = 2 y = 105 se obtiene:

xii 1. Metodos iterativos para ecuaciones no lineales

G[x ] := Sqrt[1 + 1/x]N[PuntoFijo[2,0.00001,30,G],15]En la iteracion 1 el valor de X es 1.22474487139159En la iteracion 2 el valor de X es 1.3477746773581En la iteracion 3 el valor de X es 1.31983475643837En la iteracion 4 el valor de X es 1.32577170214339En la iteracion 5 el valor de X es 1.32449147872207En la iteracion 6 el valor de X es 1.32476667564583En la iteracion 7 el valor de X es 1.32470747924203En la iteracion 8 el valor de X es 1.32472021086795En la iteracion 9 el valor de X es 1.32471747253653

Luego el punto fijo de g(x) y solucion de la ecuacion x3 x 1 = 0 en elintervalo [1, 2] es: x = 1.32471747253653. Ejecutando la version recursivase obtiene la misma solucion:

In[9]:=N[PuntoFijoRecursivo[2,0.00001,30,G],15]Out[9]:=1.32471747253653

Usando el comando Solve de Mathematica se obtiene:

N[Solve[x^3 - x - 1 == 0, x]]{{x->1.32472},{x->-0.662359+0.56228 I},{ x->-0.662359-0.56228I}}

Que coincide con la solucion encontrada por nuestro programa. Graficamentese ilustra el la Figura 2 usando el comando de Plot[{G[x],x},{x,0.1,3}]de Mathematica.

1. Metodos iterativos para ecuaciones no lineales xiii

FIGURE 2. Grafico de g(x) y de la funcion identidad.

Ejemplo 4 Dada la ecuacion del ejemplo anterior x3 x 1 = 0 en elintervalo [1, 2], Cuantas iteraciones se requieren para obtener un errorabsoluto menor que 105?

Solucion: Recuerde que q =12

de donde se tiene que:

|xn x| qn max{x0 a, b x0}

=(

12

)nmax{1, 0} (con x0 = 2)

(

12

)n.

Luego:

|xn x| 105 (

12

)n 105 n 16.6.

Tome n = 17.

Observacion 1 En la practica el programa requirio solamente 9 itera-ciones.

Ejemplo 5 Para la ecuacion x3x1 = 0 en el intervalo [1, 2], con x0 = 2estime usando el error a priori (1.2) Cuantas iteraciones se requieren paraobtener un error absoluto menor que 105?

Solucion: Se tiene que

q =12, x0 = 2, g(x) =

1 +

1x

.

xiv 1. Metodos iterativos para ecuaciones no lineales

De donde se obtiene que x1 =

1 +12

=

32 1.2 entonces:

|xn x| (

12

)n1 12

|2 1.2|

=(

12

)n1 0.8,

entonces:

|xn x| 105 (

12

)n1 0.8 105

(n 1)( log(2)) 5 log(0.8),

esto implica que n 17.28, por lo que se puede tomar n = 18.

Observacion 2 En la practica el programa requirio solamente 9 itera-ciones.

2 Metodo de la Biseccion

Las hipotesis de este metodo son:

f debe ser continua en el intervalo [a, b].

f(a) y f(b) deben tiener signos opuestos.

Luego por el Teorema de los Valores Intermedios existe x [a, b] tal quef(x) = 0, graficamente se ilustra en la Figura 3.

FIGURE 3. El metodo de la biseccion.

1. Metodos iterativos para ecuaciones no lineales xv

La idea es encontrar una sucesion (xn) tal que xn x cuando n talque f(x) = 0. Para encontrar la sucesion (xn) la idea es la siguiente:

Tome a1 = a, b1 = b, x1 =a1 + b1

2.

Si f(x1) = 0 entonces ya se tiene el cero de la ecuacion x = x1.

Si no:

Si f(x1) y f(a) tienen el mismo signo se toma:

a2 = x1, b2 = b1, x2 =a2 + b2

2.

Si no se toma:

a2 = a1, b2 = x1, x2 =a2 + b2

2,

y as sucesivamente hasta que f(xi) 0 o hasta superar elnumero maximo de iteraciones. El pseudocodigo de puede es-cribir como sigue:

Algoritmo 2 [Metodo de la Biseccion]Entrada: a, b, Tol (tolerancia), N, f .Salida: Aproximacion de x (cero de la ecuacion) o mensaje de error

Paso 1. i 1Paso 2. Mientras i N, siga los pasos 36

Paso 3. x a + b2

Paso 4. Si f(x) = 0 o |b a| < TolSalida (x)

PararPaso 5. i i + 1Paso 6. Si f(a) f(x) > 0

a xSi no

b xPaso 7. Salida ( Numero maximo de iteraciones excedido)

Parar

Este algoritmo se puede programar iterativamente en Mathematica comosigue:

Biseccion[a ,b ,Tol ,n ,G ]:=Module[{i = 1, a1 = a, b1 = b, X},

If[G[a]G[b] > 0,Print[El metodo no Converge],

xvi 1. Metodos iterativos para ecuaciones no lineales

While[i0, a1 = X,b1 = X];If[(G[X] == 0)||((b1 - a1) < Tol),Return[X]];i++;

];If[i==n+1,

Print[El metodo no Converge]];

];];

Este algoritmo se puede programar recursivamente en Mathematica comosigue:

BiseccionRecursivo[a ,b ,Tol ,F ] :=Module[{A=a,B=b,X},

X=(A+B)/2;If[(F[X]

1. Metodos iterativos para ecuaciones no lineales xvii

En la iteracion 8 el valor de X es 1.36328125En la iteracion 9 el valor de X es 1.365234375En la iteracion 10 el valor de X es 1.3642578125En la iteracion 11 el valor de X es 1.36474609375En la iteracion 12 el valor de X es 1.364990234375En la iteracion 13 el valor de X es 1.3651123046875En la iteracion 14 el valor de X es 1.36517333984375En la iteracion 15 el valor de X es 1.36520385742188En la iteracion 16 el valor de X es 1.36521911621094En la iteracion 17 el valor de X es 1.36522674560547En la iteracion 18 el valor de X es 1.36523056030273En la iteracion 19 el valor de X es 1.3652286529541En la iteracion 20 el valor de X es 1.36522960662842

Ejecutando la version recursiva se obtiene:

In[21]:=N[BiseccionRecursivo[1,2,0.000001,G],15]Out[21]:=1.36523008346558

2.1 Estudio del error en el metodo de la biseccion

Teorema 5 Sea f C[a, b], con f(a)f(b) < 0. Entonces el algoritmo dela biseccion produce una sucesion (xn) que aproxima a x, el cero de laecuacion f(x) = 0, con un error absoluto tal que:

|xn x| 0

Algoritmo 3 [Metodo de NewtonRaphson]Entrada: x0, N, Tol, f .Salida: La solucion x aproximada de la ecuacion f(x) o mensaje de error.

Paso 1. i 1Paso 2. Mientras i N, pasos 3-6

Paso 3. x x0 f(x0)f (x0)

Paso 4. Si |x x0| < Tol

xx 1. Metodos iterativos para ecuaciones no lineales

Salida (x)Parar.

Paso 5. i i + 1Paso 6. x0 x

Paso 7. Salida ( Numero maximo de iteraciones excedido)Parar

El metodo de NewtonRaphson se puede implementar iterativamente enMathematica como sigue:

NewtonRaphson[x0 , Tol , n , F ] :=Module[{i = 1, X0Tem = x0, x},

G[X ] = D[F[X],X];While[(i

1. Metodos iterativos para ecuaciones no lineales xxi

= 106 se obtiene la siguiente:

In[2]:=F[x ]:=N[Exp[-x]-x];In[3]:=N[NewtonRaphson[1,0.000001,20,F],15]En la iteracion 1 el valor de x es 0.53788284273999En la iteracion 2 el valor de x es 0.566986991405413En la iteracion 3 el valor de x es 0.567143285989123En la iteracion 4 el valor de x es 0.567143290409784Out[3]:=0.567143290409784

Mientras que ejecutando el programa recursivo se obtiene:

In[5]:=N[NewtonRaphsonRecursivo[1,0.000001,20,F],15]Out[5]:=0.567143290409784

Teorema 6 Sea f C2[a, b]. Si x [a, b] con f(x) = 0 y f (x) 6= 0,entonces existe > 0 tal que el metodo de NewtonRaphson:

xn+1 := xn f(xn)f (xn)

genera una sucesion que esta bien definida y converge a x cuando n,para todo x0 [x , x + ].

Prueba Sea

g(x) := x f(x)f (x)

.

Notese que si x [a, b] con f(x) = 0 entonces g(x) [a, b] y g(x) = x. Sedefine:

pn :={

p0 si n = 0g(pn1) si n 1

Es claro que la (pn) es la sucesion de NewtonRapson, entonces bastaprobar que g cumple las hipotesis del Teorema de punto fijo de Banach, asaber que:

> 0 y q ]0, 1[ tal que x ]x , x + [ |g(x)| q < 1,

y que g mapea el intervalo [x , x + ] en si mismo.Como f (x) 6= 0 y f es continua se tiene que existe un 1 > 0 tal quef (x) 6= 0 para todo x ]x 1, x + 1[ [a, b], de esta manera g estadefinida y es continua en ]x 1, x + 1[. Tambien lo esta:

g(x) =f(x)f (x)[f (x)]2

para todo x ]x 1, x + 1[.

xxii 1. Metodos iterativos para ecuaciones no lineales

Como f C2[a, b] entonces g C1[x 1, x + 1]. Como por hipotesisf(x) = 0 entonces:

g(x) =f(x)f (x)[f (x)]2

= 0.

Luego como g es continua, esto implica que para cualquier constante q < 1existe un , con 0 < < 1 y tal que:

|g(x)| q < 1 para todo x ]x , x + [.

Solo falta probar que g : ]x, x+[]x, x+[, pero si x ]x, x+[por el Teorema del Valor Medio para algun entre x y x se tiene que:

|g(x) g(x)| = |g()| |x x| ,

entonces:

|g(x) x| = |g(x) g(x)| = |g()| |x x| q |x x| < |x x| . (1.7)

Como x ]x , x + [ entonces |x x| < luego por (1.7) se tiene que|g(x) x| < lo cual implica que g(x) ]x , x+ [ con lo que se pruebaque g : ]x , x + []x , x + [.

Ejemplo 9 Hallar un metodo para calcular

A, con A 0.

Solucion: Probaremos que la sucesion (xn) definida por xn+1 =12

(xn +

A

xn

)converge a

A. Notese que calcular

A es equivalente a resolver la ecuacion:

x2 A = 0,

usando el metodo de NewtonRaphson con f(x) = x2 A y f (x) = 2x setiene que:

xn+1 = xn f(xn)f (xn)

= xn x2n A

2xn

=12

(xn +

A

xn

).

De donde es claro que la sucesion xn

A cuando n.

4 Metodo de la Secante

El problema con el metodo de NewtonRapson es que requiere la derivadade f(x) la cual en muchos casos no se tiene. La idea del metodo de la

1. Metodos iterativos para ecuaciones no lineales xxiii

secante es usar una aproximacion para esta derivada, como se ilustra en laFigura 5.

FIGURE 5. Metodo de la secante.

La deduccion del metodo es la siguiente:

f (xn1) = limnxn1

f(x) f(xn1)x xn1

f(xn2) f(xn1)xn2 xn1

. (1.8)

Si en el metodo de NewtonRapson xn = xn1 f(xn1)f (xn1)

sustituimos

f (xn1) por la aproximacion dada en (1.8) se tiene que:

xn xn1 f(xn1)

f(xn2) f(xn1)xn2 xn1

,

simplificando se obtiene el Metodo de la Secante:

xn xn1 (xn2 xn1)f(xn1)

f(xn2) f(xn1).

Entonces el metodo de la secante consiste en calcular la sucesion (xn)definida por:

xn =

x0 si n = 0x1 si n = 1

xn1 (xn2 xn1)f(xn1)

f(xn2) f(xn1)si n 2

El siguiente algoritmo permite calcular esta sucesion:

xxiv 1. Metodos iterativos para ecuaciones no lineales

Algoritmo 4 [Metodo de la Secante]Entrada: N,Tol, x0, x1Salida: Aproximacion de x, con f(x) = 0 o mensaje de error

Paso 1. i 2Paso 2. Mientras i N, pasos 36

Paso 3. x x1 (x0 x1)f(x1)f(x0) f(x1)

Paso 4. Si |x x0| < TolSalida (x)

PararPaso 5. x0 x1

x1 xPaso 6. i i + 1

Paso 7. Salida (Numero maximo de iteraciones excedido)Parar

Una implementacion iterativa en Mathematica del algoritmo anterior esla siguiente:

Secante[X0 ,X1 ,Tol ,N ,F ]:=Module[{i=2,X0Tem=X0,X1Tem=X1,X},

While[(i

1. Metodos iterativos para ecuaciones no lineales xxv

];

Ejemplo 10 Ejecutando el programa iterativo para resolver la ecuacionex x = 0 con x0 = 1 y x1 = 12 como aproximaciones iniciales y con unatolereacia de = 106 se obtiene la siguiente:

In[1]:=F[x ]:=Exp[-x]-xIn[2]:=N[Secante[1,0.5,0.000001,100,F],15]En la iteracion 2 el valor de P es 0.572112En la iteracion 3 el valor de P es 0.567204En la iteracion 4 el valor de P es 0.567143En la iteracion 5 el valor de P es 0.567143Out[2]:=0.567143290410387

Mientras que ejecutando la version recursiva se obtiene:

In[3]:=N[SecanteRecursivo[1,0.5,0.000001,100,F],15]Out[3]:=0.567143290410387

Teorema 7 Sea f una funcion de clase C2[a, b] con a < b. Si existe unpunto x tal que f(x) = 0 y f (x) 6= 0 entonces existe un numero > 0 talque si x0 y x1 estan dentro del intervalo [x , x + ] la sucesion generadapor el metodo de la secante

xn = xn1 (xn2 xn1)f(xn1)

f(xn2) f(xn1).

esta bien definida dentro del intervalo [x , x + ] y converge a x (cero dela ecuacion f(x) = 0).

Prueba Ejercicio.

5 Orden de convergencia

Definicion 1 Sea (xn) una sucesion que converge a x, se denota en :=xn x para n 0. Si existen constantes y positivas, tal que:

limn

|xn+1 x||xn x|

= limn

|en+1||en|

= ,

entonces se dice que la sucesion (xn) converge a x con orden y conconstante asintotica .

Observacion 6 Entre mayor sea el orden de convergencia, o sea en-tre mayor sea , mayor sera la velocidad de convergencia.

Si = 1, se dice que el metodo tiene orden lineal.

xxvi 1. Metodos iterativos para ecuaciones no lineales

Si = 2, se dice que el metodo tiene orden cuadratico.

Ejemplo 11 Suponga que tenemos dos esquemas (sucesiones) xn y xn talque:

limn

|en+1||en|

= 0.75 (metodo lineal).

limn

|en+1||en|2

= 0.75 (metodo cuadratico).

Se supone ademas que e0 = 0.5 y e0 = 0.5

Cuantas iteraciones requieren xn y xn para converger con un error abso-luto menor a 108?Solucion:

1. Analicemos primero la sucesion (esquema) xn:

|xn+1 x| < 108 |en+1| < 108.

Pero|en+1||en|

0.75 de donde |en+1| 0.75 |en| 0.752 |en1|

0.75n |e0| = 0.75n 0.5, esto implica que:

|en+1| < 108 0.75n 0.5 < 108 n log(0.75) < 8 log(0.5)

n >8 log(0.5)

log(0.75) 61.62.

Se puede tomar n = 62, por lo tanto xn requiere aproximadamente62 iteraciones para converger a x.

2. Analicemos ahora la sucesion xn:

|xn+1 x| < 108 |en+1| < 108.

Pero|en+1||en|2

0.75 de donde |en+1| 0.75 |en|2 0.75[0.75 |en1|2

]2=

0.753 |en1|4 0.753[0.75 |en2|2

]4= 0.757 |en2|8 0.752

n+11 |e0|2n+1

,

1. Metodos iterativos para ecuaciones no lineales xxvii

de donde

|en+1| < 108

0.752n+11 |e0|2

n+1

< 108 0.752

n+11 0.52n+1

< 108 0.751 0.3752

n+1< 108

2n+1 log(0.375) < 8 + log(0.75)

2n+1 >8 + log(0.5)

log(0.375)

(n + 1) log(2) > log(19.07)

n >log(19.07)

log(2) 1 3.24,

luego n = 4, por lo que xn requiere solamente de n = 4 iteracionespara converger a x mientras que esquema lineal requirio de aproxi-madamente 62 iteraciones para converger a x.

Teorema 8 Sea xn ={

x0 si n = 0g(xn1) si n 1

el esquema (la sucesion)

de punto fijo visto en la seccion 1. Si ademas se supone que:

g : [a, b] [a, b].

g C2[a, b].

Existe q tal que 0 q < 1 y |g(x)| q < 1 para todo x ]a, b[.

g(x) 6= 0 para x el punto fijo de g.

Entonces (xn) converge al menos linealmente a x, cuando n.

Prueba

|en+1| = |xn+1 x| = |g(xn) g(x)| = |g(n)(xn x)| = |g(n)en|

con n entre xn y x. Como xn x cuando n y n esta entre xn y xentonces la sucesion (n) tambien converge a x cuando n. Luego

limn

|en+1||en|

= limn

|g(n)en||en|

= limn

|g(n)| =g ( lim

n(n)

) = g(x).Por lo tanto lim

n

|en+1||en|

= g(x) := < 1, de donde la convergencia es

lineal.

xxviii 1. Metodos iterativos para ecuaciones no lineales

Teorema 9 Sea x un punto fijo de g, ademas g(x) = 0, g es continua enun intervalo abierto I que contiene a x y g(x) 6= 0. Entonces existe > 0

tal que para x0 [x , x + ] la sucesion xn ={

x0 si n = 0g(xn1) si n 1

converge al menos cuadraticamente a x.

Prueba Escoja tal que intervalo [x, x+] este contenido en I, |g(x)| q < 1 y g sea continua. Como |g(x)| q < 1 se tiene que los terminos dela sucesion (xn) estan contenidos en [x , x + ]. Expandiendo g(x) en supolinomio de Taylor para x [x , x + ] se tiene que:

g(x) = g(x) + g(x)(x x) + g()2

(x x)2,

con entre x y x. Por hipotesis g(x) = x y g(x) = 0, esto implica que:

g(x) = x +g()

2(x x)2.

En particular si se toma x = xn entonces:

xn+1 = g(xn) = x +g(n)

2(xn x)2.

con n entre xn y x. Luego

xn+1 x =g(n)

2(xn x)2. (1.9)

Como |g(x)| q < 1 y g mapea [x , x + ] en si mismo es claro que(xn) converge a x punto fijo de g, entonces como n esta entre xn y x lasucesion (n) converge tambien a x. Luego usando (1.9) se deduce que:

limn

|xn+1 x||xn x|2

=|g(x)|

2= 6= 0.

Entonces la sucesion (xn) converge cuadraticamente x.

Corolario 3 Sea f C3[a, b]. Si x [a, b] con f(x) = 0, f (x) 6= 0 yf (x) 6= 0, entonces existe > 0 tal que el metodo de NewtonRaphson:

xn+1 := xn f(xn)f (xn)

genera una sucesion que converge al menos cuadraticamente a x cuandon, para todo x0 [x , x + ].

Prueba La convergencia de (xn) se demostro en el Teorema 6. Usando el

teorema anterior se concluye el corolario, pues si se toma g(x) := x f(x)f (x)

1. Metodos iterativos para ecuaciones no lineales xxix

entonces g(x) = x f(x)f (x)

= x pues f(x) = 0 y f (x) 6= 0. Ademas

g(x) = 1 f(x)f (x) f(x)f (x)

(f (x))2= 1 1 f(x)f

(x)[f (x)]2

= f(x)f(x)

[f (x)]2

de donde g(x) = 0, pues f(x) = 0. Como:

g(x) =[f (x)]2 f (x) + f(x)f (x)f (3)(x) 2f(x) [f (x)]2

[f (x)]3,

entonces g(x) =f (x)f (x)

6= 0. Es claro que g es continua en un intervalo

que contiene a x dado que f C3[a, b]. Entonces g(x) cumple todas lashipotesis del teorema anterior por lo que (xn) converge cuadraticamente ax.

Teorema 10 Sea f una funcion de clase C2[a, b]. Si existe un punto x talque f(x) = 0, f (x) 6= 0 y f (x) 6= 0 entonces existe un numero > 0 talque si x0 y x1 estan dentro del intervalo [x , x + ] la sucesion generadapor el metodo de la secante

xn = xn1 (xn2 xn1)f(xn1)

f(xn2) f(xn1).

converge a x con orden de al menos1 +

52

1.618.

Prueba (Ejercicio) Sugerencias: Pruebe que

|en+1| C |en| |en1| , (1.10)

con C :=|f (x)||2f (x)|

. Por la definicion 1 se busca una solucion aproximada a

la ecuacion|en| = |en1| , (1.11)

con > 0 y 1. Pero considerando (1.10) como una ecuacion y susti-tuyendo en (1.11) se tiene que:

|en| = |en1|2

= C |en1|+1 . (1.12)

La ecuacion (1.12) es valida solamente para n suficientemente grandes si:

= C y 2 = + 1,

de donde =1 +

52

y = C1/.

xxx 1. Metodos iterativos para ecuaciones no lineales

6 Convergencia acelerada y el metodo deSteffensen

6.1 El metodo 42 de AitkenEl metodo 42 de Aitken tiene las siguientes hipotesis:

1. (xn) converge linealmente a x con constante asntotica tal que 0 < < 1.

2. Los signos de xn x, xn+1 x y xn+2 x son iguales.

3. Se asume que para n suficientemente grande:

xn+1 xxn x

xn+2 xxn+1 x

. (1.13)

La idea es encontrar una sucesion (xn) la cual converge mas rapidamentea x que la sucesion (xn). Note que de (1.13):

(xn+1 x)(xn+1 x) (xn x)(xn+2 x) x2n+1 2xxn+1 + x2 xn+2xn xxn+2 xxn + x2

2xxn+1 + xxn+2 + xxn x2n+1 + xn+2xn (2xn+1 + xn+2 + xn)x x2n+1 + xn+2xn

x x2n+1 + xn+2xn

(2xn+1 + xn+2 + xn)

x xn+2xn x2n+1

xn+2 2xn+1 + xn

x x2n + xn+2xn 2xnxn+1 x2n + 2xnxn+1 x2n+1

xn+2 2xn+1 + xn

x xn(xn + xn+2 2xn+1) (xn+1 xn)2

xn+2 2xn+1 + xn

x xn (xn+1 xn)2

xn+2 2xn+1 + xn

El metodo de 42 de Aitken se basa en el hecho de que la sucesion (xn)definida por:

xn+3 := xn (xn+1 xn)2

xn+2 2xn+1 + xn,

bajo ciertas condiciones, converge mas rapidamente a x que la sucesion(xn).

Notacion 1 Diferencia Progresiva

1. Metodos iterativos para ecuaciones no lineales xxxi

4(xn) := xn+1 xn para n 0.

4k(xn) = 4k1(4xn) para k 2.

Observacion 7 Notese que con esta notacion se tiene:

42(xn) = 4(4xn)= 4xn+1 4xn= xn+2 xn+1 (xn+1 xn)= xn+2 2xn+1 + xn.

Por lo que el metodo 42de Aitken se puede escribir como:

xn+3 := xn (4xn)2

42xn. (1.14)

Pero que quiere decir que una sucesion (xn) converge mas rapido a x quela sucesion (xn)?

Definicion 2 Sean (xn) y (xn) dos sucesiones que convergen a x, se diceque la sucesion (xn) converge mas rapido a x que la sucesion (xn) si:

limn

xn xxn x

= 0.

Teorema 11 Sea (xn) una sucesion que converge a x con orden lineal conconstante asintotica < 1, ademas se asume que en = xn x 6= 0 paratodo n. Entonces la sucesion (xn), definida en (1.14), converge a x masrapido que (xn).

Prueba Ejercicio.

6.2 El metodo de Steffensen

Por el Teorema 8 la sucesion de aproximaciones sucesivas (xn) convergelinealmente a x, cuando n con constante asintotica < 1, entoncestiene sentido aplicar el metodo 42 de Aitken a esta sucesion. Es as comouna combinacion entre el metodo de aproximaciones sucesivas y el metodo42 de Aitken producen un metodo conocido como el Metodo de Steffensen,el cual consiste en calcular la sucesion:

xn+1 := xn [g(xn) xn]2

g(g(xn)) 2g(xn) + xn. (1.15)

Algoritmicamente el Metodo de Steffensen para acelerar el metodo de puntofijo se puede expresar de la siguiente manera. Sea x0 la aproximacion inicialen el metodo de punto fijo, entonces se toma:

xxxii 1. Metodos iterativos para ecuaciones no lineales

x(0)0 = x0

x(0)1 = g

(x

(0)0

)x

(0)2 = g

(x

(0)1

)x

(1)0 = 42

(x

(0)0

)= x(0)0

[x

(0)1 x

(0)0

]2x

(0)2 2x

(0)1 + x

(0)0

x(1)1 = g

(x

(1)0

)x

(1)2 = g

(x

(1)1

)x

(2)0 = 42

(x

(1)0

)= x(1)0

[x

(1)1 x

(1)0

]2x

(1)2 2x

(1)1 + x

(1)0

...

En pseudocodigo el Metodo de Steffensen se puede expresar como sigue:

Algoritmo 5 [Metodo de Steffensen]Entrada: N,Tol, x0, gSalida: Aproximacion de x o mensaje de error

Paso 1. i 2Paso 2. Mientras i N, siga los pasos 36

Paso 3. x1 = g(x0)x2 = g(x1)

x = x0 (x1 x0)2

x2 2x1 + x0Paso 4. Si |x x0| < Tol

Salida (x)Parar

Paso 5. i i + 1Paso 6. x0 x

Paso 7. Salida ( Numero maximo de iteraciones excedido)Parar

Este algoritmo se puede programar iterativamente en Mathematica comosigue:

Steffensen[x0 ,Tol ,n ,G ]:=Module[{i=1,x0Tem=x0,x,x1,x2},

While[in,x1=N[G[x0Tem]];x2=N[G[x1]];

1. Metodos iterativos para ecuaciones no lineales xxxiii

x=N[x0Tem-(x1-x0Tem)^2/(x2-2*x1+x0Tem)];Print[En la iteracion , i,

el valor de x es ,N[x,15]];If[Abs[x-x0Tem]

xxxiv 1. Metodos iterativos para ecuaciones no lineales

mente entonces el orden de convergencia del metodo de Steffensen es almenos dos.

Prueba (Ejercicio) Suponga que g(x) es un numero suficiente de vecesderivable, luego pruebe que:

limn

|xn+1 x||xn x|2

=12

g(x)g(x)g(x) 1 := 6= 0.