Newton's divided differences

Suppose you build your interpolating curve one point at a time, and you want each new data point to just ADD a correction without disturbing what you already have — like adding a finer term to a series. Newton's divided-difference form does exactly this: it writes the interpolating polynomial as a nested sum where each successive term pulls the curve through one more point.

The form is p(x) = c_0 + c_1 (x - x_0) + c_2 (x - x_0)(x - x_1) + c_3 (x - x_0)(x - x_1)(x - x_2) + .... The coefficients c_k are the divided differences, computed in a triangular table. The zeroth differences are just the y-values f[x_i] = y_i. The first differences are slopes, f[x_i, x_{i+1}] = (f[x_{i+1}] - f[x_i]) / (x_{i+1} - x_i). Higher ones recurse: f[x_i, ..., x_{i+k}] = (f[x_{i+1}, ..., x_{i+k}] - f[x_i, ..., x_{i+k-1}]) / (x_{i+k} - x_i). The leading diagonal of this table gives c_0, c_1, c_2, ... directly. Each (x - x_j) factor is zero at the earlier nodes, so adding a term never breaks the earlier fits — that is why a NEW data point just appends one more coefficient and one more factor, cheap to extend.

Newton's form is the practical workhorse when you grow a data set incrementally or when you want to estimate the interpolation error (the leading neglected divided difference behaves like the error term). Building the table costs O(n^2) once; evaluating p(x) afterward is O(n) using nested (Horner-style) multiplication. The same polynomial that Lagrange writes as a weighted sum, Newton writes as a nested product — same curve, different and often more convenient bookkeeping. An honest caveat: like all single high-degree interpolation, it still suffers Runge's phenomenon at equispaced nodes.