Algoritmo de Gauss-Newton

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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[editar]

dadas m funciones f1,..., fm de n parámetros p1,..., pn con mn, queremos minimizar la suma

 S(p) = \sum_{i=1}^m (f_i(p))^2.

donde, p se refiere al vector (p1,..., pn).

El algoritmo[editar]

El algorimo de Gauss-Newton es un procedimiento iterativo. Esto significa que debemos proporcionar una estimación inicial del parámetro vector que denominaremos p0.

Estimaciones posteriores pk para el vector parámetro 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=(f1,..., fm) yJf(p) denota el Jacobiano de f en p (nótese que no es necesario que Jf sea cuadrada).

La matriz inversa, en la práctica, nunca se computa explícitamente. en lugar de ellos 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 pk+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[editar]

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 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 metodode Newton ignorando el término Σ f H(f).

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