Objectives: Topics
-
Least squares problems
-
Methods for solving least squares problems
Print preview
Section 6.5 Least-Squares Problems
Handout 6.5 Least-Squares Problems
Objectives: Goals
-
Compute general solutions and least squares errors using both:
-
the normal equations
-
the QR decomposition
-
Definition 6.50 Least Squares Solution.
Let \(A\) be an \(m\times n\) matrix. A vector \(\widehat x\) is a least squares solution to \(A\vec x=\vec b\) if
\begin{equation*}
\lVert\vec b - A\widehat x\rVert
\le
\lVert\vec b - A\vec x\rVert
\quad \text{for all } \vec x\in\mathbb{R}^n.
\end{equation*}
Note 6.51.
Suppose \(A \vec x = \vec b\) is a consistent system.
-
Then there exists at least one vector \(\vec v\) so that \(\underline{\hspace{1.5in}}\text{.}\)
Answer.
\(A\vec v = \vec b\) -
This vector \(\widehat x = \vec v\) is a least squares solution to \(A\vec x = \vec b\) and we have that\begin{equation*} \underline{\hspace{0.5in}} = \|\vec b - A\widehat x \| \leq \|\vec b - A\vec x\| \end{equation*}for all \(\vec x \in \mathbb{R}^n\text{.}\)
Answer.
\(0\)
Now, suppose \(A \vec x = \vec b\) is an inconsistent system.
-
Then there is no vector \(\vec v\) so that \(\underline{\hspace{1.5in}}\text{.}\)
Answer.
\(A\vec v = \vec b\) -
So, a least squares solution \(\widehat x\) is a vector so that \(A\widehat x\) is \(\underline{\hspace{3in}}\) to \(\vec b\text{.}\)
Answer.
as close as possible -
Recall that \(A\vec x\) is always a vector in \(\underline{\hspace{1in}}\text{.}\)
Answer.
\(\Col(A)\) -
By Theorem 6.39, we have that \(\widehat b = \underline{\hspace{2in}}\) is the vector in \(\Col(A)\) that is as close as possible to \(\vec b\text{.}\)
Answer.
\(\proj_{\Col(A)}\vec b\) -
Thus, the least squares solutions to \(A\vec x = \vec b\) are the vectors \(\widehat x\) which are solutions to the equation \(\underline{\hspace{1.5in}}\text{.}\)
Answer.
\(A\vec x = \widehat b = \proj_{\Col(A)}\vec b\)
Example 6.52.
Consider the system \(A\vec x = \vec b\) for
\begin{equation*}
A = \begin{bmatrix} 4 \amp 0 \\ 0 \amp 2 \\ 1 \amp 1 \end{bmatrix} \quad \text{and} \quad \vec b = \begin{bmatrix} 2 \\ 0 \\ 11 \end{bmatrix}\text{.}
\end{equation*}
(a)
Is the system consistent?
Solution.
Note that
\begin{equation*}
\begin{bmatrix} 4 \amp 0 \amp \rvert \amp 2 \\ 0 \amp 2 \amp \rvert \amp 0 \\ 1 \amp 1 \amp \rvert \amp 11 \end{bmatrix} \sim \begin{bmatrix} 1 \amp 0 \amp \rvert \amp \frac{1}{2} \\ 0 \amp 1 \amp \rvert \amp 0 \\ 1 \amp 1 \amp \rvert \amp 11 \end{bmatrix} \sim \begin{bmatrix} 1 \amp 0 \amp \rvert \amp \frac{1}{2} \\ 0 \amp 1 \amp \rvert \amp 0 \\ 0 \amp 0 \amp \rvert \amp \frac{21}{2}\end{bmatrix}\text{.}
\end{equation*}
Therefore, there is no solution and the system is inconsistent.
(b)
Find the vector \(\widehat b = \proj_{\Col(A)}\vec b\text{.}\)
Solution.
In order to project onto \(\Col(A)\text{,}\) we need an orthogonal basis of \(\Col(A)\text{.}\) Since the columns of \(A\) are not orthogonal, we start by using the Gram-Schmidt Process. If we assign the columns of \(A\) as \(\vec x_1\) and \(\vec x_2\text{,}\) respectively, then we have that
\begin{align*}
\vec v_1 \amp = \vec x_1 = \begin{bmatrix} 4 \\ 0 \\ 1 \end{bmatrix}\\
\vec v_2 \amp = \vec x_2 - \proj_{\vec v_1}\vec x_2 = \begin{bmatrix} 0 \\2 \\ 1 \end{bmatrix} - \dfrac{1}{17}\begin{bmatrix} 4 \\ 0 \\ 1 \end{bmatrix} = \dfrac{1}{17}\begin{bmatrix}-4 \\ 34 \\ 16\end{bmatrix}
\end{align*}
We will use \(\vec v_2' = 17\vec v_2 = \begin{bmatrix} -4 \\ 34 \\ 16 \end{bmatrix}\) in place of \(\vec v_2\text{.}\) So, \(\left\{\vec v_1, \vec v_2'\right\}\) is an orthogonal basis for \(\Col(A).\text{.}\) Therefore, we have that
\begin{align*}
\widehat b \amp = \proj_{\Col(A)}\vec b\\
\amp = \proj_{\vec v_1}\vec b + \proj_{\vec v_2'}\vec b\\
\amp = \dfrac{19}{17}\begin{bmatrix} 4 \\ 0 \\ 1 \end{bmatrix} + \dfrac{2}{17}\begin{bmatrix} -4 \\ 34 \\ 16 \end{bmatrix}\\
\amp = \dfrac{1}{17}\begin{bmatrix} 76 - 8 \\ 0 + 68 \\ 19 + 32 \end{bmatrix}\\
\amp = \begin{bmatrix} 4 \\ 4 \\ 3 \end{bmatrix}
\end{align*}
So, \(\widehat b = \begin{bmatrix} 4 \\ 4 \\ 3 \end{bmatrix}\) is the vector in \(\Col(A)\) which is as close as possible to \(\vec b\text{.}\)
(c)
Find the least squares solution to \(A\vec x = \vec b\text{.}\)
Solution.
We will solve the equation \(A\vec x = \widehat b\text{.}\) Note that
\begin{equation*}
\begin{bmatrix} 4 \amp 0 \amp \rvert \amp 4 \\ 0 \amp 2 \amp \rvert \amp 4 \\ 1 \amp 1 \amp \rvert \amp 3 \end{bmatrix} \sim \begin{bmatrix} 1 \amp 0 \amp \rvert \amp 1 \\ 0 \amp 1 \amp \rvert \amp 2 \\ 1 \amp 1 \amp \rvert \amp 3 \end{bmatrix} \sim \begin{bmatrix} 1 \amp 0 \amp \rvert \amp 1 \\ 0 \amp 1 \amp \rvert \amp 2 \\ 0 \amp 0 \amp \rvert \amp 0 \end{bmatrix}\text{.}
\end{equation*}
Thus, the least-squares solution is \(\widehat x = \begin{bmatrix} 1 \\ 2 \end{bmatrix}\text{.}\) Notice the error from our least-squares solution is
\begin{equation*}
\|\vec b - A\widehat x\| = \|\vec b - \widehat b\| = \left\|\begin{bmatrix} 2 \\ 0 \\ 11 \end{bmatrix} - \begin{bmatrix} 4 \\ 4 \\ 3 \end{bmatrix}\right\| = \sqrt{4 + 16 + 64} = \sqrt{84}.
\end{equation*}
Note 6.53.
The projection \(A\widehat x\) is the closest point in \(\operatorname{Col}(A)\) to the vector \(\vec b\text{.}\)
-
Note that if \(\widehat x\) is a least squares solution to \(A\vec x = \vec b\text{,}\) then \(\vec b - A\widehat x\) is orthogonal to every vector in \(\underline{\hspace{2in}}\text{.}\)
Answer.
\(\Col(A)\) -
Then, we have that \(\vec b - A\widehat x\) lives in \(\underline{\hspace{2in}}\text{.}\)
Answer.
\(\Col(A)^\perp\) -
By the Four Subspace Theorem, we have that \(\vec b - A\widehat x\) lives in \(\underline{\hspace{2in}}\text{.}\)
Answer.
\(\Nul(A^T)\) -
Therefore, we have that \(\underline{\hspace{1in}}\left(\vec b - A\widehat x\right) = \underline{\hspace{1in}}\text{.}\)
Answer.
\(A^T\left(\vec b - A\widehat x\right) = \vec 0\) -
It follows that \(\underline{\hspace{2in}}\text{.}\)
Answer.
\(A^TA\widehat x = A^T\vec b\)
Theorem 6.54 Normal Equations for Least Squares.
Least squares solutions of \(A\vec x=\vec b\) are precisely the solutions of
\begin{equation*}
A^T A\vec x = A^T\vec b,
\end{equation*}
refered to as the normal equations.
Example 6.55.
Use the normal equations to find the least-squares solution of \(A\vec x=\vec b\text{,}\) where
\begin{equation*}
A=\begin{bmatrix}
4 \amp 0\\
0 \amp 2\\
1 \amp 1
\end{bmatrix},
\qquad
\vec b=\begin{bmatrix}
2\\0\\11
\end{bmatrix}.
\end{equation*}
Solution.
Note that
\begin{equation*}
A^TA = \begin{bmatrix} 4 \amp 0 \amp 1 \\ 0 \amp 2 \amp 1 \end{bmatrix}\begin{bmatrix} 4 \amp 0 \\ 0 \amp 2 \\ 1 \amp 1 \end{bmatrix} = \begin{bmatrix} 17 \amp 1 \\ 1 \amp 5 \end{bmatrix}
\end{equation*}
and
\begin{equation*}
A^T\vec b = \begin{bmatrix} 4 \amp 0 \amp 1 \\ 0 \amp 2 \amp 1 \end{bmatrix}\begin{bmatrix} 2 \\ 0 \\ 11 \end{bmatrix} = \begin{bmatrix} 19 \\ 11 \end{bmatrix}\text{.}
\end{equation*}
Therefore, then normal equations are
\begin{equation*}
A^TA\widehat x = A^T\vec b \quad \implies \quad \begin{bmatrix} 17 \amp 1 \\ 1 \amp 5 \end{bmatrix}\widehat x = \begin{bmatrix} 19 \\ 11 \end{bmatrix}\text{.}
\end{equation*}
Note that
\begin{align*}
\begin{bmatrix} 17 \amp 1 \amp \rvert \amp 19 \\ 1 \amp 5 \amp \rvert \amp 11 \end{bmatrix} \amp \sim \begin{bmatrix} 1 \amp 5 \amp \rvert \amp 11 \\ 17 \amp 1 \amp \rvert \amp 19 \end{bmatrix}\\
\amp \sim \begin{bmatrix} 1 \amp 5 \amp \rvert \amp 11 \\ 0 \amp -84 \amp \rvert \amp -168 \end{bmatrix}\\
\amp \sim \begin{bmatrix} 1 \amp 5 \amp \rvert \amp 11 \\ 0 \amp 1 \amp \rvert \amp 2 \end{bmatrix}\\
\amp \sim \begin{bmatrix} 1 \amp 0 \amp \rvert \amp 1 \\ 0 \amp 1 \amp \rvert \amp 2 \end{bmatrix}
\end{align*}
It follows that the least-squares solution is \(\widehat x = \begin{bmatrix} 1 \\ 2 \end{bmatrix}\text{,}\) which agrees with our answer from Example 6.52.
Theorem 6.56 Unique Least Squares Solutions.
For an \(m\times n\) matrix \(A\text{,}\) the following are equivalent:
-
For every \(\vec b\text{,}\) the equation \(A\vec x=\vec b\) has a unique least squares solution.
-
The columns of \(A\) are linearly independent.
-
\(A^TA\) is invertible.
When these hold,
\begin{equation*}
\widehat x = (A^TA)^{-1}A^T\vec b.
\end{equation*}
Example 6.57.
Compute the least squares solution to \(A\vec x = \vec b\text{,}\) where
\begin{equation*}
A=\begin{bmatrix}
1 \amp -6\\
1 \amp -2\\
1 \amp 1\\
1 \amp 7
\end{bmatrix},
\qquad
\vec b=\begin{bmatrix}
-1\\2\\1\\6
\end{bmatrix}.
\end{equation*}
Solution.
Since the columns of \(A\) are linearly independent, we know by Theorem 6.56 there is a unique least-squares solution to \(A\vec x = \vec b\text{.}\) Note that the columns of \(A\) are already orthogonal. Therefore, this problem wouldn’t be so bad to use our original method to finding a least-squares solution like in Example 6.52. We will instead use the normal equations which is usually the fastest way, especially when the columns of \(A\) are not orthogonal.
Note that
\begin{equation*}
A^TA = \begin{bmatrix} 1 \amp 1 \amp 1 \amp 1 \\ -6 \amp -2 \amp 1 \amp 7 \end{bmatrix}\begin{bmatrix} 1 \amp -6 \\ 1 \amp -2 \\ 1 \amp 1 \\ 1 \amp 7 \end{bmatrix} = \begin{bmatrix} 4 \amp 0 \\ 0 \amp 90 \end{bmatrix}
\end{equation*}
and
\begin{equation*}
A^T\vec b = \begin{bmatrix} 1 \amp 1 \amp 1 \amp 1 \\ -6 \amp -2 \amp 1 \amp 7 \end{bmatrix}\begin{bmatrix}-1 \\ 2 \\ 1 \\ 6 \end{bmatrix} = \begin{bmatrix} 8 \\ 45 \end{bmatrix}\text{.}
\end{equation*}
(The reason \(A^TA\) is diagonal is because the columns of \(A\) are orthogonal.) It follows that
\begin{equation*}
\begin{bmatrix} 4 \amp 0 \amp \rvert \amp 8 \\ 0 \amp 90 \amp \rvert \amp 45 \end{bmatrix} \sim \begin{bmatrix} 1 \amp 0 \amp \rvert \amp 2 \\ 0 \amp 1 \amp \rvert \amp \frac{1}{2}\end{bmatrix}\text{,}
\end{equation*}
so the least square solution is
\begin{equation*}
\widehat x = \begin{bmatrix} 2 \\ \frac{1}{2}\end{bmatrix}\text{.}
\end{equation*}
Theorem 6.58 Least Squares via QR Factorization.
If \(A=QR\) is a QR decomposition of an \(m\times n\) matrix \(A\text{,}\) then for any \(\vec b\) the least squares solution of \(A\vec x=\vec b\) satisfies:
\begin{equation*}
R\widehat x = Q^T\vec b.
\end{equation*}
Example 6.59.
Compute the least squares solution to \(A\vec x=\vec b\text{,}\) where
\begin{equation*}
A=
\begin{bmatrix}
1 \amp 3 \amp 5\\
1 \amp 1 \amp 0\\
1 \amp 1 \amp 2\\
1 \amp 3 \amp 3
\end{bmatrix},
\qquad
\vec b=\begin{bmatrix}
3\\5\\7\\-3
\end{bmatrix}
\end{equation*}
given the QR factorization:
\begin{equation*}
A = \dfrac{1}{2}
\begin{bmatrix}
1 \amp 1 \amp 1\\
1 \amp -1 \amp -1\\
1 \amp -1 \amp 1\\
1 \amp 1 \amp -1
\end{bmatrix}
\begin{bmatrix}
2 \amp 4 \amp 5\\
0 \amp 2 \amp 3\\
0 \amp 0 \amp 2
\end{bmatrix}.
\end{equation*}
Solution.
Note that we are given
\begin{equation*}
Q = \tfrac12
\begin{bmatrix}
1 \amp 1 \amp 1\\
1 \amp -1 \amp -1\\
1 \amp -1 \amp 1\\
1 \amp 1 \amp -1
\end{bmatrix} \quad \text{and} \quad R = \begin{bmatrix}
2 \amp 4 \amp 5\\
0 \amp 2 \amp 3\\
0 \amp 0 \amp 2
\end{bmatrix}\text{.}
\end{equation*}
We have
\begin{equation*}
Q^T\vec b = \dfrac{1}{2}\begin{bmatrix} 1 \amp 1 \amp 1 \amp 1 \\ 1 \amp -1 \amp -1 \amp 1 \\ 1 \amp -1 \amp 1 \amp -1 \end{bmatrix}\begin{bmatrix} 3 \\ 5 \\ 7 \\ -3 \end{bmatrix} = \begin{bmatrix} 6 \\ -6 \\ 4 \end{bmatrix}\text{.}
\end{equation*}
Therefore, by Theorem 6.58, the least-squares solution to \(A\vec x = \vec b\) is the vector \(\widehat x\) so that
\begin{equation*}
\begin{bmatrix}
2 \amp 4 \amp 5\\
0 \amp 2 \amp 3\\
0 \amp 0 \amp 2
\end{bmatrix}\widehat x = \begin{bmatrix} 6 \\ -6 \\ 4 \end{bmatrix}\text{.}
\end{equation*}
If \(R\) was a \(2 \times 2\) matrix, then I usually find its inverse and multiply that to both sides. When \(R\) is \(3 \times 3\) or greater, then I usually solve it by Row Operations. Note that
\begin{align*}
\begin{bmatrix} 2 \amp 4 \amp 5 \amp \rvert \amp 6 \\ 0 \amp 2 \amp 3 \amp \rvert \amp -6 \\ 0 \amp 0 \amp 2 \amp \rvert \amp 4 \end{bmatrix} \amp \sim \begin{bmatrix} 2 \amp 4 \amp 5 \amp \rvert \amp 6 \\ 0 \amp 2 \amp 3 \amp \rvert \amp -6 \\ 0 \amp 0 \amp 1 \amp \rvert \amp 2 \end{bmatrix}\\
\amp \sim \begin{bmatrix} 2 \amp 4 \amp 0 \amp \rvert \amp -4 \\ 0 \amp 2 \amp 0 \amp \rvert \amp -12 \\ 0 \amp 0 \amp 1 \amp \rvert \amp 2 \end{bmatrix}\\
\amp \sim \begin{bmatrix} 2 \amp 4 \amp 0 \amp \rvert \amp -4 \\ 0 \amp 1 \amp 0 \amp \rvert \amp -6 \\ 0 \amp 0 \amp 1 \amp \rvert \amp 2 \end{bmatrix}\\
\amp \sim \begin{bmatrix} 2 \amp 0 \amp 0 \amp \rvert \amp 20 \\ 0 \amp 1 \amp 0 \amp \rvert \amp -6 \\ 0 \amp 0 \amp 1 \amp \rvert \amp 2 \end{bmatrix}\\
\amp \sim \begin{bmatrix} 1 \amp 0 \amp 0 \amp \rvert \amp 10 \\ 0 \amp 1 \amp 0 \amp \rvert \amp -6 \\ 0 \amp 0 \amp 1 \amp \rvert \amp 2 \end{bmatrix}
\end{align*}
Thus, the least-squares solution is
\begin{equation*}
\widehat x = \begin{bmatrix} 10 \\ -6 \\ 2\end{bmatrix}\text{.}
\end{equation*}
