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).$$

Idea clave

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$.

Por qué funciona

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.

Ejemplo resuelto: 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$.

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

Ejemplo resuelto: "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.

Respuesta: $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.

Error común

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.

Práctica

Se apoya en

Lleva a

Fuentes y lecturas