Approximating a step function with polynomials

Question

The Weierstrass approximation theorem says any continuous function $f(x): [0,1] \to \mathbb{R}$ can be approximated uniformly by polynomials. Given any $\epsilon$, we can find $p(x) = x^n + \dots $ such that:

$$ |f(x) - p(x)| < \epsilon $$

is always true. In practice how to do we find $p$? Let's say $f(x)$ was the step function:

$$ f(x) = \left\{ \begin{array}{cc} 0 & x \leq 0 \\ 1 & x > 0\end{array} \right. $$

How do we find the polynomial with $\deg p = 100$ which minimizes the tolerance $\epsilon$ ?

$$ \epsilon = \min_{\deg p = 10^2}\left[\max_{x \in [0,1]} | f(x) - p(x) | \right]$$

Hopefully I have defined a tractable problem... For example, does Lagrange Interpolation necessarily minimize $\epsilon$ ?

Answer 1

This problem is generally called the Minimax Problem. Unfortunately the step function is not continuous and therefore the Weierstrass approximation theorem does not apply. Any continuous approximation will have $\epsilon \ge 0.5$ since there is a jump of size 1 so the best you can do at that point is split the difference. In fact, $y = 1/2$ is as good as you can do for this problem due to the discontinuity although there are many higher order polynomials that fit better in other norms and just as well in the infinity norm that defines the minimax problem.

For continuous functions Chebyshev polynomials are a good approximation to the minimax solution. There is also a commonly used iterative algorithm call the Remez algorithm which approximately solves the minimax problem. The Remez algorithm leverages the equioscillation theorem which (to paraphrase) says that the polynomial of degree less than or equal to $n$ which has $n+2$ oscillations which are equally above or below the function (i.e. $f(x)\pm C$) on the desired interval is the one which solves the minimax problem for all polynomials of degree less than or equal to $n$. The Remez algorithm iteratively adjusts the coefficients of a polynomial to (approximately) achieve an equioscillating approximation function which is the solution to the minimax problem.