Rate of convergence of the discrete Pólya algorithm (Q583535): Difference between revisions

In approximating an arbitrary point of \({\mathbb{R}}^ n\) from a fixed subspace, it is known that the net of \(\ell^ p\)-best approximations, \(1\leq p<\infty\), converges to the strict uniform best approximation. The authors show that this convergence occurs at a rate no worse than 1/p. The result is sharp; it is shown by an example that this rate may be achieved. The strict uniform approximation is unique. Thus, an application of Pólya's algorithm (i.e., the calculation of \(\lim_{p\to \infty}x_ p)\) would enable us to compute the ``best'' of the \(\ell^{\infty}\)-best approximants. The need to estimate this limit naturally leads to questions regarding the rate of convergence of \(x_ p\). The purpose of this paper is to obtain a convergence estimate without assuming that there is a unique best uniform approximation; in this context linear programming may fail to return the strict approximation. This rate estimate could then be used in extrapolatory schemes in general discrete approximation problems.