Algoritmo di Gauss-Newton: differenze tra le versioni

Versione delle 01:17, 8 nov 2018

Versione attuale delle 08:00, 16 mar 2025

(16 versioni intermedie di 11 utenti non mostrate)

Riga 1:

[[File:Regression pic assymetrique.gif|thumb|300pxupright=1.4|Regressione di una curva con un modello a picco asimmetrico, utilizzando l'algoritmo di Gauss–Newton con un fattore di smorzamento <math>\alpha</math> variabile. <br /> Sopra: dati grezzi e curva del modello.<br /> Sotto: evoluzione della somma normalizzata dei quadrati dei residui.]]

L''''algoritmo di Gauss–Newton''' è un metodo [[iterazione|iterativo]] per risolvere problemi di [[minimi quadrati]] e [[regressione non lineare|regressioni non lineari]]. È una versione modificata del metodo di Newton per trovare un [[Massimo e minimo di una funzione|minimo]] di una [[funzione (matematica)|funzione]]. Diversamente da quest'ultimo, l'algoritmo di Gauss–Newton può essere utilizzato solo per minimizzare una somma di funzioni al quadrato, ma possiede il vantaggio che le derivate seconde, spesso faticose da calcolare, non sono richieste.

I problemi di minimi quadrati non lineari compaiono, aad esempio, nella [[regressione non lineare]], in cui si cercano i parametri tali che il modello sia in buono accordo con le osservazioni disponibili.

Il nome del metodo deriva dai matematici [[Carl Friedrich Gauss]] e [[Isaac Newton]].

Riga 35:

:<math> \boldsymbol \beta^{(s+1)} = \boldsymbol \beta^{(s)} + \left(\mathbf{J_f}^\mathsf{T} \mathbf{J_f} \right)^{-1} \mathbf{ J_f}^\mathsf{T} \mathbf{r}(\boldsymbol \beta^{(s)}). </math>

Da notare che <math>\left(\mathbf{J_f}^\mathsf{T} \mathbf{J_f} \right)^{-1} \mathbf{ J_f} ^\mathsf{T}</math> è la pseudoinversa di <math>\mathbf{J_f}</math>. Nell'algoritmo, l'assunzione <math>m\geq n</math> è necessaria, altrimenti la matrice <math> \mathbf{J_r}^\mathsf{T} \mathbf{J_r}</math> non è invertibile e l'le equazioni non possono essere risolte (almeno in modo unico).

L'algoritmo di Gauss–Newton si ottiene dall'[[approssimazione lineare]] del vettore delle funzioni <math>r_i</math> utilizzando il [[teorema di Taylor]]. Infatti, a ogni iterazione si ottiene:

Riga 45:

è un problema dei minimi quadrati lineare, che si risolve esplicitamente.

L'equazioneLe equazioni normali sono <math>n</math> equazioni lineari simultanee nell'incremento <math>\Delta</math> incognito. Si possono risolvere in un solo passaggio, usando la [[decomposizione di Cholesky]], o, ancora meglio, la [[fattorizzazione QR]] di <math>\mathbf{J_r}</math>. Per sistemi grandi, può essere più efficiente un [[metodo iterativo]], come quello del [[metodo del gradiente coniugato|gradiente coniugato]]. Se esiste una dipendenza lineare tra le colonne di <math>\mathbf{J_r}</math>, le iterazioni falliranno a causa della singolarità di <math>\mathbf{J_r}^\mathsf{T} \mathbf{J_r}</math>.

==Esempio==

[[File:Gauss Newton illustration.png|thumb|right|280pxupright=1.3|Curva di best fit ottenuta (in blu), con <math>\hat\beta_1=0.362</math> and <math>\hat\beta_2=0.556</math>, insieme ai dati osservati (in rosso).]]

In questo esempio, l'algoritmo di Gauss–Newton viene usato per la regressione della velocità <math>V</math> di formazione del prodotto in una reazione catalizzata da un [[enzima]] in relazione alla concentrazione del substrato <math>[S]</math>, secondo il [[Cinetica di Michaelis-Menten|modello di Michaelis-Menten]]. I dati misurati sono riportati nella seguente tabella. Le incertezze di ogni misura sono state messe uguali a 1.

:{|class="wikitable" style="text-align: center;"

! <math>i</math>

Riga 94:

==Convergenza del metodo==

Si può mostrare<ref>Björck (1996), p. 260.</ref> che l'incremento <math>\Delta</math> è una [[direzione di discesa]] per <math>S</math>, e, se l'algoritmo converge, che il limite è un [[punto critico (matematica)|punto stazionario]] di <math>S</math>. Tuttavia, la convergenza non è garantita, nemmeno quella locale come nel [[metodo delle tangenti]], o sotto le comuni condizioni di Wolfe.<ref>{{Cita pubblicazione|titolo=The divergence of the BFGS and Gauss Newton Methods |cognome1=Mascarenhas |rivista=Mathematical Programming |data=2013 |volume=147 |numero=1 |pp=253–276253-276 |doi=10.1007/s10107-013-0720-6 |arxiv=1309.7922}}</ref>

La velocità di convergenza di Gauss–Newton può diventare quadratica.<ref>Björck (1996), p. 341, 342.</ref> L'algoritmo potrebbe anche convergere lentamente o affatto se la stima iniziale è lontana dal minimo oppure la matrice <math>\mathbf{J_r^\mathsf{T} J_r}</math> è [[condizionamento (matematica)|mal condizionata]]. Per esempio, si consideri il problema con <math>m = 2</math> equazioni e <math>n = 1</math> variabili, dato da

Riga 103:

Il minimo è per <math>\beta = 0</math>. (In realtà il minimo è per <math>\beta = -1</math> se <math>\lambda = 2</math>, poiché <math>S(0) = 1^2 + (-1)^2 = 2</math>, ma <math>S(-1) = 0</math>.) Se <math>\lambda = 0</math>, allora il problema diventa lineare e il metodo trova il minimo in una sola iterazione. Se <math>|\lambda| < 1</math>, allora l'algoritmo converge linearmente e l'errore decresce asintoticamente di un fattore <math>|\lambda|</math> a ogni iterazione. Tuttavia, se <math>|\lambda| > 1</math>, non c'è convergenza nemmeno locale.<ref>Fletcher (1987), p. 113.</ref>

== Derivazione dal metodo di Newton ==

In questo paragrafo, l'algoritmo di Gauss–Newton verrà derivato dal metodo di Newton per l'ottimizzazione di funzione. Come conseguenza, la velocità di convergenza dell'algoritmo di Gauss–Newton può essere quadratico sotto certe condizioni di regolarità. In generale (sotto condizioni più deboli), la convergenza è lineare.<ref>{{Cita web |url=http://www.henley.ac.uk/web/FILES/maths/09-04.pdf# |titolo=Copia archiviata |accesso=2 novembre 2018 |urlarchivio=https://web.archive.org/web/20160804022151/http://www.henley.ac.uk/web/FILES/maths/09-04.pdf# |dataarchivio=4 agosto 2016 |urlmorto=sì }}</ref>

La [[relazione di ricorrenza]] per il metodo di Newton per la minimizzazione della funzione <math>S</math> di parametri <math>\boldsymbol\beta</math> è

:<math> \boldsymbol\beta^{(s+1)} = \boldsymbol\beta^{(s)} - \mathbf H^{-1} \mathbf g, </math>

dove <math>\mathbf g</math> indica il vettore [[gradiente]] di <math>S</math>, e <math>\mathbf H</math> la sua [[matrice hessiana]].

Riga 132:

# Le funzioni sono quasi-lineari, in modo che <math>\frac{\partial^2 r_i}{\partial \beta_j \partial \beta_k}</math> sia relativamente piccolo.

== Versioni migliorate dell'algoritmo ==

Con l'algoritmo di Gauss–Newton, la somma dei quadrati dei residui <math>S</math> può non decrescere a ogni interazione. Tuttavia, poiché <math>\Delta</math> è una direzione di discesa, a meno che <math>S(\boldsymbol \beta^s)</math> sia un punto stazionario, vale che <math>S(\boldsymbol \beta^s+\alpha\Delta) < S(\boldsymbol \beta^s)</math> per ogni <math>\alpha>0</math> sufficientemente piccolo. Quindi, se il metodo diverge, una soluzione è di impiegare una frazione <math>\alpha</math> dell'incremento <math>\Delta</math>, utilizzando la seguente formula:

:<math> \boldsymbol \beta^{s+1} = \boldsymbol \beta^s + \alpha \Delta.</math>.

In altre parole, il vettore incremento è troppo lungo, ma è diretto verso il basso, perciò avanzare soltanto di una frazione di cammino diminuirà il valore della funzione oggettiva <math>S</math>. Si può trovare il valore ottimale di <math>\alpha</math> usando un algoritmo di ''line search'', cioè il valore <math>\alpha</math> viene determinato trovando quello che minimizza <math>S</math>, di solito con un metodo di ricerca diretta nell'intervallo <math>0 < \alpha < 1</math>.

Nei casi in cui la frazione ottimale <math>\alpha</math> è vicina a zero, un metodo alternativo per il trattamento della divergenza è l'utilizzo dell'[[algoritmo di Levenberg–MarquardtLevenberg-Marquardt]], anche conosciuto come "metodo della regione di confidenza".<ref name="ab"/> Le equazioni normali sono modificate in modo che l'incremento sia rotato verso la direzione di [[Gradiente (funzione)|massima decrescita]] ,

:<math>\left(\mathbf{J^{\mathrm T} J + \lambda D}\right) \Delta = -\mathbf{J}^{\mathrm T} \mathbf{r},</math>

dove <math>\mathbf D</math> è una [[matrice diagonale]] positiva. Da notare che quando <math>\mathbf D</math> è la matrice identità <math>\mathbf I</math> e <math>\lambda \to +\infty</math>, allora <math>\lambda \Delta = \lambda \left(\mathbf{J^{\mathrm T} J} + \lambda \mathbf{I}\right)^{-1} \left(-\mathbf{J}^{\mathrm T} \mathbf{r}\right) = \left(\mathbf{I} - \mathbf{J^{\mathrm T} J}/

\lambda + \cdots \right) \left(-\mathbf{J}^{\mathrm T} \mathbf{r}\right) \to -\mathbf{J}^{\mathrm T} \mathbf{r}</math>, perciò la direzione di <math>\Delta</math> si avvicina alla direzione del gradiente negativo <math>-\mathbf{J}^{\mathrm T} \mathbf{r}</math>.

Riga 161:

== Algoritmi collegati ==

In un metodo quasi-Newton, come quello dovuto a ''Davidon, Fletcher e Powell'' oppure a ''Broyden–Fletcher–Goldfarb–Shanno'' (metodo BFGS method), si calcola numericamente una stima della Hessiana <math>\frac{\partial^2 S}{\partial \beta_j \partial\beta_k}</math> usando solo le derivate prime <math>\frac{\partial r_i}{\partial\beta_j}</math>, in modo che solo dopo <math>n</math> cicli di perfezionamento il metodo si avvicina approssimativamente a quello di Newton in termini di prestazioni. Da notare che i metodi quasi-Newton possono minimizzare funzioni arbitrarie a valori reali, mentre Gauss–Newton, Levenberg–Marquardt, ecc. risolvono solo problemi di minimi quadrati non lineari.

Un altro metodo per risolvere problemi di minimo usando solo derivate prime è la [[discesa del gradiente]]. Tuttavia, quest'ultimo metodo non considera le derivate seconde nemmeno approssimativamente, perciò è altamente inefficiente per molte funzioni, specialmente se i parametri hanno una forte correlazione.

Riga 172:

|titolo= Numerical methods for least squares problems

|editore= SIAM, Philadelphia |anno= 1996 | isbn = 0-89871-360-9 }}

* {{Cita libro|cognome1=Fletcher |nome1=Roger |titolo=Practical methods of optimization |url=https://archive.org/details/practicalmethods0000flet |editore=[[John Wiley & Sons]] |città=New York |edizione=2nd | isbn=978-0-471-91547-8 |anno=1987 }}

*{{Cita libro|cognome= Nocedal |nome= Jorge |autore2=Wright, Stephen

|titolo= Numerical optimization

|url= https://archive.org/details/numericaloptimiz0000noce |editore= New York: Springer |anno= 1999 | isbn = 0-387-98793-2 }}

== Collegamenti esterni ==

=== Implementazioni ===

*[https://www.artelys.com/en/optimization-tools/knitro Artelys Knitro] è un risolutore non lineare con un'implementazione del metodo di Gauss–Newton. È scritto in linguaggio [[C (linguaggio)|linguaggio C]] e possiede interfacce per C++/C#/Java/Python/MATLAB/R.

{{portale|matematica}}

[[Categoria:AnalisiAlgoritmi numericadi ottimizzazione|Gauss-Newton]]