Interpolation

Methods for constructing functions that pass through given data points.

Lagrange Interpolation

Theory

The Lagrange interpolating polynomial passes through all n+1 data points using basis polynomials.

P(x) = \sum_{i=0}^{n} y_i L_i(x)

L_i(x) = \prod_{j=0, j \neq i}^{n} \frac{x - x_j}{x_i - x_j}

Each basis polynomial $L_i(x)$ equals 1 at $x_i$ and 0 at all other data points.

Data Points

P0: ,

P1: ,

P2: ,

P3: ,

P4: ,

Visualization

Show Basis Polynomial L_0(x)

Polynomial Formula

P(x) = 0.04 \cdot (x - 1)(x - 2)(x - 3)(x - 4) + -0.45 \cdot x(x - 2)(x - 3)(x - 4) + 1.85 \cdot x(x - 1)(x - 3)(x - 4) + -3.35 \cdot x(x - 1)(x - 2)(x - 4) + 2.27 \cdot x(x - 1)(x - 2)(x - 3)

Practice Problems

Find the Lagrange polynomial through points (0, 1), (2, 5), (3, 4). Evaluate P(1).
Construct L₁(x) for points (-1, 2), (0, 1), (1, 4), (2, 3).
Show that Lagrange interpolation is exact for polynomials of degree ≤ n with n+1 points.

Implementation

INPUT: points (x0,y0), ..., (xn,yn), target x
OUTPUT: P(x)

P = 0
for i = 0 to n:
    L_i = 1
    for j = 0 to n, j ≠ i:
        L_i = L_i * (x - x[j]) / (x[i] - x[j])
    P = P + y[i] * L_i

RETURN P