Okay. Okay okay okay. I'm TAing a course right now where we actually teach polynomial interpolation. I'M QUALIFIED TO POST THINGS ON THE INTERNET.
If you have n points, one option is to say f(x) = a_0 + a_1x + a_2x^2 + ... + a_{n-1}x^{n-1}. That gives you n different variables in the coefficients, and n different equations through the points (x_1,y_1), ... , (x_n,y_n). You can then solve that system of equations.
Alternatively, you can use the thing Witherweaver is talking about, which is
Lagrange interpolation. The idea is that for every point (x_i, y_i), you define a polynomial f_i(x) such that
- f_i(x_j) = 0 for all j not equal to i
- f_i(x_i) = 1
If you know f_i(x) for each i, then the polynomial
f(x) = y_1 f_1(x) + y_2 f_2(x) + ... + y_n f_n(x)
passes through all the n points.
Then, you can derive each f_i(x) through inspection. The way we define it, we want a polynomial with n-1 roots, and we know the value at x_i is 1, so you can write it as
f_i(x) = (x-x_1)(x-x_2)...(x-x_{i-1})(x-x_{i+1})....(x-x_n) * (1 / (x_i - x_1)(x_i-x_2) ... (x_i-x_n))
For any N points, there is exactly one polynomial of degree up to n-1 that goes through those points. At least one exists by the method above. If f(x) and g(x) go through the same n points and are both degree <= n-1, then f(x) - g(x) has n roots and is of degree <= n-1, which is only possible if f(x) - g(x) = 0.
PPE: I've been ninjaed by all the other math people here.
