Lagrange Interpolating Polynomial

Summary

Lagrange form writes the unique interpolant as a weighted sum of cardinal basis polynomials $L_{i}$ that satisfy $L_{i} (x_{k}) = δ_{i k}$ .

Prerequisites

Existence and Uniqueness of Interpolating Polynomial
Product notation for polynomials

Problem Type

Given distinct nodes $x_{0}, \dots, x_{n}$ and values $y_{i}$ , construct $P$ with $P (x_{i}) = y_{i}$ .

Method Definition

P (x) = \sum_{i = 0}^{n} y_{i} L_{i} (x), L_{i} (x) = \prod_{\begin{matrix} j = 0 \\ j \neq i \end{matrix}}^{n} \frac{x - x_{j}}{x_{i} - x_{j}} .

Each $L_{i}$ has degree $n$ , $L_{i} (x_{i}) = 1$ , and $L_{i} (x_{j}) = 0$ for $j \neq i$ . The product is over $j \neq i$ only.^[1]

Assumptions / Requirements

Distinct $x_{i}$
Exact arithmetic ignores cancellation; numerically, barycentric Lagrange is preferred for evaluation

Algorithm

For each $i$ , form $L_{i} (x)$ as the product over $j \neq i$ .
Sum $y_{i} L_{i} (x)$ .
Optionally expand into monomial form for inspection.

Error / Accuracy

If $y_{i} = f (x_{i})$ with $f \in C^{n + 1}$ , then for some $ξ$ between the nodes and $x$ ,

f (x) - P (x) = \frac{f^{(n + 1)} (ξ)}{(n + 1)!} \prod_{i = 0}^{n} (x - x_{i}) .

If $| f^{(n + 1)} | \leq M$ on the interval of interest,

| f (x) - P (x) | \leq \frac{M}{(n + 1)!} | \prod_{i = 0}^{n} (x - x_{i}) | .

Worked Example

Nodes $(0, 2)$ , $(1, 3)$ , $(2, 5)$ .

\begin{aligned} L_{0} (x) & = \frac{(x - 1) (x - 2)}{(0 - 1) (0 - 2)} = \frac{(x - 1) (x - 2)}{2} = \frac{1}{2} (x^{2} - 3 x + 2), \\ L_{1} (x) & = \frac{(x - 0) (x - 2)}{(1 - 0) (1 - 2)} = \frac{x (x - 2)}{- 1} = - x^{2} + 2 x, \\ L_{2} (x) & = \frac{(x - 0) (x - 1)}{(2 - 0) (2 - 1)} = \frac{x (x - 1)}{2} = \frac{1}{2} (x^{2} - x) . \end{aligned}

\begin{aligned} P (x) & = 2 L_{0} (x) + 3 L_{1} (x) + 5 L_{2} (x) \\ = 2 \cdot \frac{1}{2} (x^{2} - 3 x + 2) + 3 (- x^{2} + 2 x) + 5 \cdot \frac{1}{2} (x^{2} - x) \\ = (x^{2} - 3 x + 2) + (- 3 x^{2} + 6 x) + (\frac{5}{2} x^{2} - \frac{5}{2} x) \\ = (1 - 3 + \frac{5}{2}) x^{2} + (- 3 + 6 - \frac{5}{2}) x + 2 \\ = \frac{1}{2} x^{2} + \frac{1}{2} x + 2. \end{aligned}

Checks: $P (0) = 2$ , $P (1) = 1 / 2 + 1 / 2 + 2 = 3$ , $P (2) = 2 + 1 + 2 = 5$ .

Common Failure Modes

Writing $\prod_{j}$ without excluding $j = i$
Dropping the weights $y_{i}$
High $n$ with equal spacing (Runge oscillations)

Connections

Newton Polynomial (same $P$ , different basis)
Polynomial Interpolation by Definition
Polynomial Interpolation

References

Burden & Faires, Numerical Analysis, Lagrange interpolation; NIST DLMF Ch. 3, https://dlmf.nist.gov/3 ↩︎