-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
1/77
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
2/77
apitulo VI
Sistema de Ecuaciones
Algebraicas No Lineales
ING. CRISTIAN CASTRO P.
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
3/77
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)
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
4/77
Introduccion• Se pretende que al final de la exposición el estudiante pueda
reconocer los sistemas de ecuaciones no lineales y pueda
resolverlos 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
x x x f
x x x f
x x x f
• La solución de este sistemaconsta de valores xi que
simultáneamente hacen que
todas las ecuaciones sean
iguales a cero
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
5/77
Teoría de sistemas de Ecuaciones
No lineales• La forma general de un sistema de ecuaciones no lineales es:
f 1(x1, x2 x3, …, xn) = 0
f 2(x1, x2 x3, …, xn) = 0f 3(x1, x2 x3, …, xn) = 0
....................................
f n(x1, x2 x3, …, xn) = 0
Definiendo una función F
F(x1, x2 x3, …, xn) = [f 1(x1, x2 x3, …, xn),f 2(x1, x2 x3, …, xn),f 3(x1, x2 x3, …, xn) , f n(x1, x2 x3, …, xn)]
Usando una notacion vectorial para representar las variables X1,X2,…,Xn ).El sistema puede representarse por F(x)=0
La solución a este sistema es el vector X=[x1, x2 x3, …, xn]
que hace que simultaneamente todas las ecuaciones sean igual a 0.
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
6/77
Teoría de sistemas de Ecuaciones
No linealesMétodos de Solución :
• Método de Iteración de Punto Fijo para sistemas deecuaciones no lineales (Método de punto fijo multi
variable).
• Método de Newton para sistemas de ecuaciones no
lineales.
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
7/77
SISTEMAS DE ECUACIONES NO LINEALES
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
8/77
SISTEMAS DE ECUACIONES NO LINEALES
f(x, y)=0
g(x, y)=0
x
y
x*
y*
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
9/77
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)
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
10/77
Notación
f x x xf x x x
f x x x
f IR IR
x x f x x
n
n
n n
i
n
n i n
1 1 2
2 1 2
1 2
1 1
00
0
( , ,..., )( , ,..., )
( , ,..., )
:
( ,..., ) ( ,..., )
F x F IR IR x x x f x f x
n n
n n
( ) :( , ... , ) ( ( ), ... ( ))
01 1
• Escalar
• Vectorial
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
11/77
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
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
12/77
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
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
13/77
Método de Iteración de Punto fijo para
Sistemas de Ecuaciones no Lineales
Anteriormente se desarrollo el método de iteración de punto fijo para resolver la ecuación f(x)=0 transfor-mando esta ecuación en una ecuación de la forma
x= g(x),
usando el criterio de convergencia
|g’(x)|
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
14/77
Método de Iteración de Punto fijo para
Sistemas de Ecuaciones no LinealesPara el caso de un conjunto de Ecuaciones No lineales
utilizaremos un procedimiento similar extendiéndolo a
todas 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
x g ;1||
1
2 M x g
||
2
1
x g ;1||
2
2 M x g
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
15/77
Método de Punto Fijo• Punto fijo
• Estimación inicial
• Iteraciones
• Criterio de paradax G x
k k ( ) ( )
( )
1
x x xn( ) ( ) ( )( ,..., )0 10 0
x x tol
k k ( ) ( )
1
F x x G x( ) ( ) 0
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
16/77
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;
end
if incr > tol, disp(‘No converge’), end
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
17/77
MÉTODO DE PUNTO FIJO EN
SISTEMAS 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) = 0
y-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 cercano
s a las raíces.
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
18/77
Ejemplo• Sistema no lineal
• Problema de Punto Fijo
3 081 01 106 0
20 10 3 1 0
1 2 31
2
1
2
2
2
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 1
2
3
31
20
3
106 01
1 61 2
cos( ) /
sen . .
( ) /
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
19/77
x x x
x x x
x x x
k k k
k k k
k k k
1
1
2 31
6
2
1 1
9 1
1 2
3
3
1 120 1
1
2
1
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
1
1
2 31
6
2
1 19 1
2
3
3
1 120 1 2
3
106 01
1 6
( ) ( ) ( )
( ) ( ) ( )
( ) ( ) ( )
cos( ) /
sen . .
exp /
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
20/77
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;
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
21/77
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
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
22/77
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;
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
23/77
Ejemplo 1: Desp. sucesivos
Iter x1(k) x2(k) x3(k)
0 0.10000000 0.10000000 -0.10000000
1 0.49998333 0.02222979 -0.523046132 0.49997747 0.00002815 -0.52359807
3 0.5 3.762202E-8 -0.52359877
4 0.5 5.028E-11 -0.5235987756
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
24/77
MÉTODO DEL PUNTO FIJO EN
SISTEMAS DE ECUACIONES NO LINEALES
iteració
nx
iy
i err i
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)
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
25/77
MÉTODO DEL PUNTO FIJO EN
SISTEMAS DE ECUACIONES NO LINEALES
iteració
nx
iy
i err i
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 Seidel
xn=10/(x+y)
yn=((57-y)/(3xn))^(1/2)
err=sqrt((xn-x)^2+(yn-y)^2)
Converge mas rápido!!!
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
26/77
MÉTODO DEL PUNTO FIJO EN
SISTEMAS DE ECUACIONES NO LINEALESSin embargo, con el método del punto fijo, la convergencia dependede la manera en que se formulen las ecuaciones de recurrencia y de haber elegido valores iniciales lo bastante cercanos a la solución
En 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
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
27/77
Método de Iteración de Punto fijo para
sistemas de Ecuaciones no LinealesEjemplo
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 X2del termino de (-10X2) en la segunda ecuación resulta.
X1=(X12+X22 + 8 )/ 10
X2=(X1X22+X1 + 8 ) / 10
0),(
0),(
810
810
212
21212
22121211
x x x x x x f
x x x x x f
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
28/77
Por medio de Iteración por desplazamientos simultáneos
x1k+1 = g1(x1k , x2k )
x2k+1 = g2(x1
k , x2k )
Con los valores iniciales x10 = 0 , x2
0 = 0 se inicia el proceso
Primera iteración
X11
=(02
+02
+ 8 ) / 1 0 = 0 . 8
X21=(0(0)2 + 0 + 8 ) / 10 = 0.8
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
29/77
Segunda iteración
X12=((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 siguient
e sucesión de valores
k
X1k X2
k
0 0.00000 0.00000
1 0.80000 0.80000
2 0.92800 0.93120
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
30/77
k
X1k X2
k
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
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
31/77
• Cualquiera que sea el sistema que se va a resolver
con 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 desplazamientos
sucesivos 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 .
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
32/77
Un sistema de ecuaciones no lineales
con dos incógnitas “x” y “y”
0573),(
010),(
2
2
xy y y xv
xy x y xu
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 losmétodos abiertos antes vistos.
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
33/77
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étod
o se ilustra en el siguiente ejemplo.
Ejemplo
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
34/77
Ejemplo
0573),(
010),(
2
2
xy y y xv
xy x y xu
Solución
i
ii
y
x x
2
1
10
Con base en los valores iniciales
21429.25.3
)5.1(10 2
x
2
1 357 iii y x y
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
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
35/77
98340.2
02046.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
Evaluando
x y y
xy x
%22.2
%96.3
_
_
ya
xa
E
E
%55.0
%02.1
_
_
yt
xt
E
E
Como se observa en esta ocasión
la aproximación no diverge.
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
36/77
• 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
x x x x x x f
x x x x x f
Problema Propuesto
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
37/77
MÉTODO DE PUNTO FIJO EN
SISTEMAS DE ECUACIONES NO LINEALES
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
38/77
MÉTODO DE PUNTO FIJO EN
SISTEMAS DE ECUACIONES NO LINEALES
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
39/77
MÉTODO DE NEWTON RAPHSON EN
SISTEMAS DE ECUACIONES NO LINEALES
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
40/77
MÉTODO DE NEWTON RAPHSON EN
SISTEMAS DE ECUACIONES NO LINEALES
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
41/77
MÉTODO DE NEWTON RAPHSON EN
SISTEMAS DE ECUACIONES NO LINEALES
Mét d d N t i t
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
42/77
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
x
f i
2
,1
x
f i
n
i
x
f
,1
1
,2
x f i
2
,2
x f i
n
i
x f
,2
1
,
x f in
2
,
x f in
n
in
x f
,
..........
..........
..........
.................................
....................
J(x) =
Mét d d N t i t d
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
43/77
Método de Newton para sistemas de
ecuaciones no lineales• Entonces podemos escribir
F(x)+Xi J(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 Lineales
Puesto que en cada iteración se tiene que calcular la inver
sa de la matriz J(x)y esto implica un considerable esfuerzode cálculo , para evitar este paso se utiliza el artificio de en
contrar un vector Y que satisfaga
J(x)Y= -F(x)
• Se establece un esquema iterativo donde cada nueva aproxi-mación se obtiene como:
X(k+1) = y +x(k)
Se resuelve el sistema tomando como valores iniciales
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
44/77
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
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
45/77
Algoritmo de Newtonfunction [x,iter,incr] = newton(f,x,tol, m
axiter)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;
end
if incr>tol, disp(‘No converge’), end
El archivo f.mevalúa la función
y el jacobiano
É
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
46/77
MÉTODO DE NEWTON RAPHSON EN
SISTEMAS DE ECUACIONES NO LINEALES
u(x, y)
v(x, y)
x
yNo sepuedemostrar laimagen en estemomento.
x1
y1
É
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
47/77
MÉTODO DE NEWTON RAPHSON EN
SISTEMAS DE ECUACIONES NO LINEALES• Este procedimiento corresponde, analíticamente, a extender
el uso de la derivada, ahora para calcular la intersección
entre dos funciones no lineales.
• Al igual que para una sola ecuación, el cálculo se basa en
la expansión de la serie de Taylor de primer orden, ahora de
múltiples variables, para considerar la contribución de más
de una variable independiente en la determinación de la raíz.
• Para dos variables, la serie de Taylor de primer orden se
escribe, para cada ecuación no lineal:
i i
i 1 i i 1 i i 1 i
i ii 1 i i 1 i i 1 i
u u
u u (x x ) (y y )x y
v vv v (x x ) (y y )
x y
É
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
48/77
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 i
i 1 i 1 i i i
u u u ux y u x yx y x y
v v v vx y v x y
x y x y
i i i ii i 1 i i 1 i
i i i i
i i 1 i i 1 i
u u u uu x x y y 0x x y y
v v v vv x x y y 0
x x y y
MÉTODO DE NEWTON RAPHSON EN
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
49/77
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 v
x xJu v
y y
i ii i
i 1 i
v uu vy y
x xJ
i ii i
i 1 i
u vv ux xy y
J
MÉTODO DE NEWTON RAPHSON EN
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
50/77
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
MÉTODO DE NEWTON RAPHSON EN
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
51/77
MÉTODO DE NEWTON RAPHSON EN
SISTEMAS DE ECUACIONES NO LINEALESSistema 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
i t e r a c i o n e s
x
y
2x xy 10 2y 3xy 57
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
52/77
Resolución del sistema de ecuaciones
no lineales
y
v y y
x
v x xvv
yu y y
xu x xuu
iii
iiiii
iiiiiiii
)()(
)()(
111
111
)(
)('1
i
i
ii x f
x f
x x
Utilizando Newton-Raphson.
Este cálculo se basa en la expansión de la serie de Taylorde 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 x f x x x f x f
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
53/77
x
v
y
u
y
v
x
u x
v
u x
u
v y y
x
v
y
u
y
v
x
u
y
uv
y
vu
x x
iiii
i
i
i
i
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.
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
54/77
0573),(
010),(
2
2
xy y y xv
xy x y xu
5.32)5.3)(5.1(6161
75.36)5.3(33
5.1
5.65.3)5.1(22
0
220
0
0
xy y
v
y x
v
x y
u
y x xu
Solución.
El Jacobiano para la primera iteración.
125.156)75.36)(5.1()5.32)(5.6(
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
55/77
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
2
0
2
0
y
x
v
u
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%
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
56/77
Método de Newton. Ejemplo 2
• Sistema
• Estimación inicial
• Primera
iteración
x y
x ySol x y
2 2
2 2 12
12
34
1 0
0
: ,
x y0 01 3 ,
x
y
x
y
x y
x y
x y
x y
1
1
0
0
0 0
0 0
1 02
02
0
2
0
2 12
2 2
2 2
1
R lt d N t Ej l 2
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
57/77
Resultados Newton Ejemplo 2
k x y
0 1 3
1 0.62500000000000 1.62500000000000
2 0.51250000000000 1.043269230769233 0.50015243902439 0.88108161999291
4 0.50000002323057 0.86615404660332
5 0.50000000000000 0.86602541333757
6 0.50000000000000 0.86602540378444
é d d j l
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
58/77
DF x
x x x x x x
x x x
x e x ex x x x( )
sen( ) sen( )
( . ) cos( )
3
2 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 0 1 1 06 0
20 10 3 1 0
1 2 3
1
2
1
2
2
2
3
31 2
x x xx x x
e xx x
cos( )( . ) sen( .
/
R lt d N t Ej l 3
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
59/77
Resultados Newton. Ejemplo 3
k x1 x2 x30 0.10000000 0.10000000 0.100000001 0.49986967 0.01946685 0.52152047
2 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
Variantes del Método de Newton
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
60/77
Variantes del Método de Newton
Actualización periódica del
Jacobiano Aproximación del Jacobiano por
diferencias divididas
Newton con desplazamiento
unidimensional
Métodos cuasi Newton
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
61/77
Métodos cuasi-Newton
• Idea de la secante
• No usa las derivadas
parciales
• Convergencia superlineal
• Formulación matricial
1
)1()1()2(
01
01
11
a
)x(f xx
xx
)x(f )x(f
a)x('f
)x(FAxx
A)x(DF)1(1
1
)1()2(
1
)1(
Mét d d B d
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
62/77
Método de Broyden
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
63/77
Método de Broyden
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
64/77
Método de Broyden
Método de Broyden
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
65/77
Método de Broyden
Método de Broyden
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
66/77
Método de Broyden
Método de Broyden
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
67/77
Método de Broyden
Método de Broyden
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
68/77
Método de Broyden
1)(k (k)
k
1)(k (k)
k
T
k 2k
k 1k k
1k k
(k)1
k
(k)1)(k
xxs
)F(x)F(xy
ss
)sA(y
AA
)F(xAxx
Iterar
siendo
Actualización de la inversa
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
69/77
Actualización de la inversa
A Ay A s
ss
A s A y s A
s A yk
k k k k k
k
k
k
k k k k k
k k k
1 1 12
1
1
1 11 11
1
1 12
( )
( ) , ,...
T
T
T
Algoritmo de Broyden
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
70/77
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 )
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
71/77
Algoritmo while incr > tol
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
72/77
g
de Broyden
% Inicio
v = F(x0)
M = inv(DF(x0))
% Inversa Jacobiano
s = M*v;
x = x0+s;
% Paso de Newton
incr = norm(s);
while incr > tol
w = v; % F(x(k 1))
v = F(x);
y = vw; % F(x(k)) F(x(k 1))
z = M*y; % inv(A(k 1))*y(k)
p = s' *z;
q = s' *M; % s(k)'*inv(A(k 1)
R = (s+z)*q/p;
M = M+R; % inversa de A(k)
s = M*v;
x = x+s; % Paso de Broyden
incr = norm(s);
end
Resultados de Broyden.
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
73/77
Ejemplok 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.52359768
5 0.50000000 0.00000019 0.52359877
Alternativas al primer paso
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
74/77
Alternativas al primer paso
• Estimar el Jacobiano por diferencias divididas
• Estimación unidimensional del Jacobiano
))xx/()).x(F)x(F((diagA 01010
Conclusiones
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
75/77
• Una seria desventaja de la iteración es quela convergencia depende de la manera en
que se formula la ecuación
• El método Newton Raphson para dosecuaciones se puede generalizar para
resolver n ecuaciones simultáneas.
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
76/77
-
8/16/2019 sistema de ecuaciones algrebraicas no lineales
77/77
Muchas Gracias