Chebyshev nodes
/ CHEB-ih-shev /
If equally spaced sample points cause high-degree interpolation to blow up at the ends (Runge's phenomenon), the natural question is: where SHOULD you place the points instead? The surprising answer is to bunch them up near the two ends of the interval and spread them out in the middle. Those specially placed points are the Chebyshev nodes, and they make high-degree polynomial interpolation behave beautifully.
The recipe: to get them on [-1, 1], take equally spaced angles and project them down from a circle. One common set is x_k = cos((2k+1) pi / (2n+2)) for k = 0, ..., n (the Chebyshev points of the first kind); another popular set adds the two endpoints (the Chebyshev-Gauss-Lobatto points, x_k = cos(k pi / n)). Either way the nodes cluster near -1 and +1, where equispaced grids were weakest. The reason this works is precisely the interpolation error formula: among all node placements, the Chebyshev nodes are the choice that MINIMIZES the maximum size of the node product (x - x_0)...(x - x_n), shrinking it from exponentially large (equispaced) to as small as it can be — its peak is just 2^(-n) on [-1, 1]. Tame the node product and the end-oscillations of Runge vanish.
With Chebyshev nodes, interpolating any smooth function converges rapidly and reliably as you add points, and for analytic functions the error decays geometrically. Combined with the barycentric Lagrange formula (whose weights for Chebyshev nodes are dazzlingly simple — just alternating +/-1 with halved endpoints), the whole scheme is fast and numerically stable; this is the engine inside spectral methods and the Chebfun software. The honest caveats: you must be able to SAMPLE the function wherever you like (not always possible with fixed measured data), and your interval should be mapped to [-1, 1] first. If your data sits on a fixed equispaced grid you cannot move, splines are the better tool.
For 5 Chebyshev nodes (first kind) on [-1, 1]: cos(pi/10), cos(3pi/10), cos(5pi/10), cos(7pi/10), cos(9pi/10) = 0.951, 0.588, 0, -0.588, -0.951. Notice the gaps: 0.36 between the inner pair but only 0.05 at the very ends — the points crowd toward +/-1.
Equal angles on a circle, projected down — denser at the ends.
Chebyshev nodes help only if you can choose WHERE to sample. If the data comes from a fixed equispaced grid you cannot resample, they do not apply — use splines instead. Also remember to rescale a general interval [a, b] onto [-1, 1].