Linear algebra least squares solution

1. Aug 17, 2010

SpiffyEh

1. The problem statement, all variables and given/known data

Suppose you have a set S of three points in R^2,
S1 = {(1, 12), (2, 15), (3, 16)}
S2 = {(1, 12), (1, 15), (3, 16)}
S3 = {(1, 12), (2, 15), (2, 15)}

which you seek to interpolate with the quadratic polynomial p(t) = a_0 + a_1t + a_2t^2.
Problem: Least-Squares Approximation. Find the least-squares solution for S3 which we previously found to have no solution.

2. Relevant equations

3. The attempt at a solution

I understand the idea of least squares solutions I think, if I have a matrix and a solution but i'm confused about this one. I'm just not seeing where to start this. If someone could please get me going that would be great. Thanks

2. Aug 17, 2010

hgfalling

Recall that in least squares analysis, our goal is the set of coefficients that you have identified as ai.

So we could write down the equations of this regression as:

$$a_0 + a_1 t_1 + a_2 t_1^2 = y_1$$
$$a_0 + a_1 t_2 + a_2 t_2^2 = y_2$$
$$a_0 + a_1 t_3 + a_2 t_3^2 = y_3$$

This is the same as the matrix equation:

$$\left(\begin{array}{ccc} 1 & t_1 & t_1^2 \\ 1 & t_2 & t_2^2 \\ 1 & t_3 & t_3^2 \end{array}\right) \left(\begin{array}{c} a_0\\a_1\\a_2 \end{array}\right) = \left(\begin{array}{c} y_1\\y_2\\y_3 \end{array}\right)$$

Now you can use your normal least squares technique to solve this for $\vec a$.

3. Aug 17, 2010

SpiffyEh

I don't see how to set s3 up in this way though, thats what i'm really having issues with.

4. Aug 17, 2010

hgfalling

Well, the a vector is going to be an unknown. You need to plug in for t and for y.

Your data has (independent, dependent) data, right? So plug in the data to the equation there.

5. Aug 17, 2010

SpiffyEh

umm... since S3 = {(1, 12), (2, 15), (2, 15)}

$$\left(\begin{array}{ccc}1 & 1 & 12 \\ 1 & 2 & 12 \\ 1 & 2 & 15\end{array}\right)\left(\begin{array}{c}a_0\\a_1\\a_2\end{array}\right) = \left(\begin{array}{c}y_1\\y_2\\y_3\end{array}\right)$$

Is that right? Then what do I do for y? I don't think I'm getting it

6. Aug 17, 2010

Dickfore

This is not least squares method. There is no more than one parabola passing through three points, so there is no fitting involved.

7. Aug 17, 2010

Staff: Mentor

But S3 has only two distinct points.

This problem is not stated very clearly, IMO.
I don't see any set S. I see three sets, S1, S2, and S3, the first two of which have three points, and the last of which has two points.

8. Aug 17, 2010

SpiffyEh

I'm told to use s3 which is why i'm so confused about how to set up a matrix for it and a vector b in Ax = b. I understand where to go from there.

9. Aug 17, 2010

Staff: Mentor

Can you give us the exact wording of this problem? As you have posted it, there seems to be some incorrect and/or missing information.

10. Aug 17, 2010

SpiffyEh

I attached a screen shot of the exact problem. I don't think I missed any information.

Attached Files:

• prob.png
File size:
20.7 KB
Views:
106
11. Aug 17, 2010

Staff: Mentor

No, it looks like you copied the information faithfully, but whoever wrote the problem wasn't very clear. It says that S is a set with three points, then gives three sets, S1, S2, and S3, each with (sort of) three points.

I would be inclined to ask the instructor for clarification.

12. Aug 17, 2010

Dickfore

The point is that for every set $S_{i}, (i=1,2,3)$ there are three points in the plane and you can draw at most one interpolating parabola $y = a_{0} + a_{1} \, x + a_{2} \, x^{2}$, i.e. one that passes through each of the three points according to the system:

$$\left(\begin{array}{ccc} 1 & x_{1} & x^{2}_{1} \\ 1 & x_{2} & x^{2}_{2} \\ 1 & x_{3} & x^{2}_{3} \end{array}\right) \cdot \left(\begin{array}{c} a_{0} \\ a_{1} \\ a_{2} \end{array}\right) = \left(\begin{array}{c} y_{1} & y_{2} & y_{3} \end{array}\right)$$

However, this is not least squares fitting. This is quadratic interpolation. If the determinant of the system is zero, there is no solution for this linear system. I think the problem says that for the set S3 this is the case.

In fitting, you don't require that the fitting curve passes through all of the experimental points (it can even not pass through any of them). You simply require that the coeffiicients are chosen such that the sum of the squares of the errors:

$$S(a_{0}, a_{1}, a_{2}) = \sum_{i = 1}^{3}{(a_{0} + a_{1} \, x_{i} + a_{2} \, x^{2}_{i} - y_{i})^{2}}$$

be minimal. For this, you have the conditions:

$$\frac{\partial S}{\partial a_{0}} = \frac{\partial S}{\partial a_{1}} = \frac{\partial S}{\partial a_{2}} = 0$$

By evaluating the derivatives and simplifying, you should obtain another linear system for the fitting coefficients. Try to find what the system looks like (in general) and post it here so that we can verify that your work is correct.

13. Aug 17, 2010

SpiffyEh

I'm confused. I don't know what to do with s3. If you could explain in more detail that would really help. I also emailed my professor but he hasn't gotten back to me and this is a practice problem and my exam is tomorrow so I'm hoping I can understand it before then.

14. Aug 17, 2010

SpiffyEh

ok, I found out from the professor that
A = $$\left(\begin{array}{ccc}1 & 1 & 1 \\1 & 1 & 1 \\1 & 3 & 9\end{array}\right)$$
and b = $$\left(\begin{array}{ccc}12 \\ 15 \\16\end{array}\right)$$

So, I went through and did A^TA and A^Tb and augmented the matrix and row reduced to solve for x
I got

x =$$\left(\begin{array}{ccc}391/60 \\ 5/4\\0\end{array}\right)$$ + x_3 $$\left(\begin{array}{ccc}3\\ -4\\1\end{array}\right)$$

Can someone please check my work on this? I'm worried about the 391/60, but I went through the work and I don't see an error.