catedra metodos numericos 2013 unsch 06
TRANSCRIPT
![Page 1: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/1.jpg)
METODOS NUMERICOS
Ingeniería Civil
ING.�CRISTIAN�CASTRO�P.
Facultad de Ingeniería de Minas, Geología y Civil
Departamento académico de ingeniería de minas y civil
CATEDRA 06
![Page 2: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/2.jpg)
Sistema de Ecuaciones Algebraicas No Lineales
ING.�CRISTIAN�CASTRO�P.
Capitulo VI
![Page 3: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/3.jpg)
Agenda• Planteamiento del problema• Método de Punto Fijo• Método de Newton• Variantes del método de Newton
• Evaluación diferida del jacobiano• Aproximación por diferencias finitas• Newton unidimensional
• Métodos cuasi-Newton (Broyden)
![Page 4: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/4.jpg)
Introduccion• Se pretende que al final de la exposición el estudiante pueda
reconocer los sistemas de ecuaciones no lineales y puedaresolverlos por medio de adaptaciones a los métodos Newton-Raphson e Iteración de Punto Fijo
0).,..........,(...
0).,..........,(0).,..........,(
21
212
211
nn
n
n
xxxf
xxxfxxxf
• La solución de este sistemaconsta de valores xi quesimultáneamente hacen quetodas las ecuaciones seaniguales a cero
![Page 5: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/5.jpg)
SISTEMAS DE ECUACIONES NO LINEALES
f(x, y)=0
g(x, y)=0
x
y
x*
y*
![Page 6: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/6.jpg)
SISTEMA DE ECUACIONES NO LINEALES
-2
0
2
4
6
8
10
1 1.5 2 2.5 3 3.5 4 4.5 5
2x xy 10
2y 3xy 57 (2, 3)
![Page 7: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/7.jpg)
MÉTODO DE PUNTO FIJO ENSISTEMAS DE ECUACIONES NO LINEALES
1. Considera la intersección de dos funciones no lineales f(x, y)=0 y g(x, y)=0.
2. La intersección de las curvas f(x, y)=0 y g(x, y)=0 nos da la raiz (xr, yr).
3. El método consiste en obtener las funciones que tengan las mismas raices (xr, yr):
x-F(x, y) = 0y-G(x, y) = 0
4. Considerar un valor inicial (x0, y0), como aproximación a la raíz, evaluar: x1=F(x0, y0) y1=G(x0, y0)
5. El proceso se repite n veces hasta tener valores muy cercanos a las raíces.
![Page 8: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/8.jpg)
MÉTODO DEL PUNTO FIJO ENSISTEMAS DE ECUACIONES NO LINEALES
iteración xi yi erri
1 1.5 3.5 ---2 2.0000 3.4480 0.5027
3 1.8355 2.9875 0.4890
4 2.0734 3.1319 0.2782
5 1.9211 2.9428 0.2427
6 2.0559 3.0626 0.1803
7 1.9537 2.9572 0.1468
8 2.0363 3.0365 0.1145
9 1.9713 2.9721 0.0915
2x xy 10 2y 3xy 57
x = 2 y = 3
xn=10/(x+y)yn=((57-y)/(3x))^(1/2)err=sqrt((xn-x)^2+(yn-y)^2)
![Page 9: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/9.jpg)
MÉTODO DEL PUNTO FIJO ENSISTEMAS DE ECUACIONES NO LINEALES
iteración xi yi erri
1 1.5 3.5 ---2 2.0000 2.9861 0.7170
3 2.0056 2.9962 0.0116
4 1.9993 3.0006 0.0077
5 2.0000 3.0000 0.0010
2x xy 10 2y 3xy 57
x = 2 y = 3
Variante Seidelxn=10/(x+y)yn=((57-y)/(3xn))^(1/2)err=sqrt((xn-x)^2+(yn-y)^2)
Converge mas rápido!!!
![Page 10: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/10.jpg)
MÉTODO DEL PUNTO FIJO ENSISTEMAS DE ECUACIONES NO LINEALES
Sin embargo, con el método del punto fijo, la convergencia dependede la manera en que se formulen las ecuaciones de recurrencia yde haber elegido valores iniciales lo bastante cercanos a la soluciónEn las dos formulaciones siguientes el método diverge.
iteración xi yi
1 1.5 3.5
2 1.45578231 5.166666667
3 0.64724246 5.413376566
iteración xi yi
1 1.5 3.5
2 2.21428571 -24.375
3 -0.20910518 429.713648
x = (57 - y)/3y2 y = (10 - x2)/x
x = (10 - x2)/y y = 57 - 3xy2
![Page 11: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/11.jpg)
MÉTODO DE NEWTON RAPHSON EN SISTEMAS DE ECUACIONES NO LINEALES
u(x, y)
v(x, y)
x
yNo se puede mostrar la imagen en este momento.
x1
y1
![Page 12: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/12.jpg)
MÉTODO DE NEWTON RAPHSON EN SISTEMAS DE ECUACIONES NO LINEALES
• Este procedimiento corresponde, analíticamente, a extenderel uso de la derivada, ahora para calcular la intersecciónentre dos funciones no lineales.
• Al igual que para una sola ecuación, el cálculo se basa enla expansión de la serie de Taylor de primer orden, ahora demúltiples variables, para considerar la contribución de másde una variable independiente en la determinación de la raíz.
• Para dos variables, la serie de Taylor de primer orden seescribe, para cada ecuación no lineal:
i ii 1 i i 1 i i 1 i
i ii 1 i i 1 i i 1 i
u uu u (x x ) (y y )x yv vv v (x x ) (y y )x y
![Page 13: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/13.jpg)
MÉTODO DE NEWTON RAPHSON EN SISTEMAS DE ECUACIONES NO LINEALES
• Pero ui+1 = vi+1 = 0 :
• Que reescribiendo en el orden conveniente:
i i i ii 1 i 1 i i i
i i i ii 1 i 1 i i i
u u u ux y u x yx y x yv v v vx y v x yx y x y
i i i ii i 1 i i 1 i
i i i ii i 1 i i 1 i
u u u uu x x y y 0x x y yv v v vv x x y y 0x x y y
![Page 14: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/14.jpg)
MÉTODO DE NEWTON RAPHSON EN SISTEMAS DE ECUACIONES NO LINEALES
• Y cuya solución es:
• Donde J es el determinante jacobiano del sistema es:
i i
i i
u vx xJu vy y
i ii i
i 1 i
v uu vy yx x
J
i ii i
i 1 i
u vv ux xy y
J
![Page 15: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/15.jpg)
MÉTODO DE NEWTON RAPHSON EN SISTEMAS DE ECUACIONES NO LINEALES
iteración xi yi ui vi ux uy vx vy Jacobiano
1 1.5 3.5 -2.5 1.625 6.5 1.5 36.75 32.5 156.125
2 2.03602882 2.8438751 -0.064374959 -4.756208497 6.915932746 2.036028823 24.26287675 35.74127004 197.7843034
3 1.99870061 3.002288563 -0.004519896 0.04957115 6.999689781 1.998700609 27.04120985 37.00405588 204.9696292
4 1.99999998 2.999999413 -1.28609E-06 -2.21399E-05 6.999999381 1.999999984 26.99998944 36.99999267 204.9999473
5 2 3 0 2.23821E-12 7 2 27 37 205
x2 + xy - 10 = 0 y + 3xy2 - 57 = 0
x = 2
y = 3
![Page 16: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/16.jpg)
MÉTODO DE NEWTON RAPHSON EN SISTEMAS DE ECUACIONES NO LINEALES
Sistema de ecuaciones lineales por el método de Newton Raphson
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
1 2 3 4 5 6
convergencia
itera
cion
es
x
y
2x xy 10 2y 3xy 57
![Page 17: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/17.jpg)
Teoría de sistemas de Ecuaciones No lineales
• La forma general de un sistema de ecuaciones no lineales es:f1(x1, x2 x3, …, xn) = 0f2(x1, x2 x3, …, xn) = 0 f3(x1, x2 x3, …, xn) = 0
....................................fn(x1, x2 x3, …, xn) = 0
Definiendo una función FF(x1, x2 x3, …, xn) = [f1(x1, x2 x3, …, xn),f2(x1, x2 x3, …, xn),
f3(x1, x2 x3, …, xn) , fn(x1, x2 x3, …, xn)]
Usando una notacion vectorial para representar las variables X1,X2,…,Xn ). El sistema puede representarse por F(x)=0La solución a este sistema es el vector X=[x1, x2 x3, …, xn] que hace que simultaneamente todas las ecuaciones sean igual a 0.
![Page 18: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/18.jpg)
Teoría de sistemas de Ecuaciones No lineales
Métodos de Solución :• Método de Iteración de Punto Fijo para sistemas de
ecuaciones no lineales (Método de punto fijo multivariable).
• Método de Newton para sistemas de ecuaciones no lineales.
![Page 19: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/19.jpg)
Método de Iteración de Punto fijo para sistemas de Ecuaciones no Lineales
Anteriormente se desarrollo el método de iteración depunto fijo para resolver la ecuación f(x)=0 transformando esta ecuación en una ecuación de la formax= g(x),usando el criterio de convergencia|g’(x)|<1 en el intervalo [x1,x2]donde g(x) pertenece [x1,x2]para x que pertenece a [x1,x2]
![Page 20: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/20.jpg)
Método de Iteración de Punto fijo para sistemas de Ecuaciones no Lineales Para el caso de un conjunto de ecuaciones No linealesutilizaremos un procedimiento similar extendiéndolo atodas las ecuaciones, usando un criterio de convergencia:
Una condición suficiente aunque no necesaria, para asegurar la convergencia es que
Para todos los puntos (x1,x2) de la región del plano que contiene todos los valores (x1k, x2k ) y la raíz buscada.
||
1
1
xg ;1||
1
2 M
xg
||
2
1
xg ;1||
2
2 Mxg
![Page 21: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/21.jpg)
Método de Iteración de Punto fijo para sistemas de Ecuaciones no Lineales
Ejemplo Encuentre una solución del sistema de ecuaciones no lineales
Solución
Con el despeje de X1 del termino (-10X1) en la primera ecuación y de X2 del termino de (-10X2) en la segunda ecuación resulta.
X1=(X12+X2
2 + 8 )/ 10
X2=(X1X22+X1 + 8 ) / 10
0),(
0),(
810
810
212
21212
221
21211
xxxxxxf
xxxxxf
![Page 22: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/22.jpg)
Por medio de Iteración por desplazamientos simultáneos x1
k+1 = g1(x1k , x2
k )x2
k+1 = g2(x1k , x2
k )
Con los valores iniciales x10 = 0, x2
0 = 0 se inicia el procesoPrimera iteración
X11=(02+02 + 8 )/ 10 = 0.8
X21=(0(0)2 + 0 + 8 ) / 10 = 0.8
![Page 23: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/23.jpg)
Segunda iteraciónX1
2=((0.8)2+(0.8)2 + 8)/ 10 = 0.928
X22=(0.8(0.8)2 + 0.8 + 8 ) / 10 = 0.9312
Al continuar el proceso iterativo, se encuentra la siguiente sucesión de valores
kX1
k X2k
0 0.00000 0.00000
1 0.80000 0.80000
2 0.92800 0.93120
![Page 24: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/24.jpg)
kX1
k X2k
3 0.97283 0.97327
4 0.98937 0.98944
5 0.99578 0.99579
6 0.99832 0.99832
7 0.99933 0.99933
8 0.99973 0.99973
9 0.99989 0.99989
10 0.99996 0.99996
11 0.99998 0.99998
12 0.99999 0.99999
13 1.00000 1.00000
![Page 25: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/25.jpg)
• Cualquiera que sea el sistema que se va a resolvercon este método, puede aumentarse la velocidad deconvergencia usando desplazamientos sucesivosen lugar de los desplazamientos simultáneos esdecir se itera mediante
x1k+1 = g1(x1
k , x2k )
x2k+1 = g2(x1
k+1 , x2k )
Como en el caso lineal (Jacobi y Gauss-Seidel), sila iteración por desplazamientos simultáneosdiverge generalmente el método por desplazamientossucesivos divergiría mas rápido; es decir se detectamas rapido la divergencia, por lo que en general se recomienda el uso de desplazamientos sucesivos enlugar de desplazamientos simultáneos .
![Page 26: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/26.jpg)
• Resuelva el sistema del ejemplo anterior utilizando el método de punto fijo para sistemas no lineales con desplazamientos sucesivos.
0),(
0),(
810
810
212
21212
221
21211
xxxxxxf
xxxxxf
Problema Propuesto
![Page 27: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/27.jpg)
Método de Newton para sistemas de ecuaciones no lineales
• Todas las ecuaciones deben de ser cero en las raíces • Se define la matriz J(x) como:
1
,1
xf i
2
,1
xf i
n
i
xf ,1
1
,2
xf i
2
,2
xf i
n
i
xf ,2
1
,
xf in
2
,
xf in
n
in
xf ,
..........
..........
..........
.................................
....................
J(x) =
![Page 28: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/28.jpg)
Método de Newton para sistemas de ecuaciones no lineales
• Entonces podemos escribirF(x)+XiJ(x)=Xi+1 J(x)
• Dividiendo J(x) y reacomodando:Xi+1= Xi-J(x)-1 F(x)
Esta es la Ecuación de Newton para sistemas No LinealesPuesto que en cada iteración se tiene que calcular la inversa de la matriz J(x)y esto implica un considerable esfuerzo de cálculo , para evitar este paso se utiliza el artificio de encontrar un vector Y que satisfaga
J(x)Y= -F(x)
![Page 29: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/29.jpg)
Método de Newton para sistemas de ecuaciones no lineales
• Se establece un esquema iterativo donde cada nuevaaproximacion se obtiene como:
X(k+1) = y +x(k)
Al resolver el sistema tomando como valores iniciales(x1,x2)=(0,0) se tiene:
J(x)( x1,x2)=
![Page 30: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/30.jpg)
Un sistema de ecuaciones no lineales con dos incógnitas “x” y “y”
0573),(010),(
2
2
xyyyxvxyxyxu
Así la solución de este sistema son los valores de ( x , y ) que hacen a las funciones u y v iguales a cero.
Para resolver estas ecuaciones se utilizan extensiones de los métodos abiertos antes vistos.
![Page 31: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/31.jpg)
Resolución del sistema de ecuaciones no lineales
• Utilizando la iteración de punto fijo.
La aproximación de la iteración de punto fijo, vista anteriormente, se puede modificar para resolver dos ecuaciones simultáneas no lineales
Las modificaciones y las desventajas de este método se ilustra en el siguiente ejemplo.
![Page 32: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/32.jpg)
Ejemplo
0573),(010),(
2
2
xyyyxvxyxyxu
Solución
i
ii y
xx2
110
Con base en los valores iniciales
21429.25.3
)5.1(10 2
x
21 357 iii yxy
37516.24)5.3()21429.2(357 2 y
La aproximación diverge, pero si se cambia la formulación, los resultados difieren.
Sistema de ecuaciones no lineales. Valores iniciales x=1.5 y=3.5. La solución es x=2 y=3
![Page 33: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/33.jpg)
98340.202046.23
04955.357
02046.204955.394053.110
º3
04955.394053.13
86051.257
94053.186051.217945.210
º2
86051.217945.23
5.357
17945.25.35.110
357
10
y
x
Iteración
y
x
Iteración
y
x
Evaluandox
yy
xyx
%22.2
%96.3
_
_
ya
xa
EE
%55.0
%02.1
_
_
yt
xt
EE
Como se observa en esta ocasiónla aproximación no diverge.
![Page 34: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/34.jpg)
Resolución del sistema de ecuaciones no lineales
yvyy
xvxxvv
yuyy
xuxxuu
iii
iiiii
iii
iiiii
)()(
)()(
111
111
)()(
'1i
iii xf
xfxx
Utilizando Newton-Raphson.Este cálculo se basa en la expansión de la serie de Taylor de primer orden y con ella se obtiene la ecuación para este método.
La serie de Taylor de primer orden para el caso de dos variables.
)()()()( '11 iiiii xfxxxfxf
![Page 35: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/35.jpg)
xv
yu
yv
xu
xvu
xuv
yy
xv
yu
yv
xu
yuv
yvu
xx
iiii
ii
ii
ii
iiii
ii
ii
ii
1
1
Por medio de manipulación matemática y la regla de Cramer.
El denominador de ambas ecuaciones es conocido como el determinante Jacobiano del sistema.
![Page 36: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/36.jpg)
0573),(010),(
2
2
xyyyxvxyxyxu
5.32)5.3)(5.1(6161
75.36)5.3(33
5.1
5.65.3)5.1(22
0
220
0
0
xyyv
yxv
xyu
yxxu
Solución.
El Jacobiano para la primera iteración.125.156)75.36)(5.1()5.32)(5.6(
![Page 37: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/37.jpg)
Evaluando en las funciones.
84388.2125.156
)75.36)(5.2()5.6(625.15.3
03603.2125.156
)5.1(625.1)5.32(5.25.1
625.157)5.3)(5.1(35.3
5.210)5.3(5.1)5.1(
1
1
20
20
y
x
vu
Iteración Variable Valor Error Aprox Error True
2
x 1,9986 1,87% 0,07%
y 3,0027 5,29% 0,09%
3
x 2 0,07% 0%
y 3 0,09% 0%
![Page 38: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/38.jpg)
Notación
f x x xf x x x
f x x x
f IR IRx x f x x
n
n
n n
in
n i n
1 1 2
2 1 2
1 2
1 1
00
0
( , ,..., )( , ,..., )
( , ,..., )
:( ,..., ) ( ,..., )
F xF IR IR
x x x f x f x
n n
n n
( ):
( , ... , ) ( ( ), ... ( ))
01 1
• Escalar
• Vectorial
![Page 39: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/39.jpg)
Resolución iterativa
• x(0) estimación inicial de la solución
• Iteraciones: x(1), x(2), …, x(k)
• Criterio de convergencia
• | x(k+1) x(k) | < tol
• Criterio de parada
• k > maxiter
![Page 40: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/40.jpg)
Esquema del algoritmo• Entrada: f, x0, tol, maxiter• Proceso
• Inicializar incr, iter• Mientras incr > tol & iter < maxiter
• Obtener x• incr = norm(x x0)• Actualizar x0, iter
• Salida: x, iter, incr• Si incr > tol no converge
![Page 41: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/41.jpg)
Método de Punto Fijo
• Punto fijo
• Estimación inicial
• Iteraciones
• Criterio de paradax G xk k( ) ( )( ) 1
x x xn( ) ( ) ( )( ,..., )0
10 0
x x tolk k( ) ( ) 1
F x x G x( ) ( ) 0
![Page 42: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/42.jpg)
Algoritmo de Punto Fijofunction [x,iter,incr] = pfijo(g,x0,tol,
maxiter)iter = 0;incr = tol + 1;while incr > tol & iter < maxiter
x = feval(g,x0);incr = norm(x - x0);iter = iter + 1;x0 = x;
endif incr > tol, disp(‘No converge’), end
![Page 43: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/43.jpg)
Ejemplo• Sistema no lineal
• Problema de Punto Fijo
3 081 01 106 0
20 10 3 1 0
1 2 31
2
12
22
3
31 2
x x xx x x
e xx x
cos( )( . ) sen( .
/
x x x
x x x
x e x x
1 2 31
6
21
9 12
3
31
20
3
106 01
1 61 2
cos( ) /
sen . .
( ) /
![Page 44: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/44.jpg)
x x x
x x x
x x x
k k k
k k k
k k k
11
2 31
6
21 1
9 11 2
3
31 1
20 11
21
3
1 06 0 1
1 6
( ) ( ) ( )
( ) ( ) ( )
( ) ( ) ( )
cos( ) /
sen . .
exp /
• Punto Fijo con desplazamientos simultáneos
• Punto Fijo con desplazamientos sucesivos
x x x
x x x
x x x
k k k
k k k
k k k
11
2 31
6
21 1
9 1
2
3
31 1
20 1 2
3
106 01
1 6
( ) ( ) ( )
( ) ( ) ( )
( ) ( ) ( )
cos( ) /
sen . .
exp /
![Page 45: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/45.jpg)
Código de la función
function y=f(x)% Función para el método de punto% fijo con desplazamientos simultáneos
y(1) = cos(x(2)*x(3))/3 + 1/6;y(2) = sqrt(x(1)^2+sin(x(3))+1.06)/9-0.1;y(3) = (1-exp(-x(1)*x(2)))/20 - pi/6;
![Page 46: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/46.jpg)
Ejemplo 1: Desp. simultáneos
Iter x1(k) x2
(k) x3(k)
0 0.10000000 0.10000000 -0.10000000
1 0.49998333 0.00944115 -0.52310127
2 0.49999593 0.00002557 -0.52336331
3 0.5 0.00001234 -0.52359814
4 0.5 3.41679E8 -0.52359847
5 0.5 1.64870 E8 -0.52359877
![Page 47: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/47.jpg)
Código de la función
function y=f(x)% Función para el método de punto% fijo con desplazamientos sucesivos
y(1) = cos(x(2)*x(3))/3 + 1/6;y(2) = sqrt(y(1)^2+sin(x(3))+1.06)/9-0.1;y(3) = (1-exp(-y(1)*y(2)))/20 - pi/6;
![Page 48: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/48.jpg)
Ejemplo 1: Desp. sucesivos
Iter x1(k) x2
(k) x3(k)
0 0.10000000 0.10000000 -0.10000000
1 0.49998333 0.02222979 -0.52304613
2 0.49997747 0.00002815 -0.52359807
3 0.5 3.762202E-8 -0.52359877
4 0.5 5.028E-11 -0.5235987756
![Page 49: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/49.jpg)
Método de Newton
• Sistema de ecuaciones
• Aproximación por el plano tangente
• Paso de Newton
F xF IR IR
x x x f x f x
n n
n n
( ):
( , ... , ) ( ( ), ... ( ))
01 1
F x F x DF x x x( ) ( ) ( ) ( )( ) ( ) ( ) 0 0 0
x x DF x F x( ) ( ) ( ) ( )( ) ( )1 0 0 1 0
![Page 50: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/50.jpg)
Algoritmo de Newton
function [x,iter,incr] = newton(f,x,tol, maxiter)
iter = 0; incr = tol+1;while incr > tol & iter < maxiter[fx,dfx] = feval(f,x);delta = - dfx \ fx;incr = norm(delta);iter = iter+1;x = x + delta;endif incr>tol, disp(‘No converge’), end
El archivo f.mevalúa la funcióny el jacobiano
![Page 51: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/51.jpg)
Método de Newton. Ejemplo 2• Sistema
• Estimación inicial
• Primera iteración
x yx y
Sol x y2 2
2 2 12
12
34
1 00
: ,
x y0 01 3 ,
x
y
x
y
x yx y
x y
x y
1
1
0
0
0 0
0 0
1 02
02
02
02 1
2
2 22 2
1
![Page 52: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/52.jpg)
Resultados Newton Ejemplo 2
k x y0 1 31 0.62500000000000 1.625000000000002 0.51250000000000 1.043269230769233 0.50015243902439 0.881081619992914 0.50000002323057 0.866154046603325 0.50000000000000 0.866025413337576 0.50000000000000 0.86602540378444
![Page 53: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/53.jpg)
DF xx x x x x x
x x xx e x ex x x x
( )sen( ) sen( )
( . ) cos( )
32 162 01
20
3 2 3 2 2 3
1 2 3
2 11 2 1 2
Método de Newton. Ejemplo 3• Sistema no lineal
• Jacobiana
3 081 01 106 0
20 10 3 1 0
1 2 31
2
12
22
3
31 2
x x xx x x
e xx x
cos( )( . ) sen( .
/
![Page 54: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/54.jpg)
Resultados Newton. Ejemplo 3
k x1 x2 x3
0 0.10000000 0.10000000 0.100000001 0.49986967 0.01946685 0.521520472 0.50001423 0.00160764 0.523131663 0.50000012 1.48294E5 0.523558724 0.50000000 2.08910E8 0.523598405 0.50000000 2.792E11 0.523598786 0.50000000 4.E14 0.52359878
![Page 55: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/55.jpg)
Variantes de Newton (Ejercicio...) Actualización periódica del
Jacobiano
Aproximación del Jacobiano por diferencias divididas
Newton con desplazamiento unidimensional
![Page 56: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/56.jpg)
Métodos casi-Newton
• Idea de la secante• No usa las derivadas
parciales• Convergencia superlineal
• Formulación matricial
1
)1()1()2(
01
0111
a)x(fxx
xx)x(f)x(fa)x('f
)x(FAxx
A)x(DF)1(1
1)1()2(
1)1(
![Page 57: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/57.jpg)
Método de Broyden
1)(k(k)k
1)(k(k)k
Tk2
k
k1kk1kk
(k)1k
(k)1)(k
xxs
)F(x)F(xy
ss
)sA(yAA
)F(xAxx
Iterar
siendo
![Page 58: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/58.jpg)
Actualización de la inversa
A Ay A s
ss
As A y s A
s A yk
k kk k k
k
k
kk k k k k
k k k
11
12
1
11 1
11
1
11 12
( )
( ), ,...
T
T
T
![Page 59: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/59.jpg)
Algoritmo de Broyden • Entrada
• x0 ,tol, maxiter • Inicio
• M: Inversa del Jacobiano en x0
• x1 = x0 M*F(x0) • incr, iter
• Iteraciones: k = 1, 2, ...• Actualizar M % Ak-1
-1 Ak-1
• xk+1 = xk M*F(xk)
![Page 60: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/60.jpg)
Actualización de Mw = v; % F(xk1)v = F(x); % F del iterado actualy = v w; % F(xk) F(xk1)z = M*y; % Ak1
-1 * yk
p = s' *z; % (sk - xk-1)T* Ak1
-1 * yk
q = s' *M; % skT
* Ak1-1
R = (s+z)*q/p; % Transformación rango 1M = M+R; % Inversa nueva: Ak
-1
s = M*v; % Paso de Broyden: sk+1
![Page 61: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/61.jpg)
Algoritmo de Broyden
% Iniciov = F(x0)M = inv(DF(x0))% Inversa Jacobiano
s = M*v;x = x0+s;% Paso de Newton
incr = norm(s);
while incr > tolw = v; % F(x(k1))v = F(x);y = vw; % F(x(k)) F(x(k1))z = M*y; % inv(A(k1))*y(k)p = s' *z;q = s' *M; % s(k)'*inv(A(k1)R = (s+z)*q/p; M = M+R; % inversa de A(k)s = M*v;x = x+s; % Paso de Broydenincr = norm(s);
end
![Page 62: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/62.jpg)
Resultados de Broyden. Ejemplo
k x1 x2 x3
0 0.10000000 0.10000000 0.100000001 0.49986967 0.01946684 0.521520472 0.49998637 0.00873783 0.523174573 0.50000660 0.00086727 0.523572344 0.50000032 0.00003953 0.523597685 0.50000000 0.00000019 0.52359877
![Page 63: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/63.jpg)
Alternativas al primer paso• Estimar el Jacobiano por diferencias divididas• Estimación unidimensional del Jacobiano
))xx/()).x(F)x(F((diagA 01010
![Page 64: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/64.jpg)
Conclusiones• Una seria desventaja de la iteración es que
la convergencia depende de la manera enque se formula la ecuación
• El método Newton Raphson para dosecuaciones se puede generalizar pararesolver n ecuaciones simultáneas.
![Page 65: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/65.jpg)
![Page 66: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/66.jpg)
![Page 67: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/67.jpg)
![Page 68: Catedra Metodos Numericos 2013 Unsch 06](https://reader034.vdocumento.com/reader034/viewer/2022050712/55cf9b8f550346d033a68909/html5/thumbnails/68.jpg)
Muchas Gracias