método de steffensen
DESCRIPTION
Método de SteffensenTRANSCRIPT
UNIVERSIDAD DE SAN CARLOS FACULTAD DE INGENIERIA DEPARTAMENTO DE MATEMATICA MATEMATICA APLICADA 3
MSC. Ing. Renaldo Girón Alvarado
Método de Steffensen
Aceleración de la convergencia 2 Aitken ( Método de Steffensen)
Este Método es basado en una función xgx en la cual 10
/ xg NO ES NECESARO
CALCULARLO, entonces se puede mejorar su comportamiento respecto de la rapidez de
convergencia.
Sin usar para ello ninguna derivada, el método de Steffensen proporciona convergencia
cuadrática en la localización de un punto fijo de una función real. Este método puede ser
considerado como una simplificación del método de Newton, pero este método empieza con dos
aproximaciones por el método de punto fijo, entonces tenemos la siguiente expresión:
Supongamos que nnp es una sucesión linealmente convergente con un límite de valor p.
Supongamos primero que los signos de las aproximaciones son: ,ppn ppn 1 , ppn 2
son iguales y que "n" es suficientemente grande como para que:
pp
pp
pp
pp
n
n
n
n
1
21
Entonces:
pppppp nnn 2
2
1
,2 2
22
2
1
2
1 pppppppppp nnnnnn
Transponiendo al lado izquierdo los términos que contiene "p", tenemos:
2
1212 2 nnnnnn ppppppp ,
Despejando "p" que es la aproximación a la raíz tenemos:
12
212
2
nnn
nnn
ppp
pppp
Si sumamos y restamos 2
np y nn pp 12 en el numerador y agrupando términos tenemos:
12
21
21
212
2
22
nnn
nnnnnnnnn
ppp
pppppppppp
12
21
2112
2
22
nnn
nnnnnnnn
ppp
ppppppppp
12
21
21
12
12
2
2
2
2
nnn
nnnn
nnn
nnnn
ppp
pppp
ppp
ppppp
UNIVERSIDAD DE SAN CARLOS FACULTAD DE INGENIERIA DEPARTAMENTO DE MATEMATICA MATEMATICA APLICADA 3
MSC. Ing. Renaldo Girón Alvarado
12
21
21
2
2
nnn
nnnn
ppp
pppp
npp
12
21
2
nnn
nn
ppp
pp
npp
Reescribiendo la formula tenemos:
012
201
202 ppp
pp
n pp
; Donde:
0p Punto inicial del método
01 pgp
12 pgp
2np Aproximación a la raíz
20 nppError
Si nos damos cuenta este método necesita 2 aproximaciones iníciales por el método de Punto Fijo
y luego la aproximación a la raíz por medio de la formula modifica de Newton
Ejemplo:
1) Aplique el Método de Steffesen para encontrar la aproximación a la raíz de la función
xxxf 2 en el intervalo de 1,0 con un aproximación inicial de 5.00 p y una
310*1 tol
Solución:
Primero calculamos una función xg cualquiera, para la cual 10
/ pg no importa que no
cumpla. Entonces tenemos:
xxx xgxx 2220
1era. Iteración (n=1):
Como la tolerancia contiene 3 decimales (310*1
=0.001), trabajaremos el método agregando 2
decimales mas, esto se hace para ver el comportamiento del error con el fin que en algún
momento pf no llegue a ser cero directamente ya que eso es casi imposible que suceda, por lo
tanto todos los cálculos los haremos con 5 decimales, pero el método para el criterio de paro si se
toma en cuenta 310*1
para el error.
Para esta iteración necesitamos un punto de arranque, ese punto de arranque es el punto que
nos dieron en el enunciado del problema 5.00 p , por lo tanto tenemos que hacer 2
aproximaciones iníciales por punto fijo y luego la aproximación a la raíz por la fórmula del método
5.00 p
70711.025.0 5.0
01 gpgp 61255.0270711.0 70711.0
12 gpgp
UNIVERSIDAD DE SAN CARLOS FACULTAD DE INGENIERIA DEPARTAMENTO DE MATEMATICA MATEMATICA APLICADA 3
MSC. Ing. Renaldo Girón Alvarado
64219.05.070711.0261255.0
5.070711.05.0
23
2
21
012
2
0102
pp
ppp
ppppn
14219.064219.05.020 ErrorppError n
Este error No es menor que 310*1
, como no se cumple que tolpp n 20
310*114219.0 se
hace otra iteración. Haciendo una tabla de los cálculos que tenemos hasta el momento:
n 0p 1p 2p 2np Error
1 0.5 0.70711 0.61255 0.64219 0.14219
2da Iteración (n=2)
Para esta iteración necesitamos un punto de arranque, ese punto de arranque es el punto
64219.03 p de la iteración anterior, por lo tanto tenemos que volver hacer las dos
aproximaciones por punto fijo y luego la aproximación a la raíz por la formula mejorada de
newton:
64219.00 p
64074.02
64219.0
64219.0
1
01
p
gpgp
64138.02
64074.0
64074.0
2
12
p
gpgp
64119.064074.064074.0264138.0
064219064074.064219.0
24
2
22
012
2
0102
pp
ppp
ppppn
00100.06411964219.020 ErrorppError n
Este error No es menor que 310*1
, como no se cumple que tolpp n 20
310*100100.0 se
hace otra iteración. Haciendo una tabla de los cálculos que tenemos hasta el momento:
n 0p 1p 2p 2np Error
1 0.5 0.70711 0.61255 0.64219 0.14219
2 0.64219 0.64074 0.64138 0.64119 0.00100
Seguimos haciendo las iteraciones hasta que tolpp n 20, completando el método tenemos lo
siguiente:
n 0p 1p 2p 2np Error
1 0.5 0.70711 0.61255 0.64219 0.14219
2 0.64219 0.64074 0.64138 0.64119 0.00100
3 0.64119 0.64119 0.64119 0.64119 4.75*10-8
La aproximación a la raíz es de x=0.64119
***AHORA SI ESCOGEMOS LA OTRA FORMA DE ECONTRAR LA xg TENIENDO EL MISMO INTERVALO,
PUNTO DE ARRANQUE Y TOLERANCIA TENEMOS:
2ln
ln220
xxgxx xx
UNIVERSIDAD DE SAN CARLOS FACULTAD DE INGENIERIA DEPARTAMENTO DE MATEMATICA MATEMATICA APLICADA 3
MSC. Ing. Renaldo Girón Alvarado
Ahora haciendo todos pasos para obtener todas las iteraciones respectivas y plasmándolas en la
tabla tenemos:
n 0p 1p 2p 1np Error
1 0.5 1.00000 0.00000 0.66667 0.16667
2 0.66667 0.58496 0.77358 0.64197 0.02469
3 0.64197 0.63942 0.64517 0.64119 0.00079
PODEMOS VER QUE LA APROXIMACION A LA RAIZ ES x=0.64119 , ENTONCES PODEMOS VER QUE NO
IMPORTA LA xg QUE TOMEMOS QUE SIEMPRE VAMOS A ENCONTRAR LA APROXIMACION A LA
RAIZ
2) Use el método de Steffensen para aproximar la solución de la ecuación 0cos102 xx
dentro del intervalo 4,3 , con 30 p y una 410*1 tol .
Solución:
Primero calculamos una función xg cualquiera, para la cual 10
/ pg no importa que no
cumpla. Entonces tenemos:
xxgxxxx cos10cos10cos102
1era. Iteración (n=1):
Como la tolerancia contiene 4 decimales (410*1
=0.0001), trabajaremos el método agregando 2
decimales mas, esto se hace para ver el comportamiento del error con el fin que en algún
momento pf no llegue a ser cero directamente ya que eso es casi imposible que suceda, por lo
tanto todos los cálculos los haremos con 6 decimales, pero el método para el criterio de paro si se
toma en cuenta 410*1
para el error.
Para esta iteración necesitamos un punto de arranque, ese punto de arranque es el punto que
nos dieron en el enunciado del problema 30 p , por lo tanto tenemos que hacer 2
aproximaciones iníciales por punto fijo y luego la aproximación a la raíz por la fórmula del método
30 p
146415.33cos10
3
1
01
p
gpgp
162259.3146415.3cos10
146415.3
2
12
p
gpgp
164182.33146415.32162259.3
3146415.35.0
23
2
21
012
2
0102
pp
ppp
ppppn
164182.0164182.3320 ErrorppError n
Este error No es menor que 410*1
, como no se cumple que tolpp n 10
410*1164182.0 se
hace otra iteración. Haciendo una tabla de los cálculos que tenemos hasta el momento:
n 0p 1p 2p 2np Error
1 3 3.146415 3.162259 3.164182 0.164182
2da Iteración (n=2)
UNIVERSIDAD DE SAN CARLOS FACULTAD DE INGENIERIA DEPARTAMENTO DE MATEMATICA MATEMATICA APLICADA 3
MSC. Ing. Renaldo Girón Alvarado
Para esta iteración necesitamos un punto de arranque, ese punto de arranque es el punto
164182.33 p de la iteración anterior, por lo tanto tenemos que volver hacer las dos
aproximaciones por punto fijo y luego la aproximación a la raíz por la formula mejorada de
newton:
164182.30 p
161874.3164182.3cos10
164182.3
1
01
p
gpgp
161952.3161874.3cos10
161874.3
2
12
p
gpgp
161950.3164182.3161874.32161952.3
164182.3161874.3164182.3
24
2
22
012
2
0102
pp
ppp
ppppn
002232.0161950.3164182.320 ErrorppError n
Este error No es menor que 410*1
, como no se cumple que tolpp n 10
410*1002232.0 se
hace otra iteración. Haciendo una tabla de los cálculos que tenemos hasta el momento:
n 0p 1p 2p 2np Error
1 3 3.146415 3.162259 3.164182 0.164182
2 3.164182 3.161874 3.161952 3.161950 0.002232
Seguimos haciendo las iteraciones hasta que tolpp n 20, completando el método tenemos lo
siguiente:
n 0p 1p 2p 2np Error
1 3 3.146415 3.162259 3.164182 0.164182
2 3.164182 3.161874 3.161952 3.161950 0.002232
3 3.161950 3.161950 3.161950 3.161950 1.2936E-07
La aproximación a la raíz es de x=3.161950
****AHORA SI ESCOGEMOS OTRA FORMA DE ECONTRAR LA xg TENIENDO EL MISMO INTERVALO,
PUNTO DE ARRANQUE Y TOLERANCIA TENEMOS:
x
xxg
x
xxxxxxx
cos10cos10cos10*cos102
Ahora haciendo todos pasos para obtener todas las iteraciones respectivas y plasmándolas en la
tabla tenemos:
n 0p 1p 2p 1np Error
1 3 3.299975 2.992398 3.148111 0.148111
2 3.148111 3.176441 3.146266 3.161829 0.013719
3 3.161829 3.162079 3.161813 3.161950 0.000121
4 3.161950 3.161950 3.161950 3.161950 9.3633E-09
PODEMOS VER QUE LA APROXIMACION A LA RAIZ ES x=3.161950 , ENTONCES PODEMOS VER QUE NO
IMPORTA LA xg QUE TOMEMOS QUE SIEMPRE VAMOS A ENCONTRAR LA APROXIMACION A LA
RAIZ
UNIVERSIDAD DE SAN CARLOS FACULTAD DE INGENIERIA DEPARTAMENTO DE MATEMATICA MATEMATICA APLICADA 3
MSC. Ing. Renaldo Girón Alvarado
****AHORA SI ESCOGEMOS OTRA FORMA DE ECONTRAR LA xg TENIENDO EL MISMO INTERVALO,
PUNTO DE ARRANQUE Y TOLERANCIA TENEMOS:
10cos
10cos
10cos0cos10
21
21
22 x
xgx
xx
xxx
CON ESTA FUNCION xg NO SE PUEDE ECONTRAR LA APROXIMACION A LA RAIZ PORQUE ESTA
FUNCION AL INGRESARLE LOS VALORES DE 0p , 1p Y 2p DE LA SEGUNDA ITERACION SE SALE DEL
DOMINIO DE LA FUNCION xg , POR LO CONSIGUIENTE LOS RESULTADOS SON VALORES
COMPLEJOS.
METODO DE MULLER
Un polinomio de grado “n” tiene la forma: 01
1
1 ..... aaxaxaxP n
n
n
n
, si P(x) es un polinomio
de grado “n” mayor o igual que 1 con coeficientes reales o complejos, entonces P(X)=0 tiene al
menos una raíz (posiblemente compleja). Si P(X) es un polinomio de grado “n” mayor o igual que 1
con coeficientes reales o complejos, entonces existen constantes únicas kxxxx .....,, 321
posiblemente complejas, y enteros positivos kmmmm ....., 321 tales que
k
i i nm1
y
km
k
mmm
n xxxxxxxxaxP .......321
321 , lo anterior establece que el conjunto de
ceros de un polinomio es único y que si cada cero Xi se cuenta el mismo número de veces que su
multiplicidad im , entonces un polinomio de grado “n” tendrá exactamente “n” ceros. Si queremos
localizar ceros aproximados de un polinomio P(X) con el procedimiento de Newton, necesitamos
evaluar P(X) en valores específicos. Puesto que P(X) y P´(X) son polinomio, la eficiencia
computacional requiere evaluar estas funciones en la forma anidada.
El problema de aplicar el Método de Newton a los polinomios, es la posibilidad de que el
polinomio contenga raíces complejas, cuando todos los coeficientes son números reales. Si la
aproximación inicial mediante el método de Newton es un numero real, también lo serán las
aproximaciones subsecuentes. Una manera de superar esta dificultad consiste en comenzar con
una aproximación inicial compleja y efectuar todos los cálculos por medio de la aritmética
compleja.
Si biaz es un cero complejo de multiplicidad “m” del polinomio P(X), entonces
biaz ˆ también será un cero de multiplicad “m” del polinomio P(X) y mbaaxx 222 2 será
factor de P(X). El método de Muller es una extensión del método de la Secante. Este ultimo
comienza con dos aproximaciones iniciales 10 xyx y determina la siguiente aproximación 2x
como la intersección del eje “x” con la línea que cruza 1100 ,, xfxyxfx .
El método de Muller utiliza tres aproximaciones iniciales 210 , xyxx (siendo estos valores
aproximaciones a una de las raíces) y determina la siguiente aproximación 3x al considerar la
intersección del eje “x” con la parábola que atraviese 221100 ,,,, xfxyxfxxfx . La
UNIVERSIDAD DE SAN CARLOS FACULTAD DE INGENIERIA DEPARTAMENTO DE MATEMATICA MATEMATICA APLICADA 3
MSC. Ing. Renaldo Girón Alvarado
deducción del Método de Muller comienza considerando el polinomio cuadrático
cxxbxxaxP 2
2
2 que pasa por los puntos 221100 ,,,, xfxyxfxxfx .
Podemos determinar las constantes a, b y c a partir de las condiciones:
102120
21202021
102120
20
2
2121
2
20
2
2
2
21
2
211
20
2
200
00
xxxxxx
xfxfxxxfxfxxa
yxxxxxx
xfxfxxxfxfxxb
xfcentoncescbaxP
ycxxbxxaxP
cxxbxxaxP
)()()()( 20
2
2020 xxbxxaxfxf
)()()()( 21
2
2121 xxbxxaxfxf
Resolviendo por sustitución para “a” y “b” tenemos
102120
21202021
102120
20
2
2121
2
20
2
2
2
21
2
211
20
2
200
00
xxxxxx
xfxfxxxfxfxxa
yxxxxxx
xfxfxxxfxfxxb
xfcentoncescbaxP
ycxxbxxaxP
cxxbxxaxP
Definiendo de esta forma:
010 xxh , 121 xxh
01
010
)()(
xx
xfxf
y
12
121
)()(
xx
xfxf
Sustituyendo en el sistema:
1100
2
1010 )()( hhahhbhh
11
2
11 hahbh
Teniendo como resultado los coeficientes:
01
01
hha
11 ahb )( 2xfc
Si queremos determinar 3x , un cero de P, aplicamos la formula cuadrática P(X)=0. Sin embargo,
debido a los problemas del error de redondeo ocasionado por la sustracción de números casi
iguales, utilizaremos la formula siguiente (esta fórmula esta racionalizada de la formula
cuadrática):
UNIVERSIDAD DE SAN CARLOS FACULTAD DE INGENIERIA DEPARTAMENTO DE MATEMATICA MATEMATICA APLICADA 3
MSC. Ing. Renaldo Girón Alvarado
acbb
cxx
4
2223
Esta fórmula ofrece dos posibilidades de 3x , según el signo que produce al termino radical. En el
Método de Muller, el signo se elige de modo que corresponda al signo de “b”. De esa forma el
denominador será el de mayor magnitud y hará que 3x sea seleccionada como raíz de “P” que
esta mas cercana a 2x , Por tanto:
acbb
cxx
4
2223
Una vez que determinamos 3x , reinicializamos el procedimiento usando 321 , xyxx en vez de
210 , xyxx para obtener la siguiente aproximación 4x en método prosigue hasta que se logra una
conclusión satisfactoria. En cada paso el método contiene el radical acb 42 , por tanto, puede
aproximar las raíces complejas cuando 042 acb . Con el algoritmo siguiente se establece este
procedimiento:
Ejemplo 1:
Encontrar la raíz real positiva de la función 4016122 234 xxxxxf por el método
de Muller con una tolerancia de 0.00001.
*El método de Muller para poder iniciar necesita 3 puntos cercanos a la raíz, entonces graficamos
la función y veremos qué puntos cercanos a la raíz tomamos para iniciar el método
dxfbD
dhrb
hh
rrd
h
xfxfr
h
xfxfr
xxh
xxh
PASO
**4
*
2
1
2
2
22
21
12
122
1
011
122
011
tolherror
hxraizxp
E
xfh
DbEnosi
DbEentonces
DbDbsi
PASO
23
2*2
2
raizxpx
xx
xx
PASO
32
21
10
3
UNIVERSIDAD DE SAN CARLOS FACULTAD DE INGENIERIA DEPARTAMENTO DE MATEMATICA MATEMATICA APLICADA 3
MSC. Ing. Renaldo Girón Alvarado
Graficando vemos que la raíz positiva esta cerca de x=4, tomando 3 puntos cercanos a esta corte
tenemos: 5,5.4,4 210 xxx . Ahora iniciando el método tenemos:
1era iteracion (n=1)
PASO 1:
PASO 2:
Si
Entonces
Si no
UNIVERSIDAD DE SAN CARLOS FACULTAD DE INGENIERIA DEPARTAMENTO DE MATEMATICA MATEMATICA APLICADA 3
MSC. Ing. Renaldo Girón Alvarado
PASO 3
, y
x0 = 4.5 x1 = 5 y x2 = 4.384397
2da iteración (n=2)
Volvemos a hacer los mismos pasos anteriores tomando como valores iníciales x0 = 4.5 , x1 = 5 , x2
= 4.384397. Seguimos iterando hasta que cumpla con la tolerancia, para este ejemplo solo se
necesitan 4 iteraciones para encontrar la raíz. Las columnas que necesitamos para el método de
Muller son las siguientes:
n Xo X1 X2 h1 h2 r1 r2 d b D E h P error
La Siguiente tabla contiene todas las iteraciones necesarias para encontrar un valor de "x" con una
tolerancia de 1*10-5
n Xo X1 X2 h1 h2 r1 r2
1 4 4.5000 5.0000 0.5000 0.5000 113.6250 196.3750
2 4.5 5.0000 4.3844 0.5000 -0.6156 196.3750 186.1030
3 5 4.3844 4.3811 -0.6156 -0.0033 186.1030 132.3058
4 4.3844 4.3811 4.381113 -0.0033 0.0000 132.3058 132.0531
d b D E h P error
82.7500 237.7500 135.8678 373.6178 -0.6156 4.3843977 0.6156023
88.8559 131.4031 130.8141 262.2173 -0.0033 4.3810834 0.0033143
86.9217 132.0177 132.0229 264.0406 0.0000 4.3811134 0.0000301
76.9288 132.0554 132.0554 264.1109 0.0000 4.3811134 0.0000000
El valor de "x" es aprox. = 4.381113