Gauss–Newton algorithm

The Gauß-Newton algorithm is a method for finding zeroes of a function of several real variables. It is a generalisation of Newton's method.

The aim is to solve systems of n (non-linear) equations, which amounts to finding the zeros of continuously differentiable functions F : R^k -> R^k. In the formulation given above, one then has to multiply with the inverse of the k-by-k Jacobian matrix F '(x_n) instead of dividing by f '(x_n). Rather than actually computing the inverse of this matrix, one can save time by solving the system of linear equations

$F'(x_{n})(x_{n+1}-x_{n})=-F(x_{n})$

for the unknown x_n+1 - x_n. Again, this method only works if the initial value x₀ is close enough to the true zero. Typically, a region which is well-behaved is located first with some other method (gradient descent and Newton's method is then used to "polish" a root which is already known approximately.

The Levenberg-Marquardt algorithm flexibly interpolates between a gradient descent and the Gauß-Newton method.