En análisis numérico, el método de Broyden es un método cuasi-Newton para encontrar raíces en k variables. Fue descrito originalmente por CG Broyden en 1965. [1]
El método de Newton para resolver f ( x ) = 0 usa la matriz jacobiana , J , en cada iteración. Sin embargo, calcular este jacobiano es una operación difícil y costosa. La idea detrás del método de Broyden es calcular todo el jacobiano solo en la primera iteración y hacer actualizaciones de rango uno en otras iteraciones.
En 1979, Gay demostró que cuando el método de Broyden se aplica a un sistema lineal de tamaño n × n , termina en 2 n pasos, [2] aunque, como todos los métodos cuasi-Newton, puede que no converja para sistemas no lineales.
Descripción del método
Resolver ecuaciones de una sola variable
En el método de la secante, reemplazamos la primera derivada f ′ en x n con la aproximación en diferencias finitas :
y proceda de manera similar al método de Newton :
donde n es el índice de iteración.
Resolver un sistema de ecuaciones no lineales
Considere un sistema de k ecuaciones no lineales
donde f es una función con valores vectoriales del vector x :
Para este tipo de problemas, Broyden da una generalización del método de Newton unidimensional, en sustitución de la derivada con la jacobiana J . La matriz jacobiana se determina iterativamente, con base en la ecuación secante en la aproximación de diferencias finitas:
donde n es el índice de iteración. Para mayor claridad, definamos:
por lo que lo anterior se puede reescribir como
La ecuación anterior está subdeterminada cuando k es mayor que uno. Broyden sugiere usar la estimación actual de la matriz jacobiana J n −1 y mejorarla tomando la solución de la ecuación secante que es una modificación mínima de J n −1 :
Esto minimiza la siguiente norma de Frobenius :
Entonces podemos proceder en la dirección de Newton:
Broyden también sugirió usar la fórmula de Sherman-Morrison para actualizar directamente la inversa de la matriz jacobiana:
Este primer método se conoce comúnmente como el "buen método de Broyden".
Se puede derivar una técnica similar utilizando una modificación ligeramente diferente de J n −1 . Esto produce un segundo método, el llamado "método de Broyden malo" (pero ver [3] ):
Esto minimiza una norma de Frobenius diferente:
Se han sugerido muchos otros esquemas de cuasi-Newton en la optimización , donde uno busca un máximo o mínimo encontrando la raíz de la primera derivada ( gradiente en múltiples dimensiones). El jacobiano del gradiente se llama hessiano y es simétrico, lo que agrega más restricciones a su actualización.
Otros miembros de la clase Broyden
Broyden ha definido no solo dos métodos, sino toda una clase de métodos. Otros autores han agregado otros miembros de esta clase.
- La actualización de Davidon-Fletcher-Powell es el único miembro de esta clase que se publica antes que los dos miembros definidos por Broyden. [4]
- Algoritmo de Schubert o de Broyden disperso: una modificación para matrices jacobianas dispersas. [5]
- Klement (2014): utiliza menos iteraciones para resolver muchos sistemas de ecuaciones. [6] [7]
Ver también
Referencias
- ^ Broyden, CG (octubre de 1965). "Una clase de métodos para resolver ecuaciones simultáneas no lineales" . Matemáticas de la Computación . Sociedad Matemática Estadounidense. 19 (92): 577–593. doi : 10.1090 / S0025-5718-1965-0198670-6 . JSTOR 2003941 .
- ^ Gay, DM (agosto de 1979). "Algunas propiedades de convergencia del método de Broyden". Revista SIAM de Análisis Numérico . SIAM. 16 (4): 623–630. doi : 10.1137 / 0716047 .
- ^ Kvaalen, Eric (noviembre de 1991). "Un método Broyden más rápido". BIT Matemáticas numéricas . SIAM. 31 (2): 369–372. doi : 10.1007 / BF01931297 .
- ^ Broyden, CG (octubre de 1965). "Una clase de métodos para resolver ecuaciones simultáneas no lineales" . Matemáticas de la Computación . Sociedad Matemática Estadounidense. 19 (92): 577–593. doi : 10.1090 / S0025-5718-1965-0198670-6 . JSTOR 2003941 .
- ^ Schubert, LK (1 de enero de 1970). "Modificación de un método cuasi-Newton para ecuaciones no lineales con un jacobiano escaso" . Matemáticas de la Computación . 24 (109): 27–30. doi : 10.1090 / S0025-5718-1970-0258276-9 . ISSN 0025-5718 .
- ^ Klement, enero (23 de noviembre de 2014). "Sobre el uso de algoritmos de cuasi-Newton de la clase Broyden para la correlación de modelo a prueba" . Revista de Tecnología y Gestión Aeroespacial . 6 (4): 407–414. doi : 10.5028 / jatm.v6i4.373 . ISSN 2175-9146 .
- ^ "Métodos de clase Broyden - Intercambio de archivos - MATLAB Central" . www.mathworks.com . Consultado el 4 de febrero de 2016 .
Otras lecturas
- Dennis, JE ; Schnabel, Robert B. (1983). Métodos numéricos para optimización no restringida y ecuaciones no lineales . Acantilados de Englewood: Prentice Hall. págs. 168-193. ISBN 0-13-627216-9.
- Fletcher, R. (1987). Métodos prácticos de optimización (Segunda ed.). Nueva York: John Wiley & Sons. págs. 44–79 . ISBN 0-471-91547-5.
enlaces externos
- Explicación básica simple: la historia del arquero ciego