11
$\begingroup$

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.

enter image description here

$\endgroup$

2 Answers 2

10
$\begingroup$

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.

enter image description here

$\endgroup$
4
  • $\begingroup$ 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))$. $\endgroup$
    – dohmatob
    Jul 8, 2019 at 21:45
  • 5
    $\begingroup$ 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) $\endgroup$ Jul 8, 2019 at 22:48
  • $\begingroup$ Great. Thanks for the comment. $\endgroup$
    – dohmatob
    Jul 8, 2019 at 22:59
  • 1
    $\begingroup$ (so on $[-R,R]$ the degree is $\sim 2CR/\epsilon$) $\endgroup$ Jul 9, 2019 at 10:05
13
$\begingroup$

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.

$\endgroup$
1

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.