Least Squares
The least squares method can be used to find the best fit line or curve for a group of points.
The Essentials
The equation for a line is
\( y=mx+c \). If there was a group of four points that were all on the same line, this matrix equation would find the line:
\[
\begin{cases}
y_1=mx_1+c\\
y_2=mx_2+c\\
y_3=mx_3+c\\
y_4=mx_4+c\\
\ldots
\end{cases}
\]
\[
\begin{bmatrix}
x_1&1\\
x_2&1\\
x_3&1\\
x_4&1
\end{bmatrix}
\begin{bmatrix}
m\\
c
\end{bmatrix}=
\begin{bmatrix}
y_1\\
y_2\\
y_3\\
y_4
\end{bmatrix}
\]
However, if the points are not all on the same line, the best fit line can be found using this formula
\( A^TA\vec{x}=A^T\vec{b} \):
\[
\begin{bmatrix}
x_1&x_2&x_3&x_4\\
1&1&1&1
\end{bmatrix}
\begin{bmatrix}
x_1&1\\
x_2&1\\
x_3&1\\
x_4&1
\end{bmatrix}
\begin{bmatrix}
m\\c
\end{bmatrix}=
\begin{bmatrix}
x_1&x_2&x_3&x_4\\
1&1&1&1
\end{bmatrix}
\begin{bmatrix}
y_1\\y_2\\y_3\\y_4
\end{bmatrix}
\]
Solving this equation would give a value for m and c for the best fit line. This method also works for a best fit parabola (
\( y=cx^2+dx+e \)):
\[
\begin{cases}
y_1=cx_1^2+dx_1+e\\
y_2=cx_2^2+dx_2+e\\
y_3=cx_3^2+dx_3+e\\
y_4=cx_4^2+dx_4+e\\
\ldots
\end{cases}
\]
\[
\begin{bmatrix}
x_1^2&x_2^2&x_3^2&x_4^2\\
x_1&x_2&x_3&x_4\\
1&1&1&1
\end{bmatrix}
\begin{bmatrix}
x_1^2&x_1&1\\
x_2^2&x_2&1\\
x_3^2&x_3&1\\
x_4^2&x_4&1
\end{bmatrix}
\begin{bmatrix}
c\\d\\e
\end{bmatrix}=
\begin{bmatrix}
x_1^2&x_2^2&x_3^2&x_4^2\\
x_1&x_2&x_3&x_4\\
1&1&1&1
\end{bmatrix}
\begin{bmatrix}
y_1\\y_2\\y_3\\y_4
\end{bmatrix}
\]
Example
Find the best fit line for these points: (1,3), (1,6), (3,8), (4,9), (7,10).
First, set up the system of equations for each of the lines
\( xm+c=y \) and convert it into a matrix equation:
\[
\begin{cases}
1m+c=3\\
1m+c=6\\
3m+c=8\\
4m+c=9\\
7m+c=10
\end{cases}
\]
\[
A=\begin{bmatrix}
1&1\\
1&1\\
3&1\\
4&1\\
7&1
\end{bmatrix}\hspace{12pt}
\vec{x}=\begin{bmatrix}
m\\c
\end{bmatrix}\hspace{12pt}
\vec{b}=\begin{bmatrix}
3\\
6\\
8\\
9\\
10
\end{bmatrix}
\]
Next, we use the least square formula \( A^TA\vec{x}=A^T\vec{b} \):
\[
\begin{bmatrix}
1&1&3&4&7\\
1&1&1&1&1
\end{bmatrix}
\begin{bmatrix}
1&1\\
1&1\\
3&1\\
4&1\\
7&1
\end{bmatrix}
\begin{bmatrix}
m\\c
\end{bmatrix}=
\begin{bmatrix}
1&1&3&4&7\\
1&1&1&1&1
\end{bmatrix}
\begin{bmatrix}
3\\
6\\
8\\
9\\
10
\end{bmatrix}
\]
\[
\begin{bmatrix}
76&16\\
16&5
\end{bmatrix}
\begin{bmatrix}
m\\
c
\end{bmatrix}=
\begin{bmatrix}
139\\
36
\end{bmatrix}
\]
\[
\left[\begin{array}{cc|c}
76 & 16 & 139 \\
16 & 5 & 36
\end{array}\right]
\]
\( R_1=4R_1 \)
\( R_2=19R_2 \)
\[
\left[
\begin{array}{cc|c}
304 & 64 & 556 \\
304 & 95 & 684
\end{array}
\right]
\]
\( R_2=R_2-R_1 \)
\[
\left[
\begin{array}{cc|c}
304 & 64 & 556 \\
0 & 31 & 128
\end{array}
\right]
\]
\( R_1=R_1-64/31R_2 \)
\[
\left[
\begin{array}{cc|c}
304 & 0 & \frac{9044}{31} \\
0 & 31 & 128
\end{array}
\right]
\]
\( R_1=R_1/304 \)
\( R_2=R_2/31 \)
\[
\left[
\begin{array}{cc|c}
1 & 0 & \frac{2261}{2356} \\
0 & 1 & \frac{128}{31}
\end{array}
\right]
\]
So, the best fit line for these points is approximately:
\[
y=.960x+4.129
\]
Practice
Find the best fit line for the points (1,1), (1,4), (3,5), (4,4):
Solution:
\( y(x)=\frac{2}{3}x+2 \)
Dive Deeper
This method can be used to find the best fit plane for functions of two variables. It can also be used to find the best fit conic section with the general formula for conic sections:
\[
ax^2+by^2+cxy+dx+ey+f=0
\]
To use this equation, it is best to re-write the equation in this form:
\[
By^2+Cxy+Dx+Ey+F=x^2
\]
Example
Find the least squares conic section for the following points: (-1,-1), (1,1), (-2,1), (2,-1), (-3,0).
First, the matrix equation is set up:
\[
A=\begin{bmatrix}
1&1&-1&-1&1\\
1&1&1&1&1\\
1&-2&-2&1&1\\
1&-2&1&-1&1\\
0&0&0&-3&1
\end{bmatrix}\hspace{12pt}
\vec{x}=\begin{bmatrix}
B\\C\\D\\E\\F
\end{bmatrix}\hspace{12pt}
\vec{b}=\begin{bmatrix}
1\\1\\4\\4\\9
\end{bmatrix}
\]
Now we use the least squares formula
\( A^TA\vec{x}=A^T\vec{b} \):
\[
\begin{bmatrix}
4&-2&-1&0&4\\
-2&10&2&0&-2\\
-1&2&7&-1&-1\\
0&0&-1&13&-3\\
4&-2&-1&-3&5
\end{bmatrix}\vec{x}=\begin{bmatrix}
10\\
-14\\
-4\\
-27\\
19
\end{bmatrix}
\]
\[
\left[\begin{array}{ccccc|c}
4&-2&-1&0&4&10\\
-2&10&2&0&-2&-14\\
-1&2&7&-1&-1&-4\\
0&0&-1&13&-3&-27\\
4&-2&-1&-3&5&19
\end{array}\right]
\]
\[
\left[\begin{array}{ccccc|c}
1&0&0&0&0&-7\\
0&1&0&0&0&-1\\
0&0&1&0&0&0\\
0&0&0&1&0&0\\
0&0&0&0&1&9
\end{array}\right]
\]
The conic section turns out to be an ellipse that fits all five points exactly:
\[
x^2+7y^2+xy=9
\]
Example
Find the least squares conic section for the following points: (1,2), (3,1), (3,3), (3,4), (4,2), (4,4).
First we set up the matrix:
\[
A=\begin{bmatrix}
4&2&1&2&1\\
1&3&3&1&1\\
9&9&3&3&1\\
16&12&3&4&1\\
4&8&4&2&1\\
16&16&4&4&1
\end{bmatrix}\hspace{12pt}
\vec{x}=\begin{bmatrix}
B\\C\\D\\E\\F
\end{bmatrix}\hspace{12pt}
\vec{b}=\begin{bmatrix}
1\\9\\9\\9\\16\\16
\end{bmatrix}
\]
\[
A^TA=\begin{bmatrix}
626&572&162&172&50\\
572&558&170&162&50\\
162&170&60&50&18\\
172&162&50&50&16\\
50&50&18&16&6
\end{bmatrix}\hspace{12pt}
A^T\vec{b}=\begin{bmatrix}
558\\602\\210\\170\\60
\end{bmatrix}
\]
\[
\left[\begin{array}{ccccc|c}
1&0&0&0&0&-5/8\\
0&1&0&0&0&5/4\\
0&0&1&0&0&19/8\\
0&0&0&1&0&-7/8\\
0&0&0&0&1&0
\end{array}\right]
\]
Which comes out to be the ellipse:
\[
8x^2+5y^2-10xy-19x+7y=0
\]
