Approximation

Approximation

Approximation of functions

Plates on approximation, the art of copying a function with something simpler, each one computed in the browser as you watch: the radius of convergence, Taylor polynomials that follow sin x further and further out but stop dead at |x| = 1 for arctan x, a function smooth along the whole real line, because of the singularities it has at ±i in the complex plane, where the error of every polynomial is drawn at every pixel and closes up into the disc of convergence, and the Padé approximants, rational functions found by Gaussian quadrature, which put their poles on the branch cuts and converge beyond the disc; Runge's phenomenon, polynomials through more and more equally spaced points of 1/(1 + 25x²) that swing ever more wildly near the ends, the same polynomials through Chebyshev points that converge, the reason in the complex plane, where the error is decided by the poles at ±i/5 and a curve drawn from the nodes, and the Lebesgue constant, which says how much worse than the best polynomial interpolation can be; equal ripples, the Chebyshev polynomials seen as cosines wrapped round a cylinder, the monic polynomial that stays smallest, the Remez exchange finding the best approximation to eˣ by making its error ripple with equal height, and Chebyshev coefficients that fall at a rate set by an ellipse through the nearest pole; and any continuous function, Bernstein's polynomials averaging a function with binomial weights, converging even to Weierstrass's function with no derivative anywhere, and drawing Bézier curves by de Casteljau's construction; and splines, the draftsman's strip that bends least through its points, B-splines grown from a box by sliding it along again and again until they look like the normal curve, splines converging on the equally spaced points where polynomials failed, the error falling sixteen-fold each time the spacing is halved, and Chaikin's corner cutting, which turns a polygon into a spline. The corner keeps the error, measured on the curves in the picture, beside what the theory predicts.

The radius of convergence

The Taylor polynomial of degree n copies a function at a single point, its value and its first n derivatives; the higher the degree, the longer the stretch over which it stays close to the function. For sin x the stretch grows without end. For arctan x it stops at |x| = 1, although the graph is perfectly smooth there. The reason lies in the complex plane, where arctan z has singularities at ±i: the Taylor series of a function converges inside the largest disc about its centre that contains no singularity, and diverges outside it. The plate draws the polynomials on the real line and then, at every pixel of the complex plane, the size of their error. Rational functions are not held to the disc: the Padé approximants, found by Gaussian quadrature, converge along the whole real line. The corner keeps the error, measured on the curves in the picture, beside what the theory predicts.

Plates

Notes

The error in the corner

Every plate keeps the error. The largest gap between the approximation and the function is measured on the curve drawn in the picture, and set beside what the theory says it should be: the first term a series leaves out, the residues at the poles, the Lebesgue constant, Hall's bound for splines. Some of these agree to every digit shown; others are bounds, and the measured error stays below them.

An error at every pixel

In the complex plane the shader evaluates both the function and its approximation at every pixel and draws the logarithm of their difference, one contour for each power of ten. The disc of convergence is not drawn: it is where these contours, tightening as terms are added, close up. Single precision on the GPU stops the contours at about one part in a hundred thousand; further in, little but rounding is left.

Computed, not stored

Nothing on screen is precomputed. The Padé approximants come from Gauss–Legendre quadrature, its nodes found by Newton's method on the Legendre polynomials; the interpolating polynomials are evaluated with the barycentric formula, which stays accurate at forty-one points; and the corner's second opinion on every interpolation error comes from the residue theorem, using nothing but the nodes and the poles of the function. The best approximation of Plate III is found by the Remez exchange from a poor start, the Bernstein polynomials of Weierstrass's function come from a closed form that needs twelve terms for any n, and every spline is a tridiagonal system solved afresh as its points move.