3
$\begingroup$

This is for a graduate level course on computational linear systems. I want to do it myself, without help, but it's been ten years since I took linear algebra and I'm not sure I understand what the first part is asking for. The problem states:

Find a solution $x = x^* = (x_1^*, x_2^*, x_3^*, x_4^*)^T$ to the LLS problem:

$$\left\| \begin{pmatrix} 1 & 1 & 1 & 1 \\ 0 & 0 & -e & 0 \\ e & 0 & 0 & 0 \\ 0 & 0 & 0 & e \\ 0 & e & 0 & 0 \\ -e & 0 & 0 & 0 \\ 0 & -e & 0 & 0 \\ 0 & 0 & 0 & e \\ 0 & 0 & e & 0 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{pmatrix} - \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix} \right\|_2 \to \min $$

as a function of $e$.

  1. Find a function $f(x) = f(x_1, x_2, x_3, x_4)$ such that $x$ minimizes $f(x)$ is solution $x^*$ to problem

In case it isn't clear from the formatting, we have an (4x9) matrix with a variable e (not the log base) multiplied by a vertical vector of x1,x2,x3,x4, take the difference of that and another vertical vector with one 1 and 8 zeros and minimize. At one point in the assignment, he calls them Normal Equations. I've looked those up in Wolfram Alpha, but I don't think it helps.

I'm stumped by the question labeled 1. What is the teacher asking for? This is just the beginning part. I think once I understand the question he's asking here I can move on to solving Cholesky's algorithm, etc.

  • 0
    @Calle thanks for formatting for me, but that superscript 2 is a subscript- not sure if it matters, but it's meant to be the second norm.2011-02-18
  • 1
    @6NSString: You want to write down a function, from $\mathbb{R}^4$ to $\mathbb{R}$, whose minimum corresponds precisely to finding the minimum of your problem. I suggest you try writing out what that norm is, in terms of $x_1$, $x_2$, $x_3$, and $x_4$, and see if that helps you figure out what he is asking for.2011-02-18
  • 0
    It doesn't matter (if you minimize $\| \cdot \|_2^2$ you minimize $\| \cdot \|_2$). Actually, I was wondering a bit if it was a subscript or a superscript (and if it was a superscript, if it was the 2-norm).2011-02-18
  • 0
    @Arturo, a yes. Of course. That is, if $x$ minimizes $f(x)$, then $x = x^*$, the solution to the problem.2011-02-18
  • 0
    @Arturo I'm not sure I understand. I've gone ahead and produced Ax (or A * [x1,x2,x3,x4]). I square the elements, and then take the root. (this how I get the 2 norm, yes?). Okay, so how now to go from R4 to R? I don't think I've ever seen such a trick.2011-02-18
  • 0
    @6NSString: suppose I wanted to minimize$$\left|\left|\left(\begin{array}{cc}a&b\\c&d\end{array}\right)\left(\begin{array}{c}x\\y\end{array}\right)-\left(\begin{array}{c}1\\0\end{array}\right)\right|\right|.$$This is the same as minimizing $||(ax+by-1,cx+dy)||$, which is the same as minimizing$$\sqrt{(ax+by-1)^2 + (cx+dy)^2}.$$The latter is a *real* number that depends on the two variables $x$ and $y$. So if I define$$g(x,y)=\sqrt{(ax+by-1)^2+(cx+dy)^2}$$this gives a function $\mathbb{R}^2\to\mathbb{R}$, and its minimum occurs precisely at the point(s) $(x,y)$ that solve my original problem.2011-02-18
  • 0
    @Arturo ah, I think I see. Thank you. I'll work on that for a bit.2011-02-18
  • 0
    Ok, one last clarification: is x in f(x) the vector of [x1,x2,x3,x4]?2011-02-18

1 Answers 1

1

Okay, let's call the big matrix $A$ and the vector with 9 elements $b$.

Then, of course, you want a solution $x$ such that $Ax = b$, because then $Ax - b = 0$ and $\|Ax-b\| = 0$. My guess is that this is not possible for all $e$ (it is possible for $e = 0$, easy to check).

Now, what you then have is a linear least squares problem. That is, you can "solve" for the $x$ such that $Ax$ is as close as it gets to $b$.

In question 1, the teacher probably wants you to write down a function $f$, such that if $f(x)$ reaches it minimum at $x$, then $\|Ax - b\|$ is minimal too.

  • 0
    It is certainly possible there's a typo, but that wouldn't help my understanding.2011-02-18