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.


Full Text:

PDF


DOI: http://dx.doi.org/10.7146/brics.v8i14.20471
This website uses cookies to allow us to see how the site is used. The cookies cannot identify you or any content at your own computer.
OK


ISSN: 0909-0878 

Hosted by the State and University Library and Aarhus University Library