Abstract
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 Lp 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∞ approximation. However, they hold for the Skorohodmetric, which we argue to be more appropriate than L∞ for dealing with discontinuous functions. Numerical test results and possible extensions are also discussed.
Original language | English |
---|---|
Pages (from-to) | 227-248 |
Number of pages | 22 |
Journal | Journal of Fixed Point Theory and Applications |
Volume | 6 |
Issue number | 2 |
DOIs | |
State | Published - Dec 2009 |
Bibliographical note
Funding Information:The second author was partially supported by the National Sciences Foundation under Grant DMS-0608727.
Keywords
- Adaptive algorithms
- Function approximation and integration
- Sampling
- Singularities
ASJC Scopus subject areas
- Modeling and Simulation
- Geometry and Topology
- Applied Mathematics