Effective Bounds on Strong Unicity in L1-Approximation

  • Ulrich Kohlenbach
  • Paulo B. Oliva

Abstract

In this paper we present another case study in the general project of Proof Mining which means the logical analysis of prima facie non-effective proofs with the aim of extracting new computationally relevant data. We use techniques based on monotone functional interpretation (developed in [17]) to analyze Cheney's simplification [6] of Jackson's original proof [9] from 1921 of the uniqueness of the best L1-approximation of continuous functions f in C[0, 1] by polynomials p in Pn of degree <= n. Cheney's proof is non-effective in the sense that it is based on classical logic and on the non-computational principle WKL (binary K¨onig lemma). The result of our analysis provides the first effective (in all parameters f, n and epsilon) uniform modulus of uniqueness (a concept which
generalizes `strong uniqueness' studied extensively in approximation theory). Moreover, the extracted modulus has the optimal epsilon-dependence as follows from Kroo [20]. The paper also describes how the uniform modulus of uniqueness can be used to compute the best L1-approximations of a fixed f in C[0, 1] with arbitrary precision, and includes some remarks on the case of best Chebychev approximation.

Published
2001-05-14
How to Cite
Kohlenbach, U., & Oliva, P. (2001). Effective Bounds on Strong Unicity in L1-Approximation. BRICS Report Series, 8(14). https://doi.org/10.7146/brics.v8i14.20471