pract_senl
TRANSCRIPT
Métodos numéricos para Métodos numéricos para la resolución de la resolución de
Sistemas de Ecuaciones Sistemas de Ecuaciones no Linealesno Lineales
ContenidoContenido
Planteamiento del problemaPlanteamiento del problema Método de Punto FijoMétodo de Punto Fijo Método de NewtonMétodo de Newton Variantes del método de NewtonVariantes del método de Newton
• Evaluación diferida del jacobianoEvaluación diferida del jacobiano• Aproximación por diferencias finitasAproximación por diferencias finitas• Newton unidimensionalNewton unidimensional
Métodos cuasi-Newton (Broyden)Métodos cuasi-Newton (Broyden)
NotaciónNotación
f x x x
f x x x
f x x x
f IR IR
x x f x x
n
n
n n
in
n i n
1 1 2
2 1 2
1 2
1 1
0
0
0
( , ,..., )
( , ,... , )
( , ,... , )
:
( ,..., ) ( ,..., )
F xF IR IR
x x x f x f x
n n
n n
( ):
( , ... , ) ( ( ), ... ( ))
01 1
EscalarEscalar
VectorialVectorial
Resolución iterativaResolución iterativa
xx(0)(0) estimación inicial de la solución estimación inicial de la solución
Iteraciones: xIteraciones: x(1)(1), x, x(2)(2), …, x, …, x(k)(k)
Criterio de convergenciaCriterio de convergencia
• | x| x(k+1)(k+1) x x(k)(k) | < tol | < tol
Criterio de paradaCriterio de parada
• k > maxiterk > maxiter
Esquema del algoritmoEsquema del algoritmo
Entrada: Entrada: f, xf, x00, tol, maxiter, tol, maxiter ProcesoProceso
• Inicializar Inicializar incr, iterincr, iter• Mientras Mientras incr > tolincr > tol & & iter < maxiteriter < maxiter
– Obtener Obtener xx
– incr = norm(x incr = norm(x xx00))
– Actualizar Actualizar x x00, iter, iter
Salida: Salida: x, iter, incrx, iter, incr• Si Si incr > tol incr > tol no converge no converge
Método de Punto FijoMétodo de Punto Fijo
Punto fijoPunto fijo
Estimación inicialEstimación inicial
Iteraciones Iteraciones
Criterio de paradaCriterio de parada
x G xk k( ) ( )( ) 1
x x xn( ) ( ) ( )( ,..., )0
10 0
x x tolk k( ) ( ) 1
F x x G x( ) ( ) 0
Algoritmo de Punto FijoAlgoritmo de Punto Fijo
function [x,iter,incr] = pfijo(g,x0,tol, function [x,iter,incr] = pfijo(g,x0,tol, maxiter)maxiter)
iter = 0;iter = 0;
incr = tol + 1;incr = tol + 1;
while incr > tol & iter < maxiterwhile incr > tol & iter < maxiter
x = feval(g,x0);x = feval(g,x0);
incr = norm(x - x0);incr = norm(x - x0);
iter = iter + 1;iter = iter + 1;
x0 = x;x0 = x;
endend
if incr > tol, disp(‘No converge’), endif incr > tol, disp(‘No converge’), end
EjemploEjemplo Sistema no linealSistema no lineal
Problema de Punto FijoProblema de Punto Fijo
3 0
81 01 106 0
20 10 3 1 0
1 2 31
2
12
22
3
31 2
x x x
x 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
106 01
1 6
( ) ( ) ( )
( ) ( ) ( )
( ) ( ) ( )
cos( ) /
sen . .
exp /
Punto Fijo con desplazamientos simultáneosPunto Fijo con desplazamientos simultáneos
Punto Fijo con desplazamientos sucesivosPunto 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ónCódigo de la función
function y=f(x)function y=f(x)
% Función para el método de punto% Función para el método de punto
% fijo con desplazamientos simultáneos% fijo con desplazamientos simultáneos
y(1) = cos(x(2)*x(3))/3 + 1/6;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(2) = sqrt(x(1)^2+sin(x(3))+1.06)/9-0.1;
y(3) = (1-exp(-x(1)*x(2)))/20 - pi/6;y(3) = (1-exp(-x(1)*x(2)))/20 - pi/6;
Ejemplo 1: Desp. simultáneos 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.41679E 8 -0.52359847
5 0.5 1.64870 E 8 -0.52359877
Código de la funciónCódigo de la función
function y=f(x)function y=f(x)
% Función para el método de punto% Función para el método de punto
% fijo con desplazamientos sucesivos% fijo con desplazamientos sucesivos
y(1) = cos(x(2)*x(3))/3 + 1/6;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(2) = sqrt(y(1)^2+sin(x(3))+1.06)/9-0.1;
y(3) = (1-exp(-y(1)*y(2)))/20 - pi/6;y(3) = (1-exp(-y(1)*y(2)))/20 - pi/6;
Ejemplo 1: Desp. sucesivos 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 de NewtonMétodo de Newton
Sistema de ecuacionesSistema de ecuaciones
Aproximación por el plano tangenteAproximación por el plano tangente
Paso de NewtonPaso 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 NewtonAlgoritmo de Newton
function [x,iter,incr] = newton(f,x,tol, maxiter)function [x,iter,incr] = newton(f,x,tol, maxiter)
iter = 0; incr = tol+1;iter = 0; incr = tol+1;
while incr > tol & iter < maxiterwhile incr > tol & iter < maxiter
[fx,dfx] = feval(f,x);[fx,dfx] = feval(f,x);
delta = - dfx \ fx;delta = - dfx \ fx;
incr = norm(delta);incr = norm(delta);
iter = iter+1;iter = iter+1;
x = x + delta;x = x + delta;
endend
if incr>tol, disp(‘No converge’), endif incr>tol, disp(‘No converge’), end
El archivo f.mEl archivo f.m evalúa la función evalúa la función
y el jacobiano y el jacobiano
Método de Newton. Ejemplo 2Método de Newton. Ejemplo 2
SistemaSistema
Estimación inicialEstimación inicial
Primera Primera iteracióniteració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
02
02 1
2
2 2
2 2
1
Resultados Newton Ejemplo 2Resultados Newton Ejemplo 2
k x y
0 1 3
1 0.62500000000000 1.62500000000000
2 0.51250000000000 1.04326923076923
3 0.50015243902439 0.88108161999291
4 0.50000002323057 0.86615404660332
5 0.50000000000000 0.86602541333757
6 0.50000000000000 0.86602540378444
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 3Método de Newton. Ejemplo 3 Sistema no linealSistema no lineal
JacobianaJacobiana
3 0
81 01 106 0
20 10 3 1 0
1 2 31
2
12
22
3
31 2
x x x
x x x
e xx x
cos( )
( . ) sen( .
/
Resultados Newton. Ejemplo 3Resultados 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.48294E 5 0.523558724 0.50000000 2.08910E 8 0.523598405 0.50000000 2.792E 11 0.523598786 0.50000000 4.E 14 0.52359878
Variantes de Newton (Ejercicio...)Variantes de Newton (Ejercicio...)
Actualización periódica del Actualización periódica del
JacobianoJacobiano
Aproximación del Jacobiano por Aproximación del Jacobiano por
diferencias divididasdiferencias divididas
Newton con desplazamiento Newton con desplazamiento
unidimensionalunidimensional
Métodos casi-NewtonMétodos casi-Newton
Idea de la secanteIdea de la secante• No usa las No usa las
derivadas derivadas parcialesparciales
• Convergencia Convergencia superlinealsuperlineal
Formulación Formulación matricialmatricial
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 BroydenMé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
IterarIterar
siendosiendo
Actualización de la inversaActualizació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 1 2
( )
( ), ,...
T
T
T
Algoritmo de Broyden Algoritmo de Broyden EntradaEntrada
• xx00 ,tol, maxiter ,tol, maxiter
InicioInicio• M: Inversa del Jacobiano en xM: Inversa del Jacobiano en x00
• xx11 = x = x00 M*F(x M*F(x00) )
• incr, iterincr, iter Iteraciones: k = 1, 2, ...Iteraciones: k = 1, 2, ...
• Actualizar M Actualizar M % A% Ak-1k-1-1-1 A Akk
-1-1
• xxk+1k+1 = x = xkk M*F(x M*F(xkk))
Actualización de MActualización de M
w = v;w = v; % F(x% F(xkk11))
v = F(x);v = F(x); % F del iterado actual% F del iterado actual
y = v y = v w;w; % F(x% F(xkk) ) F(x F(xkk11))
z = z = M*y;M*y; % % AAkk11-1 -1
* * yykk
p = p = s' *z;s' *z; % (s% (skk - x - xk-1k-1))TT ** A Akk11-1 -1
* * yykk
q = s' *M;q = s' *M; % s% skk TT ** A Akk11-1 -1
R = (s+z)*q/p; R = (s+z)*q/p; % Transformación rango 1% Transformación rango 1
M = M+R;M = M+R; % Inversa nueva: A% Inversa nueva: Akk-1 -1
s = s = M*v;M*v; % Paso de Broyden: s% Paso de Broyden: sk+1k+1
Algoritmo Algoritmo de Broyden de Broyden
% Inicio% Inicio
v =v = F(xF(x00))
M = inv(DF(xM = inv(DF(x00))))
% Inversa Jacobiano% Inversa Jacobiano
s = s = M*v; M*v;
x = xx = x00+s;+s;
% Paso de Newton% Paso de Newton
incr = norm(s);incr = norm(s);
while incr > tolwhile incr > tol
w = v;w = v; % F(x(k % F(x(k1))1))
v = F(x);v = F(x);
y = vy = vw;w; % F(x(k)) % F(x(k)) F(x(k F(x(k1))1))
z = z = M*y;M*y; % % inv(A(kinv(A(k1))*y(k)1))*y(k)
p = p = s' *z;s' *z;
q = s' *M;q = s' *M; % s(k)'*inv(A(k % s(k)'*inv(A(k1)1)
R = (s+z)*q/p; R = (s+z)*q/p;
M = M+R;M = M+R; % inversa de A(k) % inversa de A(k)
s = s = M*v;M*v;
x = x+s;x = x+s; % Paso de Broyden % Paso de Broyden
incr = norm(s);incr = norm(s);
endend
Resultados de Broyden. Ejemplo 3Resultados de Broyden. Ejemplo 3
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 pasoAlternativas al primer paso
Estimar el Jacobiano por diferencias Estimar el Jacobiano por diferencias divididasdivididas
Estimación unidimensional del Estimación unidimensional del Jacobiano Jacobiano
))xx/()).x(F)x(F((diagA 01010