{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T16:19:32Z","timestamp":1776788372138,"version":"3.51.2"},"reference-count":33,"publisher":"American Mathematical Society (AMS)","issue":"264","license":[{"start":{"date-parts":[[2009,4,24]],"date-time":"2009-04-24T00:00:00Z","timestamp":1240531200000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"

\n 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\n \n \n \n \n F<\/mml:mi>\n r<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msubsup>\n F_r^1<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n be the class of scalar functions\n \n \n \n \n f<\/mml:mi>\n :<\/mml:mo>\n [<\/mml:mo>\n 0<\/mml:mn>\n ,<\/mml:mo>\n T<\/mml:mi>\n ]<\/mml:mo>\n \n \u2192\n \n <\/mml:mo>\n \n R<\/mml:mi>\n <\/mml:mrow>\n <\/mml:mrow>\n f:[0,T]\\to \\mathbb {R}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n whose derivatives of order up to\n \n \n \n r<\/mml:mi>\n r<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n are continuous at any point except for one unknown\n singular<\/italic>\n point. We provide an adaptive algorithm\n \n \n \n \n \n A<\/mml:mi>\n <\/mml:mrow>\n n<\/mml:mi>\n \n ad<\/mml:mtext>\n <\/mml:mrow>\n <\/mml:msubsup>\n \\mathcal {A}_n^\\textrm {ad}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n that uses at most\n \n \n \n n<\/mml:mi>\n n<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n samples of\n \n \n \n f<\/mml:mi>\n f<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n and whose\n worst case<\/italic>\n \n \n \n \n L<\/mml:mi>\n p<\/mml:mi>\n <\/mml:msup>\n L^p<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n error (\n \n \n \n \n 1<\/mml:mn>\n \n \u2264\n \n <\/mml:mo>\n p<\/mml:mi>\n ><\/mml:mo>\n \n \u221e\n \n <\/mml:mi>\n <\/mml:mrow>\n 1\\le p>\\infty<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n ) with respect to \u2018reasonable\u2019 function classes\n \n \n \n \n \n \n F<\/mml:mi>\n <\/mml:mrow>\n r<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msubsup>\n \n \u2282\n \n <\/mml:mo>\n \n F<\/mml:mi>\n r<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msubsup>\n <\/mml:mrow>\n \\mathcal {F}_r^1\\subset F_r^1<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n is proportional to\n \n \n \n \n n<\/mml:mi>\n \n \n \u2212\n \n <\/mml:mo>\n r<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n n^{-r}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . On the other hand, the worst case error of any nonadaptive algorithm that uses\n \n \n \n n<\/mml:mi>\n n<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n samples is at best proportional to\n \n \n \n \n n<\/mml:mi>\n \n \n \u2212\n \n <\/mml:mo>\n 1<\/mml:mn>\n \n \/<\/mml:mo>\n <\/mml:mrow>\n p<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n n^{-1\/p}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n .\n <\/p>\n

\n The restriction to only one singularity is necessary for superiority of adaption in the worst case setting. Fortunately, adaption regains its power in the\n asymptotic setting<\/italic>\n even for a very general class\n \n \n \n \n F<\/mml:mi>\n r<\/mml:mi>\n \n \u221e\n \n <\/mml:mi>\n <\/mml:msubsup>\n F_r^\\infty<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n consisting of piecewise\n \n \n \n \n C<\/mml:mi>\n \n r<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n C^{r}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n -smooth functions, each having a finite number of singular points. For any\n \n \n \n \n f<\/mml:mi>\n \n \u2208\n \n <\/mml:mo>\n \n F<\/mml:mi>\n r<\/mml:mi>\n \n \u221e\n \n <\/mml:mi>\n <\/mml:msubsup>\n <\/mml:mrow>\n f\\in F_r^\\infty<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n our adaptive algorithm approximates\n \n \n \n f<\/mml:mi>\n f<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n with error converging to zero at least as fast as\n \n \n \n \n n<\/mml:mi>\n \n \n \u2212\n \n <\/mml:mo>\n r<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n n^{-r}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n . We also prove that the rate of convergence for nonadaptive methods cannot be better than\n \n \n \n \n n<\/mml:mi>\n \n \n \u2212\n \n <\/mml:mo>\n 1<\/mml:mn>\n \n \/<\/mml:mo>\n <\/mml:mrow>\n p<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n n^{-1\/p}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , i.e., is much slower.\n <\/p>\n

\n The results mentioned above do not hold if the errors are measured in the\n \n \n \n \n L<\/mml:mi>\n \n \u221e\n \n <\/mml:mi>\n <\/mml:msup>\n L^\\infty<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n norm, since no algorithm produces small\n \n \n \n \n L<\/mml:mi>\n \n \u221e\n \n <\/mml:mi>\n <\/mml:msup>\n L^\\infty<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n errors for functions with unknown discontinuities. However, we strongly believe that the\n \n \n \n \n L<\/mml:mi>\n \n \u221e\n \n <\/mml:mi>\n <\/mml:msup>\n L^\\infty<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n norm is inappropriate when dealing with singular functions and that the\n Skorohod metric<\/italic>\n 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\n \n \n \n \n \n F<\/mml:mi>\n <\/mml:mrow>\n r<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msubsup>\n \\mathcal {F}_r^1<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n equals\n \n \n \n \n \n \u0398\n \n <\/mml:mi>\n (<\/mml:mo>\n \n n<\/mml:mi>\n \n \n \u2212\n \n <\/mml:mo>\n r<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n \\Theta (n^{-r})<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n , and the convergence in the asymptotic setting for\n \n \n \n \n F<\/mml:mi>\n r<\/mml:mi>\n \n \u221e\n \n <\/mml:mi>\n <\/mml:msubsup>\n F_r^\\infty<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n is\n \n \n \n \n n<\/mml:mi>\n \n \n \u2212\n \n <\/mml:mo>\n r<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n n^{-r}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n .\n <\/p>\n

Numerical results confirm the theoretical properties of our algorithms.<\/p>","DOI":"10.1090\/s0025-5718-08-02103-0","type":"journal-article","created":{"date-parts":[[2008,7,25]],"date-time":"2008-07-25T12:55:42Z","timestamp":1216990542000},"page":"2309-2338","source":"Crossref","is-referenced-by-count":21,"title":["The power of adaption for approximating functions with singularities"],"prefix":"10.1090","volume":"77","author":[{"given":"Leszek","family":"Plaskota","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Grzegorz","family":"Wasilkowski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yaxi","family":"Zhao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[2008,4,24]]},"reference":[{"issue":"1","key":"1","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1137\/S0036142903426245","article-title":"Interpolation and approximation of piecewise smooth functions","volume":"43","author":"Arandiga, Francesc","year":"2005","journal-title":"SIAM J. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0036-1429","issn-type":"print"},{"key":"2","isbn-type":"print","volume-title":"An introduction to numerical analysis","author":"Atkinson, Kendall E.","year":"1989","ISBN":"https:\/\/id.crossref.org\/isbn\/0471624896","edition":"2"},{"key":"3","first-page":"1014","article-title":"The optimality of linear operator approximation methods on convex function classes","volume":"11","author":"Bahvalov, N. S.","year":"1971","journal-title":"\\v{Z}. Vy\\v{c}isl. Mat i Mat. Fiz.","ISSN":"https:\/\/id.crossref.org\/issn\/0044-4669","issn-type":"print"},{"key":"4","volume-title":"Convergence of probability measures","author":"Billingsley, Patrick","year":"1968"},{"issue":"2","key":"5","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1002\/cpa.10116","article-title":"New tight frames of curvelets and optimal representations of objects with piecewise \ud835\udc36\u00b2 singularities","volume":"57","author":"Cand\u00e8s, Emmanuel J.","year":"2004","journal-title":"Comm. Pure Appl. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0010-3640","issn-type":"print"},{"key":"6","series-title":"Computer Science and Applied Mathematics","volume-title":"Methods of numerical integration","author":"Davis, Philip J.","year":"1975"},{"key":"7","doi-asserted-by":"crossref","unstructured":"C. de Boor, CADRE: An algorithm for numerical quadrature, Mathematical Software, pp. 201\u2013209, Academic Press, New York, 1971.","DOI":"10.1016\/B978-0-12-587250-8.50015-1"},{"key":"8","series-title":"CBMS-NSF Regional Conference Series in Applied Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970104","volume-title":"Ten lectures on wavelets","volume":"61","author":"Daubechies, Ingrid","year":"1992","ISBN":"https:\/\/id.crossref.org\/isbn\/0898712742"},{"issue":"6","key":"9","doi-asserted-by":"publisher","first-page":"2435","DOI":"10.1109\/18.720544","article-title":"Data compression and harmonic analysis","volume":"44","author":"Donoho, David L.","year":"1998","journal-title":"IEEE Trans. Inform. Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"},{"issue":"2","key":"10","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1080\/00036818008839292","article-title":"Optimal sequential and nonsequential procedures for evaluating a functional","volume":"10","author":"Gal, Shmuel","year":"1980","journal-title":"Applicable Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0003-6811","issn-type":"print"},{"key":"11","first-page":"239","article-title":"On the Skorohod convergence","volume":"1","author":"Kolmogorov, A. N.","year":"1956","journal-title":"Teor. Veroyatnost. i Primenen.","ISSN":"https:\/\/id.crossref.org\/issn\/0040-361X","issn-type":"print"},{"key":"12","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611971460","volume-title":"Computational integration","author":"Krommer, Arnold R.","year":"1998","ISBN":"https:\/\/id.crossref.org\/isbn\/0898713749"},{"key":"13","doi-asserted-by":"publisher","first-page":"483","DOI":"10.1145\/321526.321537","article-title":"Notes on the adaptive Simpson quadrature routine","volume":"16","author":"Lyness, J. N.","year":"1969","journal-title":"J. Assoc. Comput. Mach.","ISSN":"https:\/\/id.crossref.org\/issn\/0004-5411","issn-type":"print"},{"key":"14","doi-asserted-by":"crossref","unstructured":"W. M. McKeeman, Algorithm 145, adaptive numerical integration by Simpson\u2019s rule, Comm. ACM 5 (1962), pp. 604.","DOI":"10.1145\/355580.369102"},{"key":"15","isbn-type":"print","first-page":"287","article-title":"Polynomial frames: a fast tour","author":"Mhaskar, H. N.","year":"2005","ISBN":"https:\/\/id.crossref.org\/isbn\/0972848258"},{"key":"16","series-title":"Lecture Notes in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0079792","volume-title":"Deterministic and stochastic error bounds in numerical analysis","volume":"1349","author":"Novak, Erich","year":"1988","ISBN":"https:\/\/id.crossref.org\/isbn\/3540503684"},{"issue":"3","key":"17","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1006\/jcom.1996.0015","article-title":"On the power of adaption","volume":"12","author":"Novak, Erich","year":"1996","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"key":"18","series-title":"Probability and Mathematical Statistics, No. 3","volume-title":"Probability measures on metric spaces","author":"Parthasarathy, K. R.","year":"1967"},{"key":"19","series-title":"Springer Series in Computational Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-61786-7","volume-title":"QUADPACK","volume":"1","author":"Piessens, Robert","year":"1983","ISBN":"https:\/\/id.crossref.org\/isbn\/3540125531"},{"key":"20","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511600814","volume-title":"Noisy information and computational complexity","author":"Plaskota, Leszek","year":"1996","ISBN":"https:\/\/id.crossref.org\/isbn\/0521553687"},{"issue":"1","key":"21","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1007\/s00211-005-0640-3","article-title":"Adaption allows efficient integration of functions with unknown singularities","volume":"102","author":"Plaskota, Leszek","year":"2005","journal-title":"Numer. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0029-599X","issn-type":"print"},{"key":"22","series-title":"International Series in Pure and Applied Mathematics","isbn-type":"print","volume-title":"A first course in numerical analysis","author":"Ralston, Anthony","year":"1978","ISBN":"https:\/\/id.crossref.org\/isbn\/0070511586","edition":"2"},{"key":"23","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1145\/321864.321870","article-title":"A metalgorithm for adaptive quadrature","volume":"22","author":"Rice, John R.","year":"1975","journal-title":"J. Assoc. Comput. Mach.","ISSN":"https:\/\/id.crossref.org\/issn\/0004-5411","issn-type":"print"},{"key":"24","series-title":"Lecture Notes in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0103934","volume-title":"Average-case analysis of numerical problems","volume":"1733","author":"Ritter, Klaus","year":"2000","ISBN":"https:\/\/id.crossref.org\/isbn\/3540674497"},{"key":"25","isbn-type":"print","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780195106909.001.0001","volume-title":"Optimal solution of nonlinear equations","author":"Sikorski, Krzysztof A.","year":"2001","ISBN":"https:\/\/id.crossref.org\/isbn\/0195106903"},{"key":"26","first-page":"289","article-title":"Limit theorems for stochastic processes","volume":"1","author":"Skorohod, A. V.","year":"1956","journal-title":"Teor. Veroyatnost. i Primenen.","ISSN":"https:\/\/id.crossref.org\/issn\/0040-361X","issn-type":"print"},{"key":"27","unstructured":"G. M. Trojan, Asymptotic Setting for Linear Problems, unpublished Ph.D. dissertation, 1980. (See also [28, Sect. 2, Chap. 10].)"},{"key":"28","series-title":"Computer Science and Scientific Computing","isbn-type":"print","volume-title":"Information-based complexity","author":"Traub, J. F.","year":"1988","ISBN":"https:\/\/id.crossref.org\/isbn\/0126975450"},{"key":"29","series-title":"Lezioni Lincee. [Lincei Lectures]","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1080\/16073606.1997.9631861","volume-title":"Complexity and information","author":"Traub, J. F.","year":"1998","ISBN":"https:\/\/id.crossref.org\/isbn\/0521485061"},{"key":"30","series-title":"ACM Monograph Series","isbn-type":"print","volume-title":"A general theory of optimal algorithms","author":"Traub, Joe Fred","year":"1980","ISBN":"https:\/\/id.crossref.org\/isbn\/0126976503"},{"issue":"3","key":"31","doi-asserted-by":"publisher","first-page":"204","DOI":"10.1016\/0885-064X(86)90002-6","article-title":"Information of varying cardinality","volume":"2","author":"Wasilkowski, G. W.","year":"1986","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"key":"32","series-title":"CBMS-NSF Regional Conference Series in Applied Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970128","volume-title":"Spline models for observational data","volume":"59","author":"Wahba, Grace","year":"1990","ISBN":"https:\/\/id.crossref.org\/isbn\/0898712440"},{"key":"33","series-title":"Oxford Mathematical Monographs","isbn-type":"print","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198535898.001.0001","volume-title":"The computational complexity of differential and integral equations","author":"Werschulz, Arthur G.","year":"1991","ISBN":"https:\/\/id.crossref.org\/isbn\/0198535899"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2008-77-264\/S0025-5718-08-02103-0\/S0025-5718-08-02103-0.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2008-77-264\/S0025-5718-08-02103-0\/S0025-5718-08-02103-0.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T15:29:58Z","timestamp":1776785398000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2008-77-264\/S0025-5718-08-02103-0\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,4,24]]},"references-count":33,"journal-issue":{"issue":"264","published-print":{"date-parts":[[2008,10]]}},"alternative-id":["S0025-5718-08-02103-0"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-08-02103-0","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2008,4,24]]}}}