Example Problems

Suppose we are given the equations \left\{\begin{array}[l] 2x - y = 2 \\ x + 2y = 1 \\ x + y = 4\end{array}\right.. Let's try solving for the values of $x$ and $y$ that satisfy all three equations.

$\begin{bmatrix} 2 & 1 \\ 1 & 2 \\ 1 & 1 \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} 2 \\ 1 \\ 4 \end{bmatrix}$

By performing Gaussian elimination, we end up with

$\begin{bmatrix} 2 & -1 \\ 0 & -5 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} 2 \\ 0 \\ -3 \end{bmatrix}$

The system is overdetermined! $y$ cannot equal $0$ and $-3$ simultaneously. In this type of situation, we have to resort to using least squares. We will find values of $x'$ and $y'$ that is the "closest" to each of the equations (imagine minimizing the squared distances between $(x', y')$ and each of the lines). Let's solve for this using the equation $\textbf{A}^T\textbf{A}\vec{x}=\textbf{A}^T\vec{b}$.

$\textbf{A}^T\textbf{A} = \begin{bmatrix} 2 & 1 & 1 \\ -1 & 2 & 1 \end{bmatrix} \begin{bmatrix} 2 & -1 \\ 1 & 2 \\ 1 & 1 \end{bmatrix} = \begin{bmatrix} 6 & 1 \\ 1 & 6 \end{bmatrix}$

Sanity check: $\textbf{A}^T\textbf{A}$ is always a symmetric matrix. Why? $(\textbf{A}^T\textbf{A})^T = \textbf{A}^T\textbf{A}^{T^T} = \textbf{A}^T\textbf{A}$

$\textbf{A}^T\vec{b} = \begin{bmatrix} 2 & 1 & 1 \\ -1 & 2 & 1 \end{bmatrix} \begin{bmatrix} 2 \\ 1 \\ 4 \end{bmatrix} = \begin{bmatrix} 9 \\ 4 \end{bmatrix}$

Now we have

$\begin{bmatrix} 6 & 1 \\ 1 & 6 \end{bmatrix} \vec{x} = \begin{bmatrix} 9 \\ 4 \end{bmatrix}$

$\vec{x} = \begin{bmatrix} 6 & 1 \\ 1 & 6 \end{bmatrix}^{-1}\begin{bmatrix} 9 \\ 4 \end{bmatrix}$

$\vec{x} = \frac{1}{35} \begin{bmatrix} 6 & -1 \\ -1 & 6\end{bmatrix} \begin{bmatrix} 9 \\ 4 \end{bmatrix} = \begin{bmatrix} \frac{10}{7} \\ \frac{3}{7} \end{bmatrix}$