# Low-degree polynomial approximation of the piecewise-linear function $x \mapsto \max(x, 0)$ on an interval $x \in [-R,R]$

For $$R > 0$$, consider the piecewise-linear function $$\sigma_R: [-R,R] \rightarrow \mathbb R^+$$, defined by $$\sigma_R(x) := \max(x,0)$$.

# Question

Given $$\epsilon> 0$$, find a "low-degree" polynomial $$P_\epsilon$$ (the smaller the degree, the better!) which approximates $$\sigma_R$$ within $$\epsilon$$ w.r.t the sup-norm, ie. $$\|\sigma_R-P_\epsilon\|_\infty := \max_{x \in [-R,R]}|\sigma_R(x)-P_\epsilon(x)| \le \epsilon.$$

# Observations

Here is a graphical illustration of such an approximation. This is done by using Remes's algorithm. It is implemented in Mathematica's command MiniMaxApproximation[]. Below is an image of the corresponding Mathematica notebook, giving a polynomial approximation of degree $$10$$. (Click on the image to see it better.) The quality of the approximation seems substantially better than in your picture. • Thanks for the response, and for Ramez algorithm. My interest for the question is almost purely analytical. In particular, for a fixed sup-norm accuracy $\epsilon$, I'm interested in degree of the best polynomial approximation (+ existence), in terms of $R$ and $epsilon$. Intuitively it should be something like $\text{poly}(R,1/\epsilon)$ or even $\text{poly}(R,\log(1/\epsilon))$. Jul 8 '19 at 21:45
• According to Bernstein, for polynomials of degree $2n$, and $R=1$, one has $\epsilon\sim C/n$ with $0.278\le C\le0.286$ (check the link in my answer) Jul 8 '19 at 22:48
• Great. Thanks for the comment. Jul 8 '19 at 22:59
• (so on $[-R,R]$ the degree is $\sim 2CR/\epsilon$) Jul 9 '19 at 10:05

Subtracting $$x/2$$, and rescaling, the problem is reduced to the best uniform approximation of $$|x|$$ on $$[-1,1]$$ by polynomials, a problem already considered by Bernstein.
According to Chebyshev's theory, the polynomial of degree $$\le n$$ that minimizes the uniform distance on $$[-1,1]$$ from the absolute value function is unique and is characterized by Chebyshev's equioscillation theorem. It is also even, by symmetrization argument. More details should be easily available in the literature; for instance, these notes devote the whole chapter 3 exactly to the problem.

• Jul 8 '19 at 22:49
• Thanks for the response. Jul 8 '19 at 22:56