Lagrange Interpolation

In Writing Quadratics from Points you found the parabola through three points by solving three equations. Interpolation asks the same question for any number of points, and Lagrange's idea answers it with no system to solve, by building the polynomial from pieces that each vanish where they should, as in Writing a Polynomial from Its Zeros.

Given $n + 1$ points $(x_0, y_0), \ldots, (x_n, y_n)$ with different $x$-values (the nodes), define for each $k$ the Lagrange basis polynomial $$L_k(x) = \prod_{j \ne k}\frac{x - x_j}{x_k - x_j}.$$ Then the interpolating polynomial is $$p(x) = \sum_{k=0}^{n}y_kL_k(x).$$

Key idea

Exactly one polynomial of degree at most $n$ passes through $n + 1$ points with different $x$-values. Each $L_k$ is $1$ at its own node $x_k$ and $0$ at every other node, so $\sum y_kL_k$ takes the value $y_k$ at $x_k$.

Why it works

The numerator of $L_k$ has a factor $(x - x_j)$ for every node except $x_k$, so $L_k$ vanishes at those $n$ nodes; the denominator is the same product evaluated at $x_k$, so $L_k(x_k) = 1$. Each $L_k$ has degree $n$, so $p$ has degree at most $n$. Uniqueness: if $p$ and $q$ both interpolate, $p - q$ has degree at most $n$ but vanishes at $n + 1$ different nodes. A nonzero polynomial of degree at most $n$ has at most $n$ roots, so $p - q = 0$.

One Lagrange basis polynomial lit up (blue): it is 1 at its own node and 0 at the other four. The gray curves are the other basis polynomials.

Worked example: Building the polynomial

Find the polynomial through $(0, 1)$, $(1, 3)$, $(3, 2)$, and its value at $x = 2$.

$L_0(x) = \frac{(x - 1)(x - 3)}{(0 - 1)(0 - 3)} = \frac{(x - 1)(x - 3)}{3}$.
$L_1(x) = \frac{(x - 0)(x - 3)}{(1 - 0)(1 - 3)} = -\frac{x(x - 3)}{2}$.
$L_2(x) = \frac{(x - 0)(x - 1)}{(3 - 0)(3 - 1)} = \frac{x(x - 1)}{6}$.
At $x = 2$: $L_0 = -\frac{1}{3}$, $L_1 = 1$, $L_2 = \frac{1}{3}$, so $p(2) = 1\left(-\frac{1}{3}\right) + 3(1) + 2\left(\frac{1}{3}\right) = \frac{10}{3}$.
Expanded, $p(x) = -\frac{5}{6}x^{2} + \frac{17}{6}x + 1$; check $p(1) = 3$ and $p(3) = 2$.

Answer: $p(2) = \frac{10}{3}$

Worked example: "At most" matters

Find the polynomial of degree at most 3 through $(0, 1)$, $(1, 3)$, $(2, 5)$, $(3, 7)$.

The four points lie on the line $y = 2x + 1$.
That line is a polynomial of degree at most 3 through all four points, and the interpolant is unique, so it is the interpolant.
Four points do not force degree 3; they allow it. The Lagrange formula would give the same line after the $x^{3}$ and $x^{2}$ terms cancel.

Answer: $p(x) = 2x + 1$

The Lagrange form is perfect for proving things and for seeing the structure: the interpolant depends linearly on the data $y_k$. For computing with many points or adding points one at a time, Newton's divided differences are handier, and for large $n$ a rearrangement called the barycentric formula is both fast and numerically stable. All of them produce the same polynomial.

Common mistake

Expecting degree $n + 1$ for $n + 1$ points (two points determine a line, degree 1), or building a basis polynomial that is $0$ at the wrong nodes, for example including the factor $(x - x_k)$ in $L_k$. Check each $L_k$ by plugging in the nodes: it must give $1$ at $x_k$ and $0$ at all the others.

Sources and further reading

Tobin A. Driscoll and Richard J. Braun, Fundamentals of Numerical Computation (University of Delaware, free online edition): chapter "Global function approximation", section "Polynomial interpolation"

Autar Kaw, Holistic Numerical Methods (University of South Florida): Interpolation, "Lagrangian Interpolation"

Lagrange Interpolation

Practice

Builds on

Leads to

Sources and further reading