Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



The power of adaption for approximating functions with singularities

Authors: Leszek Plaskota, Grzegorz W. Wasilkowski and Yaxi Zhao
Journal: Math. Comp. 77 (2008), 2309-2338
MSC (2000): Primary 65Y20, 65D05, 41A10, 41A25
Published electronically: April 24, 2008
MathSciNet review: 2429887
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Consider approximating functions based on a finite number of their samples. We show that adaptive algorithms are much more powerful than nonadaptive ones when dealing with piecewise smooth functions. More specifically, let $ F_r^1$ be the class of scalar functions $ f:[0,T]\to\mathbb{R}$ whose derivatives of order up to $ r$ are continuous at any point except for one unknown singular point. We provide an adaptive algorithm $ \mathcal{A}_n^{\rm ad}$ that uses at most $ n$ samples of $ f$ and whose worst case $ L^p$ error ( $ 1\le p<\infty$) with respect to `reasonable' function classes $ \mathcal{F}_r^1\subset F_r^1$ is proportional to $ n^{-r}$. On the other hand, the worst case error of any nonadaptive algorithm that uses $ n$ samples is at best proportional to $ n^{-1/p}$.

The restriction to only one singularity is necessary for superiority of adaption in the worst case setting. Fortunately, adaption regains its power in the asymptotic setting even for a very general class $ F_r^\infty$ consisting of piecewise $ C^{r}$-smooth functions, each having a finite number of singular points. For any $ f\in F_r^\infty$ our adaptive algorithm approximates $ f$ with error converging to zero at least as fast as $ n^{-r}$. We also prove that the rate of convergence for nonadaptive methods cannot be better than $ n^{-1/p}$, i.e., is much slower.

The results mentioned above do not hold if the errors are measured in the $ L^\infty$ norm, since no algorithm produces small $ L^\infty$ errors for functions with unknown discontinuities. However, we strongly believe that the $ L^\infty$ norm is inappropriate when dealing with singular functions and that the Skorohod metric should be used instead. We show that our adaptive algorithm retains its positive properties when the approximation error is measured in the Skorohod metric. That is, the worst case error with respect to $ \mathcal{F}_r^1$ equals $ \Theta(n^{-r})$, and the convergence in the asymptotic setting for $ F_r^\infty$ is $ n^{-r}$.

Numerical results confirm the theoretical properties of our algorithms.

References [Enhancements On Off] (What's this?)

  • 1. F. Arandiga, A. Cohen, R. Donat, and N. Dyn, Interpolation and approximation of piecewise smooth functions, SIAM J. of Numerical Analysis 43 (2005), pp. 41-57. MR 2177955 (2006h:41002)
  • 2. K. E. Atkinson, An Introduction to Numerical Analysis, 2nd ed., Wiley, New York, 1989. MR 1007135 (90m:65001)
  • 3. N. S. Bakhvalov, On the optimality of linear methods for the operator approximation in convex classes of functions (in Russian), Zh. Vychisl. Mat. Mat. Fiz. 11 (1971), pp. 1014-1018. MR 0290523 (44:7703)
  • 4. P. Billingsley, Convergence of Probability Measures, Wiley, New York, 1968. MR 0233396 (38:1718)
  • 5. E.J. Candès and D.L. Donoho, New tight frames of curvelets and optimal representations of objects with piecewise $ C^2$ singularities, Comm. Pure Appl. Math. 57 (2004), pp. 219-266. MR 2012649 (2004k:42052)
  • 6. P. J. Davis and P. Rabinowitz, Methods of Numerical Integration, Academic Press, New York, 1975. MR 0448814 (56:7119)
  • 7. C. de Boor, CADRE: An algorithm for numerical quadrature, Mathematical Software, pp. 201-209, Academic Press, New York, 1971.
  • 8. I. Daubechies, Ten lectures on wavelets, SIAM, Philadelphia, 1992. MR 1162107 (93e:42045)
  • 9. D.L. Donoho, M. Vetterli, R.A. DeVore, and I. Daubechies, Data compression and harmonic analysis, IEEE Trans. Inform. Theory 44 (1998), pp. 2435-2476. MR 1658775 (99i:94028)
  • 10. S. Gal and C. A. Micchelli, Optimal sequential and non-sequential procedures for evaluating a functional, Appl. Anal. 10 (1980), pp. 105-120. MR 575536 (82c:65033)
  • 11. A. N. Kolmogorov, On Skorohod convergence, Theor. Prob. Appl. 1 (1956) (in Russian). MR 0085638 (19:69i)
  • 12. A. R. Krommer and C. W. Ueberhuber, Computational Integration, SIAM, Philadelphia, 1998. MR 1625683 (99g:65027)
  • 13. J. M. Lyness, Notes on the adaptive Simpson quadrature routine, J. Assoc. Comput. Mach. 16 (1969), pp. 483-495. MR 0240981 (39:2326)
  • 14. W. M. McKeeman, Algorithm 145, adaptive numerical integration by Simpson's rule, Comm. ACM 5 (1962), pp. 604.
  • 15. H. N. Mhaskar and J. Prestin, Polynomial frames: a fast tour, in Approximation Theory XI, Gatlinburg 2004 (Eds. C.K. Chui, M. Neamtu, L.L. Schumaker), pp. 287-318, Nashboro Press, Brentwood, TN, 2005 MR 2126687 (2005k:42087)
  • 16. E. Novak, Deterministic and Stochastic Error Bounds in Numerical Analysis, Springer-Verlag, Berlin, 1988. MR 971255 (90a:65004)
  • 17. E. Novak, On the power of adaption, J. Complexity 12 (1996), pp. 199-238. MR 1408328 (97g:65008)
  • 18. K. R. Parthasarathy, Probability Measures on Metric Spaces, Academic Press, London, 1967. MR 0226684 (37:2271)
  • 19. R. Piessens, E. deDoncker-Kapenga, C. Überhuber, and D. Kahaner, QUADPACK: A Subroutine Package for Automatic Integration, Springer Verlag, New York, 1983. MR 712135 (85b:65022)
  • 20. L. Plaskota, Noisy Information and Computational Complexity, Cambridge University Press, Cambridge, 1996. MR 1446005 (99b:65189)
  • 21. L. Plaskota and G. W. Wasilkowski, Adaption allows efficient integration of functions with unknown singularities, Numerische Mathematik 102 (2005), pp. 123-144. MR 2206675 (2006k:65066)
  • 22. A. Ralston and P. Rabinowitz, A First Course in Numerical Analysis, 2nd ed., McGraw-Hill, New York, 1978. MR 0494814 (58:13599)
  • 23. J. R. Rice, A metalgorithm for adaptive quadrature, J. Assoc. Comput. Mach. 22 (1975), pp. 61-82. MR 0483327 (58:3340)
  • 24. K. Ritter, Average-Case Analysis of Numerical Problems, Springer-Verlag, Berlin, 2000. MR 1763973 (2001i:65001)
  • 25. K. Sikorski, Optimal Solution of Nonlinear Equations, Oxford Press, Oxford, 2000. MR 1827804 (2002h:65002)
  • 26. A. V. Skorohod, Limit theorem for stochastic processes, Theory Prob. Appl. 1 (1956), pp. 261-290. MR 0084897 (18:943c)
  • 27. G. M. Trojan, Asymptotic Setting for Linear Problems, unpublished Ph.D. dissertation, 1980. (See also [28, Sect. 2, Chap. 10].)
  • 28. J. F. Traub, G. W. Wasilkowski and H. Woźniakowski, Information-Based Complexity, Academic Press, New York, 1988. MR 958691 (90f:68085)
  • 29. J. F. Traub and A. G. Werschulz, Complexity and Information, Cambridge University Press, Cambridge, 1998. MR 1692462 (2000m:65170)
  • 30. J. F. Traub and H. Woźniakowski, A General Theory of Optimal Algorithms, Academic Press, New York, 1980. MR 584446 (84m:68041)
  • 31. G. W. Wasilkowski, Information of varying cardinality, J. Complexity 1 (1986), pp. 107-117. MR 922813 (88m:65099)
  • 32. G. Wahba, Spline Models for Observational Data, SIAM, Philadelphia, 1990. MR 1045442 (91g:62028)
  • 33. A. G. Werschulz, The Computational Complexity of Differential and Integral Equations, Oxford University Press, Oxford, 1991. MR 1144521 (93a:68061)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 65Y20, 65D05, 41A10, 41A25

Retrieve articles in all journals with MSC (2000): 65Y20, 65D05, 41A10, 41A25

Additional Information

Leszek Plaskota
Affiliation: Faculty of Mathematics, Informatics, and Mechanics, University of Warsaw, Banacha 2, 02-097 Warsaw, Poland

Grzegorz W. Wasilkowski
Affiliation: Department of Computer Science, University of Kentucky, 773 Anderson Hall, Lexington, Kentucky 40506-0046

Yaxi Zhao
Affiliation: Department of Computer Science, University of Kentucky, 773 Anderson Hall, Lexington, Kentucky 40506-0046

Keywords: Function approximation, sampling, singularities, adaptive algorithms
Received by editor(s): July 24, 2007
Published electronically: April 24, 2008
Article copyright: © Copyright 2008 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society