In many real-life applications, a system of equations of the form \( A x = B \) may be inconsistent. This typically occurs because real-world data contains measurement errors (noise) and systems are usually overdetermined (meaning more data points are collected than there are unknown variables to increase reliability). Because the collected data points do not perfectly align, an exact mathematical solution \( x \) cannot be found. However, it is often possible to find an optimal approximate solution \( \hat{x} \).
The least squares problem seeks to find an approximate solution \( \hat{x} \) such that the distance between the vectors \( A \hat{x} \) and \( B \) (given by the norm \( ||A \hat{x} - B|| \)) is as small as possible.
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 \).
Given the system \( Ax = B \) with:
$$ A = \begin{bmatrix} 2 & 0 \\ 0 & 1 \\ 1 & 2 \end{bmatrix} \quad \text{and} \quad B = \begin{bmatrix} 1 \\ 0 \\ 3 \end{bmatrix} $$a) Show that the system is inconsistent (has no solution).
b) Find the least squares solution to the inconsistent system.
c) Determine the least squares error given by \( || A \hat{x} - B || \).
a) Show the system is inconsistent
We write the system as an augmented matrix and row reduce it:
$$ \begin{bmatrix} 2 & 0 & | & 1 \\ 0 & 1 & | & 0 \\ 1 & 2 & | & 3 \end{bmatrix} $$After applying Gauss-Jordan elimination:
$$ \begin{bmatrix} 1 & 0 & | & 0 \\ 0 & 1 & | & 0 \\ 0 & 0 & | & 1 \end{bmatrix} $$The last row translates to the equation \( 0x_1 + 0x_2 = 1 \), which is impossible. Therefore, the system is inconsistent.
b) Find the least squares solution
First, find the transpose of \( A \):
$$ A^T = \begin{bmatrix} 2 & 0 & 1 \\ 0 & 1 & 2 \end{bmatrix} $$Calculate \( A^T A \):
$$ A^T A = \begin{bmatrix} 2 & 0 & 1 \\ 0 & 1 & 2 \end{bmatrix} \begin{bmatrix} 2 & 0 \\ 0 & 1 \\ 1 & 2 \end{bmatrix} = \begin{bmatrix} 5 & 2 \\ 2 & 5 \end{bmatrix} $$Calculate \( A^T B \):
$$ A^T B = \begin{bmatrix} 2 & 0 & 1 \\ 0 & 1 & 2 \end{bmatrix} \begin{bmatrix} 1 \\ 0 \\ 3 \end{bmatrix} = \begin{bmatrix} 5 \\ 6 \end{bmatrix} $$Set up the normal equation \( A^T A \hat{x} = A^T B \):
$$ \begin{bmatrix} 5 & 2 \\ 2 & 5 \end{bmatrix} \hat{x} = \begin{bmatrix} 5 \\ 6 \end{bmatrix} $$Solving this system yields the approximate solution:
$$ \hat{x} = \begin{bmatrix} \frac{13}{21} \\ \frac{20}{21} \end{bmatrix} $$c) Determine the least squares error
First, calculate the vector \( A \hat{x} - B \):
$$ A \hat{x} - B = \begin{bmatrix} 2 & 0 \\ 0 & 1 \\ 1 & 2 \end{bmatrix} \begin{bmatrix} \frac{13}{21} \\ \frac{20}{21} \end{bmatrix} - \begin{bmatrix} 1 \\ 0 \\ 3 \end{bmatrix} = \begin{bmatrix} \frac{5}{21} \\ \frac{20}{21} \\ -\frac{10}{21} \end{bmatrix} $$Next, find the norm (length) of this vector:
$$ ||A \hat{x} - B|| = \sqrt{\left(\frac{5}{21}\right)^2 + \left(\frac{20}{21}\right)^2 + \left(-\frac{10}{21}\right)^2} = \frac{5\sqrt{21}}{21} \approx 1.1 $$Given the system \( Ax = B \) with:
$$ A = \begin{bmatrix} 1 & 0 & 1 \\ 2 & 0 & 2 \\ 0 & -1 & 1 \\ 0 & -2 & 2 \end{bmatrix} \quad \text{and} \quad B = \begin{bmatrix} 2 \\ 3 \\ 4 \\ 7 \end{bmatrix} $$a) Show that the system is inconsistent.
b) Find the least squares solution to the inconsistent system.
c) Determine the least squares error given by \( || Ax - B || \).
a) Show the system is inconsistent
Write the 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} $$Writing in row-reduced form (Gauss-Jordan) gives:
$$ \begin{bmatrix} 1 & 0 & 1 & | & 0 \\ 0 & 1 & -1 & | & 0 \\ 0 & 0 & 0 & | & 1 \\ 0 & 0 & 0 & | & 0 \end{bmatrix} $$The third row translates to the equation \( 0x_1 + 0x_2 + 0x_3 = 1 \), which has no solution. The system is therefore inconsistent.
b) Find the least squares solution
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 \):
$$ A^T A = \begin{bmatrix} 1 & 2 & 0 & 0 \\ 0 & 0 & -1 & -2 \\ 1 & 2 & 1 & 2 \end{bmatrix} \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} $$Calculate \( A^T B \):
$$ A^T B = \begin{bmatrix} 1 & 2 & 0 & 0 \\ 0 & 0 & -1 & -2 \\ 1 & 2 & 1 & 2 \end{bmatrix} \begin{bmatrix} 2 \\ 3 \\ 4 \\ 7 \end{bmatrix} = \begin{bmatrix} 8 \\ -18 \\ 26 \end{bmatrix} $$Set up the normal equation \( A^T A \hat{x} = A^T B \):
$$ \begin{bmatrix} 5 & 0 & 5 \\ 0 & 5 & -5 \\ 5 & -5 & 10 \end{bmatrix} \hat{x} = \begin{bmatrix} 8 \\ -18 \\ 26 \end{bmatrix} $$Write this as an augmented matrix and row reduce:
$$ \begin{bmatrix} 5 & 0 & 5 & | & 8 \\ 0 & 5 & -5 & | & -18 \\ 5 & -5 & 10 & | & 26 \end{bmatrix} \rightarrow \begin{bmatrix} 1 & 0 & 1 & | & \frac{8}{5} \\ 0 & 1 & -1 & | & -\frac{18}{5} \\ 0 & 0 & 0 & | & 0 \end{bmatrix} $$Here, \( x_3 \) is a free variable.
From the second row: \( x_2 - x_3 = -\frac{18}{5} \implies x_2 = x_3 - \frac{18}{5} \)
From the first row: \( x_1 + x_3 = \frac{8}{5} \implies x_1 = -x_3 + \frac{8}{5} \)
The general solution is given by:
$$ \hat{x} = \begin{bmatrix} -x_3 + \frac{8}{5} \\ x_3 - \frac{18}{5} \\ x_3 \end{bmatrix} \quad \text{for any } x_3 \in \mathbb{R} $$Note: There are an infinite number of solutions to this specific least squares problem.
c) Determine the least squares error
First, calculate the vector \( A \hat{x} - B \):
$$ A \hat{x} - B = \begin{bmatrix} 1 & 0 & 1 \\ 2 & 0 & 2 \\ 0 & -1 & 1 \\ 0 & -2 & 2 \end{bmatrix} \begin{bmatrix} -x_3 + \frac{8}{5} \\ x_3 - \frac{18}{5} \\ x_3 \end{bmatrix} - \begin{bmatrix} 2 \\ 3 \\ 4 \\ 7 \end{bmatrix} = \begin{bmatrix} -\frac{2}{5} \\ \frac{1}{5} \\ -\frac{2}{5} \\ \frac{1}{5} \end{bmatrix} $$Next, find the norm of this vector:
$$ ||A \hat{x} - B|| = \sqrt{\left(-\frac{2}{5}\right)^2 + \left(\frac{1}{5}\right)^2 + \left(-\frac{2}{5}\right)^2 + \left(\frac{1}{5}\right)^2} = \frac{\sqrt{2}}{5} \approx 0.63 $$Note: The least squares error is constant and does not depend on the free variable \( x_3 \).