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

1. Vector Spaces - Questions with Solutions
2. Solve Least Squares Problems by the QR Decomposition
3. Linear Algebra and its Applications - 5 th Edition - David C. Lay , Steven R. Lay , Judi J. McDonald
4. Elementary Linear Algebra - 7 th Edition - Howard Anton and Chris Rorres