Skip to content
Tutorials Center
My learning

Topics

Lesson 19 of 37 ยท Interpolation and Curve Fitting

Polynomial Interpolation: Lagrange and Newton

Build the unique polynomial through your data points with the Lagrange form and Newton divided differences, then compare both with NumPy and SciPy.

Often you know a function only at a few points: sensor readings, a table of values, the output of an expensive simulation. Interpolation builds a function that passes exactly through those points so you can estimate values in between. The simplest family is the polynomials, and they have a lovely guarantee: for n + 1 points with distinct x values there is exactly one polynomial of degree at most n that passes through all of them.

This lesson shows two ways to write that polynomial, the Lagrange form and the Newton form, implements both from scratch, and checks them against SciPy. They produce the same curve; they differ in how convenient they are when you add points or evaluate many times.

The problem

Given points (x0, y0), (x1, y1), ..., (xn, yn) with all xi different, find p(x) of degree at most n with p(xi) = yi for every i.

You could write p(x) = a0 + a1 x + ... + an x^n and solve a linear system for the coefficients (a Vandermonde system). That works for tiny cases but the matrix becomes badly conditioned very fast. The two forms below avoid it.

The Lagrange form

For each node xi, build a basis polynomial that is 1 at xi and 0 at every other node:

Li(x) = product over j != i of (x - xj) / (xi - xj)

Then the interpolating polynomial is simply p(x) = sum of yi * Li(x). At x = xi every term but one vanishes and the surviving term equals yi, so the curve passes through the data by construction.

Python Lagrange interpolation from scratch

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The cost is O(n^2) for each evaluation point, and if you add one more data point you have to start over. That is the main reason to prefer the Newton form for incremental work.

The Newton form and divided differences

Newton writes the same polynomial as a nested sum:

p(x) = c0 + c1 (x - x0) + c2 (x - x0)(x - x1) + ... + cn (x - x0)...(x - x(n-1))

The coefficients ck are divided differences. Define f[xi] = yi and

f[xi, ..., x(i+k)] = (f[x(i+1), ..., x(i+k)] - f[xi, ..., x(i+k-1)]) / (x(i+k) - xi)

Then ck = f[x0, ..., xk]. You compute them in a triangular table, one column at a time.

flowchart LR
  A["f[x0]<br/>f[x1]<br/>f[x2]<br/>f[x3]"] --> B["f[x0,x1]<br/>f[x1,x2]<br/>f[x2,x3]"]
  B --> C["f[x0,x1,x2]<br/>f[x1,x2,x3]"]
  C --> D["f[x0,x1,x2,x3]"]

The top entry of each column is a Newton coefficient.

Python Newton divided differences

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The nested evaluation costs only O(n) per point, and adding a data point only appends one more coefficient, so the existing ones are reused. For the same data both forms give p(3) = 1.5, because the polynomial is unique.

Checking against SciPy

SciPy offers scipy.interpolate.lagrange (fine for a handful of points) and the numerically more robust BarycentricInterpolator, which uses a rearranged Lagrange formula that is stable and costs O(n) per evaluation after setup.

Python Compare with SciPy

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The error formula

If the data come from a smooth function f, the error of the interpolating polynomial is

f(x) - p(x) = f^(n+1)(t) / (n+1)! * (x - x0)(x - x1)...(x - xn)

for some t in the interval. Two things follow. First, the error is tiny when f has small high derivatives. Second, it depends on the product of distances to the nodes, so it is small inside the node range and large outside it. Evaluating outside the data (extrapolation) is dangerous. The next lesson, the Runge phenomenon and Chebyshev nodes, shows how this product can blow up and how to fix it.

Do not fit a polynomial of degree 20 through 21 evenly spaced points and trust it. The result passes through every point and can still swing wildly between them.

Common mistakes

  • Using duplicate x values. The formulas divide by xi - xj, so they fail (or give nonsense) when two nodes coincide.
  • Forgetting that unsorted nodes are fine for the polynomial but the plain lagrange helper in SciPy can be numerically poor for more than about 20 points.
  • Extrapolating far from the data.
  • Choosing a high degree "to be accurate". More points on one polynomial rarely help; piecewise methods, covered in cubic splines, usually do better.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. How many polynomials of degree at most n pass through n + 1 points with distinct x values?

    The interpolating polynomial is unique, so Lagrange and Newton forms are two ways of writing the same curve.
  2. 2. Which advantage does the Newton form have over the Lagrange form?

    Divided differences are reused when a node is added, and nested evaluation costs only O(n) per point.
  3. 3. What does the product (x - x0)...(x - xn) in the error formula tell you?

    The product grows quickly outside the nodes, so extrapolation is risky, and node placement affects accuracy.
  4. 4. Why is building the Vandermonde system usually avoided for many nodes?

    Vandermonde matrices have enormous condition numbers as the degree grows, so rounding errors dominate.

Summary

  • Through n + 1 distinct points there is exactly one polynomial of degree at most n.
  • The Lagrange form is easy to write and prove; the Newton form is better for adding points and cheap evaluation.
  • Barycentric interpolation is the stable way to evaluate it in practice.
  • The error depends on a high derivative and on node placement; never extrapolate far.

Next: The Runge phenomenon and Chebyshev nodes