Chebyshev and Minimax Approximation

Minimax approximation seeks the approximant whose largest error is as small as possible, giving a uniform accuracy guarantee; Chebyshev polynomials and the Remez algorithm are the central tools for computing and understanding such best uniform approximations.

Definition

Minimax approximation is the determination of the approximant that minimizes the maximum absolute error over the domain, and Chebyshev approximation is the body of theory and methods built around Chebyshev polynomials that delivers or closely approaches this best uniform fit.

Scope

This topic covers best uniform (minimax) approximation in the maximum norm, the Chebyshev equioscillation theorem, the role and near-optimality of Chebyshev polynomials and Chebyshev interpolation, and the Remez exchange algorithm for computing minimax polynomial and rational approximations.

Core questions

• What characterizes the best uniform approximation, and why is it unique?
• Why are Chebyshev polynomials central to near-optimal polynomial approximation?
• How does the Remez algorithm compute the true minimax approximation iteratively?
• When is a minimax fit preferable to a least-squares fit, and at what computational cost?

Key theories

Equioscillation theorem

A polynomial of degree at most n is the best uniform approximation to a continuous function if and only if its error attains its maximum magnitude with alternating signs at at least n+2 points; this characterization makes the best approximation unique and computable.

Near-optimality of Chebyshev approximation

Interpolation or expansion in Chebyshev polynomials at Chebyshev points yields approximations whose maximum error is within a small, logarithmically growing factor of the best possible, so Chebyshev methods provide an inexpensive substitute for true minimax fits.

Remez exchange algorithm

The Remez algorithm iteratively adjusts a candidate set of reference points to enforce the equioscillation condition, converging rapidly to the exact best polynomial or rational minimax approximation.

Mechanisms

The Remez algorithm begins with a guess of the equioscillation points, solves a small linear system so the error equioscillates with equal magnitude and alternating sign on that reference set, then relocates the reference points to the new error extrema and repeats; the procedure converges quadratically to the minimax solution. Chebyshev approximation instead expands the function in Chebyshev polynomials — computable efficiently via the fast Fourier transform — exploiting their minimal sup-norm property to obtain near-best accuracy without iteration.

Clinical relevance

Minimax and Chebyshev approximation are used to build the elementary-function routines in mathematical libraries, to design digital filters with uniform frequency-response error, and to construct compact, uniformly accurate approximations for embedded and real-time computation where a worst-case error bound matters more than average error.

History

The theory originates with Chebyshev's nineteenth-century study of best uniform approximation and the equioscillation principle; Evgeny Remez devised his exchange algorithm in the 1930s, and Chebyshev-based computation became a practical mainstay of numerical software in the later twentieth century, notably through automatic-differentiation-free Chebyshev technology in modern systems.

Key figures

• Pafnuty Chebyshev
• Evgeny Remez
• Lloyd N. Trefethen

Seminal works

• trefethen2013
• powell1981
• cheney1966

Frequently asked questions

What does equioscillation mean intuitively?

It means the best uniform approximation distributes its error so that the error curve repeatedly touches its maximum height, alternating between positive and negative, at enough points. Any other candidate could be improved, so this balanced error pattern signals optimality.

Why use Chebyshev interpolation instead of the exact minimax polynomial?

Computing the exact minimax polynomial requires the iterative Remez algorithm, whereas Chebyshev interpolation is fast and non-iterative and comes within a small factor of the best possible error, so it is usually the practical choice.