Problem statement
The objective consists of adjusting the parameters of a model function so as to best fit a data set. A simple data set consists of n points (data pairs) [ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة], i = 1, ..., n, where [ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة] is an independent variable and [ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة] is a dependent variable whose value is found by observation. The model function has the form [ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة], where the m adjustable parameters are held in the vector [ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة]. We wish to find those parameter values for which the model "best" fits the data. The least squares method defines "best" as when the sum, S, of squared residuals
[ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة]
is a minimum. A residual is defined as the difference between the values of the dependent variable and the predicted values from the estimated model,
[ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة]
An example of a model is that of the straight line. Denoting the intercept as β0 and the slope as β1, the model function is given by
[ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة]
See the example of linear least squares for a fully worked out example of this model.
A data point may consist of more than one independent variable. For an example, when fitting a plane to a set of height measurements, the plane is a function of two independent variables, x and z, say. In the most general case there may be one or more independent variables and one or more dependent variables at each data point.
[ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذا الرابط]The objective consists of adjusting the parameters of a model function so as to best fit a data set. A simple data set consists of n points (data pairs) [ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة], i = 1, ..., n, where [ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة] is an independent variable and [ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة] is a dependent variable whose value is found by observation. The model function has the form [ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة], where the m adjustable parameters are held in the vector [ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة]. We wish to find those parameter values for which the model "best" fits the data. The least squares method defines "best" as when the sum, S, of squared residuals
[ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة]
is a minimum. A residual is defined as the difference between the values of the dependent variable and the predicted values from the estimated model,
[ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة]
An example of a model is that of the straight line. Denoting the intercept as β0 and the slope as β1, the model function is given by
[ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة]
See the example of linear least squares for a fully worked out example of this model.
A data point may consist of more than one independent variable. For an example, when fitting a plane to a set of height measurements, the plane is a function of two independent variables, x and z, say. In the most general case there may be one or more independent variables and one or more dependent variables at each data point.
Solving the least squares problem
Least squares problems fall into two categories, linear and non-linear. The linear least squares problem has a closed form solution, but the non-linear problem does not and is usually solved by iterative refinement; at each iteration the system is approximated by a linear one, so the core calculation is similar in both cases.
The minimum of the sum of squares is found by setting the gradient to zero. Since the model contains m parameters there are m gradient equations.
[ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة]
and since [ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة] the gradient equations become
[ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة]
The gradient equations apply to all least squares problems. Each particular problem requires particular expressions for the model and its partial derivatives.
Linear least squares
Main article: Linear least squares
A regression model is a linear one when the model comprises a linear combination of the parameters, i.e.
[ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة]
where the coefficients, φj, are functions of xi.
Letting
[ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة]
we can then see that in that case the least square estimate (or estimator, if we are in the context of a random sample), [ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة] is given by
[ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة]
For a derivation of this estimate see Linear least squares.
[ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذا الرابط]A regression model is a linear one when the model comprises a linear combination of the parameters, i.e.
[ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة]
where the coefficients, φj, are functions of xi.
Letting
[ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة]
we can then see that in that case the least square estimate (or estimator, if we are in the context of a random sample), [ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة] is given by
[ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة]
For a derivation of this estimate see Linear least squares.
Non-linear least squares
Main article: Non-linear least squares
There is no closed-form solution to a non-linear least squares problem. Instead, numerical algorithms are used to find the value of the parameters β which minimize the objective. Most algorithms involve choosing initial values for the parameters. Then, the parameters are refined iteratively, that is, the values are obtained by successive approximation.
[ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة]
k is an iteration number and the vector of increments, [ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة] is known as the shift vector. In some commonly used algorithms, at each iteration the model may be linearized by approximation to a first-order Taylor series expansion about [ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة]
[ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة]
The Jacobian, J, is a function of constants, the independent variable and the parameters, so it changes from one iteration to the next. The residuals are given by
[ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة]
and the gradient equations become
[ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة]
which, on rearrangement, become m simultaneous linear equations, the normal equations.
[ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة]
The normal equations are written in matrix notation as
[ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة]
These are the defining equations of the Gauss–Newton algorithm.
[ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذا الرابط]There is no closed-form solution to a non-linear least squares problem. Instead, numerical algorithms are used to find the value of the parameters β which minimize the objective. Most algorithms involve choosing initial values for the parameters. Then, the parameters are refined iteratively, that is, the values are obtained by successive approximation.
[ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة]
k is an iteration number and the vector of increments, [ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة] is known as the shift vector. In some commonly used algorithms, at each iteration the model may be linearized by approximation to a first-order Taylor series expansion about [ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة]
[ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة]
The Jacobian, J, is a function of constants, the independent variable and the parameters, so it changes from one iteration to the next. The residuals are given by
[ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة]
and the gradient equations become
[ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة]
which, on rearrangement, become m simultaneous linear equations, the normal equations.
[ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة]
The normal equations are written in matrix notation as
[ندعوك للتسجيل في المنتدى أو التعريف بنفسك لمعاينة هذه الصورة]
These are the defining equations of the Gauss–Newton algorithm.