Насколько полезны адаптивные алгоритмы для аппроксимации функций?
Просмотры: 0 / Загрузок PDF: 0
Ключевые слова:
Приближение функций, адаптивные алгоритмы, интерполяция Лагранжа, асимптотические константы, кусочная гладкостьАннотация
Адаптивные алгоритмы широко используются для решения численных задач. Классическими примерами являются метод Ньютона для нахождения нулей функций и адаптивные квадратурные формулы для численного интегрирования. В настоящей статье рассматриваются отдельные результаты, касающиеся применения адаптивных алгоритмов к задаче приближения скалярных функций. Допустимые алгоритмы используют значения функции, которые могут выбираться адаптивно или неадаптивно. Рассматриваются постановки в наихудшем и в асимптотическом случаях в рамках теории информационной сложности. В обеих постановках адаптивные алгоритмы не обеспечивают более высоких скоростей сходимости по сравнению с неадаптивными алгоритмами для гладких функций. Преимущества адаптации проявляются при приближении кусочно-гладких функций и оптимизации асимптотических констант. В частности, для кусочно-гладких функций адаптация необходима для восстановления оптимальной скорости сходимости, достигаемой в случае гладких функций. Адаптивные алгоритмы также позволяют существенно улучшить асимптотические константы по сравнению с неадаптивными алгоритмами, особенно для функций, соответствующие производные которых резко изменяются.
Библиографические ссылки
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}.)
