Algoritmo de Gauss-Newton

En matemáticas, el algoritmo de Gauss-Newton se utiliza para resolver problemas no lineales de mínimos cuadrados. Es una modificación del método de optimización de Newton que no usa segundas derivadas y se debe a Carl Friedrich Gauss.

El problema

Dadas m funciones f₁,..., f_m de n parámetros p₁,..., p_n con m≥n, queremos minimizar la suma

${\displaystyle S(p)=\sum _{i=1}^{m}(f_{i}(p))^{2};}$

donde p se refiere al vector de parámetros: p=(p₁,..., p_n).

El algoritmo

El algoritmo de Gauss-Newton es un procedimiento iterativo. Esto significa que debemos proporcionar una estimación inicial del vector de parámetros, que denominaremos p^0.

Estimaciones posteriores p^k para el vector de parámetros son producidas por la relación recurrente:

${\displaystyle p^{k+1}=p^{k}-{\Big (}J_{f}(p^{k})^{\top }J_{f}(p^{k}){\Big )}^{-1}J_{f}(p^{k})^{\top }f(p^{k}),}$

donde f=(f₁,..., f_m), y J_f(p) denota el Jacobiano de f en p (nótese que no es necesario que J_f sea cuadrada).

La matriz inversa, en la práctica, nunca se computa explícitamente. En lugar de ello se utiliza

${\displaystyle p^{k+1}=p^{k}+\delta ^{k},\,}$

y se computa la actualización de δ^k resolviendo el sistema lineal

${\displaystyle J_{f}(p^{k})^{\top }J_{f}(p^{k})\,\delta ^{k}=-J_{f}(p^{k})^{\top }f(p^{k}).}$

Una buena implementación del algoritmo de Gauss-Newton utiliza también un algoritmo de búsqueda lineal: en lugar de la fórmula anterior para p^k+1, se utiliza

${\displaystyle p^{k+1}=p^{k}+\alpha ^{k}\,\delta ^{k},}$

donde el número α^k es de algún modo óptimo.

Otros algoritmos

La relación de recurrencia del Método de Newton para minimizar la función S es

${\displaystyle p^{k+1}=p^{k}-[H(S)(p^{k})]^{-1}J_{S}(p^{k}),\,}$

donde ${\displaystyle J_{S}}$ y ${\displaystyle H(S)}$ denotan el Jacobiano y Hessiano de S respectivamente. Utilizando el método de Newton para minimizar la función

${\displaystyle S(p)=\sum _{i=1}^{m}(f_{i}(p))^{2},}$

obtenemos la relación recurrente

${\displaystyle p^{k+1}=p^{k}-\left(J_{f}(p)^{\top }J_{f}(p)+\sum _{i=1}^{m}f_{i}(p)\,H(f_{i})(p)\right)^{-1}J_{f}(p)^{\top }f(p).}$

Podemos concluir que el método de Gauss-Newton es el mismo que el método de Newton, pero ignorando el término de la matriz Hessiana Σ f H(f).

Otros algoritmos utilizados para resolver el problema de los mínimos cuadrados incluyen el Algoritmo de Levenberg-Marquardt y de descenso de gradiente.

• Datos: Q1496373