Best polynomials equioscillate their worst errors
Approximation theory asks how to replace hard functions with simpler ones and how to measure the damage. Computer libraries need polynomials using only arithmetic ops that nearly match floating-point accuracy. The equioscillation theorem says a best uniform approximation hits its peak error with alternating signs.
What counts as best and what counts as simpler depends on the job. For a maths library, simpler means built from operations a chip can do, like addition and multiplication, so designers use polynomials or ratios of polynomials. The aim is accuracy near the limit of the machine's floating-point arithmetic, reached either by raising the degree or by shrinking the interval. Addition and scaling formulas help with the shrinking, and modern libraries often split the domain into many tiny pieces, each handled by a low-degree polynomial.
With the interval and degree fixed, the target is the smallest possible worst-case gap between polynomial and function. For well-behaved functions, the optimal degree-N polynomial produces an error curve that swings between equal highs and lows N+2 times, two of those extremes landing on the interval's endpoints; for degree four approximations of log and exp, that means six level peaks. The proof is short: if some other degree-N polynomial did better at every peak, the difference of the two would change sign N+1 times and so need N+1 roots, impossible for its degree. Contrived functions can defeat the result, but rarely in practice.
A shortcut to a nearly optimal answer is to expand the function in Chebyshev polynomials and truncate, a cousin of Fourier analysis. It works because, for rapidly converging series, the first discarded term dominates the error, and Chebyshev polynomials themselves oscillate evenly between plus and minus one. The result is closer to optimal for exp, whose series converges very fast, than for log. Chebyshev expansion also underlies Clenshaw–Curtis numerical integration.
To reach the true optimum, the iterative Remez algorithm picks N+2 test points, solves linear equations forcing equal, alternating errors there, and repeats until the error curve levels out.
Source: Approximation theory
