Gauss–Newtons metod

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. 

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.

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

 

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

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  och reaktionshastighet  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   (koncentration) och  (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. 

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:  

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

Anmärkningar

Referenser

Noter

Källor

 .
 

Optimeringsalgoritmer