6.5 Least-Squares Problems

Print preview

Section 6.5 Least-Squares Problems

Handout 6.5 Least-Squares Problems

Objectives: Topics

Least squares problems

🔗
Methods for solving 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{.}$
🔗

🔗
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{.}$

🔗

🔗

🔗

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{.}$
🔗

🔗
So, a least squares solution $\widehat x$ is a vector so that $A\widehat x$ is $\underline{\hspace{3in}}$ to $\vec b\text{.}$
🔗

🔗
Recall that $A\vec x$ is always a vector in $\underline{\hspace{1in}}\text{.}$
🔗

🔗
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{.}$
🔗

🔗
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{.}$
🔗

🔗

🔗

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?

🔗

(b)

Find the vector $\widehat b = \proj_{\Col(A)}\vec b\text{.}$

🔗

(c)

Find the least squares solution to $A\vec x = \vec b\text{.}$

🔗

Note 6.53.

$Geometric interpretation of least squares projection.$

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{.}$
🔗

🔗
Then, we have that $\vec b - A\widehat x$ lives in $\underline{\hspace{2in}}\text{.}$
🔗

🔗
By the Four Subspace Theorem, we have that $\vec b - A\widehat x$ lives in $\underline{\hspace{2in}}\text{.}$
🔗

🔗
Therefore, we have that $\underline{\hspace{1in}}\left(\vec b - A\widehat x\right) = \underline{\hspace{1in}}\text{.}$
🔗

🔗
It follows that $\underline{\hspace{2in}}\text{.}$
🔗

🔗

🔗

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*}

🔗

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*}

🔗

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*}

🔗

Prev Top Next