Algorisme de Gauss-Newton

A matemàtiques, l'algorisme de Gauss-Newton s'utilitza per a resoldre problemes no lineals de mínims quadrats.[1] É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.[2]

El problema

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

S ( p ) = ∑ i = 1 m ( f i ( p ) ) 2 . {\displaystyle S(p)=\sum _{i=1}^{m}(f_{i}(p))^{2}.}

on, p fa al vector ( p 1 ,..., 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 0 .

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 ) ⊤ J f ( p k ) ) − 1 J f ( p k ) ⊤ f ( p k ) , {\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}),}

on f = ( f 1 ,..., 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 + δ k , {\displaystyle P^{k+1}=p^{k}+\delta ^{k},\,}

i es computa l'actualització de δ k resolent el sistema lineal

J f ( p k ) ⊤ J f ( p k ) δ k = − J f ( p k ) ⊤ f ( p k ) . {\displaystyle J_{f}(p^{k})^{\top }J_{f}(p^{k})\,\delta ^{k}=-J_{f}(p^{k})^{\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 + α k δ k , {\displaystyle 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 ) , {\displaystyle P^{k+1}=p^{k}-[H(S)(p^{k})]^{-1}J_{S}(p^{k}),\,}

on J S {\displaystyle J_{S}} i H ( S ) {\displaystyle H(S)} denoten el Jacobià i Hessiana de S respectivament. utilitzant el mètode de Newton per a la funció

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

obtenim la relació recurrent

P k + 1 = p k − ( J f ( p ) ⊤ J f ( p ) + ∑ i = 1 m f i ( p ) H ( f i ) ( p ) ) − 1 J f ( p ) ⊤ f ( p ) . {\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).}

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.

Referències

  1. ↑ «Gauss-Newton algorithm for nonlinear models». Arxivat de l'original el 2019-06-10. [Consulta: 16 juny 2019].
  2. ↑ Stephanie. «Gauss-Newton Method: Brief Overview» (en anglès), 20-08-2017. Arxivat de l'original el 2019-06-16. [Consulta: 16 juny 2019].