web.archive.org

Gauss-Newton algorithm: Information from Answers.com

️Wed Jul 01 2015

In mathematics, the Gauss-Newton algorithm is used to solve nonlinear least squares problems. It is a modification of Newton's method that does not use second derivatives, and is due to Carl Friedrich Gauss.

The problem

Given m functions f₁, ..., f_m of n parameters p₁, ..., p_n with m≥n, we want to minimize the sum

$S(p) = \sum_{i=1}^m (f_i(p))^2.$

Here, p stands for the vector (p₁, ..., p_n).

The algorithm

The Gauss-Newton algorithm is an iterative procedure. This means that the user has to provide an initial guess for the parameter vector p, which we will call p⁰.

Subsequent guesses p^k for the parameter vector are then produced by the recurrence relation

$p^{k+1} = p^k - \Big(J_f(p^k)^\top J_f(p^k)\Big)^{-1} J_f(p^k)^\top f(p^k),$

where f=(f₁, ..., f_m) and J_f(p) denotes the Jacobian of f at p (note that J_f need not be square).

The matrix inverse is never computed explicitly in practice. Instead, we use

$p^{k+1} = p^k + \delta^k, \,$

and we compute the update δ^k by solving the linear system

$J_f(p^k)^\top J_f(p^k) \, \delta^k = -J_f(p^k)^\top f(p^k).$

A good implementation of the Gauss-Newton algorithm also employs a line search algorithm: instead of the above formula for p^k+1, we use

$p^{k+1} = p^k + \alpha^k \, \delta^k,$

where the number α^k is in some sense optimal.

Other algorithms

The recurrence relation for Newton's method for minimizing a function S is

$p^{k+1} = p^k - [H (S)(p^k)]^{-1} J_S(p^k), \,$

where J_S and H(S) denote the Jacobian and Hessian of S respectively. Using Newton's method for our function

$S(p) = \sum_{i=1}^m (f_i(p))^2$

yields the recurrence relation

$p^{k+1} = p^k - \left( J_f(p)^\top J_f(p) + \sum_{i=1}^m f_i(p) \, H(f_i)(p) \right)^{-1} J_f(p)^\top f(p).$

We can conclude that the Gauss-Newton method is the same as Newton's method with the Σ f H(f) term ignored.

Other algorithms for solving least squares problems include the Levenberg-Marquardt algorithm and gradient descent.

This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)