# 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()... –  Ｊ. Ｍ. 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. :) –  Ｊ. Ｍ. 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... –  Ｊ. Ｍ. 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?)