Approximating step functions with polynomials

approximationnumerical methodspolynomialsreal-analysis

Let $t_1 < t_2 < \cdots <t_m$ be real, and $X = \cup_{i=1}^{m-1} (t_i, t_{i+1})$ be a union of real open intervals. Let $f:X \rightarrow \{-1, 1\}$ be any piecewise constant function of form
$$
f(x) =
\begin{cases}
a_1 & \text{ if } t_1 < x < t_2 \\
a_2 & \text{ if }t_2 < x < t_3 \\
\vdots \\
a_{m-2} & \text{ if } t_{m-2} < x < t_{m-1} \\
a_{m-1} & \text{ if } t_{m-1} < x < t_m
\end{cases}
$$
Where $a_i \in \{-1, 1\}$, and $a_{i} = -a_{i+1}$ for $i = 1, …, m-1$.

I have a number of questions regarding polynomial approximations of such a function $f$:

  1. Can we always find a sequence of polynomials $(p_n)$ so that $(p_n)$ converge pointwise to $f$, AND we have some fixed (not arbitrary) global error bound, say $1$, such that $|p_n(x) – f(x)| \leq 1$ for all $x \in X$ and $n \in \mathbb{N}$?
  2. If so, are such polynomials easy to find?
  3. How quickly do we get convergence?

I am aware that, upon picking a suitable inner product, we can use any collection of orthonormal polynomials to make approximations of functions. For example I know the Chebyshev, Bernstein, Jacobi etc. polynomials can be used to approximate continuous functions on bounded intervals, but I have found no theorem that says we can use these to construct approximations for arbitrary piecewise constant functions like the one given above.

Indeed, it is easy to find a polynomial approximation for the Heaviside Step function for example, however it is unclear how, or if this an be done for more complicated step functions.

Best Answer

The answer is yes, there do exist such polynomials, and in fact we can construct them in a way that they converge to the step function at an exponential rate. We can do this by defining polynomial one-dimensional maps with an unstable fixed point and an attracting period two orbit. The iteration of this map then converges to the period two orbit, so we can iterate this map over an appropriate polynomial, to achieve the approximation we desire.

See the papers https://arxiv.org/abs/1008.3765 and https://arxiv.org/abs/math/0604324 for complete study of this problem.

Related Question