2
$\begingroup$

Find the least square solution and optimal least square solution of the linear system:

$$x_1 + 2x_3 = 1$$ $$x_2 +3x_3 = 0$$ $$-x_1 + x_2 + x_3 =0$$ $$-x_2 -3x_3 =1$$

Letting $A$ be the matrix of coefficents, I get that $A^*A$ is

$$A^*A =\left(\begin{array}{rrr} 2 & -1 & 1 \\ -1 & 3 & 7 \\ 1 & 7 & 23 \end{array}\right)$$

which is not invertible. How can I get the least square solution then? Can someone help me with this please? Thanks.

$\endgroup$
2
$\begingroup$

This is correct:

$$A^*A =\left(\begin{array}{rrr} 2 & -1 & 1 \\ -1 & 3 & 7 \\ 1 & 7 & 23 \end{array}\right)$$

Since you have a singular result, you will likely have infinite solutions.

Use Gaussian elimination to arrive at:

$$x_1 = \dfrac 25 - 2 x_3~, x_2 = -\dfrac 15 - 3x_3~, x_3 = \mbox{free variable}$$

For example, take $x_3 = \dfrac{1}{70}$,

$\endgroup$
1
$\begingroup$

You want the least-squares solution of $$ \left[\begin{array}{rrr}1 & 0 & 2 \\ 0 & 1 & 3 \\ -1 & 1 & 1 \\ 0 & -1 & -3 \end{array}\right]x =\left[\begin{array}{r}1 \\ 0 \\ 0 \\ 1\end{array}\right] $$ What this means is that you want to minimize the distance between the two sides. Let $c_{1}$, $c_{2}$, $c_{3}$ denote the column vectors of the coefficient matrix. The following is orthogonal to $c_1$: $$ c_{2}' = c_{2}-\frac{(c_2,c_1)}{(c_1,c_1)}c_1=c_2+\frac{1}{2}c_1 =\left[\begin{array}{c} 1/2 \\ 1 \\ 1/2 \\ -1 \end{array}\right] $$ And the following is orthogonal to $c_1$, $c_2$: $$ c_{3}'=c_3-\frac{(c_3,c_1)}{(c_1,c_1)}c_1 -\frac{(c_3,c_2')}{(c_2',c_2')}(c_1+\frac{1}{2}c_2) \\ = c_{3}-\frac{1}{2}c_1-\frac{15/2}{5/2}(c_2+\frac{1}{2}c_1) \\\ = c_{3}-2c_1 -3c_2 = \left[\begin{array}{c} 0\\0\\0\\0\end{array}\right]. $$ Now we know that $x_1=-2, x_2=-3, c_3=1$ is in the null space of the original problem, which makes the least squares solution non-unique. So we'll choose a particular least squares solution to minimize $x_1^{2}+x_2^{2}+x_3^{2}$. In other words, there are two minimization problems required to solve this problem.

Let $c_{4}$ denote the column vector on the right. A best solution $x$ is where $$ c_{4} - \frac{(c_4,c_1)}{(c_1,c_1)}c_1-\frac{(c_4,c_2')}{(c_2',c_2')}(c_2+\frac{1}{2}c_1) \\ = c_4 -\frac{1}{2}c_1-\frac{-1/2}{5/2}(c_2+\frac{1}{2}c_1) \\ = c_4 -\frac{2}{5}c_1+\frac{1}{5}c_2. $$ Therefore, a least squares solution is $$ x = \left[\begin{array}{c}2/5 \\ -1/5 \\ 0\end{array}\right] $$ But we may vary this over the null space of the matrix $$ x=\left[\begin{array}{c}2/5 \\ -1/5 \\ 0\end{array}\right] +\alpha\left[\begin{array}{c}2 \\ 3 \\ -1\end{array}\right] $$ The solution vector of smallest length is where $\alpha$ is chosen so that the above is orthogonal to the second vector on the right: $$ x=\left[\begin{array}{c}2/5 \\ -1/5 \\ 0\end{array}\right]-\frac{1/5}{14}\left[\begin{array}{c}2 \\ 3 \\ -1\end{array}\right] = \left[\begin{array}{r}13/35 \\ -17/70 \\1/70\end{array}\right] $$

$\endgroup$
0
$\begingroup$

In order to find the 'best' solution out of those possible, I believe people use the singular value decomposition of $A$. The coefficient matrix ($n\times m$) is broken down into rotation ($m\times m$), scaling ($n\times m$), and second rotation ($n\times n$) matrices. In particular,

$$ A = VLU^* $$

where $U$ and $V$ are orthogonal matrices and the diagonal of $L$ holds the singular values of $A$ (see link). Then the 'pseudoinverse' of $A$ is formed by the product $U \tilde L V^*$ where $\tilde L$ is an $m\times n$ matrix whose diagonal zeros match those of $L$ and whose nonzero diagonal entries are the inverses of those in $L$. Apply the pseudoinverse matrix to the image vector $[1 ~~ 0 ~~ 0 ~~ 1]^T$ to find the least squares solution (the vector whose image under $A$ is closest to the desired image vector in euclidean distance).

$\endgroup$
  • $\begingroup$ Sure you can, see page 407 (analysis of variance problems): math.usu.edu/powell/pseudoinverses.pdf $\endgroup$ – Amzoti Nov 16 '14 at 2:46
  • $\begingroup$ Perhaps I'm misunderstanding your post and comment - are you saying that there are infinite solutions that all minimize $$ \| Ax - b \| ?$$ $\endgroup$ – Titus Nov 16 '14 at 2:51
  • 1
    $\begingroup$ No, he is asking two questions if I am reading it correctly. For the least squares, he has a singular matrix and this can lead to infinite solutions. He is also asking for the optimal solution which I think you are addressing. My answer shows both results, although I did not show the details of how I chose $x_3$. However, that $x_3$ gives the optimal for the variables (which is from the infinite set of solutions). $\endgroup$ – Amzoti Nov 16 '14 at 2:53
  • $\begingroup$ I see. So taking $x_3 = 0$ in your solution will lead to the same solution as my method, is that right? $\endgroup$ – Titus Nov 16 '14 at 3:01
  • $\begingroup$ Yes. Although I would say the problem could have been more clearly written. When I first saw the title, I was asking myself, okay, what is the Op really asking and maybe they are not sure. Regards. $\endgroup$ – Amzoti Nov 16 '14 at 3:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.