Lagrange polynomial

Content sourced from Wikipedia, licensed under CC BY-SA 3.0.

The Lagrange interpolating polynomial is the unique polynomial of lowest possible degree that goes through a given set of points. If you have k+1 distinct x-values x0, x1, ..., xk and their corresponding y-values y0, y1, ..., yk, there exists a polynomial L(x) of degree at most k such that L(xj) = yj for every j.

L(x) can be written as a sum of simple building blocks called Lagrange basis polynomials:
L(x) = y0·l0(x) + y1·l1(x) + ... + yk·lk(x),
where each basis polynomial li(x) is designed to be 0 at all nodes except xj, where it is 1. Specifically, li(x) = product over m ≠ i of (x − xm) / (xi − xm). This guarantees that L(xj) = yj for all j, so the polynomial exactly interpolates the data. Each li has degree k, so L has degree at most k, and the interpolation is unique.

A more computationally friendly form is the barycentric form. It uses weights wj = product over m ≠ j of 1/(xj − xm) and writes
L(x) = [ sum from j=0 to k of wj·yj/(x − xj) ] / [ sum from j=0 to k of wj/(x − xj) ].
If the weights are precomputed, evaluating L at any x costs only O(k) operations. This form also handles values of x near the nodes well, and when x equals a node xj, you simply set L(xj) = yj.

Two important properties:
- The basis functions sum to 1 for all x: sum j lj(x) = 1. This is called a partition of unity and helps with stability.
- You can add a new node efficiently by updating the weights rather than rebuilding everything from scratch.

Practically, bare L(x) expressed as a sum of li(x) can be numerically unstable for many points, especially with evenly spaced x. This Runge phenomenon can be reduced by using Chebyshev (nonuniform) nodes. The barycentric form is often preferred in computation because it is fast and robust.

In short, Lagrange interpolation gives you the simplest polynomial that fits the data, with a clear construction from basis polynomials, plus a highly efficient and stable way to compute it using the barycentric form.