# $L^{\infty}$ polynomial approximation

In short: For a given smooth or continuous function, how can we obtain the best $L^{\infty }$ approximating polynomial?

Jackson (1911) proved that there is a best approximating polynomial in the $L^{\infty}$ sense. The proof Can be found in the references below. The theorem is

Let $I=\lbrack -1,1]$, then there is a constant $C>0$ such that for all $f\in C\left( \bar{I} \right)$ we have:

$\| f - \Psi_{\infty, n} (f) \|_{\infty } \leq C sup_{\left| x-y\right| < \frac{2}{n}} \left| f(x) - f(y) \right|$

Where $\Psi_{\infty, n} (f)$ is the best interpolating polynomial in the aforementioned sense. However, I couldn't find anything about what would be this polynomial, or how to build it. I would assume that some advance was made since, but I couldn't find it in these textbooks.

Thank you

References

[1] Funaro, Polynomial Approximation of Differential Equations, theorem 6.1.2

[2] Davis, Approximation Theory, theorem 13.3.7.

• Search for the Remez algorithm. – Asaf Apr 3 '16 at 14:19
• Chapter 3 of the book "Constructive Approximation" (Springer, 1993) by R.A. DeVore and G.G. Lorentz (the same guy from "Lorentz spaces") has a good discussion on best uniformly approximating polynomials, including the Remez algorithm mentioned by Asaf above. – Pedro Lauridsen Ribeiro Apr 3 '16 at 15:18
• The book "Approximation Theory and Practice" by Trethefen has a lot of material about best approximations, why they're not always "best", and alternatives that are almost as good. Trethefen is one of the creators of the Chebfun system mentioned in the answer you accepted. – bubba Jun 5 '16 at 4:05

You are looking for the well-known Remez algorithm, which dates to 1934. For a practical implementation (with an excellent description), I highly recommend the Chebfun function remez() and this paper that describes it.
If $f\in C^{\infty} (\lbrack -1,1\rbrack)$, and given the Legendre expansion $f_N(x) = \sum\limits_{n=0}^N \hat{f} (n) p_n (x)$, then one have $\| f- f_N \|_{\infty} \sim r^{-n-1}$, where $r$ is the radius of convergence on the complex plane.