Catedra Metodos Numericos 2015 - UNSCH (06) [Modo de ... · Método de Iteración de Punto fijo...

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

Capitulo VI

Sistema de Ecuaciones Algebraicas No Lineales

ING.�CRISTIAN�CASTRO�P.

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)

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

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.

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.

SISTEMAS DE ECUACIONES NO LINEALES

SISTEMAS DE ECUACIONES NO LINEALES

f(x, y)=0

g(x, y)=0

x

y

x*

y*

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)

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

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

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

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 transfor-mando esta ecuación en una ecuación de la formax= g(x),usando el criterio de convergencia|g’(x)|

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

Método de Punto Fijo

• Punto fijo

• Estimación inicial

• Iteraciones

• Criterio de paradax G xk k( ) ( )( ) 1

x x xn( ) ( ) ( )( ,..., )0 1

0 0

x x tolk k( ) ( ) 1

F x x G x( ) ( ) 0

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

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.

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 . .

( ) /

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 /

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;

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

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;

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

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)


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!!!


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 yi1 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

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+X22 + 8 )/ 10

X2=(X1X22+X1 + 8 ) / 10

0),(

0),(

810

810

212

21212

221

21211

xxxxxxf

xxxxxf

Por medio de Iteración por desplazamientos simultáneos x1k+1 = g1(x1k , x2k )x2k+1 = g2(x1k , x2k )

Con los valores iniciales x10 = 0, x20 = 0 se inicia el procesoPrimera iteración

X11=(02+02 + 8 )/ 10 = 0.8

X21=(0(0)2 + 0 + 8 ) / 10 = 0.8

Segunda iteraciónX12=((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

kX1k X2k

0 0.00000 0.00000

1 0.80000 0.80000

2 0.92800 0.93120

kX1k 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

• 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(x1k , x2k )x2k+1 = g2(x1k+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 .

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.

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.

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

98340.202046.2304955.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.

• 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

MÉTODO DE PUNTO FIJO ENSISTEMAS DE ECUACIONES NO LINEALES

MÉTODO DE NEWTON RAPHSON EN SISTEMAS DE ECUACIONES NO LINEALES

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) =

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)

• 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

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

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


u(x, y)

v(x, y)

x

yNo se puede mostrar la imagen en este momento.

x1

y1

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ó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


• 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


• 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


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


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

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

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.

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(

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%

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

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

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( .

/

Resultados Newton. Ejemplo 3

k x1 x2 x30 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

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

• 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(

Método de Broyden

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

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

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)

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 * ykp = s' *z; % (sk - xk-1)T * Ak1-1 * ykq = s' *M; % sk T * 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

Algoritmo de Broyden

% Inicio

v = F(x0)M = inv(DF(x0))% Inversa Jacobiano

s = M*v;x = x0+s;

% Paso de Newtonincr = 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

Resultados de Broyden. Ejemplo

k x1 x2 x30 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

Alternativas al primer paso• Estimar el Jacobiano por diferencias divididas• Estimación unidimensional del Jacobiano

))xx/()).x(F)x(F((diagA 01010

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.

Muchas Gracias

Catedra Metodos Numericos 2015 - UNSCH (06) [Modo de ... · Método de Iteración de Punto fijo...

Documents

Transcript of Catedra Metodos Numericos 2015 - UNSCH (06) [Modo de ... · Método de Iteración de Punto fijo...