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.

Improve this question
$\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
    Commented Sep 17, 2021 at 17:53
  • $\begingroup$ If there any reason you want pointwise convergence instead of uniform convergence on compact sets? $\endgroup$
    – Joseph Van Name
    Commented Sep 18, 2021 at 13:40

3 Answers 3

Reset to default
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$.

Improve this answer
$\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.

Improve this answer
$\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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .