Lagrangian Interpolation

Given a set of points \( (x_1,y_1), (x_2,y_2) \dots (x_n,y_n)\) we want to find a polynomial of degree \(n-1\) which passes through all of the given points.

We start by observing that:

\[P_j(x) = y_j\frac{ \prod_{i=1, i\ne j}^n (x-x_i)}{\prod_{i=1, i\ne j}^n (x_j-x_i)}\]
is a polynomial of degree \(n-1\) which is zero for all of the \(x_i\)'s except for \(i=j\) where it takes the value \(y_j\). This is by construction since the polynomial is set up to have roots \(x_i,\ i=1..j-1,j+1, ...n\), and to take the value \(y_j\) at \(x_j\)

Now consider the polynomial:
\[P(x)=\sum_{j=1}^n P_j(x)\]
This is of degree \(n-1\) and only the \(k\)-th term is non-zero at \(x_k\) where it takes the value \(y_k\) and so \(P(x_k)=y_k\). Hence \(P(x)\) is a polynomial of degree \(n-1\) which passes through all the points in our given set.

Example:
Take the points: \( (1,2), (2,1), (4,3), (7,5) \), then our polynomials are:
\[ \begin{aligned} P_1(x)&=-\frac{(x-2)(x-4)(x-7)}{9}\\ P_2(x)&=\phantom{-}\frac{(x-1)(x-4)(x-7)}{10}\\P_3(x)&=-\frac{(x-1)(x-2)(x-7)}{6}\\P_4(x)&=\phantom{-}\frac{(x-1)(x-2)(x-4)}{18}\end{aligned}\]
Then combining these and simplifying:
\[P(x)=P_1(x)+P_2(x)+P_3(x)+P_4(x) =-\frac{11x^3-137x^2+424x-478}{90}\]