Download - Apuntes_Metodos_Numericos
7/23/2019 Apuntes_Metodos_Numericos
http://slidepdf.com/reader/full/apuntesmetodosnumericos 1/12
Universidad Católica del Norte
Facultad de CienciasDepartamento de Matemáticas
Análisis NuméricoProfesor Dr. Juan C. Egaña
0.1 Análisis de Error para los Métodos Iterativos
De…nición 1 Supongamos que f png1n=0 es una sucesión que converge a p,con pn 6= p para todo n. Si las constantes positivas y existen tales que
limn!1
j pn+1 pj
j pn pj = ;
entonces f png1n=0 converge a p con orden y una constante de error
asintótico .
Observación 1 Si = 1, la sucesión se dice linealmente convergente.Si = 2, la sucesión se dice cuadráticamente convergente.
Observación 2 Entre más alto es el valor de , más rápida es la conver-gencia de la sucesión.
Ejemplo 1 Supongamos que f png1n=0 convergente linealmente a 0, con
limn!1
j pn+1j
j pnj = 0:5
y que fe png1n=0 converge cuadráticamente a 0 con la misma constante de error asintótico,
limn!1
je pn+1j
j
e pnj2
= 0:5:
Por razones de simplicidad, supongamos que
j pn+1j
j pnj 0:5 y
je pn+1j
je pnj2 0:5:
En el esquema linealmente convergente, esta suposición signi…ca que
1
7/23/2019 Apuntes_Metodos_Numericos
http://slidepdf.com/reader/full/apuntesmetodosnumericos 2/12
j pn 0j = j pnj 0:5 j pn1j (0:5)2 j pn2j (0:5)n j p0j ;
mientras que el procedimiento cuadráticamente convergente tiene
je pn 0j = je pnj 0:5 je pn1j2 (0:5)
(0:5) je pn2j22
= (0:5)3 je pn2j4
(0:5)3
(0:5) je pn3j24
= (0:5)7 je pn3j8
(0:5)2n1 j
e p0j2
n
:
La siguiente Tabla ilustra la rapidez relativa de convergencia a cero de las sucesiones cuando j p0j = je p0j = 1.
n
Sucesión lineal convergente f png1n=0
(0:5)n
Sucesión cuadrática convergente fe png1n=0
(0:5)2n1
1 5:0000 101 5:0000 101
2 2:5000 101 1:2500 101
3 1:2500 101 7:8125 103
4 6:2500 102
3:0518 105
5 3:1250 102 4:6566 1010
6 1:5625 102 1:0842 1019
7 7:8125 103 5:8775 1039
Teorema 1 Sea g 2 C [a; b] y supongamos que g(x) 2 [a; b] para todo x 2[a; b]. Supongamos, además, que g0 es continua en (a; b) con
jg0(x)j k < 1; 8x 2 (a; b) :
Si g0( p) 6= 0, entonces para cualquier p0 en [a; b], la sucesión
pn = g( pn1); n 1;
converge linealmente al único punto …jo p en [a; b].
2
7/23/2019 Apuntes_Metodos_Numericos
http://slidepdf.com/reader/full/apuntesmetodosnumericos 3/12
Demostración. Del teorema de existencia y unicidad del punto …jo
tenemos que existe k tal que
jg0(x)j k < 1; 8x 2 (a; b)
y g ( pn1) = pn converge a p. Por otra parte, del teorema del valor medio
pn+1 p = g ( pn) g ( p) = g 0 ( n) ( pn p) ;
donde n 2 ( pn; p). Pero pn ! p, entonces n ! p (ya que n siempre estáentre pn y p). Luego, como g0 es continua en [a; b], tenemos
limn!1
g0 ( n) = g 0 ( p) :
Así,
limn!1
j pn+1 pj
j pn pj =
limn!1
pn+1 p
pn p
=
limn!1
g0 ( n)
= jg0 ( p)j :
Por tanto, la iteración del punto …jo converge linealmente si g0 ( p) 6= 0.
Observación 3 El teorema anterior induce a pensar que la iteración del punto …jo podría tener una convergencia de orden superior cuando g 0 ( p) = 0.
Teorema 2 Sea p una solución de la ecuación x = g(x). Supongamos que g0 ( p) = 0 y g00 es una función continua y estrictamente acotada por M en un intervalo I conteniendo a p. Entonces existe un > 0 tal que, para p0 2 [ p ; p + ], cuando n 1, converge al menos cuadráticamente a p.Además, para valores de n su…cientemente grande
j pn+1 pj < M
2
j pn pj2 :
Observación 4 El teorema anterior dice que el procedimiento
pn = g ( pn1) ; n 1 (1)
3
7/23/2019 Apuntes_Metodos_Numericos
http://slidepdf.com/reader/full/apuntesmetodosnumericos 4/12
es cuadráticamente convergente siempre que g0 ( p) = 0; donde p es el punto
…jo. A partir de este resultado es posible deducir que el método de New-ton (para encontrar las raíces de la ecuación f (x) = 0) es cuadráticamente convergente. En efecto, consideremos el esquema (1) con
g (x) = x (x)f (x);
donde es una función arbitraria. Entonces
1. Si p es un cero de f , g ( p) = p ( p)f ( p) = p, es decir, p es un punto …jo de g.
2. El procedimiento iterativo (1) es cuadráticamente convergente si g 0 ( p) =
0.
3. g0 (x) = 1 0(x)f (x) (x)f 0(x). Entonces g0 ( p) = 1 0( p)f ( p) ( p)f 0( p) = 1 ( p)f 0( p), pues f ( p) = 0.
4. Del paso 3., tenemos que
g0 ( p) = 0
si y solamente si
( p) = 1f 0( p)
; f 0( p) 6= 0.
Entonces
pn = g ( pn1) = pn1 1
f 0( pn1):f ( pn1) (2)
es cuadráticamente convergente, siempre que f 0( p) 6= 0, donde p es solución de f (x) = 0.
Observación 5 El análisis hecho en la observación (14) establece clara-mente que el método de Newton converge cuadráticamente a p siempre que f 0( p) 6= 0. Entonces una pregunta natural es: ¿ Bajo qué condiciones se cumplen las condicones f ( p) = 0 y f 0( p) 6= 0 ?
4
7/23/2019 Apuntes_Metodos_Numericos
http://slidepdf.com/reader/full/apuntesmetodosnumericos 5/12
De…nición 2 Una solución p de f (x) = 0 es un cero de multiplicidad m de
f si
f (x) = (x p)mq (x); x 6= p;
donde limx! p
q (x) 6= 0.
Teorema 3 f 2 C 1 [a; b] (el conjunto de todas las funciones cuya primera derivada existe y es continua) tiene un cero de multiplicidad uno (o un cerosimple) en p 2 (a; b)
si y solamente si
f ( p) = 0 y f 0( p) 6= 0:
En general, f 2 C m [a; b] tiene un cero de multiplicidad m en p 2 (a; b)
si y solamente si
0 = f ( p) = f 0( p) = f 00
( p) = = f (m1)( p) y f (m)( p) 6= 0:
Observación 6 De acuerdo al teorema (8), el método de Newton converge cuadráticamente a p en un intervalo cerrado que lo contenga, para cualquier chute inicial, siempre que p sea un cero simple de f .
Ejemplo 2 Sea f (x) = ex x 1. Muestre que f tiene un cero de multipli-cidad dos en p = 0. Además, veri…que que el método de Newton no converge cuadráticamente.
Solución 1 f (0) = e0 0 1 y f 0(x) = ex 1; f 00(x) = ex entonces f 0(0) =e0 1 = 0 y f 00(0) = e0 = 1 6= 0. Por otra parte,
f (x) = (x 0)2 (ex x 1)
x2 | {z } q (x)
Por la regla de L’Hôpital tenemos
5
7/23/2019 Apuntes_Metodos_Numericos
http://slidepdf.com/reader/full/apuntesmetodosnumericos 6/12
limx!0 q (x) = limx!0
ex x 1
x2
= limx!0
ex 1
2x
= limx!0
ex
2 6= 0:
En la siguiente Tabla se incluyen los términos que se generaron con el método de Newton aplicado a f con p0 = 1. La sucesión converge claramente a cero, pero no es cuadráticamente convergente.
n pn n pn
0 1:0 9 2:7750 103
1 0:58198 10 1:3881 103
2 0:31906 11 6:9411 104
3 0:16800 12 3:4703 104
4 0:08635 13 1:7416 104
5 0:04380 14 8:8041 105
6 0:02206 15 4:2610 105
7 0:01107 16 1:9142 106
8 0:005545
Ejercicio 1 1. Suponga que f es una función que tiene una raíz de mul-tiplicidad m 1 en p. Se de…ne la función
(x) = f (x)
f 0(x)
Demuestre que tiene una raíz de multiplicidad uno en p. Aplique el método de Newton a para deducir un método iterativo de Newton
modi…cado dado por
pn = pn1 f ( pn1)f 0( pn1)
f 0( pn1)2
f ( pn1))
f 00( pn1)) (3)
6
7/23/2019 Apuntes_Metodos_Numericos
http://slidepdf.com/reader/full/apuntesmetodosnumericos 7/12
para aproximar el cero de multiplicidad m 1 de f . (En otras pal-
abras el procedimiento (3) es un método para el problema de las raíces múltiples de una función f ).
2. Considere las funciones f (x) = ex x 1, con p = 0 de multiplici-dad dos y g(x) = x3 + 4x2 10, con p = 1:36523001 de multiplicidad uno. Aplique el método de Newton modi…cado (3) a las funciones f y g. Compare los resultados y realice el mayor número de conclusiones acerca de la convergencia de ambos métodos (Newton y Newton modi-
…cado).
0.2 Convergencia Acelerada
Un procedimiento llamado Método de Aitken 2 puede ser usado para acel-erar la convergencia de una sucesión de convergencia lineal.
Supongamos que f png es una sucesión linealmente convergente a p conun error asintótico menor que 1, es decir,
limn!1
j pn+1 pj
j pn pj = < 1; = 1:
Supongamos que pn p, pn+1 p, pn+2 p tienen el mismo signo. Paran su…cientemente grande, se tiene
pn+1 p pn p
pn+2 p pn+1 p
:
Entonces
( pn+1 p)2 ( pn+2 p) ( pn p) ;
por tanto
7
7/23/2019 Apuntes_Metodos_Numericos
http://slidepdf.com/reader/full/apuntesmetodosnumericos 8/12
p2n+1 2 pn+1 p + p2 pn+2 pn pn+2 p pn p + p2
=) pn+2 p + pn p 2 pn+1 p pn+2 pn p2n+1
=) ( pn+2 + pn 2 pn+1) p pn+2 pn p2n+1
=) p pn+2 pn p2n+1 pn+2 + pn 2 pn+1
= p2n + pn+2 pn 2 pn+1 pn + 2 pn+1 pn p2n p2n+1
pn+2 + pn 2 pn+1
= ( p2n + pn+2 pn 2 pn+1 pn)
p2n 2 pn+1 pn + p2n+1
pn+2 + pn 2 pn+1
= pn ( pn+1 pn)2
pn+2 + pn 2 pn+1
Por lo tanto
p pn ( pn+1 pn)2
pn+2 + pn 2 pn+1
El método de Aitken 2 está basado en el supuesto que la sucesión f b png1n=1de…nida por:
b pn = pn ( pn+1 pn)2
pn+2 + pn 2 pn+1(4)
converge con mayor rapidez a p que la sucesión original f png1n=1.
Teorema 4 Sea f png1n=1 una sucesión que converge linealmente a p con una constante asintótica menor que uno y pn p 6= 0; 8n 0. Entonces la
sucesión f b png1
n=1 converge a p con mayor rapidez que f png1
n=1 en el sentidode
limn!1
b pn p
pn p = 0:
8
7/23/2019 Apuntes_Metodos_Numericos
http://slidepdf.com/reader/full/apuntesmetodosnumericos 9/12
De…nición 3 La sucesión f png1n=1, donde pn = cos
1
n, converge lineal-
mente a p = 1, en la siguiente Tabla se incluyen los primeros términos de las sucesiones f png1n=1 y f b png1n=1. Sin duda parece que f b png1n=1 converge más rápidamente a p = 1 que f png1n=1.
n pn b pn1 0:54030 0:961782 0:87758 0:982133 0:94496 0:989794 0:96891 0:99342
5 0:98007 0:995416 0:986147 0:98981
De…nición 4 La sucesión f png1n=1 de…nida por
pn = pn+1 pn; n 0:
es llamada diferencia progresiva . Recursivamente,
k pn =
k1 pn
; k 2:
Por ejemplo,2 pn = ( pn)
== ( pn+1 pn)
= pn+2 pn+1 pn+1 + pn
= pn+2 2 pn+1 + pn:
y la fórmula b pn de la ecuación (4) puede escribirse así
b pn = pn ( p
n)2
2 pn; n 0: (5)
Observación 7 Si pn ! p, entonces b pn, de…nida por el método de Aitken 2, converge más rápidamente a p que pn
9
7/23/2019 Apuntes_Metodos_Numericos
http://slidepdf.com/reader/full/apuntesmetodosnumericos 10/12
b pn = pn ( p
n)2
2 pn; n 0:
Esta idea puede usarse para acelerar la convergencia del método del punto …jo, es decir, para tener convergencia cuadrática en vez de lineal.
Podemos resumir el procedimiento para acelerar la convergencia de la iteración del punto …jo de la siguiente forma:
Paso 1. Comenzar con el chute inicial p0.Paso 2. Sea p
(0)0 = p0
p(0)1 = g
p(0)0
p(0)2 = g p
(0)1
p(1)0 = b p0 = p
(0)0
p
(0)02
2 p(0)0
= p(0)0
p(0)1 p
(0)02
p(0)2 p
(0)0 2 p
(0)1
Nota : p(1)1 = b p0 converge a p más rápidamente que p
(0)2
Paso 3 . Si p(1)0 p
(0)0
",
p(1)1 = g
p(1)0
p(1)2 = g
p(1)1
p(2)
0 = b p0 = p(1)
0 p
(1)0
2
2 p(1)0
= p(1)
0 p(1)1 p
(1)0
2
p(1)2 p
(1)0 2 p
(1)1
Paso 4. Repetir los pasos 2 y 3 hasta que p(k)0 p(k1)0
< ":
Algoritmo 1 Método de Ste¤ensen
Para encontrar una solución a p = g( p) dada una aproximación inicial p0 :
ENTRADA: aproximación inicial p0; tolerancia T OL; número máximode interaciones N 0.
SALIDA: solución aproximada p o mensaje de falla.Paso 1. Tome i = 1;Paso 2 . Mientras i N 0 haga los pasos 3-6.
Paso 3 . Tome p1 = g ( p0) ; (Calcule p(i1)1 ).
p2 = g ( p1) ; (Calcule p(i1)2 ).
10
7/23/2019 Apuntes_Metodos_Numericos
http://slidepdf.com/reader/full/apuntesmetodosnumericos 11/12
p = p0 ( p1 p0)2
( p2 + p0 2 p1)
: (Calcule p(i)0 ).
Paso 4. Si j p p0j < TOL entonces SALIDA ( p); (Procedimiento terminado satis
factoriamente).PARAR.
Paso 5 . Tome i = i + 1:
Paso 6 . Tome p0 = p: (Rede…na p0).Paso 7 . SALIDA (’El método falló después de N 0 iteraciones, N 0 =’,
N 0); (Procedimiento terminado sin éxito).PARAR.
Ejemplo 3 Para resolver x3
+4x2
10 = 0, usando el método de Ste¤ensen,hacemos
x3 + 4x2 = 10
x2(x + 4) = 10
x2 = 10
x + 4
x = r 10
x + 4
:
Entonces de…nimos g(x) =
r 10
x + 4. El procedimiento de Ste¤ensen con
p0 = 1:5 da los valores de la siguiente Tabla. La exactitud de la iteración p(2)0 = 1:365230013 es de nueve cifras decimales. En este ejemplo, con el
método de Ste¤ensen se obtuvo casi la misma rapidez de convergencia que con el método de Newton.
k p(k)0 p
(k)1 p
(k)2
0 1:5 1:348399725 1:3673763721 1:365265224 1:365225534 1:3652305832 1:365230013
Ejercicio 2 Usar el método de Newton para resolver x3 + 4x2 10 = 0 y comparar los resultados obtenidos con el método de Ste¤ensen.
11
7/23/2019 Apuntes_Metodos_Numericos
http://slidepdf.com/reader/full/apuntesmetodosnumericos 12/12
Teorema 5 Supongamos que g(x) = x tiene solución p con g0( p) 6= 1. Si
existe un > 0 tal que g 2 C 3
[ p ; p + ], entonces el método de Ste¤ensen converge cuadráticamente para cualquier p0 2 [ p ; p + ].
12