1
$\begingroup$

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)_{n=1}^\infty$ so that $(p_n)_{n=1}^\infty$ converge pointwise to $f$, and $|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 and construct (i.e. do we have closed form solutions)?
  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.

$\endgroup$
2
  • $\begingroup$ Since you have Heaviside approximations already, let $H_\epsilon(x)$ be a polynomial which is between $0$ and $\epsilon$ when $ -1<x<-\epsilon$, between $0$ and $1$ when $-1<x<1$, and between $1-\epsilon$ and $1$ when $\epsilon<x<1$. Now assume WLOG that $t_1=0$, $t_m=1$. Then let $f_1(x)=a_1$ $$f_{i+1}(x)=(1+\frac{a_{i+1}}{a_i}H_{\epsilon/m}(x-t_i))f_i(x).$$ I claim that $f_m(x)$ is now within $\epsilon$ on $f(x)$ except on a set of measure $2m \epsilon$, so taking the $f_m$ as $\epsilon\to 0$ gives the desired sequence of approximations. $\endgroup$
    – user44143
    Sep 17, 2021 at 17:53
  • $\begingroup$ If there any reason you want pointwise convergence instead of uniform convergence on compact sets? $\endgroup$ Sep 18, 2021 at 13:40

3 Answers 3

3
$\begingroup$

The polynomial $Q(y):=\frac43y-\frac13 {y^3}$ is increasing on the interval $[-1,1]$; it has fixed points $0$ and $\pm1$, and $\text{sgn }( Q(y)-y )=\text{sgn}y$. Thus the iterates of $Q$ starting from any $y\in [-1,1]\setminus\{0\}$ converge monotonically to $\text{sgn } y$ (in fact with exponential rate given by $Q'(\pm1)=\frac13$, and uniformly away from $0$ ).

Assuming w.l.o.g $a_i=(-1)^i$, your step function can be written $f(x):= \text{sgn} P(x)$ with $P(x):= \prod_{i=1}^m(t_i-x)$, for any $x\in X$. If we choose any $M\ge \|P(x)\|_{\infty,X}$ the polynomial sequence of iterates $Q^{n}\big( {P(x)}/ M\big)$ converges to $f$ on $X$; in fact increasing/decreasing between consecutive nodes, and uniformly on compacts set of $X$.

$\endgroup$
3
$\begingroup$

This question has been studied in two papers of Peter Yuditskii and myself: Zbl 1241.41005 (arXiv:1008.3765) and Zbl 1168.30020 (arXiv:math/0604324), where we determined the polynomial of best approximation to sgn(x), and the asymptotics of the error term. For the general case, take a linear combination of shifts sgn(x-a_j). There is no "Gibbs phenomenon" in this situation.

$\endgroup$
1
$\begingroup$

Yes. We can get pointwise convergence (and even uniform convergence on compact sets), and bounds on the rate of convergence are known. This is a consequence of this theorem that I proved as answers to this question.

Theorem: Suppose that $f,g:[a,b]\rightarrow\mathbb{R}$ are continuous functions such that $f\leq g,f(0)<g(0),f(1)<g(1)$, and there are finitely many points $c\in(a,b)$ with $f(c)=g(c)$. Furthermore, suppose that if $f(c)=g(c)$, then there is a polynomial $p$, constants $\delta>0,\alpha>0$, and a natural number $n$ such that if $|x-c|<\delta$, then $$f(x)\leq p(x)-\alpha|x-c|^{n}\leq p(x)+\alpha|x-c|^{n}\leq g(x).$$ Then there is some polynomial $q$ such that $f(x)\leq q(x)\leq g(x)$ for each $x\in[a,b]$.

The above result can either be proven using Mergelyan's theorem from complex analysis or the Stone Weierstrass theorem. The above result can be made constructive since the Bernstein polynomials produce a constructive proof of the Stone Weierstrass theorem; if $f:[0,1]\rightarrow\mathbb{R}$ is a continuous function, then $B_{n}(f)\rightarrow f$ uniformly where $B_{n}(f)$ is the Bernstein polynomial defined by $$B_{n}(f)=\sum_{k=0}^{n}\binom{n}{k}x^{k}(1-x)^{n-k}f(\frac{k}{n}).$$

The rate of convergence for the Bernstein polynomials has been studied. In particular, we have $$|B_{n}(f)(x)-f(x)|\leq\frac{5}{4}\omega_{f}(n^{-1/2})$$ where $\omega_{f}$ denotes the modulus of continuity of $f$ [3].

[3] T Popoviciu. Sur l'approximation des fonctions convexes d'ordere supérieur Mathematica (Cluj), 10 (1935), pp. 49-54

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.