High School
SAT
ACT
University
MCAT
LSAT
DAT
Wize University Linear Algebra Textbook > Least Squares Approximation

Least Squares Approximation

Higher Order Differential EquationsPrevious Section
Basics of CryptographyNext Section
Popular Courses
Find My Course
0:00 / 0:00

Least Squares Approximation

Normal Equation

Given a linear systemAx⃗=b⃗A\vec x=\vec b, we can write the normal equation:
(ATA)z⃗=ATb⃗\boxed{\quad (A^TA)\vec z=A^T\vec b \quad}
Why is this useful?

The solution, z⃗\vec z, of the normal equation is a best possible approximation to a solution of Ax⃗=b⃗A\vec x=\vec b.
That is, z⃗\vec z is the vector such that Az⃗A\vec z is as close as possible to b⃗\vec b.
Note: this result is usually used when the system Ax⃗=b⃗A\vec x=\vec b is inconsistent, because otherwise we can find an exact solution!
PAGE BREAK

Polynomials of Best Fit

Suppose we want to find a degree mm polynomial that "best fits" a set of points (x1,y1),(x2,y2),...,(xn,yn)(x_1,y_1),(x_2,y_2),...,(x_n,y_n).
We'll define this polynomial of best fit to be:
f(x)=c0+c1x+c2x2+...+cmxmf(x)=c_0+c_1x+c_2x^2+...+c_mx^m
Let y⃗=[y1⋮yn]\vec y= \begin{bmatrix} y_1\\ \vdots\\ y_n \end{bmatrix}.
Form the following matrix, just as we did when finding an interpolating polynomial:
M=[1x1x12...x1m1x2x22...x2m⋮⋮⋮⋮1xnxn2...xnm]M=\left[\begin{array}{rrrrr}1&x_1&x_1^2&...&x_1^m\\1&x_2&x_2^2&...&x_2^m\\\vdots&\vdots&\vdots&&\vdots\\1&x_n&x_n^2&...&x_n^m\end{array}\right]
Then, the coefficients of the polynomial c⃗=[c0⋮cm]\vec c= \begin{bmatrix} c_0\\ \vdots\\ c_m \end{bmatrix} are found by solving the normal equation:
MTMc⃗=MTy⃗\boxed{\quad M^TM\vec c=M^T\vec y \quad}
Note: If the degree of the polynomial is smaller than the number of unique x-coordinates (of the given points), then the coefficients are uniquely determined.

Wize Tip
The special case of this result with m=1m=1 is the line of best fit for a set of points.

0:00 / 0:00

Example: Least Squares for Linear Functions

Find the equation of the line that comes as close as possible to passing through the points: (0,1),(2,3),(3,4),(4,7)(0,1),(2,3),(3,4),(4,7).
First, define the vector y⃗\vec y (look at each of the y-values):
y⃗=[1347]\vec y=\left[\begin{array}{r}1\\3\\4\\7\end{array}\right]
Now fill in the matrix MM according to: M=[1x1x12...x1m1x2x22...x2m⋮⋮⋮⋮1xnxn2...xnm]M=\left[\begin{array}{rrrrr}1&x_1&x_1^2&...&x_1^m\\1&x_2&x_2^2&...&x_2^m\\\vdots&\vdots&\vdots&&\vdots\\1&x_n&x_n^2&...&x_n^m\end{array}\right]
Note: Since we are looking for a line to approximate, we want a degree 1 polynomial, so m=1m=1.
Thus we have just 2 columns:
M=[10121314]M=\left[\begin{array}{rr}1&0\\1&2\\1&3\\1&4\end{array}\right]
Now look at the normal equation MTMc⃗=MTy⃗M^TM\vec c = M^T\vec y to see what else we need to calculate:
MTM=[49929]MTy⃗=[1546]M^TM=\left[\begin{array}{rr}4&9\\9&29\end{array}\right] \qquad M^T\vec y=\left[\begin{array}{rr}15\\46\end{array}\right]
Row reduce the augmented matrix for the system of normal equations:

[491592946]→RREF[103/5017/5]\left[\begin{array}{rr|r}4&9&15\\9&29&46\end{array}\right]\xrightarrow{RREF} \left[\begin{array}{rr|r}1&0&3/5\\0&1&7/5\end{array}\right]

  ⟹  [c1c2]=[3/57/5]  ⟹  f(x)=(3/5)+(7/5)x←line of best fit\begin{aligned} &\implies \begin{bmatrix} c_1\\ c_2 \end{bmatrix} = \begin{bmatrix} 3/5\\ 7/5 \end{bmatrix}\\[1.5em] &\implies \boxed{f(x)=(3/5)+(7/5)x} \leftarrow \text{line of best fit} \end{aligned}

Example: Least Squares for Polynomials

Find the equation of a quadratic polynomial that comes as close as possible to passing through the points: (1,2),(1,3),(2,3)(1,2),(1,3),(2,3).

Note that there are only 2 distinct x-coordinates among the set of points, so a quadratic (degree 2) does NOT have degree strictly less than the number of unique x-coordinates. Therefore, we expect the answer NOT to be uniquely determined.
First, we look at all the y-coordinates to write: y⃗=[233]\vec y=\left[\begin{array}{r}2\\3\\3\end{array}\right]
Then we can form the matrix MM and calculate the pieces of the normal equation MTMc⃗=MTy⃗M^TM\vec c = M^T\vec y:
M=[111111124]MTM=[346461061018]MTy⃗=[81117]M=\left[\begin{array}{rrr}1&1&1\\1&1&1\\1&2&4\end{array}\right] \quad M^TM=\left[\begin{array}{rrr}3&4&6\\4&6&10\\6&10&18\end{array}\right]\quad M^T\vec y=\left[\begin{array}{rr}8\\11\\17\end{array}\right]
Therefore, the normal equation can be solved by row reducing:
[34684610116101817]→RREF[10−220131/20000]\left[\begin{array}{rrr|r}3&4&6&8\\4&6&10&11\\6&10&18&17\end{array}\right] \xrightarrow{RREF} \left[\begin{array}{rrr|r}1&0&-2&2\\0&1&3&1/2\\0&0&0&0\end{array}\right]
Here we have a free variable for the third column, representing c2c_2:
{c0−2c2=2c1+3c2=1/2c2=t  ⟹  {c0=2+2tc1=1/2−3tc2=t\left\{ \begin{array}{l} c_0-2c_2=2\\ c_1+3c_2=1/2\\ c_2=t \end{array} \right. \implies \left\{ \begin{array}{l} c_0=2+2t\\ c_1=1/2-3t\\ c_2=t \end{array} \right.
So for any choice of the parameter tt, the function f(x)=(2+2t)+(1/2−3t)x+tx2\boxed{f(x)=(2+2t) + (1/2-3t)x+tx^2} would work.
For example, with t=1t=1 we have: f(x)=4−(5/2)x+x2f(x)=4-(5/2)x+x^2.
Interestingly, the case t=0t=0 gives a linear function which approximates exactly as well (in terms of minimizing the squared distance from the given points): f(x)=2+12xf(x)=2+\dfrac{1}{2}x
checklist
Mark Yourself Question
  1. Grab a piece of paper and try this problem yourself.
  2. When you're done, check the "I have answered this question" box below.
  3. View the solution and report whether you got it right or wrong.

Practice: Least Squares Approximation

Find the cubic polynomial which best fits the data points (−2,−1),(−1,1),(0,0),(1,−2),(2,3)(-2,-1),(-1,1),(0,0),(1,-2),(2,3).

Extra Practice
Practice: Least Squares Approximation
Find the cubic polynomial which best fits the data points (−2,−1),(−1,1),(0,0),(1,−2),(2,3)(-2,-1),(-1,1),(0,0),(1,-2),(2,3).
19.4F_133_8.2_Mock_F1_$\tkco{eg2}$_$\key{Final}$_Builder_$\tkcth{8.2.}\tkcf{2}$_
Show that, in the case that the matrix A‾\A is invertible, the least squares solution corresponding to the system:
A‾ x⃗  =  b⃗, \A \, \vx \; = \; \vb,
is the same as the solution to the system itself.
Least Squares for Mix of Quadratic and Linear Functions
Find a least squares approximation of form a+bx+cx2+dya+bx+cx^2+dy for the following data:
x‾y‾result‾11112−121−3222011\begin{array}{r|r|r}\underline{x}&\underline{y}&\underline{result}\\1&1&1\\1&2&-1\\2&1&-3\\2&2&2\\0&1&1\end{array}
Least Squares
Find a function of the form a0+a1x+a3x3a_0+a_1x+a_3x^3 (note there is no squared term) which is a best approximation in the sense of least squares to the following data points: (0,1),(−1,1),(1,2),(−2,1)(0,1),(-1,1),(1,2),(-2,1) .
Practice Question: Least Squares for Polynomials
Find the cubic polynomial which best fits the data points (−2,−1),(−1,1),(0,0),(1,−2),(2,3)(-2,-1),(-1,1),(0,0),(1,-2),(2,3) in the least squares sense.
Example: Least Squares for non-Polynomials
Example: Least Squares for non-Polynomials
Find the function of form c1sin⁡(x)+c2cos⁡(x)c_1\sin(x)+c_2\cos(x) which best fits the data points (−π,−3),(0,−4),(π/2,−5)(-\pi,-3),(0,-4),(\pi/2,-5) in the least squares sense.
Solution:
Example: Least Squares for Linear Functions
Example: Least Squares for Linear Functions
Find the equation of the line that comes as close as possible to passing through the points: (0,1),(2,3),(3,4),(4,7)(0,1),(2,3),(3,4),(4,7).
Example: Least Squares for Linear Functions
Example: Least Squares for Linear Functions
Find the equation of the line that comes as close as possible to passing through the points: (0,1),(2,3),(3,4),(4,7)(0,1),(2,3),(3,4),(4,7).
Example: Least Squares for Linear Functions
Example: Least Squares for Linear Functions
Find the equation of the line that comes as close as possible, in the least squares sense, to passing through the points: (0,1),(2,3),(3,4),(4,7)(0,1),(2,3),(3,4),(4,7) .
Solution:
Example: Least Squares for Polynomials
Example: Least Squares for Polynomials
Find the equation of a quadratic polynomial that comes as close as possible to passing through the points: (1,2),(1,3),(2,3)(1,2),(1,3),(2,3).