Lagrange Interpolation Polynomials
If we wish to describe all of the ups and downs in a data set, and hit every point, we use what is called an interpolation polynomial. This method is due to Lagrange.
Suppose the data set consists of N data points:
(x_{1}, y_{1}), (x_{2}, y_{2}), (x_{3}, y_{3}), ..., (x_{N}, y_{N})
The interpolation polynomial will have degree N – 1 . It is given by:
P(x) = j_{1}(x) y_{1} + j_{2}(x) y_{2} + j_{3}(x) y_{3} + ... + j_{N}(x) y_{N}
where the functions j_{i}(x) (i = 1, 2, 3, ..., n) are given by:
Don't fret! This is easier than it looks. The key thing to notice is that the numerator of j_{i}(x) contains the entire sequence of factors (x – x_{1}), (x – x_{2}), (x – x_{3}), ... (x – x_{N}), with the exception of the single factor (x – x_{i}). Likewise, the denominator contains the entire sequence of factors (x_{i} – x_{1}), (x_{i} – x_{2}), (x_{i} – x_{3}), ... (x_{i} – x_{N}), with the exception of the single factor (x_{i} – x_{i}).
Now notice: j_{i}(x_{i}) = 1 (numerator = denominator), but j_{i}(x_{j}) = 0 (numerator = 0, since it contains the factor (x_{j} – x_{j}) ) for any j not equal to i . This means that P(x_{i}) = y_{i} , which is exactly what we want!
If this seems like smoke and mirrors, consider a simple example. Here's the data for g again:
x

g(x)

0

–250

10

0

20

50

30

–100

In this case there are N = 4 data points, so we will create a polynomial of degree N – 1 = 3 . We have x_{1} = 0 , x_{2} = 10 , x_{3} = 20 , x_{4} = 30 , and y_{1} = –250 , y_{2} = 0 , y_{3} = 50 , y_{4} = 100 . So:
Multiplying each of these by the appropriate y_{i} (i = 1, 2, 3, 4) and adding together the terms of like power then gives:
The cubic terms cancel, and we arrive at a simple quadratic description of the data.
A quick plot of the data together with the polynomial shows that it indeed passes through each of the data points:
For an interactive demonstration of Lagrange interpolation polynomials, showing how variations in the data points affect the resulting curve, go here.