Algoritmo di Gauss-Newton: differenze tra le versioni

Versione delle 18:56, 5 apr 2020

Versione attuale delle 08:00, 16 mar 2025

(6 versioni intermedie di 5 utenti non mostrate)

Riga 3:

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|upright=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 107:

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 140:

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-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 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 ==