The error that keeps coming back to its worst

Every polynomial built so far was chosen by where it agrees with the function. The Taylor polynomial agrees at one point, to as many derivatives as it has coefficients. The interpolating polynomial agrees at several points, one value at each. Both are chosen by a local condition and then judged, afterwards, by how far they stray somewhere else.

There is a more direct question. Fix an interval, fix a degree, and ask for the polynomial whose largest error over the whole interval is as small as it can be — the polynomial that is best at its worst. That is what a computer’s library routine for $e^x$ actually wants: nobody who calls it cares about the error at one point, only about the worst error anywhere it will be called.

The figure below is the answer for $e^x$ on $[-1, 1]$ at degree three, drawn as its error curve. The curve rises to $0.00553$, falls to $-0.00553$, rises again, falls again, and rises again: five times it touches the same largest size, with the signs alternating. That pattern is not a coincidence of this function. It is the whole theory.

Five touches for a cubic #

A cubic has four coefficients. Its best error curve touches the largest error five times — one more than the number of coefficients — and consecutive touches have opposite signs. For degree $n$ the count is $n + 2$.

Pafnuty Chebyshev found this criterion in the 1850s, and he found it while working on a problem about steam engines: James Watt’s linkage for turning rotation into nearly straight motion traces a curve that is nearly straight, and Chebyshev wanted the linkage whose worst deviation from straightness was smallest. It is the same question, asked of a mechanism instead of a polynomial, and the answer he gave for polynomials is exact:

A polynomial of degree $n$ is the best uniform approximation to a continuous function on an interval if and only if its error attains its largest absolute value at $n + 2$ points, with alternating signs. And the best polynomial is unique.

The word that matters is “if and only if”. Most characterisations of an optimum say what the optimum must satisfy and leave the searcher to hunt for candidates. This one is a test that a single candidate can pass, and passing it proves that nothing better exists — without comparing the candidate to a single other polynomial.

Why there is anything to find #

Before the criterion, a question it quietly assumes: can the worst error be made small at all? A continuous function on an interval can be wildly irregular — nowhere differentiable, with a corner at every point — and it is not obvious that smooth polynomials can follow it everywhere at once.

Karl Weierstrass proved in 1885 that they can: for every continuous function on a closed interval and every tolerance, some polynomial stays within that tolerance everywhere. The cleanest proof came from Bernstein in 1912 and it is probabilistic. Average the function’s values along a row of Pascal’s triangle — weight $f(k/n)$ by the chance of $k$ heads in $n$ tosses of a coin that lands heads with probability $x$ — and the result is a polynomial in $x$ that converges to $f$ uniformly, because the number of heads concentrates near $nx$.

Bernstein’s polynomials are very bad approximations in practice; the error shrinks only like $1/n$ even for the smoothest function. But they settle existence, and existence is what makes the question of this essay well posed. For each degree $n$ there is a smallest achievable worst error $E_n(f)$, the sequence falls to nought, and the only questions left are which polynomial achieves $E_n$ and how fast $E_n$ falls.

Why alternation is a proof #

The argument that alternation certifies optimality is a counting argument about roots, and it is short enough to give whole.

Suppose $p$ has degree $n$ and its error $f - p$ touches its largest size $E$ at $n + 2$ points with alternating signs. Suppose some other polynomial $q$ of degree $n$ did better, with every error below $E$. Look at the difference

$$q - p = (f - p) - (f - q).$$

At each of the $n + 2$ touching points, $f - p$ is $\pm E$ and $f - q$ is smaller than $E$ in size, so $q - p$ has the same sign as $f - p$ there. Those signs alternate, so $q - p$ changes sign at least $n + 1$ times, and a continuous function that changes sign $n + 1$ times has $n + 1$ roots. But $q - p$ is a polynomial of degree at most $n$, and a non-zero polynomial of degree $n$ has at most $n$ roots. So $q - p$ is the zero polynomial, and $q$ was never better at all.

The converse — that the best polynomial must alternate that many times — runs the argument in reverse. If the error of $p$ reached its maximum with fewer than $n + 2$ alternations, there is a polynomial of degree $n$ with a sign pattern that matches the error at every place it is largest, and subtracting a small multiple of it lowers the error everywhere it was worst without raising it anywhere else to that height. Only when the alternations run out does no correction exist.

The degree of the polynomial and the number of alternations are tied by the same fact that makes interpolation through $n + 1$ points possible and unique: a polynomial of degree $n$ is pinned down by $n + 1$ conditions and can wiggle through at most $n$ sign changes. The alternation theorem is the uniform-error version of that sentence.

Three answers to the same question #

With the best cubic in hand, the older methods can be scored on the question it answers.

The Taylor cubic is excellent at nought and poor at the ends, because every bit of information it has is information about nought: its error has an unknown in it, $e^\xi x^4/24$, and at $x = \pm 1$ that unknown is as large as it gets. Its worst error is $0.052$, nearly ten times the best.

The cubic through the four Chebyshev points is a different story. It is within about twenty per cent of the best, at no extra cost — it needs four values of the function and nothing else. That near-miss is not luck, and the next section is the reason for it.

And the best cubic sits below both, with its five touches. Its error is spread across the interval as evenly as an error can be spread. None of the effort goes into being very accurate anywhere; all of it goes into not being inaccurate anywhere.

It is worth saying what “best” does not mean here. At the centre, the Taylor cubic is enormously better than the best one — its error there is nought and the best cubic’s is about $0.0055$. The best polynomial wins only on the one number it was chosen to minimise, and a user who evaluates mostly near nought would be better served by the Taylor polynomial. Best is always best at something, and the choice of the something is the real decision.

The smallest monic polynomial #

One special case of the alternation theorem explains why the Chebyshev points work, and it closes a loop that was left open with the points that ruin the fit.

Take the function $x^n$ and approximate it by polynomials of degree $n - 1$. The error $x^n - p(x)$ is then a monic polynomial of degree $n$ — leading coefficient one — and the best approximation is the same thing as the monic polynomial of degree $n$ that stays smallest on the interval.

The answer is the Chebyshev polynomial $T_n(x) = \cos(n \arccos x)$, scaled by $2^{1-n}$. Its equioscillation is visible in its definition: as $x$ runs across $[-1, 1]$, $\arccos x$ runs from $\pi$ to $0$, and $\cos(n\theta)$ swings between $+1$ and $-1$ exactly $n + 1$ times — which is $n + 2$ for degree $n - 1$ approximation, the count the theorem demands. The figure did not quote this: it ran the exchange algorithm below on $x^5$ and found the Chebyshev polynomial.

Now recall how interpolation fails. The error of the polynomial through $n$ nodes is the $n$-th derivative of the function, times the product $(x - x_1)(x - x_2)\cdots(x - x_n)$, divided by $n!$. The derivative factor is out of anybody’s control. The product is a monic polynomial whose roots are the nodes, and it is the only part of the error the choice of nodes can touch. Choosing the nodes to make that product as small as possible is choosing the smallest monic polynomial, and so the best nodes are the roots of $T_n$ — which are exactly the Chebyshev points, the shadows of equally spaced points on a semicircle. The node rule that looked like a clever trick is the alternation theorem applied to the one piece of the error that can be chosen.

The same polynomials turn up far from approximation. $T_n$ composed with $T_m$ is $T_{nm}$, so they commute under composition, and the map $x \mapsto T_2(x) = 2x^2 - 1$ is a chaotic map that can be solved exactly, because the substitution $x = \cos\theta$ turns it into doubling an angle. The swing between $+1$ and $-1$ that makes $T_n$ the smallest monic polynomial is the same swing that makes it chaotic.

Finding the best by exchanging points #

The theorem says how to recognise the best polynomial, and Evgeny Remez turned that into a way of finding it in 1934.

Pick $n + 2$ trial points — the reference — and demand that the error take equal size $E$ at them with alternating signs. That is $n + 2$ linear equations in $n + 2$ unknowns, the $n + 1$ coefficients and $E$, and it has a unique solution. The resulting polynomial alternates at the reference but may be worse somewhere else. So find where its error is actually largest, move the reference to those places — one extreme in each region where the error keeps one sign — and solve again.

What makes the iteration trustworthy is a theorem of Charles de la Vallée Poussin: if a polynomial’s error alternates in sign at $n + 2$ points, the best possible error is at least the smallest of those alternating values. So at every step the levelled error $|E|$ is a proven lower bound on the best error, and the true maximum error of the current polynomial is trivially an upper bound. The two numbers trap the answer, the figure shows both, and when they meet the iteration has not merely converged — it has produced a certificate.

That is a different kind of stopping rule from most numerical methods, which stop when successive answers stop changing and hope the answer is right. Here the method stops when a lower bound and an upper bound agree, and the agreement is a proof.

The same exchange designs digital filters. In 1972 Thomas Parks and James McClellan adapted it to find the filter whose frequency response deviates least from an ideal one, and the resulting “equiripple” filters — whose error ripples to the same height again and again across the band — are the alternation theorem, used in every piece of equipment that processes a signal.

Where the function is hardest, the points crowd #

The touching points of the hero’s error curve are spread nearly symmetrically, because $e^x$ is equally easy everywhere on $[-1, 1]$. For a function that is harder near one end they are not.

The function $1/(1.2 - x)$ blows up at $x = 1.2$, a fifth of a unit beyond the interval. Nothing on the interval itself is wrong — the function is smooth and bounded there — but near $x = 1$ it climbs steeply, and a quartic has to spend its flexibility there. The six touching points of the best error bunch up toward the right: the error’s humps are narrow where the function is hard and broad where it is easy.

That is the alternation theorem allocating effort. The error must reach its largest size six times with alternating signs, and the polynomial distributes the six touches wherever the function forces it to bend most. No rule of the form “use Chebyshev points” can do this, because Chebyshev points are chosen before the function is known; the best polynomial is chosen after.

It is also the first appearance of a pole outside the interval deciding what happens inside it. The pole at $1.2$ is not on $[-1, 1]$, but its distance from the interval sets how fast the best error falls as the degree rises — the same way a pole off the real line set the radius of a Taylor series. What replaces the radius, when the question is about an interval rather than a point, is the business of an ellipse, not a disc.

Weights, ratios, and what a library actually computes #

The criterion is more robust than its statement suggests, and the robustness is why it matters outside textbooks.

A library routine for $e^x$ does not minimise the absolute error; it minimises the relative error, $(f - p)/f$, since a floating-point result is judged by how many of its leading digits are right. The alternation theorem holds unchanged with any positive continuous weight: the best polynomial for the weighted error is the one whose weighted error touches its largest size $n + 2$ times with alternating signs. The exchange algorithm runs unchanged too.

It also holds for ratios of polynomials. A rational function $p/q$ with numerator of degree $m$ and denominator of degree $k$ is best when its error alternates $m + k + 2$ times — slightly fewer if the best ratio can be written with smaller degrees. Rational approximations are what most mathematical libraries actually use for functions with nearby singularities, because a denominator can imitate a pole that no polynomial can, which is the same reason Padé’s ratios summed a series that diverged.

What does not survive is the interval. On a region of the complex plane, or in several variables, the uniqueness fails in general and no characterisation as clean as alternation exists. The theorem is a fact about the real line, and specifically about the fact that a polynomial of degree $n$ on a line can change sign at most $n$ times.

A corner, and slow progress #

For a smooth function like $e^x$ the best error falls extraordinarily fast as the degree rises: $0.045$ at degree two, $0.0055$ at three, $0.00054$ at four — a factor of about ten for each degree added, and the factor itself keeps growing. For a function with a corner it does not.

The best degree-six approximation to $|x|$ has error $0.046$, and doubling the degree roughly halves it. Sergei Bernstein proved in 1913 that the best error at degree $n$ is about $\beta / n$ for a constant $\beta$ near $0.28$. Every polynomial is smooth, the corner is not, and the best a smooth curve can do near a corner is round it off over a width proportional to $1/n$.

That is the first sign of the relationship the Bernstein ellipse makes exact: how fast the best error falls is decided by how smooth the function is, and for smooth functions by something geometric in the complex plane, exactly as the radius of convergence was for Taylor series. A corner is the crudest kind of roughness, and it costs a whole power of $n$.

What an error curve does not say #

The pictures show error curves, and an error curve is a statement about one function at one degree. What they cannot show is the part of the theory that makes it usable.

They cannot show uniqueness except by example. Each figure finds one polynomial and checks that it alternates, which proves that polynomial is best; it does not show what goes wrong when two candidates both look good, because the theorem says that never happens.

They cannot show how the reference points move when the function changes. The exchange converges very fast for smooth functions and can be delicate for functions whose error has many nearly equal humps, where two candidate extremes compete; the figures show well-behaved cases because those are the ones that demonstrate the method, and a library implementation spends most of its care on the others.

And they use a finite grid. The largest error is found by sampling four thousand points and polishing each extreme, so “touches its largest size” means “to about seven significant figures on that grid”. For the polynomials drawn that is ample, and it is still a measurement rather than a proof — the proof is the alternation argument above, which the measurement is checking the hypotheses of.

Still open: a closed form for Bernstein’s constant #

Bernstein’s constant is the limit of $n$ times the best error in approximating $|x|$ on $[-1, 1]$ by polynomials of degree $n$. Bernstein computed it to be about $0.282$ and conjectured, reasonably, that it was $1/(2\sqrt\pi) = 0.28209\ldots$ — a number close enough to his estimate that it seemed the obvious candidate.

It is not. Richard Varga and Amos Carpenter computed the constant to fifty digits in 1985 and found $\beta = 0.28016949902\ldots$, which disagrees with $1/(2\sqrt\pi)$ in the third decimal place. No closed form for $\beta$ is known, and there is no strong reason to expect one: it is defined by a limit of optimisation problems, each of which has an answer characterised by alternation and computed by exchange, and nothing in that description suggests the limit should be a combination of familiar constants.

It is a small question and a characteristic one. The theory tells exactly what the best polynomial is at every degree and how to find it to any accuracy. What it does not tell is the number that summarises all of them at once.