Lagrange interpolation

Remarks

Each $\ell_j$ has degree $n$, with $\ell_j(x_j) = 1$ and $\ell_j(x_k) = 0$ for $k \ne j$. So $L$ has degree at most $n$ and $L(x_i) = y_i$ for all $i$: it is the unique interpolation polynomial of the data. Example: for the data $(0, 1)$, $(1, 3)$, $(2, 7)$, the basis polynomials are $\ell_0 = \frac{(x-1)(x-2)}{2}$, $\ell_1 = -x(x-2)$ and $\ell_2 = \frac{x(x-1)}{2}$. Then $L = \ell_0 + 3 \ell_1 + 7 \ell_2 = x^2 + x + 1$, and indeed $L(0) = 1$, $L(1) = 3$, $L(2) = 7$. Non-example: if two nodes coincide, $x_j = x_k$ with $j \ne k$, the denominator $x_j - x_k$ is $0$ and the formula has no meaning.