Metodo De Broyden 375e31

MÉTODO DE BROYDEN Universidad Nacional Mayor de San Marcos

Maestría en Matemática Aplicada Métodos Numéricos Profesora: Vilma Fajardo Presentado por: Sergio Luque Mamani & Javier Valeriano Mamani

Métodos Numéricos

Introducción En análisis numérico, el método de Broyden es un método cuasinewtoniano para la solución numérica de sistemas ecuaciones no lineales con más de una variable. Fue descrito originalmente por C. G. Broyden en 1965.  Idea de la secante  No usa las derivadas parciales  Convergencia superlineal

f ' ( x1 )  a1  x

( 2)

f ( x1 )  f ( x0 ) x1  x0

f ( x (1) ) x  a1 (1)

 Formulación matricial

DF ( x (1) )  A1 1

x ( 2)  x (1)  A1  F ( x (1) )

Sergio Luque & Javier Valeriano

Métodos Numéricos

Método de Broyden Un punto débil en el método de Newton para resolver sistemas de ecuaciones no lineales es la necesidad de calcular la matriz Jacobiana en cada iteración y resolver un sistema lineal 𝒏 × 𝒏 asociado a esta matriz. Para ilustrar la magnitud de esta debilidad, consideremos la cantidad de cálculos necesarios para llevar a cabo una iteración del método de Newton. La matriz Jacobiana asociada a un sistema de n ecuaciones no lineal escrita en la forma 𝑭(𝒙) = 𝟎 requiere la determinación y evaluación de las n2 derivadas parciales de las n componentes de 𝑭. En la mayoría de los casos, la evaluación exacta de las derivadas parciales es complicada y en muchas ocasiones imposible. Para superar esta dificultad se pueden usar aproximaciones de diferencia finita a las derivadas parciales.

donde h es pequeño en valor absoluto y 𝒆𝒌 es el vector cuyo único elemento diferente de cero es 1 en la 𝑘 − é𝑠𝑖𝑚𝑎 coordenada. Esta aproximación, sin embargo, requiere aún la realización de por lo menos n 2 evaluaciones funcionales escalares para aproximar el Jacobiano y no reduce la cantidad de cálculos, que es en general 𝑶(𝒏𝟑), para resolver el sistema lineal que contiene al Jacobiano aproximado. El esfuerzo computacional total para sólo una iteración del método de Newton es entonces de por lo menos, (𝒏𝟐 + 𝒏) evaluaciones funcionales escalares (𝒏𝟐 para la evaluación de la matriz Jacobiana y n para la evaluación de 𝑭) junto con 𝑶(𝒏𝟑) operaciones aritméticas para resolver el sistema lineal. Esta cantidad de esfuerzo computacional es prohibitiva excepto para valores relativamente pequeños de n y para funciones escalares fáciles de evaluar. En este apartado consideraremos una generalización del método de la secante en sistemas de ecuaciones no lineales y, en particular, consideraremos una técnica conocida como el método de Broyden. El método requiere solamente de n evaluaciones funcionales escalares por iteración y reduce también el número de cálculos aritméticos a 𝑶(𝒏𝟐). Es uno de los métodos conocidos como renovaciones de secante de mínimo cambio que producen los algoritmos llamados cuasi-Newton. Estos métodos reemplazan la matriz Jacobiana en el método de Newton por una matriz de aproximación que se renueva en cada iteración. La desventaja de estos métodos consiste en que se pierde la convergencia cuadrática del método de Newton y se reemplaza por una convergencia llamada superlineal.

Sergio Luque & Javier Valeriano

Métodos Numéricos

Método de Broyden 1

Iterar:

x (k 1)  x (k)  A k  F(x (k) )

Siendo:

A k  A k 1 

(y k  A k 1s k ) sk

2

sk

T

y k  F(x (k) )  F(x (k 1) ) s k  x (k)  x (k 1) Actualización de la inversa: 1

 ( y  Ak 1sk ) T  1 Ak   Ak 1  k sk  2   s k   1 k 1

A

( sk  Ak11 yk ) sk Ak11  k  1,2,... T sk Ak11 yk T

Algoritmo de Broyden:  Entrada  𝑥0 , 𝑡𝑜𝑙, 𝑚𝑎𝑥𝑖𝑡𝑒𝑟  Inicio  𝑀: 𝐼𝑛𝑣𝑒𝑟𝑠𝑎 𝑑𝑒𝑙 𝐽𝑎𝑐𝑜𝑏𝑖𝑎𝑛𝑜 𝑒𝑛 𝑥0  𝑥1 = 𝑥0 − 𝑀 ∗ 𝐹(𝑥0 )  𝑖𝑛𝑐𝑟, 𝑖𝑡𝑒𝑟  Iteraciones: 𝑘 = 1, 2, . ..  Actualizar M

−1 % 𝐴−1 𝑘−1  𝐴𝑘

 𝑥𝑘+1 = 𝑥𝑘 − 𝑀 ∗ 𝐹(𝑥𝑘 )

Sergio Luque & Javier Valeriano

Métodos Numéricos

Actualización de M: 𝑤 = 𝑣;

% 𝐹(𝑥𝑘−1 )

𝑣 = 𝐹(𝑥);

% 𝐹 𝑑𝑒𝑙 𝑖𝑡𝑒𝑟𝑎𝑑𝑜 𝑎𝑐𝑡𝑢𝑎𝑙

𝑦 = 𝑣 − 𝑤;

% 𝐹(𝑥𝑘 ) − 𝐹(𝑥𝑘−1 )

𝑧 = − 𝑀 ∗ 𝑦;

% − 𝐴−1 𝑘−1 𝑦𝑘

𝑝 = − 𝑠′ ∗ 𝑧;

% (𝑆𝑘 − 𝑥𝑘−1 )𝑇 𝐴−1 𝑘−1 𝑦𝑘

𝑞 = 𝑠′ ∗ 𝑀;

% 𝑆𝑘𝑇 𝐴−1 𝑘−1

𝑅 = (𝑠 + 𝑧) ∗ 𝑞/𝑝; % 𝑇𝑟𝑎𝑛𝑠𝑓𝑜𝑟𝑚𝑎𝑐𝑖ó𝑛 𝑟𝑎𝑛𝑔𝑜 1 𝑀 = 𝑀 + 𝑅;

% 𝐼𝑛𝑣𝑒𝑟𝑠𝑎 𝑛𝑢𝑒𝑣𝑎: 𝐴−1 𝑘

𝑠 = − 𝑀 ∗ 𝑣;

% 𝑃𝑎𝑠𝑜 𝑑𝑒 𝐵𝑟𝑜𝑦𝑑𝑒𝑛: 𝑆𝑘+1

Algoritmo de Broyden:

while 𝑖𝑛𝑐𝑟 > 𝑡𝑜𝑙 𝑤 = 𝑣; % 𝐹(𝑥(𝑘 − 1))

% 𝐼𝑛𝑖𝑐𝑖𝑜

𝑣 = 𝐹 (𝑥 ); % 𝐹 𝑑𝑒𝑙 𝑖𝑡𝑒𝑟𝑎𝑑𝑜 𝑎𝑐𝑡𝑢𝑎𝑙

𝑣 = 𝐹 (𝑥0 );

𝑦 = 𝑣 − 𝑤; % 𝐹(𝑥(𝑘)) − 𝐹(𝑥(𝑘 − 1))

% 𝐼𝑛𝑣𝑒𝑟𝑠𝑎 𝐽𝑎𝑐𝑜𝑏𝑖𝑎𝑛𝑜

𝑧 = − 𝑀 ∗ 𝑦; % − 𝑖𝑛𝑣(𝐴(𝑘 − 1)) ∗ 𝑦(𝑘)

𝑀 = 𝑖𝑛𝑣(𝐷𝐹(𝑥0 ));

𝑝 = − 𝑠′ ∗ 𝑧;

𝑠 = − 𝑀 ∗ 𝑣;

𝑞 = 𝑠′ ∗ 𝑀; % 𝑠(𝑘)′ ∗ 𝑖𝑛𝑣(𝐴(𝑘 − 1)

% 𝑃𝑎𝑠𝑜 𝑑𝑒 𝑁𝑒𝑤𝑡𝑜𝑛

% 𝑇𝑟𝑎𝑛𝑠𝑓𝑜𝑟𝑚𝑎𝑐𝑖ó𝑛 𝑟𝑎𝑛𝑔𝑜 1

𝑥 = 𝑥0 + 𝑠;

𝑅 = (𝑠 + 𝑧) ∗ 𝑞/𝑝;

𝑖𝑛𝑐𝑟 = 𝑛𝑜𝑟𝑚(𝑠);

𝑀 = 𝑀 + 𝑅; % 𝑖𝑛𝑣𝑒𝑟𝑠𝑎 𝑑𝑒 𝐴−1 𝑘 𝑠 = − 𝑀 ∗ 𝑣; % 𝑃𝑎𝑠𝑜 𝑑𝑒 𝐵𝑟𝑜𝑦𝑑𝑒𝑛 𝑥 = 𝑥 + 𝑠; 𝑖𝑛𝑐𝑟 = 𝑛𝑜𝑟𝑚(𝑠); 𝑒𝑛𝑑

Sergio Luque & Javier Valeriano

Métodos Numéricos

Sergio Luque & Javier Valeriano

Métodos Numéricos

Implementación Computacional con MATLAB y su aplicación Se desea estimar la presión 𝑝2 existente en el punto 𝑃2, así como los caudales 𝑄, 𝑄1 𝑦 𝑄2 , que circulan por cada una de las ramas de la red de tuberías antes descrita. El sistema dado puede escribirse, de acuerdo a los datos del ejercicio, como:

El sistema de 4 ecuaciones con 4 incógnitas puede aligerarse computacionalmente utilizando la última ecuación inyectada en la primera y reformulando el sistema como:

Se va a aplicar el método de Broyden a este último sistema, donde los valores iniciales son:

Con el método de Broyden implementado con MATLAB, se define la siguiente función para el sistema de ecuaciones no lineales:

Sergio Luque & Javier Valeriano

Métodos Numéricos

Luego, se llama a la función de Broyden con los valores iniciales proporcionados.

Obteniéndose el siguiente resultado:

Con los siguientes valores como solución:

Sergio Luque & Javier Valeriano

Métodos Numéricos

También se ha implementado una aplicación GUI con interfaz de de nombre 𝑏𝑟𝑜𝑦𝑑𝑒𝑛_𝑎𝑝𝑝, el cual nos muestra directamente los resultados al ejecutar con los valores iniciales dados.

Sergio Luque & Javier Valeriano

Métodos Numéricos

Conclusiones 

El método de Broyden nos permite hallar la solución de un sistema no lineal, sin necesidad de recurrir repetidas veces al cálculo del jacobiano del sistema.



Su algoritmo es practico e intuitivo, por lo que no se necesita de un análisis fuerte, ni tampoco lleva a confusión.



Es un método de resolución numérica de fácil implementación computacional.

Sergio Luque & Javier Valeriano

Métodos Numéricos

Bibliografía 

Conde C. y Schiavi E. Métodos numéricos de resolución de ecuaciones no lineales. Departamento de Matemática Aplicada. España.



Ferrante J. Sistema de ecuaciones no lineales.



Burden R. y Faires D. Análisis numérico. Grupo editorial Iberoamérica.



Chapra S. y Canale R. Métodos numéricos para ingenieros. Mc Graw Hill.



MATLAB. https://la.mathworks.com/

Sergio Luque & Javier Valeriano