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$ .

Answer: We have

$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&0 \\ 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&0 \\ 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}$

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.

Buy me a snack to sponsor more posts like this!

Linear Algebra and Its Applications, Exercise 3.3.4

Related

Leave a Reply Cancel reply

Archives

Meta