# Linear Algebra Question (Polynomial Interpolation)

Given the data for an experiment:

Velocity: 0, 2, 4, 6, 8, 10
Force: 0 , 2.9, 14.8, 39.6, 74.3, 119

(One force value listed below one velocity value in a table)

Find an interpolating polynomial $p(t) = a_0 + a_1 t + a_2 t^2 + a_3 t^3 + a_4 t^4 + a_5 t^5$ for these data.

What happens if you try to use a polynomial of degree less than 5?

(This is a MATLAB question, but our class was never taught how to answer this kind of question in the first place)

-
How would I set that up as a matrix? That's all we've really been taught so far. – Randy Oct 4 '11 at 23:47
As for actually doing these computations in MATLAB: constructing the Vandermonde matrix and then using the operator  \  is fine, but then there's polyfit()... – J. M. Oct 5 '11 at 8:55

Here goes: remember the statement "two points determine a line"? The generalization of this statement to polynomials is that "$n+1$ conditions are needed to uniquely determine an $n$-th degree polynomial". That is, "three points determine a quadratic", "four points determine a cubic", ... you get the drift.

You were given six points: thus, any uniquely determined polynomial that must pass through those six points (you are interpolating, after all) should have a degree at most five (there are polynomials with degree $> 5$ that pass through those points, but you won't be able to pin them down unless you've other conditions). It can happen that the degree of the underlying interpolating polynomial might be less, but there's a way to check for that: take successive differences repeatedly until you encounter a constant sequence ($2.9-0, 14.9-2.8, \dots$ and then keep repeating). When I try it out, I've needed five iterations to reach a constant sequence, so an interpolating polynomial of degree $5$ should be expected.

However, there is a related procedure, called fitting or regression, that attempts to derive a polynomial of degree usually less than $n$ that is a "best approximation" of your data. Such a function won't pass through the given points, however, and the underlying assumptions are different.

-
"any polynomial that must pass through those six points (you are interpolating, after all) should have a degree at most five." - I understand what you mean, but what you said here sounds a little like if you have 2 points, then you can join them only using a line. Certainly a parabola could be made to pass through the points as well. :) – Srivatsan Oct 4 '11 at 23:49
Of course, but the parabola through two points isn't uniquely determined anymore. :) – J. M. Oct 4 '11 at 23:53
Sure. But still I disagree with "any polynomial..should have degree at most 5". Perhaps you can expand that bit explaining that the polynomial can be uniquely determined with degree 5, and won't be for higher degrees. – Srivatsan Oct 4 '11 at 23:56
Okay, let me fix the phrasing... – J. M. Oct 4 '11 at 23:57

Correct answers were already given. Because you seem to have difficulties to "see" your solution from this I show this as explicte matrix-equation. I assume, your "Forces" are x, the determining values and your "veclocities" are the y, the resulting values. Then a matrix X contains the powers of the x, the matrix A contains the coefficients a and the matrix Y contains the values y, such that $\small X \cdot A = Y$. In an explicite display this looks like $$\small \begin{array} {rrrrrr|r} & . & . & . & . & . & a_0 \\ . & . & . & . & . & . & a_1 \\ . & . & . & . & . & . & a_2 \\ . & . & . & . & . & . & a_3 \\ . & . & . & . & . & . & a_4 \\ . & . & . & . & . & * & a_5 \\ \hline\\ x_0^0 & x_0^1 & x_0^2 & x_0^3 & x_0^4 & x_0^5 & y_0 \\ x_1^0 & x_1^1 & x_1^2 & x_1^3 & x_1^4 & x_1^5 & y_1 \\ x_2^0 & x_2^1 & x_2^2 & x_2^3 & x_2^4 & x_2^5 & y_2 \\ x_3^0 & x_3^1 & x_3^2 & x_3^3 & x_3^4 & x_3^5 & y_3 \\ x_4^0 & x_4^1 & x_4^2 & x_4^3 & x_4^4 & x_4^5 & y_4 \\ x_5^0 & x_5^1 & x_5^2 & x_5^3 & x_5^4 & x_5^5 & y_5 \end{array}$$ Then you compute $\small A = X^{-1} \cdot Y$ which should be a simple matlab-operation. Note, that this straightforward expression works in simple cases, for instance X must be invertible and thus must be square and no two x can be equal and something more. The usual procedure of gaussian elimination simply avoids the full inversion of X and can be understood as a rotation of X to triangular form from which a solution can then be computed in a wider class of problem-configurations.

-

One simple way to solve this would be write it as a linear system of equation. Here the polynomial coefficients $a_0, \ldots, a_5$ are the variables. You have six equations, each of the form $$p(v_i) = f_i$$ where $v_i$ is the $i^{th}$ "velocity" value and $f_i$ is the corresponding value for the "force". For example, the equation corresponding to "velocity"$=4$ would look like: $$a_0 + 4 a_1 + 4^2 a_2 + 4^3 a_3 + 4^4 a_4 + 4^5 a_5 = 14.8.$$ Similarly, you can write down five more equations as well, forming a linear system in six variables and six unknowns. Have they taught you to solve linear equations?

(Try doing the same thing assuming a degree of $4$ instead of $5$. Where will you get stuck?)

-
@Randy First, are you able to write down the system of equations? Next step: do you want help in writing that system of linear equations in matrix form? – Srivatsan Oct 4 '11 at 23:52
So if i set this up as an (augmented?) matrix, it would look like: | 0 0 0 0 0 0 0 | | 0 2 2^2 2^3 2^4 2^5 2.9 | | 0 4 4^2 4^3 4^4 4^5 14.8 | | 0 6 6^2 6^3 6^4 6^5 39.6 | etc? sorry for formatting.. – Randy Oct 4 '11 at 23:53
So I put that matrix into Matlab and row reduced it. I now have a solution for 5 x's, with the first column being all zero, we'll say they are C1-C5. Do I simply construct the final polynomial as: p(t) = 0 + C1*t + C2*t^2 + C3*t^3.....? – Randy Oct 5 '11 at 0:10
@Randy I cannot follow you. Is it possible for you to read off the solution for the linear system for me? – Srivatsan Oct 5 '11 at 0:11
Ok so I set up the augmented matrix how you said. This means a 6x7 matrix, with the left column being all zero (x1 is free?? zero?). The second column onward has all been reduced, with the answers x2=1.7, x3=-1.19, x4=0.66, x5=-0.07, and x6=0.002. The final row is also all zero. – Randy Oct 5 '11 at 0:15