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

$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⁰.

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

$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

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

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

$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

$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

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

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

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

obtenemos la relación recurrente

$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