the barycentric Lagrange formula
/ bar-ee-SEN-trik /
Lagrange interpolation is elegant in theory but the naive version is slow and shaky in arithmetic. The barycentric formula is a clever rewriting of the SAME interpolating polynomial that keeps Lagrange's directness while becoming fast, stable, and trivial to re-evaluate at many points. It is the form practitioners actually use.
The idea is to precompute, once, a barycentric WEIGHT for each node, w_i = 1 / (product over j not equal to i of (x_i - x_j)). Then the interpolant is evaluated by the strikingly simple ratio p(x) = [ sum_i w_i y_i / (x - x_i) ] / [ sum_i w_i / (x - x_i) ]. Both the numerator and denominator are quick sums; computing the weights is a one-time O(n^2) cost, after which each evaluation of p(x) takes only O(n) work. ADDING a new data point only multiplies each old weight by one factor and computes one new weight — cheap, unlike rebuilding the naive Lagrange basis. The bottom 'partition of unity' trick (the denominator) is what makes it numerically stable, far better behaved than solving a Vandermonde system.
The formula shines brightest with good nodes: for Chebyshev nodes the weights collapse to a closed form (just alternating +/-1, with the two endpoint weights halved), so you skip the O(n^2) setup entirely and interpolation becomes both stable and essentially optimal in accuracy. This combination — Chebyshev nodes plus the barycentric formula — is the backbone of modern polynomial interpolation and of tools like Chebfun. One honest pitfall: if you evaluate exactly AT a node, the term (x - x_i) is zero and the formula divides by zero — code must special-case 'x equals a node' and return y_i directly.
Nodes 0, 1, 2: weights w_0 = 1/((0-1)(0-2)) = 0.5, w_1 = 1/((1-0)(1-2)) = -1, w_2 = 1/((2-0)(2-1)) = 0.5. With y = (1, 3, 2), evaluate at x = 0.5: numerator = 0.5*1/0.5 + (-1)*3/(-0.5) + 0.5*2/(-1.5) = 1 + 6 - 0.667; denominator = 0.5/0.5 - 1/(-0.5) + 0.5/(-1.5) = 1 + 2 - 0.333; ratio = 6.333/2.667 ~ 2.375.
Precompute weights once; each evaluation is then a fast ratio of sums.
Watch the singularity: if x exactly equals a node x_i, both sums divide by zero. A correct implementation tests for this and returns y_i. Otherwise the second barycentric form is among the most stable ways to interpolate.