Welcome to our community

Be a part of something great, join today!

[SOLVED] Least square method process

Juliayaho

New member
Apr 11, 2013
13
Hi does anyone know the "formula/process" for the least square method if the are giving several (x,y) points and asking me to find y=Ax^2 + B?
 

chisigma

Well-known member
Feb 13, 2012
1,704
Hi does anyone know the "formula/process" for the least square method if the are giving several (x,y) points and asking me to find y=Ax^2 + B?
Are You searching the 'particular' quadratic polynomial $A\ x^{2} + B$ and not the 'general' quadratic polynonial $A\ x^{2} + B\ x + C$?...

Kind regards

$\chi$ $\sigma$
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,868
Hi does anyone know the "formula/process" for the least square method if the are giving several (x,y) points and asking me to find y=Ax^2 + B?
Sounds like you want a non-linear least squares.

Suppose we write your equation like:
$$\begin{bmatrix}y_1 \\ \vdots \\ y_n \end{bmatrix} =
\begin{bmatrix}x_1^2 & 1 \\ \vdots & \vdots \\ x_n^2 & 1 \end{bmatrix}
\begin{bmatrix}A \\ B \end{bmatrix}$$

If we call the matrix J, and the vector of coefficients $\mathbf a$, we can write this as:
$$\mathbf y = J \mathbf a$$
The least square solution (minimizing the summed square residues of y) is:
$$\mathbf a = (J^T J)^{-1} J^T \mathbf y$$
 

Prove It

Well-known member
MHB Math Helper
Jan 26, 2012
1,404
Hi does anyone know the "formula/process" for the least square method if the are giving several (x,y) points and asking me to find y=Ax^2 + B?
Bring in a dummy variable \(\displaystyle \displaystyle X = x^2\) to give you a new set of points, and then perform a linear least squares regression on X vs y to give an equation of the form \(\displaystyle \displaystyle y = A\,X + B = A\,x^2 + B\).
 

chisigma

Well-known member
Feb 13, 2012
1,704
Hi does anyone know the "formula/process" for the least square method if there are giving several (x,y) points and asking me to find y=Ax^2 + B?
Let's suppose that the approximating polynomial is $y=A\ x + B$ so that we have the so called 'least square straight line'. In this case if we have a discrete set of N + 1 points $[y_{i},x_{i}],\ i=0,1,...,N$ then we have to minimize respect to A and B the sum...

$\displaystyle S= \sum_{i=0}^{N} [y_{i} - A\ x_{i} - B]^{2}$ (1)

Proceeding in standard fashion we compute the partial derivatives and impose them to vanish...

$\displaystyle \frac{\partial{S}}{\partial{A}} = - 2\ \sum_{i=0}^{N} x_{i}\ (y_{i} - A x_{i} - B) = 0$

$\displaystyle \frac{\partial{S}}{\partial{B}} = - 2\ \sum_{i=0}^{N} (y_{i} - A x_{i} - B) = 0$ (2)

Reordering we arrive to the 2 x 2 linear system of equations...

$\displaystyle A\ \sum_{i=0}^{N} x_{i}^{2} + B\ \sum_{i=0}^{N} x_{i} = \sum_{i=0}^{N} x_{i}\ y_{i}$

$\displaystyle A\ \sum_{i=0}^{N} x_{i} + B\ (N+1) = \sum_{i=0}^{N} y_{i}$ (3)

... the solution of which is...

$\displaystyle A = \frac{(N+1)\ \sum_{i=0}^{N} x_{i}\ y_{i}- \sum_{i=0}^{N} x_{i}\ \sum_{i=0}^{N} y_{i}}{(N+1)\ \sum_{i=0}^{N} x_{i}^{2} - (\sum_{i=0}^{N} x_{i})^{2}}$

$\displaystyle B = \frac {\sum_{i=0}^{N} x_{i}^{2}\ \sum_{i=0}^{N} y_{i} - \sum_{i=0}^{N} x_{i}\ \sum_{i=0}^{N} x_{i}\ y_{i}}{(N+1)\ \sum_{i=0}^{N} x_{i}^{2} - (\sum_{i=0}^{N} x_{i})^{2}}$ (4)

Very well!... but what to do if we want to use a polynomial of degree n>1?... we will examine that [if necessary...] in a next post...

Kind regards

$\chi$ $\sigma$
 

chisigma

Well-known member
Feb 13, 2012
1,704
Let's suppose that the approximating polynomial is $y=A\ x + B$ so that we have the so called 'least square straight line'. In this case if we have a discrete set of N + 1 points $[y_{i},x_{i}],\ i=0,1,...,N$ then we have to minimize respect to A and B the sum...

$\displaystyle S= \sum_{i=0}^{N} [y_{i} - A\ x_{i} - B]^{2}$ (1)

Proceeding in standard fashion we compute the partial derivatives and impose them to vanish...

$\displaystyle \frac{\partial{S}}{\partial{A}} = - 2\ \sum_{i=0}^{N} x_{i}\ (y_{i} - A x_{i} - B) = 0$

$\displaystyle \frac{\partial{S}}{\partial{B}} = - 2\ \sum_{i=0}^{N} (y_{i} - A x_{i} - B) = 0$ (2)

Reordering we arrive to the 2 x 2 linear system of equations...

$\displaystyle A\ \sum_{i=0}^{N} x_{i}^{2} + B\ \sum_{i=0}^{N} x_{i} = \sum_{i=0}^{N} x_{i}\ y_{i}$

$\displaystyle A\ \sum_{i=0}^{N} x_{i} + B\ (N+1) = \sum_{i=0}^{N} y_{i}$ (3)

... the solution of which is...

$\displaystyle A = \frac{(N+1)\ \sum_{i=0}^{N} x_{i}\ y_{i}- \sum_{i=0}^{N} x_{i}\ \sum_{i=0}^{N} y_{i}}{(N+1)\ \sum_{i=0}^{N} x_{i}^{2} - (\sum_{i=0}^{N} x_{i})^{2}}$

$\displaystyle B = \frac {\sum_{i=0}^{N} x_{i}^{2}\ \sum_{i=0}^{N} y_{i} - \sum_{i=0}^{N} x_{i}\ \sum_{i=0}^{N} x_{i}\ y_{i}}{(N+1)\ \sum_{i=0}^{N} x_{i}^{2} - (\sum_{i=0}^{N} x_{i})^{2}}$ (4)

Very well!... but what to do if we want to use a polynomial of degree n>1?... we will examine that [if necessary...] in a next post...
Of course if we are searching a polynomial like $\displaystyle y=A\ x^{2} + B$ all what we have to do is to write $x_{i}^{2}$ instead of $x_{i}$ in (4)...

Kind regards

$\chi$ $\sigma$
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,868
Let's suppose that the approximating polynomial is $y=A\ x + B$ so that we have the so called 'least square straight line'. In this case if we have a discrete set of N + 1 points $[y_{i},x_{i}],\ i=0,1,...,N$ then we have to minimize respect to A and B the sum...

$\displaystyle S= \sum_{i=0}^{N} [y_{i} - A\ x_{i} - B]^{2}$ (1)

Proceeding in standard fashion we compute the partial derivatives and impose them to vanish...

$\displaystyle \frac{\partial{S}}{\partial{A}} = - 2\ \sum_{i=0}^{N} x_{i}\ (y_{i} - A x_{i} - B) = 0$

$\displaystyle \frac{\partial{S}}{\partial{B}} = - 2\ \sum_{i=0}^{N} (y_{i} - A x_{i} - B) = 0$ (2)

Reordering we arrive to the 2 x 2 linear system of equations...

$\displaystyle A\ \sum_{i=0}^{N} x_{i}^{2} + B\ \sum_{i=0}^{N} x_{i} = \sum_{i=0}^{N} x_{i}\ y_{i}$

$\displaystyle A\ \sum_{i=0}^{N} x_{i} + B\ (N+1) = \sum_{i=0}^{N} y_{i}$ (3)

... the solution of which is...

$\displaystyle A = \frac{(N+1)\ \sum_{i=0}^{N} x_{i}\ y_{i}- \sum_{i=0}^{N} x_{i}\ \sum_{i=0}^{N} y_{i}}{(N+1)\ \sum_{i=0}^{N} x_{i}^{2} - (\sum_{i=0}^{N} x_{i})^{2}}$

$\displaystyle B = \frac {\sum_{i=0}^{N} x_{i}^{2}\ \sum_{i=0}^{N} y_{i} - \sum_{i=0}^{N} x_{i}\ \sum_{i=0}^{N} x_{i}\ y_{i}}{(N+1)\ \sum_{i=0}^{N} x_{i}^{2} - (\sum_{i=0}^{N} x_{i})^{2}}$ (4)

Very well!... but what to do if we want to use a polynomial of degree n>1?... we will examine that [if necessary...] in a next post...

Kind regards

$\chi$ $\sigma$
The set of derivatives of all the equations with respect to the coefficients is a Jacobian matrix J.
Solving the system is equivalent to multiplying by $(J^T J)^{-1}J^T$.
This can be generalized to more complicated expressions.
The solution remains the same as long as the expression is linear in the coefficients.
 

chisigma

Well-known member
Feb 13, 2012
1,704
The set of derivatives of all the equations with respect to the coefficients is a Jacobian matrix J.
Solving the system is equivalent to multiplying by $(J^T J)^{-1}J^T$.
This can be generalized to more complicated expressions.
The solution remains the same as long as the expression is linear in the coefficients.
From the 'pure theoretically' point of view what You say is true... from the 'pratical' point of view, when You have an approximating polynomial of degree n>1, the procedure leads in most cases to an ill conditioned linear problem so that a different approach [disovered by the German mathematician Karl Friedriek Gauss...] has to be used...

Kind regards

$\chi$ $\sigma$
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,868
From the 'pure theoretically' point of view what You say is true... from the 'pratical' point of view, when You have an approximating polynomial of degree n>1, the procedure leads in most cases to an ill conditioned linear problem so that a different approach [disovered by the German mathematician Karl Friedriek Gauss...] has to be used...

Kind regards

$\chi$ $\sigma$
I believe the only practical problem is how to find the inverse matrix.
For 2 coefficients there is no problem, as it is straight forward to find the inverse matrix, as your equations show.
For 3 or more coefficients we may need to be careful how to find the inverse (if the problem is ill-conditioned).
For that there are numerical methods that minimize the rounding errors.