The power of adaptive algorithms for functions with singularities

作     者：Plaskota, Leszek Wasilkowski, Grzegorz W. 

作者机构：Univ Warsaw Fac Math Informat & Mech PL-02097 Warsaw Poland Univ Kentucky Dept Comp Sci Lexington KY 40506 USA 

出 版 物：《JOURNAL OF FIXED POINT THEORY AND APPLICATIONS》 (不动点理论与应用杂志)

年 卷 期：2009年第6卷第2期

页      面：227-248页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

基　　金：National Sciences Foundation [DMS-0608727] 

主　　题：Function approximation and integration sampling singularities adaptive algorithms 

摘      要：This is an overview of recent results on complexity and optimality of adaptive algorithms for integrating and approximating scalar piecewise r-smooth functions with unknown singular points. We provide adaptive algorithms that use at most n function samples and have the worst case errors proportional to n(-r) for functions with at most one unknown singularity. This is a tremendous improvement over nonadaptive algorithms whose worst case errors are at best proportional to n(-1) for integration and n(-1/p) for the L-p approximation problem. For functions with multiple singular points the adaptive algorithms cease to dominate the nonadaptive ones in the worst case setting. Fortunately, they regain their superiority in the asymptotic setting. Indeed, they yield convergence of order n(-r) for piecewise r-smooth functions with an arbitrary (unknown but finite) number of singularities. None of these results hold for the L-a approximation. However, they hold for the Skorohodmetric, which we argue to be more appropriate than L-a for dealing with discontinuous functions. Numerical test results and possible extensions are also discussed.