Polynomial Interpolation

Polynomial interpolation constructs a polynomial passing through given data points, providing a fundamental tool for approximating functions and numerical differentiation and integration.

DefinitionPolynomial Interpolation Problem

Given $n+1$ distinct points $(x_0, y_0), (x_1, y_1), \ldots, (x_n, y_n)$ , find a polynomial $p_n(x)$ of degree at most $n$ such that: $p_n(x_i) = y_i, \quad i = 0, 1, \ldots, n$

Such a polynomial exists and is unique. It is called the interpolating polynomial for the given data.

The existence and uniqueness follow from linear algebra: the system of $n+1$ equations in $n+1$ unknowns (polynomial coefficients) has a unique solution when the $x_i$ are distinct. The Vandermonde matrix has non-zero determinant $\prod_{i<j}(x_j - x_i) \neq 0$ .

DefinitionLagrange Form

The Lagrange form of the interpolating polynomial is: $p_n(x) = \sum_{i=0}^n y_i L_i(x)$ where the Lagrange basis polynomials are: $L_i(x) = \prod_{j=0, j \neq i}^n \frac{x - x_j}{x_i - x_j}$

Each $L_i(x)$ satisfies $L_i(x_j) = \delta_{ij}$ (Kronecker delta), so $p_n(x_i) = y_i$ automatically.

ExampleQuadratic Interpolation

Interpolate $(0,1)$ , $(1,0)$ , $(2,3)$ . The Lagrange basis polynomials are: $L_0(x) = \frac{(x-1)(x-2)}{(0-1)(0-2)} = \frac{1}{2}(x-1)(x-2)$ $L_1(x) = \frac{(x-0)(x-2)}{(1-0)(1-2)} = -(x)(x-2) = -x^2 + 2x$ $L_2(x) = \frac{(x-0)(x-1)}{(2-0)(2-1)} = \frac{1}{2}x(x-1)$

The interpolating polynomial is: $p_2(x) = 1 \cdot L_0(x) + 0 \cdot L_1(x) + 3 \cdot L_2(x) = \frac{1}{2}(x-1)(x-2) + \frac{3}{2}x(x-1)$ $= \frac{1}{2}[x^2 - 3x + 2 + 3x^2 - 3x] = 2x^2 - 3x + 1$

Verification: $p_2(0) = 1$ , $p_2(1) = 0$ , $p_2(2) = 8 - 6 + 1 = 3$ . ✓

Remark

Computational Considerations: The Lagrange form is conceptually simple but computationally expensive ( $O(n^2)$ operations per evaluation). The Newton divided difference form is more efficient for sequential data addition and uses $O(n)$ operations per evaluation after $O(n^2)$ preprocessing.

Runge Phenomenon: High-degree polynomial interpolation with equally-spaced points can exhibit large oscillations near interval endpoints. Using Chebyshev nodes $x_i = \cos\left(\frac{2i+1}{2(n+1)}\pi\right)$ minimizes this effect.

Polynomial interpolation forms the basis for numerical quadrature (integration), differentiation formulas, and piecewise polynomial methods like splines. The interpolation error for smooth functions is $|f(x) - p_n(x)| \leq \frac{M_{n+1}}{(n+1)!} \prod_{i=0}^n |x - x_i|$ where $M_{n+1} = \max |f^{(n+1)}(\xi)|$ , showing that error depends on data spacing and function smoothness.