$L^{\infty}$ polynomial approximation

Question

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.

Answer 1

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.

Answer 2

Only for Analytic Functions. In an answer to a related question, carlo beenakker referred to me to the following paper by Wang and Xiang. There, in theorem 2.5 it states, roughly, that

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.