Sources
Help build the largest human-edited directory on the web.
Submit a site - Become an editor
Wikipedia. Licensed under the GNU Free Documentation License.
Are you an expert in this subject? Join the discussion and share your knowledge at Wikipedia.org.
Gauss-Newton algorithm
From Wikipedia, the free encyclopedia
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.
Given m functions f1, ..., fm of n parameters p1, ..., pn with m≥n, we want to minimize the sum
Here, p stands for the vector (p1, ..., pn).
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 p0.
Subsequent guesses pk for the parameter vector are then produced by the recurrence relation
where f=(f1, ..., fm) and Jf(p) denotes the Jacobian of f at p (note that Jf is not square).
The matrix inverse is never computed explicitly in practice. Instead, we use
and we compute the update δk by solving the linear system
A good implementation of the Gauss-Newton algorithm also employs a line search algorithm: instead of the above formula for pk+1, we use
where the number αk is in some sense optimal.
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), \,](../../../math/1/e/0/1e07bdb3393907d5fabca19900366381.png)
where JS and H(S) denote the Jacobian and Hessian of S respectively. Using Newton's method for our function
yields the recurrence relation
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.