Método de Broyden

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.^[1]​

Para hallar la solución del sistema de ecuaciones ${\displaystyle \displaystyle f_{i}(x_{1},x_{2},...,x_{n})=0}$, con ${\displaystyle i=1,2,...,n}$, el método de Newton emplea el jacobiano ${\displaystyle \displaystyle J}$ en cada iteración, además de calcular su inversa. Sin embargo, computar ese jacobiano es una operación difícil y costosa. La idea que subyace en el método de Broyden consiste en computar el jacobiano entero solamente en la primera iteración, y llevar a cabo una actualización de rango 1 en las demás iteraciones.

${\displaystyle f_{i}(x_{1},x_{2},...,x_{n})}$ se supone continua y diferenciable en un conjunto abierto en ${\displaystyle \mathbb {R} ^{n}}$ con derivadas parciales continuas en ese abierto.^[2]​

En 1979, Gay demostró que, cuando se aplica el método de Broyden a un sistema lineal, se requieren 2n pasos.^[3]​

Descripción del método

El método de Broyden considera el método de la secante y establece una generalización de él para el espacio multidimensional.

El método de la secante sustituye la primera derivada ${\displaystyle \displaystyle f'(x_{n})}$ por la aproximación de diferencia finita

${\displaystyle f'(x_{n})\simeq {\frac {f(x_{n})-f(x_{n-1})}{x_{n}-x_{n-1}}}}$

y procede según el método de Newton:

${\displaystyle x_{n+1}=x_{n}-{\frac {1}{f'(x_{n})}}f(x_{n})}$

Broyden establece una generalización de esa fórmula para un sistema de ecuaciones mediante una sustitución de ${\displaystyle {\frac {1}{f'(x_{n})}}}$ por la inversa del jacobiano ${\displaystyle \displaystyle J}$. Este se determina por medio de la ecuación de la secante (la aproximación de diferencia finita):

${\displaystyle J_{n}\cdot (x_{n}-x_{n-1})\simeq F(x_{n})-F(x_{n-1})}$

Sin embargo, esta ecuación está infradeterminada por más de una dimensión.

Broyden sugiere un procedimiento que consta de los siguientes 3 pasos:

1) Emplear la aproximación del jacobiano ${\displaystyle \displaystyle J_{n-1}}$

2) Tomar la solución de la ecuación de la secante que suponga la modificación mínima de ${\displaystyle \displaystyle J_{n-1}}$ (entendiendo por mínima que se dé una minimización de la norma de Frobenius ${\displaystyle \displaystyle \|J_{n}-J_{n-1}\|_{F}}$)

${\displaystyle J_{n}=J_{n-1}+{\frac {\Delta F_{n}-J_{n-1}\Delta x_{n}}{\|\Delta x_{n}\|^{2}}}\Delta x_{n}^{T}}$

3) Continuar según el método de Newton:

${\displaystyle x_{n+1}=x_{n}-J_{n}^{-1}F(x_{n}).}$

En esa última fórmula,

${\displaystyle \displaystyle x_{n}=(x_{1}[n],...,x_{k}[n])}$

y

${\displaystyle \displaystyle F_{n}(x)=(f_{1}(x_{1}[n],...,x_{k}[n]),...,f_{k}(x_{1}[n],...,x_{k}[n])}$

son vectores columna de k elementos en un sistema de k dimensiones.

Así:

${\displaystyle \Delta x_{n}={\begin{bmatrix}x_{1}[n]-x_{1}[n-1]\\...\\x_{k}[n]-x_{k}[n-1]\end{bmatrix}}\quad {\text{y}}\quad \Delta F_{n}={\begin{bmatrix}f_{1}(x_{1}[n],...,x_{k}[n])-f_{1}(x_{1}[n-1],...,x_{k}[n-1])\\...\\f_{k}(x_{1}[n],...,x_{k}[n])-f_{k}(x_{1}[n-1],...,x_{k}[n-1])\end{bmatrix}}.}$

Broyden sugiere también la fórmula de Sherman-Morrison para actualizar directamente el inverso de la aproximación del jacobiano por la aproximación de diferencia finita:

${\displaystyle J_{n}^{-1}=J_{n-1}^{-1}+{\frac {\Delta x_{n}-J_{n-1}^{-1}\Delta F_{n}}{\Delta x_{n}^{T}J_{n-1}^{-1}\Delta F_{n}}}(\Delta x_{n}^{T}J_{n-1}^{-1})}$

Este último se conoce como el « buen método de Broyden».

Se puede obtener a partir de él una técnica similar empleando una modificación ligeramente distinta de ${\displaystyle J_{n-1}}$ que minimiza en su lugar ${\displaystyle \displaystyle \|J_{n}^{-1}-J_{n-1}^{-1}\|_{F}}$

Tal sería el llamado « mal método de Broyden»:

${\displaystyle J_{n}^{-1}=J_{n-1}^{-1}+{\frac {\Delta x_{n}-J_{n-1}^{-1}\Delta F_{n}}{\Delta F_{n}^{T}\Delta F_{n}}}\Delta F_{n}^{T}}$

Pero, en cuanto a lo de « mal método», véase "A faster Broyden method" ("Un método de Broyden más rápido").^[4]​

Se han sugerido muchos otros procedimientos cuasinewtonianos en el campo de la optimización, en el que se busca un máximo o un mínimo hallando la raíz de la primera derivada, o el gradiente si se trata de un espacio multidimensional. Se califica al jacobiano del gradiente de «hessiano», y es simétrico, lo que añade restricciones a la hora de llevar a cabo su actualización.

Fórmula de Sherman Morrison^[5]​

Si A es una matriz no singular y ${\displaystyle x}$ y ${\displaystyle y}$ son vectores con ${\displaystyle y^{t}A^{-1}x\neq -1}$ entonces ${\displaystyle A+xy^{t}}$ es no singular y

${\displaystyle (A+xy^{t})^{-1}=A^{-1}-{A^{-1}xy^{t}A^{-1} \over 1+y^{t}A^{-1}x}}$

Esta fórmula de Sherman-Morrison permite calcular la inversa de una matriz a partir de la inversa del Jacobiano, es por eso que solo se requiere en la primera iteración del método de Broyden, ya que para las iteraciones subsecuentes se va empleando la aproximación de la iteración anterior.

Referencias

Véase también

• Rango (álgebra lineal)

• Método de la secante

• Método de Newton

Enlaces externos

• Artículo sobre los métodos cuasinewtonianos en la Wikipedia en inglés.

• Artículo sobre los métodos cuasinewtonianos en la Wikipedia en francés.

• Artículo sobre los métodos cuasinewtonianos en la Wikipedia en alemán.

• Empleo de métodos cuasinewtonianos en el campo de la optimización y actualizaciones de rango 1 y 2.

• Artículo sobre el uso del método de Newton en el campo de la la optimización en la Wikipedia en inglés.

• Artículo sobre la fórmula de Davidon–Fletcher–Powell en la Wikipedia en inglés.

• Artículo sobre el método Broyden–Fletcher–Goldfarb–Shanno (método BFGS) en la Wikipedia en inglés.

• John H. Mathews: "Cursillo sobre el método de Broyden". En inglés.