BIT Numerical Mathematics Прикладная математика
Construction of optimal algorithms for function approximation in Gaussian Sobolev spaces
Аннотация
Abstract This paper studies function approximation in Gaussian Sobolev spaces over the real line and measures the error in a Gaussian-weighted $$L^p$$ L p -norm. We construct two linear approximation algorithms using n function evaluations that achieve the optimal or almost optimal rate of worst-case convergence in a Gaussian Sobolev space of order $$\alpha $$ α . The first algorithm is based on scaled trigonometric interpolation and achieves the optimal rate $$n^{-\alpha }$$ n - α up to a logarithmic factor. This algorithm can be constructed in almost-linear time with the fast Fourier transform. The second algorithm is more complicated, being based on spline smoothing, but attains the optimal rate $$n^{-\alpha }$$ n - α .