Introduction to Lagrange Interpolation

Introduction

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.

Try It Live

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">Drag any point and the curve redraws itself instantly. It always passes through every point exactly — that is what the Lagrange formula guarantees. Add or remove points to change the polynomial's degree.</p>
<canvas id="plot" width="560" height="320"></canvas>
<div class="status" id="status">Drag a point to begin.</div>
<div class="btns">
  <button id="addpt" type="button">Add point</button>
  <button id="delpt" type="button">Remove point</button>
  <button id="reset" type="button" class="ghost">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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Lagrange interpolation demo: recompute and redraw the unique polynomial through every draggable point on each move.
const canvas = document.getElementById('plot');
const ctx = canvas.getContext('2d');
const W = canvas.width, H = canvas.height;
const PAD = 30;

// Map data coordinates (xMin..xMax, yMin..yMax) to pixel coordinates and back.
const xMin = -5, xMax = 5, yMin = -5, yMax = 5;
const toPx = (x, y) => [
  PAD + (x - xMin) / (xMax - xMin) * (W - 2 * PAD),
  H - PAD - (y - yMin) / (yMax - yMin) * (H - 2 * PAD)
];
const toData = (px, py) => [
  xMin + (px - PAD) / (W - 2 * PAD) * (xMax - xMin),
  yMin + (H - PAD - py) / (H - 2 * PAD) * (yMax - yMin)
];

// The draggable points; index of the point currently being dragged (-1 = none).
let points = [[-3, -2], [-1, 2], [1, -1], [3, 3]];
let dragIndex = -1;

// P(x) = sum_i y_i * prod_{j != i} (x - x_j) / (x_i - x_j) — the Lagrange formula itself.
function lagrangeAt(pts, x) {
  let total = 0;
  for (let i = 0; i < pts.length; i++) {
    const [xi, yi] = pts[i];
    let term = yi;
    for (let j = 0; j < pts.length; j++) {
      if (j === i) continue;
      const xj = pts[j][0];
      term *= (x - xj) / (xi - xj);
    }
    total += term;
  }
  return total;
}

function sortedPoints() {
  return [...points].sort((a, b) => a[0] - b[0]);
}

function draw() {
  ctx.clearRect(0, 0, W, H);

  // Draw the x and y axes through the origin.
  ctx.strokeStyle = '#cdd9e3';
  ctx.lineWidth = 1;
  const [ox, oy] = toPx(0, 0);
  ctx.beginPath(); ctx.moveTo(PAD, oy); ctx.lineTo(W - PAD, oy); ctx.stroke();
  ctx.beginPath(); ctx.moveTo(ox, PAD); ctx.lineTo(ox, H - PAD); ctx.stroke();

  const pts = sortedPoints();

  // Sample the interpolating polynomial densely and draw it as a smooth curve.
  ctx.strokeStyle = '#e63946';
  ctx.lineWidth = 2.5;
  ctx.beginPath();
  const steps = 240;
  for (let s = 0; s <= steps; s++) {
    const x = xMin + (xMax - xMin) * s / steps;
    let y = lagrangeAt(pts, x);
    y = Math.max(yMin - 20, Math.min(yMax + 20, y));
    const [px, py] = toPx(x, y);
    if (s === 0) ctx.moveTo(px, py); else ctx.lineTo(px, py);
  }
  ctx.stroke();

  // Draw each control point on top of the curve.
  for (const [x, y] of points) {
    const [px, py] = toPx(x, y);
    ctx.beginPath();
    ctx.arc(px, py, 7, 0, Math.PI * 2);
    ctx.fillStyle = '#1d3557';
    ctx.fill();
    ctx.strokeStyle = '#fff';
    ctx.lineWidth = 2;
    ctx.stroke();
  }
}

function setStatus(t) { document.getElementById('status').textContent = t; }

function updateStatus() {
  const n = points.length;
  setStatus(i18nFmt('%n% points -> a polynomial of degree up to %deg%.', { n: n, deg: n - 1 }));
}

function nearestPoint(px, py) {
  let best = -1, bestDist = 16 * 16;
  points.forEach(([x, y], i) => {
    const [qx, qy] = toPx(x, y);
    const d = (qx - px) ** 2 + (qy - py) ** 2;
    if (d < bestDist) { bestDist = d; best = i; }
  });
  return best;
}

function eventPos(e) {
  const rect = canvas.getBoundingClientRect();
  const scaleX = W / rect.width, scaleY = H / rect.height;
  const cx = (e.touches ? e.touches[0].clientX : e.clientX) - rect.left;
  const cy = (e.touches ? e.touches[0].clientY : e.clientY) - rect.top;
  return [cx * scaleX, cy * scaleY];
}

canvas.addEventListener('pointerdown', (e) => {
  const [px, py] = eventPos(e);
  dragIndex = nearestPoint(px, py);
  if (dragIndex >= 0) canvas.classList.add('dragging');
});
window.addEventListener('pointermove', (e) => {
  if (dragIndex < 0) return;
  const [px, py] = eventPos(e);
  let [x, y] = toData(px, py);
  x = Math.max(xMin, Math.min(xMax, x));
  y = Math.max(yMin, Math.min(yMax, y));
  // Keep x-coordinates distinct so the formula's denominators never hit zero.
  const others = points.filter((_, i) => i !== dragIndex).map(p => p[0]);
  const tooClose = others.some(ox => Math.abs(ox - x) < 0.15);
  if (!tooClose) points[dragIndex] = [x, y];
  draw();
});
window.addEventListener('pointerup', () => {
  if (dragIndex >= 0) { dragIndex = -1; canvas.classList.remove('dragging'); }
});

function addPoint() {
  if (points.length >= 8) return;
  // Look for a free x slot half a unit apart from existing points.
  const xs = points.map(p => p[0]);
  let x = 0;
  for (let cand = xMin + 0.5; cand <= xMax - 0.5; cand += 0.5) {
    if (!xs.some(ox => Math.abs(ox - cand) < 0.4)) { x = cand; break; }
  }
  const y = (Math.random() * 6 - 3);
  points.push([Math.round(x * 10) / 10, Math.round(y * 10) / 10]);
  updateStatus();
  draw();
}
function removePoint() {
  if (points.length <= 2) return;
  points.pop();
  updateStatus();
  draw();
}
function resetAll() {
  points = [[-3, -2], [-1, 2], [1, -1], [3, 3]];
  updateStatus();
  draw();
}

document.getElementById('addpt').addEventListener('click', addPoint);
document.getElementById('delpt').addEventListener('click', removePoint);
document.getElementById('reset').addEventListener('click', resetAll);

updateStatus();
draw();

<p class="hint">Drag any point and the curve redraws itself instantly. It always passes through every point exactly — that is what the Lagrange formula guarantees. Add or remove points to change the polynomial's degree.</p>
<canvas id="plot" width="560" height="320"></canvas>
<div class="status" id="status">Drag a point to begin.</div>
<div class="btns">
  <button id="addpt" type="button">Add point</button>
  <button id="delpt" type="button">Remove point</button>
  <button id="reset" type="button" class="ghost">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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Lagrange interpolation demo: recompute and redraw the unique polynomial through every draggable point on each move.
const canvas = document.getElementById('plot');
const ctx = canvas.getContext('2d');
const W = canvas.width, H = canvas.height;
const PAD = 30;

// Map data coordinates (xMin..xMax, yMin..yMax) to pixel coordinates and back.
const xMin = -5, xMax = 5, yMin = -5, yMax = 5;
const toPx = (x, y) => [
  PAD + (x - xMin) / (xMax - xMin) * (W - 2 * PAD),
  H - PAD - (y - yMin) / (yMax - yMin) * (H - 2 * PAD)
];
const toData = (px, py) => [
  xMin + (px - PAD) / (W - 2 * PAD) * (xMax - xMin),
  yMin + (H - PAD - py) / (H - 2 * PAD) * (yMax - yMin)
];

// The draggable points; index of the point currently being dragged (-1 = none).
let points = [[-3, -2], [-1, 2], [1, -1], [3, 3]];
let dragIndex = -1;

// P(x) = sum_i y_i * prod_{j != i} (x - x_j) / (x_i - x_j) — the Lagrange formula itself.
function lagrangeAt(pts, x) {
  let total = 0;
  for (let i = 0; i < pts.length; i++) {
    const [xi, yi] = pts[i];
    let term = yi;
    for (let j = 0; j < pts.length; j++) {
      if (j === i) continue;
      const xj = pts[j][0];
      term *= (x - xj) / (xi - xj);
    }
    total += term;
  }
  return total;
}

function sortedPoints() {
  return [...points].sort((a, b) => a[0] - b[0]);
}

function draw() {
  ctx.clearRect(0, 0, W, H);

  // Draw the x and y axes through the origin.
  ctx.strokeStyle = '#cdd9e3';
  ctx.lineWidth = 1;
  const [ox, oy] = toPx(0, 0);
  ctx.beginPath(); ctx.moveTo(PAD, oy); ctx.lineTo(W - PAD, oy); ctx.stroke();
  ctx.beginPath(); ctx.moveTo(ox, PAD); ctx.lineTo(ox, H - PAD); ctx.stroke();

  const pts = sortedPoints();

  // Sample the interpolating polynomial densely and draw it as a smooth curve.
  ctx.strokeStyle = '#e63946';
  ctx.lineWidth = 2.5;
  ctx.beginPath();
  const steps = 240;
  for (let s = 0; s <= steps; s++) {
    const x = xMin + (xMax - xMin) * s / steps;
    let y = lagrangeAt(pts, x);
    y = Math.max(yMin - 20, Math.min(yMax + 20, y));
    const [px, py] = toPx(x, y);
    if (s === 0) ctx.moveTo(px, py); else ctx.lineTo(px, py);
  }
  ctx.stroke();

  // Draw each control point on top of the curve.
  for (const [x, y] of points) {
    const [px, py] = toPx(x, y);
    ctx.beginPath();
    ctx.arc(px, py, 7, 0, Math.PI * 2);
    ctx.fillStyle = '#1d3557';
    ctx.fill();
    ctx.strokeStyle = '#fff';
    ctx.lineWidth = 2;
    ctx.stroke();
  }
}

function setStatus(t) { document.getElementById('status').textContent = t; }

function updateStatus() {
  const n = points.length;
  setStatus(i18nFmt('%n% points -> a polynomial of degree up to %deg%.', { n: n, deg: n - 1 }));
}

function nearestPoint(px, py) {
  let best = -1, bestDist = 16 * 16;
  points.forEach(([x, y], i) => {
    const [qx, qy] = toPx(x, y);
    const d = (qx - px) ** 2 + (qy - py) ** 2;
    if (d < bestDist) { bestDist = d; best = i; }
  });
  return best;
}

function eventPos(e) {
  const rect = canvas.getBoundingClientRect();
  const scaleX = W / rect.width, scaleY = H / rect.height;
  const cx = (e.touches ? e.touches[0].clientX : e.clientX) - rect.left;
  const cy = (e.touches ? e.touches[0].clientY : e.clientY) - rect.top;
  return [cx * scaleX, cy * scaleY];
}

canvas.addEventListener('pointerdown', (e) => {
  const [px, py] = eventPos(e);
  dragIndex = nearestPoint(px, py);
  if (dragIndex >= 0) canvas.classList.add('dragging');
});
window.addEventListener('pointermove', (e) => {
  if (dragIndex < 0) return;
  const [px, py] = eventPos(e);
  let [x, y] = toData(px, py);
  x = Math.max(xMin, Math.min(xMax, x));
  y = Math.max(yMin, Math.min(yMax, y));
  // Keep x-coordinates distinct so the formula's denominators never hit zero.
  const others = points.filter((_, i) => i !== dragIndex).map(p => p[0]);
  const tooClose = others.some(ox => Math.abs(ox - x) < 0.15);
  if (!tooClose) points[dragIndex] = [x, y];
  draw();
});
window.addEventListener('pointerup', () => {
  if (dragIndex >= 0) { dragIndex = -1; canvas.classList.remove('dragging'); }
});

function addPoint() {
  if (points.length >= 8) return;
  // Look for a free x slot half a unit apart from existing points.
  const xs = points.map(p => p[0]);
  let x = 0;
  for (let cand = xMin + 0.5; cand <= xMax - 0.5; cand += 0.5) {
    if (!xs.some(ox => Math.abs(ox - cand) < 0.4)) { x = cand; break; }
  }
  const y = (Math.random() * 6 - 3);
  points.push([Math.round(x * 10) / 10, Math.round(y * 10) / 10]);
  updateStatus();
  draw();
}
function removePoint() {
  if (points.length <= 2) return;
  points.pop();
  updateStatus();
  draw();
}
function resetAll() {
  points = [[-3, -2], [-1, 2], [1, -1], [3, 3]];
  updateStatus();
  draw();
}

document.getElementById('addpt').addEventListener('click', addPoint);
document.getElementById('delpt').addEventListener('click', removePoint);
document.getElementById('reset').addEventListener('click', resetAll);

updateStatus();
draw();

Result

Console

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.

The Real Complexity

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.

Where It Matters

"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?

Conclusion

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.

Comments

Loading comments...

https://www.kipuhub.com/en/article/lagrange-interpolation/Content licensed under CC BY-NC 4.0.

Cookies & privacy

Lagrange Interpolation

Building a polynomial straight from its points