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-(J_f(p^k{)}^{\mathrm{\top }}{J}_f(p^k){)}^{-1}{J}_f(p^k{)}^{\mathrm{\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{)}^{\mathrm{\top }}{J}_f(p^k){\delta }^k=-J_f(p^k{)}^{\mathrm{\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-{(J_f(p{)}^{\mathrm{\top }}{J}_f(p)+\sum _{i=1}^m{f}_i(p)H(f_i)(p))}^{-1}{J}_f(p{)}^{\mathrm{\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.