1 Métodos numéricos para la resolución de Sistemas de Ecuaciones no Lineales

2 Contenido Planteamiento del problema Método de Punto FijoMé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)

3 Notación Escalar Vectorial

4 Resolución iterativa x(0) estimación inicial de la soluciónIteraciones: x(1), x(2), …, x(k) Criterio de convergencia | x(k+1) - x(k) | < tol Criterio de parada k > maxiter

5 Esquema del algoritmo Entrada: f, x0, tol, maxiter ProcesoInicializar 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

6 Método de Punto Fijo Punto fijo Estimación inicial IteracionesCriterio de parada

7 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 Ejemplo Sistema no lineal Problema de Punto Fijo

9 Punto Fijo con desplazamientos simultáneosPunto Fijo con desplazamientos sucesivos

10 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;

11 Ejemplo 1: Desp. simultáneos

12 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;

13 Ejemplo 1: Desp. sucesivos

14 Método de Newton Sistema de ecuacionesAproximación por el plano tangente Paso de Newton

15 El archivo f.m evalúa la función y el jacobianoAlgoritmo 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; end if incr>tol, disp(‘No converge’), end El archivo f.m evalúa la función y el jacobiano

16 Método de Newton. Ejemplo 2Sistema Estimación inicial Primera iteración

17 Resultados Newton Ejemplo 2

18 Método de Newton. Ejemplo 3Sistema no lineal Jacobiana

19 Resultados Newton. Ejemplo 3

20 Variantes de Newton (Ejercicio...)Actualización periódica del Jacobiano Aproximación del Jacobiano por diferencias divididas Newton con desplazamiento unidimensional

21 Métodos casi-Newton Idea de la secante Formulación matricialNo usa las derivadas parciales Convergencia superlineal Formulación matricial

22 Método de Broyden Iterar siendo

23 Actualización de la inversa

24 Algoritmo de Broyden Entrada Inicio Iteraciones: k = 1, 2, ...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)

25 Actualización de M w = v; % F(xk-1) v = F(x); % F del iterado actualy = v - w; % F(xk) - F(xk-1) z = - M*y; % - Ak-1-1 * yk p = - s' *z; % (sk - xk-1)T * Ak-1-1 * yk q = s' *M; % sk T * Ak-1-1 R = (s+z)*q/p; % Transformación rango 1 M = M+R; % Inversa nueva: Ak-1 s = - M*v; % Paso de Broyden: sk+1

26 Algoritmo de Broyden while incr > tol w = v; % F(x(k-1)) v = F(x);y = v-w; % 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 % Inicio v = F(x0) M = inv(DF(x0)) % Inversa Jacobiano s = - M*v; x = x0+s; % Paso de Newton incr = norm(s);

27 Resultados de Broyden. Ejemplo 3

28 Alternativas al primer pasoEstimar el Jacobiano por diferencias divididas Estimación unidimensional del Jacobiano

29 F i n