Finding the best solution to an inconsistent system $A\mathbf{u} = \mathbf{b}$.

Question

Let $A = \begin{bmatrix} -1 & 1 \\ 2 & -1 \\ 1 & 1 \end{bmatrix}$ and $\mathbf{b} = \begin{bmatrix} 1 \\ 2 \\ 0 \end{bmatrix}$.
1. Find a "best solution" to the inconsistent system $A\mathbf{u} = \mathbf{b}$.
2. Find the orthogonal projection of $\mathbf{b}$ onto the column space of $A$.

For the second question the column space of $A$ has vectors that are all linearly independent. We first find the projection matrix given by $P = A(A^TA)^{-1}A^T$. Lets first calculate $A^TA$ \begin{equation*} A^TA = \begin{bmatrix} -1 & 2 & 1 \\ 1 & -1 & 1 \end{bmatrix} \begin{bmatrix} -1 & 1 \\ 2 & -1 \\ 1 & 1 \end{bmatrix} = \begin{bmatrix} 6 & -2 \\ -2 & 3 \end{bmatrix}. \end{equation*} This means that \begin{equation*} (A^TA)^{-1} = \frac{1}{14}\begin{bmatrix} 3 & 2 \\ 2 & 6 \end{bmatrix}. \end{equation*} Hence, \begin{equation*} \begin{split} P = A(A^TA)^{-1}A^T &= \frac{1}{14}\begin{bmatrix} -1 & 1 \\ 2 & -1 \\ 1 & 1 \end{bmatrix} \begin{bmatrix} 3 & 2 \\ 2 & 6 \end{bmatrix} \begin{bmatrix} -1 & 2 & 1 \\ 1 & -1 & 1 \end{bmatrix} \\ &= \frac{1}{14}\begin{bmatrix} -1 & 1 \\ 2 & -1 \\ 1 & 1 \end{bmatrix} \begin{bmatrix} -1 & 4 & 5 \\ 4 & -2 & 8 \end{bmatrix} \\ &= \frac{1}{14}\begin{bmatrix} 5 & -6 & 3 \\ -6 & 10 & 2 \\ 3 & 2 & 13 \end{bmatrix}. \end{split} \end{equation*} So the orthogonal projection of $\mathbf{b} = (1,2,0)$ onto the column space of $A$ is \begin{equation*} \frac{1}{14}\begin{bmatrix} 5 & -6 & 3 \\ -6 & 10 & 2 \\ 3 & 2 & 13 \end{bmatrix} \begin{bmatrix} 1 \\ 2 \\ 0 \\ \end{bmatrix} = \frac{1}{14}\begin{bmatrix} -7 \\ 14 \\ 7 \end{bmatrix} = \begin{bmatrix} -1/2 \\ 1 \\ 1/2 \end{bmatrix}. \end{equation*} Not sure what is meant by the "best solution" to the system. Any would help would be great!!!

Answer 1

As you said $A\mathbf{u} = \mathbf{b}$ is an inconsistent system that has no solution. So the best you can hope for is to find a $\mathbf{u}$ that makes $A\mathbf{u}$ "close to" $\mathbf{b}$. Or to say the same thing you can try to make $A\mathbf{u} - \mathbf{b}$ "as close to $\mathbf{0}$ as possible".

So the problem boils down to minimizing the size of $A\mathbf{u} - \mathbf{b}$ i.e. $||A\mathbf{u} - \mathbf{b}||$. Though in practice it is more convenient to minimize $F(\mathbf{u}) = ||A\mathbf{u} - \mathbf{b}||^2$ instead.

Now if you set $\mathbf{u} = \begin{bmatrix}x \\ y \end{bmatrix}$ you can multiply things out to get: $$ A\mathbf{u} - \mathbf{b} = \begin{bmatrix} -x + y - 1 \\ 2x - y - 2 \\ x + y \end{bmatrix} $$ So that $$ F(x, y) = ||A\mathbf{u} - \mathbf{b}||^2 = (-x + y -1)^2 + (2x - y - 2)^2 + (x + y)^2 $$

A standard way to try to minimize a multivariable function like $F(x, y)$ is to take the partial derivatives w.r.t. to $x$ and $y$ and set the resulting equations to $0$: $$ \partial_x F(x, y) = 12x - 4y - 6 = 0 $$ $$ \partial_y F(x, y) = -4x + 6y + 2 = 0 $$

And solving these gives you $x = \frac{1}{2}$ and $y = 0$. If you want to convince yourself that these values of $x$ and $y$ do in fact minimize $F(x, y) = ||A\mathbf{u} - \mathbf{b}||^2$, you can use the Second Partial Derivative Test: $$ \partial_{xx} F(x, y) = 12 $$ $$ \partial_{xy} F(x, y) = -4 = \partial_{yx} F(x, y) $$ $$ \partial_{yy} F(x, y) = 6 $$ And note that the matrix of these second partials i.e. the Hessian of $F(x, y)$ $$ \begin{bmatrix} \partial_{xx} F(x, y) &\partial_{xy} F(x, y) \\ \partial_{yx} F(x, y) &\partial_{yy} F(x, y) \end{bmatrix} = \begin{bmatrix} 12 &-4 \\ -4 &6 \end{bmatrix} $$ has positive determinant $56 > 0$ and furthermore, at $(\frac{1}{2}, 0)$ the value of $\partial_{xx} F(x, y)$ is always positive: $12 > 0$. So the Second Partial Derivative Test says that $(\frac{1}{2}, 0)$ does indeed minimize $F(x, y) = ||A\mathbf{u} - \mathbf{b}||^2$ and hence $$ \mathbf{u} = \begin{bmatrix}\frac{1}{2} \\ 0 \end{bmatrix} $$ is the best solution to our linear system.

Answer 2

Actually there are three lines $$-x+y=1, 2x-y=2, x+y=0~~~(1)$$ which make a triangle. pre-multiply the given inconsistent equation $$AX=B,~~ A=\begin{bmatrix} -1 & 1\\ 2 & 1 \\ 1 & 1 \end{bmatrix}, B=\begin{bmatrix} 1 \\ 2\\ 0 \end{bmatrix} ~~~~(2)$$ by $A^{T}$ to get $$ A^T A X= A^T B$$ which is nothing but $${\cal A} X= {\cal B},~~ {\cal A}_{2 \times 2},~~ {\cal B}_{2,1} ~~~(3)$$ You can then solve (3) for two unknowns $(x_0, y_0)$. This point $P(x_0, y_0)$ is inside the triangle mentioned above. This solution is a representative approximate solution of the inconsistent equations (1),(2). Here in your case $${\cal A}=\begin{bmatrix} 6 & -2 \\ -2 & 3 \end{bmatrix}, ~~{\cal B}=\begin{bmatrix} 3 \\ -1 \end{bmatrix} \Rightarrow X={\cal A}^{-1} {\cal B}\Rightarrow X=\begin{bmatrix} 1/2 \\ 0 \end{bmatrix} \Rightarrow ~~x_0=1/2, y_0=0.$$ So $(1/2,0)$ is representative solution of these inconsistent/ overdetermined equations (1) and (2). Further it will be interesting to see if it is also least square or the best solution to these equations.