The Gauss–Newton algorithm is used to solve non-linear least squares problems, which is equivalent to minimizing a sum of squared function values. It is an extension of Newton's method for finding a minimum of a non-linear function. Since a sum of squares must be nonnegative, the algorithm can be viewed as using Newton's method to iteratively approximate zeroes of the components of the sum, and thus minimizing the sum. In this sense, the algorithm is also an effective method for solving overdetermined systems of equations. It has the advantage that second derivatives, which can be challenging to compute, are not required.
Non-linear least squares problems arise, for instance, in non-linear regression, where parameters in a model are sought such that the model is in good agreement with available observations.
The method is named after the mathematicians Carl Friedrich Gauss and Isaac Newton, and first appeared in Gauss' 1809 work Theoria motus corporum coelestium in sectionibus conicis solem ambientum.
Description
Given functions (often called residuals) of variables with the Gauss–Newton algorithm iteratively finds the value of the variables that minimize the sum of squares
Starting with an initial guess for the minimum, the method proceeds by the iterations
where, if r and β are column vectors, the entries of the Jacobian matrix are
and the symbol denotes the matrix transpose.
At each iteration, the update can be found by rearranging the previous equation in the following two steps:
With substitutions , , and , this turns into the conventional matrix equation of form , which can then be solved in a variety of methods (see Notes).
If , the iteration simplifies to
which is a direct generalization of Newton's method in one dimension.
In data fitting, where the goal is to find the parameters such that a given model function best fits some data points , the functions are the residuals:
Then, the Gauss–Newton method can be expressed in terms of the Jacobian of the function as
Note that is the left pseudoinverse of .
Notes
The assumption in the algorithm statement is necessary, as otherwise the matrix is not invertible and the normal equations cannot be solved (at least uniquely).
The Gauss–Newton algorithm can be derived by linearly approximating the vector of functions ri. Using Taylor's theorem, we can write at every iteration:
with . The task of finding minimizing the sum of squares of the right-hand side; i.e.,
is a linear least-squares problem, which can be solved explicitly, yielding the normal equations in the algorithm.
The normal equations are n simultaneous linear equations in the unknown increments . They may be solved in one step, using Cholesky decomposition, or, better, the QR factorization of . For large systems, an iterative method, such as the conjugate gradient method, may be more efficient. If there is a linear dependence between columns of Jr, the iterations will fail, as becomes singular.
When is complex the conjugate form should be used: .
Example
In this example, the Gauss–Newton algorithm will be used to fit a model to some data by minimizing the sum of squares of errors between the data and model's predictions.
In a biology experiment studying the relation between substrate concentration and reaction rate in an enzyme-mediated reaction, the data in the following table were obtained.
It is desired to find a curve (model function) of the form
that fits best the data in the least-squares sense, with the parameters and to be determined.
Denote by and the values of and rate respectively, with . Let and . We will find and such that the sum of squares of the residuals
is minimized.
The Jacobian of the vector of residuals with respect to the unknowns is a matrix with the -th row having the entries
Starting with the initial estimates of and , after five iterations of the Gauss–Newton algorithm, the optimal values and are obtained. The sum of squares of residuals decreased from the initial value of 1.445 to 0.00784 after the fifth iteration. The plot in the figure on the right shows the curve determined by the model for the optimal parameters with the observed data.
Convergence properties
The Gauss-Newton iteration is guaranteed to converge toward a local minimum point under 4 conditions: The functions are twice continuously differentiable in an open convex set , the Jacobian is of full column rank, the initial iterate is near , and the local minimum value is small. The convergence is quadratic if .