Algorisme de Gauss-Newton

De Viquipèdia
Dreceres ràpides: navegació, cerca

A matemàtiques, el 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 menys empreu segones derivades i es deu a Carl Friedrich Gauss.

El problema[modifica | modifica el codi]

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

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

on, p fa al vector ( p 1 ,..., p n ).

L'algorisme[modifica | modifica el codi]

El 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 - \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+\delta^k, \,

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

 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+\alpha^k \, \delta^k,

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

Altres algorismes[modifica | modifica el codi]

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 - \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.