Lagrange polynomial interpolation - question about computation from 4 points I have these sample data points (0,1), (1,4), (2,11), (3,22), and I have to compute the corresponding lagrange polynomial and express it in the form $p(x)= a_nx^n + a_{n-1}x^{n-1}...+a_1x + a_0$
My approach: third order Lagrange polynomial: $ f_3(x)=L_1f(x_1)+L_2f(x_2)+L_3f(x_3)+L_4+f(x_4) $
So to compute $L_1$ I say:
$L_1 = \frac{(x-x2)(x-x3)(x-x4)}{(x1-x2)(x1-x3)(x1-x4)}$
(and for L2, L3, L3, I use same formula with the respective x-values)
This give me a rather "messy" third order polynomial, which I can't see how translate to $p(x)= a_nx^n + a_{n-1}x^{n-1}...+a_1x + a_0$
So, I'm in doubt wether this is this the right approach at all?
 A: Substitute the numerical values of $x_i$ and $f(x_i)$ and expand the polynomials in the numerators of $L$'s. Now you have four cubic polynomials, so simply add the coefficients at corresponding powers of $x$.
A: One approach to this problem could be to look at the differences:
$d_1(1)=f(2)-f(1)\\d_1(2)=f(3)-f(2)\\d_1(3)=f(4)-f(3)$
etc. If these differences are constant, then you know you have a linear polynomial, and you can use that constant difference and one of the values (e.g. $f(0)$) to find the equation of the line.
If the differences aren't constant, you can look at the second differences:
$d_2(1)=d_1(2)-d_1(1)\\d_2(2)=d_1(3)-d_1(2)\\d_2(3)=d_1(4)-d_1(3)$
etc.  If these differences are constant, it turns out that the polynomial is quadratic.  (For example, if the polynomial is $f(x)=x^2$, the first differences are 1, 3, 5, 7,..., while the second differences are constantly 2.)
This pattern continues: cubic polynomials have constant third differences, degree four polynomials have constant fourth differences, and so on.
Once you know the degree of your polynomial, you can use various methods to find the coefficients.  You could plug in your points and set up a system of equations; you could compare to the values of $x^d$ where $d$ is the degree you've settled on and see how your function compares; or if you've worked out in general how these successive differences come out, you might have some ideas about how to use the differences to reconstruct the coefficients.
