How useful are adaptive algorithms for function approximation?
Views: 0 / PDF downloads: 0
Keywords:
function approximation, adaptive algorithms, Lagramge interpolation, asymptotic constants, piecewise smoothnessAbstract
Adaptive algorithms are widely used to solve numerical problems, with Newton's method for finding zeros and adaptive quadratures for numerical integration being prominent examples. In this paper, we review selected results concerning the application of adaptive algorithms to the problem of approximating scalar functions. Allowable algorithms utilize function values, which can be collected adaptively or nonadaptively. The worst case and asymptotic settings of \emph{information based complexity} theory are considered. In both settings, adaptive algorithms do not provide better convergence rates than nonadaptive algorithms for smooth functions. The advantage of adaption manifests itself in the approximation of piecewise smooth functions and in the optimization of asymptotic constants. In particular, for piecewise smooth functions, the use of adaption is necessary to restore the optimal convergence rate from the smooth case. Adaptive algorithms can also significantly improve the asymptotic constants compared to nonadaptive algorithms, especially for functions whose corresponding derivatives change drastically.
References
F.Arandiga, A. Cohen, R. Donat, N.Dyn, Interpolation and approximation of piecewise smooth functions,
SIAM Journal of Numerical Analysis, 43 (2006), No 1, 41--57.
N. S.Bakhvalov, On the optimality of linear methods for operator approximation in convex classes of functions,
Zh. Vychisl. Mat. Mat. Fiz., 11 (1971), No 4, 1014--1018; U.S.S.R. Comput. Math. Math. Phys., 11 (1971), No 4, 244--249.
S.Gal, C.A. Micchelli, , Optimal sequential and non-sequential procedures for evaluating a functional,
Applicable Analysis, 10 (1980), 105--120.
A.Ka{l}u{.z}a, L. Plaskota, Asymptotic analysis of adaptive Simpson quadratures for piecewise smooth functions,
Monte Carlo and Quasi-Monte Carlo, 2024, Ch. Lemieux and B. Feng eds.,
Springer Proceedings in Mathematics and Statistics, 52, Springer, 2026, 297--315.
P. M.Morkisz, L.Plaskota, Approximation of piecewise H{"o}lder functions from inexact information, Journal of Complexity, 32(2016), No 1, 122--136.
P.M. Morkisz, L.Plaskota, Complexity of approximating H{"o}lder classes from information with varying Gaussian noise,
Journal of Complexity, 60 (2020), 101497.
E.Novak, On the power of adaption, Journal of Complexity, 12(1996), 199-237.
M.Perlik, L.Plaskota, Approximation of piecewise smooth functions from information contaminated with random noise, Submitted, 2026.
R.Piessens, E.de Doncker-Kapenga, C. W. Ueberhuber, D. K.Kahaner, QUADPACK: A subroutine package for automatic integration, Springer Verlag, 1983.
L.Plaskota, Automatic integration using asymptotically optimal adaptive Simpson quadrature, Numerische Mathematik, 131(2015), 173--198.
L.Plaskota, Noisy Information and Computational Complexity, Cambridge Univ. Press, Cambridge, 1996.
L.Plaskota, P.Przyby{l}owicz, Stc{e}pie{'n}, Monte Carlo integration of $C^r$ functions with adaptive variance reduction: an asymptotic analysis, BIT Numerical Analysis, 63(2023), 1--24.
L.Plaskota, P.Samoraj, Automatic approximation using asyptotically optimal adaptive interpolation, Numerical Algorithms, 89(2021), 277--302.
L.Plaskota, G.W. Wasilkowski, Adaption allows efficient integration of functions with singularities, Numerische Mathematik, 10 (2005), 123--144.
L.Plaskota, G. W. Wasilkowski, Y.Zhao, The power of adaption for approximating functions with singularities, Mathematics of Computation, 77(2008), 2309-2338.
J. F.Traub, H.Wo'zniakowski, A General Theory of Optimal Algorithms, Academic Press, New York, 1980.
J. F.Traub, G.W. Wasilkowski, H.Wo'zniakowski, Information-Based Complexity, Academic Press, New York, 1988.
G. M.Trojan,Asymptotic setting for linear problems, manuscript (1983) (See also cite{TWW88}.)
