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 x with hat to the given system A x = B is enough.
The least squares problems is to find an approximate solution x with hat such that the distance between the vectors A x and B given by is the smallest.
It is shown in Linear Algebra and its Applications that the approximate solution x with hat is given by the normal equation
Matrix Equation where AT is the transpose of matrix A .



Examples with Solutions

Example 1
a) Show that the system A x = B with Matrices A and B 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 || A x = 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
Matrix Equation
Write the above system in augmented matrix form
Matrix Equation
Row reduce (Gauss Jordan) the above augmented matrix
Matrix Equation \( \) \( \) \( \) \( \)
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