Editing Gauss–Newton algorithm (section)

==Notes==

The assumption {{math|''m'' ≥ ''n''}} in the algorithm statement is necessary, as otherwise the matrix <math> \mathbf{J_r}^T\mathbf{J_r} </math> is not invertible and the normal equations cannot be solved (at least uniquely).

The Gauss–Newton algorithm can be derived by [[linear approximation|linearly approximating]] the vector of functions ''r''<sub>''i''</sub>. Using [[Taylor's theorem]], we can write at every iteration:
<math display="block">\mathbf{r}(\boldsymbol \beta) \approx \mathbf{r}\left(\boldsymbol \beta^{(s)}\right) + \mathbf{J_r}\left(\boldsymbol \beta^{(s)}\right)\Delta</math>

with <math>\Delta = \boldsymbol \beta - \boldsymbol \beta^{(s)}</math>. The task of finding <math> \Delta </math> minimizing the sum of squares of the right-hand side; i.e.,
<math display="block">\min \left\|\mathbf{r}\left(\boldsymbol \beta^{(s)}\right) + \mathbf{J_r}\left(\boldsymbol \beta^{(s)}\right)\Delta\right\|_2^2,</math>

is a [[linear least squares (mathematics)|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 <math> \Delta </math>. They may be solved in one step, using [[Cholesky decomposition]], or, better, the [[QR factorization]] of <math> \mathbf{J_r} </math>. 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 '''J'''<sub>'''r'''</sub>, the iterations will fail, as <math> \mathbf{J_r}^T\mathbf{J_r} </math>  becomes singular.

When <math>\mathbf{r}</math> is complex <math>\mathbf{r}:\Complex^n \to \Complex</math> the conjugate form should be used: <math>\left(\overline \mathbf{J_r}^\operatorname{T} \mathbf{J_r}\right)^{-1}\overline \mathbf{J_r}^\operatorname{T}</math>.