Solve Least Squares Problems by the Normal Equations
Least Square Problem
In many real life applications, when a solution \( x \) to a system of equations of the form
\[ A x = B \]
cannot be found (i.e. the system is inconsistent), it is possible that an approximate solution \( \hat x \) to the given system \( A x = B \) is enough.
The least squares problems is to find an approximate solution \( \hat x \) such that the distance between the vectors \( Ax \) and \( B \) given by \( || A\hat x - B || \) is the smallest.
It is shown in Linear Algebra and its Applications that the approximate solution \( \hat x \) is given by the normal equation
\[ A^T A \hat x = A^T B \]
where \( A^T \) is the transpose of matrix \( A \).
Examples with Solutions
Example 1
a) Show that the system \( A x = B \) with
\( A =
\begin{bmatrix}
2 & 0 \\
0 & 1 \\
1 & 2
\end{bmatrix}
\) and \( B =
\begin{bmatrix}
1 \\
0 \\
3
\end{bmatrix}
\)
is inconsistent (system with no solutions).
b) Find the least square solution to the inconsistent system \( A x = B \).
c) Determine the least square error given by \( || Ax - B || \) for the solution found in part b).
Solution to Example 1
a)
The system of equations to solve may be written in the form
\[
\begin{bmatrix}
2 & 0 \\
0 & 1 \\
1 & 2
\end{bmatrix}
\begin{bmatrix}
x_1\\
x_2
\end{bmatrix}
=
\begin{bmatrix}
1 \\
0 \\
3
\end{bmatrix}
\]
Write the above system in augmented matrix form
\(
\begin{bmatrix}
2 & 0 &|&1\\
0 & 1 &|&0 \\
1 & 2 &|&3
\end{bmatrix}
\)
Row reduce (Gauss Jordan) the above augmented matrix
\(
\begin{bmatrix}
1 & 0 & | & 0\\
0 & 1 & | & 0 \\
0 & 0 & | & 1
\end{bmatrix}
\)
The last row gives the equation \( 0 \cdot x_1 + 0 \cdot x_2 = 1 \) which has no solution and therefore the system is inconsistent.
b)
Let us find \( A^T \)
\( A^T =
\begin{bmatrix}
2 & 0 & 1\\
0 & 1 & 2
\end{bmatrix}
\)
Calculate \( A^T A \) and \( A^T B \)
\( A^T A =
\begin{bmatrix}
2 & 0 & 1\\
0 & 1 & 2
\end{bmatrix} \cdot
\begin{bmatrix}
2 & 0 \\
0 & 1 \\
1 & 2
\end{bmatrix} =
\begin{bmatrix}
5 & 2\\
2 & 5
\end{bmatrix}
\)
\( A^T B =
\begin{bmatrix}
2 & 0 & 1\\
0 & 1 & 2
\end{bmatrix} \cdot
\begin{bmatrix}
1 \\
0 \\
3
\end{bmatrix} =
\begin{bmatrix}
5\\
6
\end{bmatrix}
\)
Substitute \( A^T A \) and \( A^T B \) by their numerical values in the normal equation \( A^T A \hat x = A^T B \), we obtain the system
\(
\begin{bmatrix}
5 & 2\\
2 & 5
\end{bmatrix}
\cdot \hat x =
\begin{bmatrix}
5\\
6
\end{bmatrix}
\)
Solve the above to obtain
\( \hat x =
\begin{bmatrix}
\dfrac{13}{21}\\
\dfrac{20}{21}
\end{bmatrix}
\)
c)
\( A \cdot \hat x - B =
\begin{bmatrix}
2 & 0 \\
0 & 1 \\
1 & 2
\end{bmatrix}
\begin{bmatrix}
\dfrac{13}{21}\\
\dfrac{20}{21}
\end{bmatrix} -
\begin{bmatrix}
1 \\
0 \\
3
\end{bmatrix} =
\begin{bmatrix}
\dfrac{5}{21}\\
\dfrac{20}{21}\\
- \dfrac{10}{21}\end{bmatrix}
\)
\( || A \cdot \hat x - B || = \sqrt { (\dfrac{5}{21})^2 + (\dfrac{20}{21})^2 + (- \dfrac{10}{21})^2 } = \dfrac{5\sqrt{21}}{21} \approx 1.1 \)
Example 2
a) Show that the system \( A x = B \) with
\( A =
\begin{bmatrix}
1 & 0 & 1\\
2 & 0 & 2 \\
0 & -1 & 1\\
0 & -2 & 2
\end{bmatrix}
\) and \( B =
\begin{bmatrix}
2 \\
3 \\
4 \\
7
\end{bmatrix}
\)
is inconsistent.
b) Find the least square solution to the inconsistent system \( A x = B \).
c) Determine the least square error given by \( || Ax - B || \) for the solution found in part b).
Solution to Example 2
a)
The system of equations to solve may be written in the form
\[
\begin{bmatrix}
1 & 0 & 1\\
2 & 0 & 2 \\
0 & -1 & 1\\
0 & -2 & 2
\end{bmatrix}
\begin{bmatrix}
x_1\\
x_2 \\
x_3
\end{bmatrix}
=
\begin{bmatrix}
2 \\
3 \\
4 \\
7
\end{bmatrix}
\]
Write the above system in augmented matrix form
\(
\begin{bmatrix}
1 & 0 & 1 & |& 2\\
2 & 0 & 2 & | & 3 \\
0 & -1 & 1 & | & 4 \\
0 & -2 & 2 & | & 7
\end{bmatrix}
\)
Write in row reduced form (Gauss - Jordan)
\(
\begin{bmatrix}
1 & 0 & 1 & | & 0\\
0 & 1 & -1 & | & 0 \\
0 & 0 & 0 & | & 1 \\
0 & 0 & 0 & | & 0
\end{bmatrix}
\)
The third row gives the equation \( 0 \cdot x_1 + 0 \cdot x_2 + 0 \cdot x_3 = 1 \) which has no solution and therefore the system is inconsistent.
b)
Let us first find \( A^T \)
\( A^T =
\begin{bmatrix}
1 & 2 & 0 & 0\\
0 & 0 & -1 & -2\\
1 & 2 & 1 & 2
\end{bmatrix}
\)
Calculate \( A^T A \) and \( A^T B \)
\( A^T A =
\begin{bmatrix}
1 & 2 & 0 & 0\\
0 & 0 & -1 & -2\\
1 & 2 & 1 & 2
\end{bmatrix} \cdot
\begin{bmatrix}
1 & 0 & 1\\
2 & 0 & 2 \\
0 & -1 & 1\\
0 & -2 & 2
\end{bmatrix} =
\begin{bmatrix}
5 & 0 & 5\\
0 & 5 & -5\\
5 & -5 & 10
\end{bmatrix}
\)
\( A^T B =
\begin{bmatrix}
1 & 2 & 0 & 0\\
0 & 0 & -1 & -2\\
1 & 2 & 1 & 2
\end{bmatrix} \cdot
\begin{bmatrix}
2 \\
3 \\
4 \\
7
\end{bmatrix} =
\begin{bmatrix}
8\\
-18\\
26
\end{bmatrix}
\)
Substitute \( A^T A \) and \( A^T B \) by their numerical values in the normal equation \( A^T A \hat x = A^T B \), we obtain the system
\(
\begin{bmatrix}
5 & 0 & 5\\
0 & 5 & -5\\
5 & -5 & 10
\end{bmatrix}
\cdot \hat x =
\begin{bmatrix}
8\\
-18\\
26
\end{bmatrix}
\)
Write the above system in augmented matrix form
\(
\begin{bmatrix}
5 & 0 & 5 & | & 8\\
0 & 5 & -5 & | & -18\\
5 & -5 & 10 & | & 26
\end{bmatrix}
\)
Row reduce the above matrix
\(
\begin{bmatrix}
1 & 0 & 1 & | & \dfrac{8}{5}\\
0 & 1 & -1 & | & -\dfrac{18}{5}\\
0 & 0 & 0 & | & 0
\end{bmatrix}
\)
\( x_3 \) is the free variable.
second row gives: \( x_2 - x_3 = -\dfrac{18}{5} \) hence \( x_2 = x_3 -\dfrac{18}{5} \)
first row gives: \( x_1 + x_3 = \dfrac{8}{5} \) hence \( x_1 = - x_3 + \dfrac{8}{5} \)
The solution is given by
\( \hat x =
\begin{bmatrix}
-x_3 + \dfrac{8}{5}\\
x_3 -\dfrac{18}{5}\\
x_3
\end{bmatrix}
\)
with \( x_3 \in \mathbb{R} \)
Note that there is an infinite number of solutions to this least square problem.
c)
\( A \cdot \hat x - B =
\begin{bmatrix}
1 & 0 & 1\\
2 & 0 & 2 \\
0 & -1 & 1\\
0 & -2 & 2
\end{bmatrix}
\begin{bmatrix}
-x_3 + \dfrac{8}{5}\\
x_3 -\dfrac{18}{5}\\
x_3
\end{bmatrix} -
\begin{bmatrix}
2 \\
3 \\
4 \\
7
\end{bmatrix} =
\begin{bmatrix}
-\dfrac{2}{5}\\
\dfrac{1}{5}\\
-\dfrac{2}{5}\\
\dfrac{1}{5}
\end{bmatrix}
\)
\( || A \cdot \hat x - B || = \sqrt { (-\dfrac{2}{5})^2 + (\dfrac{1}{5})^2 + (-\dfrac{2}{5})^2 + (\dfrac{1}{5})^2} = \dfrac{\sqrt{2}}{5} \approx 0.63 \)
Note that the least square error \( || Ax - B || \) is constant and does not depend on \( x_3 \).
More References and links
- Vector Spaces - Questions with Solutions
- Solve Least Squares Problems by the QR Decomposition
- Linear Algebra and its Applications - 5 th Edition - David C. Lay , Steven R. Lay , Judi J. McDonald
- Elementary Linear Algebra - 7 th Edition - Howard Anton and Chris Rorres
