Effective Bounds on Strong Unicity in L1-Approximation

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.