## Linear Algebra and Its Applications, Exercise 3.3.4

Exercise 3.3.4. Given $A = \begin{bmatrix} 1&0 \\ 0&1 \\ 1&1 \end{bmatrix} \qquad x = \begin{bmatrix} u \\ v \end{bmatrix} \qquad b = \begin{bmatrix} 1 \\ 3 \\ 4 \end{bmatrix}$

expand the expression $E^2 = \| Ax - b \|^2$, compute its partial derivatives with respect to $u$ and $v$, and set them to zero. Compare the resulting equations to $A^TA\bar{x} = A^Tb$ to confirm that you obtain the same normal equations in both cases (i.e., using calculus vs. geometry). Then find the projection $p = A\bar{x}$ and explain why $p = b$. $Ax-b = \begin{bmatrix} 1&0 \\ 0&1 \\ 1&1 \end{bmatrix} \begin{bmatrix} u \\ v \end{bmatrix} - \begin{bmatrix} 1 \\ 3 \\ 4 \end{bmatrix}$ $= \begin{bmatrix} u \\ v \\ u+v \end{bmatrix} - \begin{bmatrix} 1 \\ 3 \\ 4 \end{bmatrix} = \begin{bmatrix} u-1 \\ v-3 \\ (u+v)-4 \end{bmatrix}$

so that $E^2 = \| Ax-b \| = \left(Ax-b\right)^T\left(Ax-b\right)$ $= (u-1)^2 + (v-3)^2 + [(u+v)-4]^2$ $= (u^2-2u+1) + (v^2-6v+9) +[ (u+v)^2 - 8(u+v) + 16]$ $= u^2-2u+1+v^2-6v+9+u^2+2uv+v^2-8u-8v+16$ $= 2u^2+2v^2+2uv-10u-14v+26$

Taking the partial derivative of this expression with respect to $u$ we have $\partial E^2/{\partial u} = \partial/{\partial u}(2u^2+2v^2+2uv-10u-14v+26)$ $= 4u+2v-10$

and setting it to zero we have $4\bar{u}+2\bar{v}-10 = 0$

where $\bar{u}$ and $\bar{v}$ represent the least squares solution.

Taking the partial derivative of this expression with respect to $v$ we have $\partial E^2/{\partial v} = \partial/{\partial v}(2u^2+2v^2+2uv-10u-14v+26)$ $= 4v+2u-14$

and setting it to zero we have $4\bar{v}+2\bar{u}-14 = 0$

where again $\bar{u}$ and $\bar{v}$ represent the least squares solution.

We then have a system of two equations $\begin{array}{rcrcr} 4\bar{u}&+&2\bar{v}&=&10 \\ 2\bar{u}&+&4\bar{v}&=&14 \end{array}$

that is equivalent to the matrix equation $\begin{bmatrix} 4&2 \\ 2&4 \end{bmatrix} \begin{bmatrix} \bar{u} \\ \bar{v}\end{bmatrix} = \begin{bmatrix} 10 \\ 14 \end{bmatrix}$

We now compare this to the normal equations $A^TA\bar{x} = A^Tb$. We have $A^TA = \begin{bmatrix} 1&0&1 \\ 0&1&1 \end{bmatrix} \begin{bmatrix} 1&0 \\ 0&1 \\ 1&1 \end{bmatrix} = \begin{bmatrix} 2&1 \\ 1&2 \end{bmatrix}$

and $A^Tb = \begin{bmatrix} 1&0&1 \\ 0&1&1 \end{bmatrix} \begin{bmatrix} 1 \\ 3 \\ 4 \end{bmatrix} = \begin{bmatrix} 5 \\ 7 \end{bmatrix}$

so that the normal equation in matrix form is $\begin{bmatrix} 2&1 \\ 1&2 \end{bmatrix} \begin{bmatrix} \bar{u} \\ \bar{v} \end{bmatrix} = \begin{bmatrix} 5 \\ 7 \end{bmatrix}$

Note that this equation is the same as the previous equation calculated from taking the derivatives, except with both sides divided by 2.

We can now solve for $\bar{x} = \left(A^TA\right)^{-1}A^Tb$. We have $\left(A^TA\right) = \begin{bmatrix} 2&1 \\ 1&2 \end{bmatrix}^{-1} = \frac{1}{2 \cdot 2 - 1 \cdot 1} \begin{bmatrix} 2&-1 \\ -1&2 \end{bmatrix}$ $= \frac{1}{3} \begin{bmatrix} 2&-1 \\ -1&2 \end{bmatrix} = \begin{bmatrix} \frac{2}{3}&-\frac{1}{3} \\ -\frac{1}{3}&\frac{2}{3} \end{bmatrix}$

so that $\bar{x} = \left(A^TA\right)^{-1}A^Tb = \begin{bmatrix} \frac{2}{3}&-\frac{1}{3} \\ -\frac{1}{3}&\frac{2}{3} \end{bmatrix} \begin{bmatrix} 5 \\ 7 \end{bmatrix}$ $= \begin{bmatrix} \frac{10}{3}-\frac{7}{3} \\ -\frac{5}{3}+\frac{14}{3} \end{bmatrix} = \begin{bmatrix} 1 \\ 3 \end{bmatrix}$

We can multiply $\bar{x}$ by $A$ to obtain the projection $p$ of $b$ onto the column space of $A$: $p = A\bar{x} = \begin{bmatrix} 1&0 \\ 0&1 \\ 1&1 \end{bmatrix} \begin{bmatrix} 1 \\ 3 \end{bmatrix} = \begin{bmatrix} 1 \\ 3 \\ 4 \end{bmatrix} = b$

We have $p = b$ because $b$ is already in the column space of $A$; in particular, $b$ is equal to the first column of $A$ plus 3 times the second column of $A$: $b = \begin{bmatrix} 1 \\ 3 \\ 4 \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix} + 3 \begin{bmatrix} 0 \\ 1 \\ 1 \end{bmatrix}$

UPDATE: Fixed a typo in the equations involving $A^TA$ and $A^Tb$. Thanks go to Matt for finding this error.

NOTE: This continues a series of posts containing worked out exercises from the (out of print) book Linear Algebra and Its Applications, Third Edition by Gilbert Strang.

If you find these posts useful I encourage you to also check out the more current Linear Algebra and Its Applications, Fourth Edition , Dr Strang’s introductory textbook Introduction to Linear Algebra, Fourth Edition and the accompanying free online course, and Dr Strang’s other books .

This entry was posted in linear algebra and tagged , , , . Bookmark the permalink.

### 2 Responses to Linear Algebra and Its Applications, Exercise 3.3.4

1. Matt says:

You have a slight misprint with A transposed about half way through the page. The top row should be 1 0 1 not the 1 0 0 that you have. I see you have it wrong twice but the answer is still correct. Probably just copied it wrong.

• hecker says:

Fixed. Thanks for catching this!