Polynomial Approximations to Common Functions

On this page, we list many functions which can be uniformly approximated by low-degree polynomials on bounded domains. For all results stated here, we let $f(x)$ denote the function we want to approximate, $d$ denote the degree of the polynomial approximation, and $\varepsilon$ denote the uniform approximation error, so that

\sup_{x\in[a,b]}\left|f(x) - p(x)\right| \leq \varepsilon \hspace{1cm} \text{for some deg}(p) \leq d

Theorem 1: Approximate Monomial
Theorem

Fix positive integers

d

and

q

, and suppose we want to approximate

f(x)=x^q

for

x\in[-1,1]

. Then there exists a polynomial

p(x)

with degree

d

such that

\sup_{x\in[-1,1]} \left|p(x)-x^q\right| \leq 2e^{-\frac{d^2}{q}}

Or, equivalently, there exists a degree $d=\sqrt{2q\ln(\frac2\varepsilon)}$ polynomial $p(x)$ such that

\sup_{x\in[-1,1]} \left|p(x)-x^q\right| \leq \varepsilon

(Theorem 3.3 from Sachdeva Vishnoi (2013))

Theorem 2: Approximate Negative Exponential
Theorem

Suppose we want to approximate

f(x)=e^{-x}

for

x\in[0,b]

. Then there exists a degree

d=O(\sqrt{\max\{b,\log(\frac1\varepsilon)\} \cdot \log(\frac1\varepsilon)})

polynomial

p

such that

\sup_{x\in[0,b]} \left|p(x)-e^{-x}\right| \leq \varepsilon

(Theorem 4.1 from Sachdeva Vishnoi (2013))

This result for negative exponential can be very easily generalized to other functions, given Theorem 1, so if you need to make your own polynomial approximation, consider reading Chapter 4 from Sachdeva Vishnoi (2013).

Bibliography

Vishnoi and Vishnoi. Faster algorithms via approximation theory. Theoretical Computer Science 2013.

Polynomial Approximations to Common Functions

Theorem 1: Approximate Monomial Theorem

Theorem 2: Approximate Negative Exponential Theorem

Bibliography

Theorem 1: Approximate Monomial
Theorem

Theorem 2: Approximate Negative Exponential
Theorem