Gauss–Newton algoritmen

Gauss–Newton algoritmen er ei tilnærming av Newtons metode i optimering og vert primært nytta for å løysa ikkje-lineære minstekvadratersproblem. I likskap med Newtons metode i optimering, så finn Gauss-Newton algoritmen stasjonære punkt for ein gjeven funksjon.

Til samanlikning er Gauss–Newton algoritmen meir robust enn Newtons metode i optimering. Ein er alltid garantert at retninga algoritmen går i er ei nedgangsretning, i motsetning til Newtons metode i optimering. Om algoritmen konvergerer er ein altså garantert at det vert konvergens mot eit stasjonært punkt. I motsetning til Newtons metode, krev heller ikkje Gauss–Newton algoritmen andrederiverte i utrekninga si. Dette gjev færre utrekningar per steg enn i Newtons metode.

Definisjon

Algoritmen er særs lik Newtons metode i optimering, den einaste skilnaden er at ein tilnærmar den andrederiverte ved å rekna ut

$\Delta ^{2}f\approx J_{r}^{T}J_{r}$

I staden for å rekna ut den andrederiverte direkte. Dette gjev den følgjande iterative algoritmen, gjeve eit særskilt startpunkt $x_{0}$ og ein funksjon $f$ som ein ønskjer å minimera:

$x_{n+1}=x_{n}-(J_{r}(x_{n})^{T}J_{r}(x_{n}))^{-1}\Delta f(x_{n})$

$J_{f}$ er her kjend som jakobimatrisa for funksjonen $f$ og $\Delta f(x_{n})$ er den deriverte av $f(x_{n})$.

Ein er som nemnt garantert at retninga algoritmen går i er ei nedgangsretning, men det er framleis ingen garanti at algoritmen vil konvergera. I praksis vil ein implementera ei steglengde i itereringa og nytta einkvan regel, til dømes armijos regel for å sørgja for ei stor nok nedgang ved kvar iterering så algoritmen konvergerer.