Lagrange Interpolation

You already know this fact from school: two points determine a line, and three points (not all on one line) determine a parabola. What you may not know is how far that pattern goes: give me any $n+1$ points with distinct $x$-coordinates, and there is exactly one polynomial of degree at most $n$ that passes through every single one.

The question is not whether that polynomial exists — that part is guaranteed. The question is how to write it down without grinding through a system of $n+1$ linear equations for its coefficients.

In 1795, Joseph-Louis Lagrange published a beautifully direct answer: build the polynomial as a weighted sum of simple pieces, one per point, each engineered to vanish at every other point. No system to solve, no matrix to invert — just plug in the coordinates and read off the formula.

Below is a small set of points on a plane. Drag any of them and watch the curve instantly recompute — it always passes through every point, exactly, because that is what the Lagrange formula guarantees.

<p class="hint">{{hint_para}}</p>
<canvas id="plot" width="560" height="320"></canvas>
<div class="status" id="status">{{status_ready}}</div>
<div class="btns">
  <button id="addpt" type="button">{{btn_add}}</button>
  <button id="delpt" type="button">{{btn_remove}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
canvas { width: 100%; max-width: 560px; height: auto; background: #f7f9fb; border: 1px solid #cdd9e3;
         border-radius: 8px; touch-action: none; cursor: grab; display: block; }
canvas.dragging { cursor: grabbing; }
.status { font-size: .95rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .5; cursor: not-allowed; }

// Code not found

Add a point and the curve's degree grows with it: $n+1$ points force a polynomial of degree up to $n$. That is also the demo's cautionary tale — with more points the curve can start to wiggle wildly between them, a phenomenon called Runge's phenomenon. Passing through the points exactly is not the same as looking "smooth" in between.

Lagrange interpolation is one of the rare topics on this site with a fully solved, constructive answer — published by Lagrange in 1795 (building on earlier work by Waring in 1779). There is no open question about whether it works; the interesting part is why the formula is correct and how cheap it is to use.

• The basis trick. For points $(x_0, y_0), \dots, (x_n, y_n)$ with distinct $x_i$, define the Lagrange basis polynomial

  $$\ell_i(x) = \prod_{j \neq i} \frac{x - x_j}{x_i - x_j}.$$

  By construction $\ell_i(x_j) = 0$ for every $j \neq i$, and $\ell_i(x_i) = 1$. Each $\ell_i$ is a spotlight that lights up exactly one point.
• The sum. The interpolating polynomial is just

  $$P(x) = \sum_{i=0}^{n} y_i \, \ell_i(x).$$

  Evaluate this sum at $x = x_k$: every term with $i \neq k$ vanishes (its $\ell_i(x_k) = 0$), and the surviving term is $y_k \cdot 1 = y_k$. The curve hits every point by design, not by luck.
• Uniqueness. Could a different polynomial of degree $\le n$ also pass through all $n+1$ points? If $Q(x)$ did too, then $P(x) - Q(x)$ would be a polynomial of degree $\le n$ with $n+1$ distinct roots — but a nonzero polynomial of degree $\le n$ can have at most $n$ roots. So $P - Q$ must be the zero polynomial: $P$ is the only one.
• Cost. Evaluating $P$ at one new point directly from this formula costs $O(n^2)$ arithmetic operations; smarter schemes (Newton's divided differences, or barycentric interpolation) get incremental updates down to $O(n)$ per new point, and fast-multiplication methods push interpolation and evaluation at many points to $O(n \log^2 n)$.

So the complexity story here is the opposite of most articles on this site: not "this might be intractable," but "this is exact, unique, and fast — the hard part is just remembering it exists" instead of falling back on a slower system solve like Gaussian elimination.

"Reconstruct the whole thing from a handful of samples" is exactly the kind of problem that shows up everywhere once you know to look for it:

• Error-correcting codes: Reed-Solomon codes encode a message as the values of a polynomial at many points; as long as enough correct values survive transmission, Lagrange interpolation recovers the original polynomial — and the message — even after data loss or corruption.
• Secret sharing: Shamir's secret sharing hides a secret as the constant term of a random polynomial, splits it into shares that are points on that polynomial, and uses Lagrange interpolation to rebuild the secret only when enough shares come together.
• Numerical analysis: interpolation underlies numerical integration (Newton-Cotes formulas), root-finding, and building smooth approximations to functions known only at a few sampled points, such as experimental measurements.
• Computer graphics and animation: keyframe-based motion and curve fitting use polynomial (and related spline) interpolation to fill in the frames between the ones an artist actually draws.

Every one of these fields is really asking the same question Lagrange answered in 1795: given some points, what is the function passing through them?

Lagrange interpolation answers a question that feels like it should need heavy machinery — "what is the one polynomial through all these points?" — with a formula you can write from memory: build one basis polynomial per point, weight it by that point's $y$-value, and add them up.

Two centuries later that same trick reconstructs messages scattered across a noisy channel and rebuilds secrets split among strangers. Whenever you see "recover the whole thing from a few samples," there is a good chance a version of Lagrange's 1795 formula is quietly doing the work, just as it does when you reach for Reed-Solomon codes.