February 28, 2026 at 18:58 Tags Math
Polynomial interpolation is a method of finding a polynomial function that fits a given set of data perfectly. More concretely, suppose we have a set of n+1 distinct points :
\[(x_0,y_0), (x_1, y_1), (x_2, y_2)\cdots(x_n, y_n)\]
And we want to find the polynomial coefficients {a_0\cdots a_n} such that:
\[p(x)=a_0 + a_1 x + a_2 x^2 + \cdots + a_n x^n\]
Fits all our points; that is p(x_0)=y_0 , p(x_1)=y_1 etc.
This post discusses a common approach to solving this problem, and also shows why such a polynomial exists and is unique.
Showing existence using linear algebra When we assign all points (x_i, y_i) into the generic polynomial p(x) , we get: \[\begin{aligned} p(x_0)&=a_0 + a_1 x_0 + a_2 x_0^2 + \cdots a_n x_0^n = y_0\\ p(x_1)&=a_0 + a_1 x_1 + a_2 x_1^2 + \cdots a_n x_1^n = y_1\\ p(x_2)&=a_0 + a_1 x_2 + a_2 x_2^2 + \cdots a_n x_2^n = y_2\\ \cdots \\ p(x_n)&=a_0 + a_1 x_n + a_2 x_n^2 + \cdots a_n x_n^n = y_n\\ \end{aligned}\] We want to solve for the coefficients a_i . This is a linear system of equations that can be represented by the following matrix equation: \[{\renewcommand{\arraystretch}{1.5}\begin{bmatrix} 1 & x_0 & x_0^2 & \dots & x_0^n\\ 1 & x_1 & x_1^2 & \dots & x_1^n\\ 1 & x_2 & x_2^2 & \dots & x_2^n\\ \vdots & \vdots & \vdots & \ddots &\vdots \\ 1 & x_n & x_n^2 & \dots & x_n^n \end{bmatrix} \begin{bmatrix} a_0\\ a_1\\ a_2\\ \vdots\\ a_n\\ \end{bmatrix}= \begin{bmatrix} y_0\\ y_1\\ y_2\\ \vdots\\ y_n\\ \end{bmatrix} }\] The matrix on the left is called the Vandermonde matrix. This matrix is known to be invertible (see Appendix for a proof); therefore, this system of equations has a single solution that can be calculated by inverting the matrix. In practice, however, the Vandermonde matrix is often numerically ill-conditioned, so inverting it isn’t the best way to calculate exact polynomial coefficients. Several better methods exist.
Lagrange Polynomial Lagrange interpolation polynomials emerge from a simple, yet powerful idea. Let’s define the Lagrange basis functions l_i(x) ( i \in [0, n] ) as follows, given our points (x_i, y_i) : \[l_i(x) = \begin{cases} 1 & x = x_i \\ 0 & x = x_j \quad \forall j
eq i \end{cases}\] In words, l_i(x) is constrained to 1 at and to 0 at all other x_j . We don’t care about its value at any other point. The linear combination: \[p(x)=\sum_{i=0}^{n}y_i l_i(x)\] is then a valid interpolating polynomial for our set of n+1 points, because it’s equal to at each (take a moment to convince yourself this is true). How do we find l_i(x) ? The key insight comes from studying the following function: \[l'_i(x)=(x-x_0)\cdot (x-x_1)\cdots (x-x_{i-1}) \cdot (x-x_{i+1})\cdots (x-x_n)= \prod_{\substack{0\leq j \leq n \\ j
... continue reading