Gauss–Newtons metod

Anpassning av en brusig kurva med en asymmetrisk modell för topparna med Gauss-Newton-algoritmen med variabel dämpningsfaktor α.

Överst: Rådata och modell.

Nederst: Utveckling av den normaliserade kvadratsumman av felen.

Gauss-Newtons metod används för att lösa icke-linjära minsta kvadrat-problem. Dessa uppstår till exempel vid icke-linjär regression, där parametrar i en modell söks så att modellen stämmer väl överens med tillgängliga observationer.

Det är en variant av Newtons metod för att hitta ett minimum av en funktion. Till skillnad från Newtons metod kan Gauss-Newton-algoritmen endast användas för att minimera summan av kvadrerade funktionsvärden, men den har fördelen att andraderivator, som kan vara svåra att beräkna, inte krävs.[1]

Metoden är uppkallad efter matematikerna Carl Friedrich Gauss och Isaac Newton och presenterades först i Gauss verk från 1809 Theoria motus corporum coelestium in sectionibus conicis solem ambientum.[2]

Beskrivning

Givna funktioner (ofta kallade rester) av variabler med [a] hittar Gauss-Newton-algoritmen iterativt värdet av variablerna som minimerar kvadratsumman [3]

Man börjar med en första gissning och fortsätter iterativt

där elementen i jakobianen är

r och β är kolumnvektorer och symbolen betecknar matristransponering.

Beräkningar

Vid varje iteration, kan uppdateringen hittas genom att ordna om föregående ekvation i följande två steg:

Med beteckningarna , , och , förvandlas detta till den vanliga matrisekvationen , som sedan kan lösas på en mängd olika metoder (se anmärkningar ).

När är komplex den konjugerade formen ska användas: . Om m = n, kan iterationen förenklas till

vilket är en direkt generalisering av Newtons metod i en dimension.

Normalekvationerna är n samtidiga linjära ekvationer i okända steg . De kan lösas i ett steg, med hjälp av Choleskyuppdelning, eller, bättre, QR-faktorisering av .[4] För stora system kan en iterativ metod, såsom konjugatgradientmetoden, vara mer effektiv. Om det finns ett linjärt beroende mellan kolumner i J r kommer iterationerna att misslyckas, då blir singular.

Beräkningar för dataanpassning

Inom dataanpassning, där målet är att hitta parametrarna så att en given modell fungerar passar bäst på vissa datapunkter , är funktionerna är residualerna :

Sedan kan Gauss-Newton-metoden uttryckas i termer av jakobianen av funktionen som

Observera att är den vänstra pseudoinversen av .

Exempel

Beräknad kurva erhållen med och (i blått) kontra observerade data (i rött).

I det här exemplet kommer Gauss-Newton-metoden att användas för att anpassa en modell till vissa data genom att minimera summan av kvadrater av fel mellan data och modellens förutsägelser.

I ett biologiskt experiment som studerade sambandet mellan substratkoncentration [S] och reaktionshastighet V i en enzymmedierad reaktion, erhölls data i följande tabell.

Det är önskvärt att hitta en kurva (modellfunktion) av formen

som bäst passar data i minsta kvadrat-mening. Då bestäms parametrarna och .

Beteckna med och värdena för [S] (koncentration) och V (hastighet) för . Låt och och hitta och så att summan av kvadraterna av residualerna

minimeras.

Jakobianen av vektorn av residualerna med hänsyn till de okända är en -matrismed där den :te raden har elementen

Man börjar med de första uppskattningarna och och efter fem iterationer av Gauss-Newton-metoden erhålls de optimala värdena och erhålls. Summan av kvadraterna på residualerna minskade från initialvärdet 1,445 till 0,00784 efter den femte iterationen. Figuren till höger visar kurvan som bestäms av modellen för de optimala parametrarna med de observerade data.

Härledning från Newtons metod

I det följande kommer Gauss–Newton-metoden att härledas från Newtons metod för funktionsoptimering via en approximation. Som en konsekvens kan konvergenshastigheten för Gauss-Newton-metoden vara kvadratisk under vissa regularitetsförhållanden. I allmänhet (under svagare förhållanden) är konvergenshastigheten linjär.[5]

Iterationsekvationen för Newtons metod för att minimera en funktion S av parametrarna är

där g betecknar gradientvektorn för S och H betecknar den hessianen för S .

Eftersom , ges gradienten av

Hessianens element beräknas genom att derivera gradientelementen, , med avseende på  :

Gauss-Newton-metoden erhålls genom att försumma andra ordningens derivator (den andra termen i summanderna). Det vill säga, hessianen approximeras av

där är element i jakobianen J r. Gradienten och den ungefärliga hessianen kan skrivas i matrisnotation som

Dessa uttryck ersätts i iterationsekvationen ovan för att erhålla ekvationerna

Konvergens av Gauss-Newton-metoden garanteras inte i alla fall. Uppskattningen

behöver gälla för att kunna försumma andra ordningens derivator. Det kan ske i två fall och då förväntas konvergens: [6]

  1. Funktionsvärdena är små i storleksordningen, åtminstone runt minimum.
  2. Funktionerna är bara "milt" olinjära, så att är relativt liten i omfattning.

Anmärkningar

  1. ^ Antagandet m ≥ n i algoritm är nödvändigt, då annars är matrisen inte inverterbar och normalekvationerna kan inte lösas (åtminstone inte entydigt).

Referenser

Den här artikeln är helt eller delvis baserad på material från engelskspråkiga Wikipedia.

Noter

  1. ^ Mittelhammer, Ron C.; Miller, Douglas J.; Judge, George G. (2000). Econometric Foundations. Cambridge: Cambridge University Press. sid. 197–198. ISBN 0-521-62394-4. https://books.google.com/books?id=fycmsfkK6RQC&pg=PA197 
  2. ^ Floudas, Christodoulos A.; Pardalos, Panos M. (2008). Encyclopedia of Optimization. Springer. sid. 1130. ISBN 9780387747583 
  3. ^ Björck 1996.
  4. ^ Ramsin 1976, s. 152.
  5. ^ S. Gratton, A.S. Lawless och N.K. Nichols. ”Approximate Gauss-Newton methods for nonlinear least squares problems”. The University of Reading. Arkiverad från originalet den 4 augusti 2016. https://web.archive.org/web/20160804022151/http://www.henley.ac.uk/web/FILES/maths/09-04.pdf. Läst 18 december 2022. 
  6. ^ Nocedal 1999, s. 259.

Källor

  • Björck, Åke (1996). Numerical methods for least squares problems. Philadelphia, Pa: SIAM, Society for Industrial and Applied Mathematics. ISBN 0898713609 
  • Fletcher, Roger (1987). Practical methods of optimization (2nd). New York: John Wiley & Sons. ISBN 978-0-471-91547-8. https://archive.org/details/practicalmethods0000flet 
  • Nocedal, Jorge; Wright, Stephen (1999). Numerical optimization. New York: Springer. ISBN 0-387-98793-2 
  • Ramsin, Håkan (1976). Ickelinjär optimering. Lund: Liber läromedel. ISBN 91-40-04288-X 

Media som används på denna webbplats

Gauss Newton illustration.png
Illustration of Gauss-Newton applied to a curve-fitting problem with noisy data. What is plotted is the best fit curve versus the data with the fitting parameters obtained via Gauss-Newton.
Regression pic assymetrique.gif
Författare/Upphovsman: Cdang (Christophe Dang Ngoc Chan), Licens: CC BY-SA 3.0
Successive steps of Gauss-Newton regression, with variable damping factor α, to fit a dissymetrical noisy peak. Pictures created with Scilab, animated with The Gimp.