Algorisme de Gauss-Newton

A matemàtiques, l'algorisme de Gauss-Newton s'utilitza per a resoldre problemes no lineals de mínims quadrats. És una modificació del mètode d'optimització de Newton que no depèn de calcular segones derivades i es deu a Carl Friedrich Gauss.

El problema

Donades m funcions f ₁ ,..., f _m de n paràmetres p ₁ ,..., p _n amb m ≥ n , volem minimitzar la suma

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

on, p fa al vector ( p ₁ ,..., p _n ).

L'algorisme

L'algorisme de Gauss-Newton és un procediment iteratiu. Això significa que hem de proporcionar una estimació inicial del paràmetre vector que anomenarem p ⁰ .

Estimacions posteriors p ^k per al vector paràmetre són produïdes per la relació recurrent:

$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),$

on f = ( f ₁ ,..., f _m ) i J _f ( p ) denota el Jacobià de f a p (noti's que no cal que J _f sigui quadrada).

La matriu inversa, en la pràctica, mai es computa explícitament. en lloc d'ells s'utilitza

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

i es computa l'actualització de δ ^k resolent 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 bona implementació de l'algorisme de Gauss-Newton utilitza també un algorisme de cerca lineal: en lloc de la fórmula anterior per p ^{k +1} , s'utilitza

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

on el nombre α ^k és d'alguna manera òptim.

Altres algorismes

La relació de recurrència del Mètode de Newton per minimitzar la funció S és

$P^{k+1}=p^k-[H(S)(p^k){]}^{-1}{J}_S(p^k),$

on $J_S$ i $H(S)$ denoten el Jacobià i Hessiana de S respectivament. utilitzant el mètode de Newton per a la funció

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

obtenim la relació recurrent

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

Podem concloure que el mètode de Gauss-Newton és el mateix que el metodode Newton ignorant el terme Σ f H ( f ).

Altres algorismes utilitzats per a resoldre el problema dels mínims quadrats inclouen l'algorisme de Levenberg-Marquardt algorithm i de descens de gradient.