Effective Bounds on Strong Unicity in $L_1$-Approximation

Ulrich Kohlenbach
Paulo B. Oliva

May 2001


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 by the first author) to analyze Cheney's simplification from 1965 of Jackson's original proof from 1921 of the uniqueness of the best $L_1$-approximation of continuous functions $f \in C[0,1]$ by polynomials $p\in P_n$ of degree $\leq 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önig Lemma). The result of our analysis provides the first effective (in all parameters $f, n$ and $\varepsilon$) uniform modulus of uniqueness (a concept which generalizes `strong uniqueness' studied extensively in approximation theory). Moreover, the extracted modulus has the optimal $\varepsilon$-dependency as follows from Kroo 78. The paper also describes how the uniform modulus of uniqueness can be used to compute the best $L_1$-approximations of a fixed $f \in C[0,1]$ with arbitrary precision, and includes some remarks on the case of best Chebycheff approximation

Available as PostScript, PDF, DVI.


Last modified: 2003-06-08 by webmaster.