5
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ Search for the Remez algorithm. $\endgroup$
    – Asaf
    Apr 3, 2016 at 14:19
  • 1
    $\begingroup$ 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. $\endgroup$ Apr 3, 2016 at 15:18
  • $\begingroup$ 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. $\endgroup$
    – bubba
    Jun 5, 2016 at 4:05

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.