I'm familiar with Newman's rational approximation of the absolute value function via rational functions. Are there other explicit functions that approximate $|x|$ with exponential error? I was under the impression that Chebhyshev polynomials also can give such good approximations to $|x|$ but I could not find this proved anywhere. Can someone point to a book/paper where I can read more about this?
$\begingroup$
$\endgroup$
7
-
1$\begingroup$ Doesn't Newman's paper state that polynomial approximations of the absolute value function can only give $1/n$ error and no better? This rules out approximations by Chebhyshev polynomials, no? $\endgroup$– Willie WongCommented Mar 20, 2018 at 20:14
-
$\begingroup$ @WillieWong Yes, it does. What I meant was rational function analgoues of Chebyshev polynomials. Admittedly this is quite vague, but I heard something similar in a talk, but couldn't find anything like that/ $\endgroup$– mathstudent42Commented Mar 20, 2018 at 20:19
-
$\begingroup$ Have you looked at the related papers on MathSciNet? There are quite a few about rational approximation of $|x|$ using Chebyshev nodes. For example mathscinet.ams.org/mathscinet-getitem?mr=1464051 proves 1/n log(n) rate, and there are some 1/n^2 results mathscinet.ams.org/mathscinet-getitem?mr=1645981 $\endgroup$– Willie WongCommented Mar 20, 2018 at 20:26
-
$\begingroup$ @WillieWong Thanks! I'll look at those. Is Newman's function the only one which guarantees exponential error? For my application, I need exponential error, but ran in to a few difficulties using Newman's function. Hence the question. $\endgroup$– mathstudent42Commented Mar 20, 2018 at 20:30
-
$\begingroup$ If you go to the MathSciNet entry for Newman's paper, there are 54 papers in the database that cited Newman. At least a few of them proved exponential rates. Taking a quick cursory glance at them they seem to be mostly based on modifications of Newman's method. $\endgroup$– Willie WongCommented Mar 20, 2018 at 20:33
|
Show 2 more comments
2 Answers
$\begingroup$
$\endgroup$
Denote the minimal approximation error to the function $f(x)=|x|$ in the uniform norm on $[-1,1]$ by $$ E_{mn}(f,[-1,1])=\inf_{r\in\mathcal{R}_{mn}}\|f-r\|_{\infty,[-1,1]}, $$ where $\mathcal{R}_{mn}$ denotes the set of rational functions with numerators of degree at most $m$ and denominators of degree at most $n$.
For rational approximation, it is known, by a result of H.R. Stahl (1992), that $$ \lim_{n\to\infty}e^{\pi\sqrt{n}}E_{nn}(f,[-1,1])=8, $$ while for polynomial approximation, by a classical result of S.N. Bernstein, there exists a constant $\alpha$ such that $$ \lim_{n\to\infty}nE_{n0}(f,[-1,1])=\alpha, $$ (no explicit expression for the so-called Bernstein constant $0.27<\alpha<0.28$ is known).
In particular, the rate of approximation by (any) polynomials can only decrease like $O(1/n)$.
A possible reference is
Petrushev, P. P.; Popov, V. A. Rational approximation of real functions. Encyclopedia of Mathematics and its Applications, 28. Cambridge University Press, Cambridge, 1987.
$\begingroup$
$\endgroup$
6
The Chebyshev series for $|x|$ on the interval $[-1,1]$ corresponds to the Fourier series for $|\cos(t)|$ on $[0, \pi]$. This Fourier series is
$$ \frac{2}{\pi} + \sum_{k=1}^\infty \frac{4 (-1)^{k+1}}{\pi (4 k^2-1)} \cos(2 k t) $$
i.e. the Chebyshev series is
$$ |x| = \frac{2}{\pi} + \sum_{k=1}^\infty \frac{4(-1)^{k+1}}{\pi (4 k^2-1)} T_{2k}(x) $$
Since the coefficients are rational functions of $k$, truncations can't provide exponential error.
answered Mar 20, 2018 at 20:24
-
$\begingroup$ Thanks! But are there other rational functions known which provide exponential error apart from Newman's function? $\endgroup$ Commented Mar 20, 2018 at 20:26
-
$\begingroup$ Where did you find out about this relation? I'd there some reference I may study for more results like this? $\endgroup$ Commented Jun 23, 2020 at 22:18
-
$\begingroup$ You might look at Wikipedia, or at Trefethen, Approximation Theory and Approximation Practice $\endgroup$ Commented Jun 24, 2020 at 1:17
-
$\begingroup$ @RobertIsrael Thank you. I was looking for a specific reference for the fact that "The Chebyshev series for |x| corresponds to the Fourier series for |cos(t)|". I don't think it's on Wikipedia, and the only mention of the absolute value function in the book appears to be Exercise 8.7. $\endgroup$ Commented Jun 24, 2020 at 9:18
-
$\begingroup$ There's nothing special about the absolute value function. The fact that $T_n(\cos(\theta)) = \cos(n \theta)$ means that a Fourier cosine series for $f(x)$ corresponds to a Chebyshev series for $f(\cos(t))$. This is mentioned in Wikipedia, e.g. "Since a Chebyshev series is related to a Fourier cosine series through a change of variables,..." $\endgroup$ Commented Jun 24, 2020 at 13:02