×

Fast and stable approximation of analytic functions from equispaced samples via polynomial frames. (English) Zbl 1528.41009

Summary: We consider approximating analytic functions on the interval \([-1,1]\) from their values at a set of \(m+1\) equispaced nodes. A result of Platte, Trefethen & Kuijlaars states that fast and stable approximation from equispaced samples is generally impossible. In particular, any method that converges exponentially fast must also be exponentially ill-conditioned. We prove a positive counterpart to this ‘impossibility’ theorem. Our ‘possibility’ theorem shows that there is a well-conditioned method that provides exponential decay of the error down to a finite, but user-controlled tolerance \(\varepsilon>0\), which in practice can be chosen close to machine epsilon. The method is known as polynomial frame approximation or polynomial extensions. It uses algebraic polynomials of degree \(n\) on an extended interval \([-\gamma,\gamma],\gamma>1\), to construct an approximation on \([-1,1]\) via a SVD-regularized least-squares fit. A key step in the proof of our main theorem is a new result on the maximal behaviour of a polynomial of degree \(n\) on \([-1,1]\) that is simultaneously bounded by one at a set of \(m+1\) equispaced nodes in \([-1,1]\) and \(1/\varepsilon\) on the extended interval \([-\gamma,\gamma]\). We show that linear oversampling, i.e. \(m=cn\log(1/\varepsilon)/\sqrt{\gamma^2-1}\), is sufficient for uniform boundedness of any such polynomial on \([-1,1]\). This result aside, we also prove an extended impossibility theorem, which shows that such a possibility theorem (and consequently the method of polynomial frame approximation) is essentially optimal.

MSC:

41A10 Approximation by polynomials
41A25 Rate of convergence, degree of approximation
41A17 Inequalities in approximation (Bernstein, Jackson, Nikol’skiĭ-type inequalities)

References:

[1] Adcock, B.; Brugiapaglia, S.; Webster, CG, Sparse Polynomial Approximation of High-Dimensional Functions (2022), Philadelphia: Society for Industrial and Applied Mathematics, Philadelphia · Zbl 07515822 · doi:10.1137/1.9781611976885
[2] Adcock, B.; Hansen, AC, Stable reconstructions in Hilbert spaces and the resolution of the Gibbs phenomenon, Appl. Comput. Harmon. Anal., 32, 3, 357-388 (2012) · Zbl 1245.94058 · doi:10.1016/j.acha.2011.07.004
[3] Adcock, B.; Hansen, AC, Generalized sampling and the stable and accurate reconstruction of piecewise analytic functions from their Fourier coefficients, Math. Comput., 84, 237-270 (2014) · Zbl 1312.41010 · doi:10.1090/S0025-5718-2014-02860-3
[4] Adcock, B.; Hansen, AC; Shadrin, A., A stability barrier for reconstructions from Fourier samples, SIAM J. Numer. Anal., 52, 1, 125-139 (2014) · Zbl 1296.41003 · doi:10.1137/130908221
[5] Adcock, B.; Huybrechs, D., On the resolution power of Fourier extensions for oscillatory functions, J. Comput. Appl. Math., 260, 312-336 (2014) · Zbl 1293.65177 · doi:10.1016/j.cam.2013.09.069
[6] Adcock, B.; Huybrechs, D., Frames and numerical approximation, SIAM Rev., 61, 3, 443-473 (2019) · Zbl 1421.42015 · doi:10.1137/17M1114697
[7] Adcock, B.; Huybrechs, D., Approximating smooth, multivariate functions on irregular domains, Forum Math. Sigma, 8 (2020) · Zbl 1440.41006 · doi:10.1017/fms.2020.23
[8] Adcock, B.; Huybrechs, D., Frames and numerical approximation II: generalized sampling, J. Fourier Anal. Appl., 26, 6, 87 (2020) · Zbl 1462.42048 · doi:10.1007/s00041-020-09796-w
[9] Adcock, B.; Huybrechs, D.; Martín-Vaquero, J., On the numerical stability of Fourier extensions, Found. Comput. Math., 14, 4, 635-687 (2014) · Zbl 1298.65198 · doi:10.1007/s10208-013-9158-8
[10] Adcock, B.; Platte, R., A mapped polynomial method for high-accuracy approximations on arbitrary grids, SIAM J. Numer. Anal., 54, 4, 2256-2281 (2016) · Zbl 1342.65088 · doi:10.1137/15M1023853
[11] Adcock, B.; Platte, R.; Shadrin, A., Optimal sampling rates for approximating analytic functions from pointwise samples, IMA J. Numer. Anal., 39, 3, 1360-1390 (2019) · Zbl 1462.65024 · doi:10.1093/imanum/dry024
[12] Adcock, B.; Ruan, J., Parameter selection and numerical approximation properties of Fourier extensions from fixed data, J. Comput. Phys., 273, 453-471 (2014) · Zbl 1351.42034 · doi:10.1016/j.jcp.2014.05.036
[13] Boyd, J.P.: Chebyshev and Fourier Spectral Methods. Springer-Verlag (1989) · Zbl 0681.65079
[14] Boyd, JP, A comparison of numerical algorithms for Fourier Extension of the first, second, and third kinds, J. Comput. Phys., 178, 118-160 (2002) · Zbl 0999.65132 · doi:10.1006/jcph.2002.7023
[15] Boyd, JP; Ong, JR, Exponentially-convergent strategies for defeating the Runge phenomenon for the approximation of non-periodic functions, I. Single-Interval Schemes Commun. Comput. Phys., 5, 2-4, 484-497 (2009) · Zbl 1364.65025
[16] Bruno, OP; Han, Y.; Pohlman, MM, Accurate, high-order representation of complex three-dimensional surfaces via Fourier continuation analysis, J. Comput. Phys., 227, 2, 1094-1125 (2007) · Zbl 1128.65017 · doi:10.1016/j.jcp.2007.08.029
[17] Bullen, PS, Dictionary of Inequalities. Monographs and Research Notes in Mathematics (2015), Boca Raton: CRC Press, Boca Raton · Zbl 1316.26017 · doi:10.1201/b18548
[18] Cheney, EW, Introduction to Approximation Theory (1982), Providence: AMS Chelsea Publishing, Providence · Zbl 0535.41001
[19] Christensen, O., An Introduction to Frames and Riesz Bases. Applied and Numerical Harmonic Analysis (2016), Basel: Birkhäuser, Basel · Zbl 1348.42033
[20] Coppé, V.; Huybrechs, D.; Matthysen, R.; Webb, M., The AZ algorithm for least squares systems with a known incomplete generalized inverse, SIAM J. Mat. Anal. Appl., 41, 3, 1237-1259 (2020) · Zbl 1461.65058 · doi:10.1137/19M1306385
[21] Coppersmith, D.; Rivlin, TJ, The growth of polynomials bounded at equally spaced points, SIAM J. Math. Anal., 23, 970-983 (1992) · Zbl 0769.26003 · doi:10.1137/0523054
[22] Don, W-S; Solomonoff, A., Accuracy enhancement for higher derivatives using Chebyshev collocation and a mapping technique, SIAM J. Sci. Comput., 18, 1040-1055 (1997) · Zbl 0906.65019 · doi:10.1137/S1064827594274607
[23] Geronimo, JS; Liechty, K., The Fourier extension method and discrete orthogonal polynomials on an arc of the circle, Adv. Math., 365 (2020) · Zbl 07184866 · doi:10.1016/j.aim.2020.107064
[24] Gottlieb, D.; Orszag, SA, Numerical Analysis of Spectral Methods: Theory and Applications (1977), Philadelphia: Society for Industrial and Applied Mathematics, Philadelphia · Zbl 0412.65058 · doi:10.1137/1.9781611970425
[25] Hale, N.; Trefethen, LN, New quadrature formulas from conformal maps, SIAM J. Numer. Anal., 46, 2, 930-948 (2008) · Zbl 1173.65020 · doi:10.1137/07068607X
[26] Huybrechs, D., On the Fourier extension of non-periodic functions, SIAM J. Numer. Anal., 47, 6, 4326-4355 (2010) · Zbl 1209.65153 · doi:10.1137/090752456
[27] Konyagin, S., Shadrin, A.: On stable reconstruction of analytic functions from selected Fourier coefficients. In preparation (2021)
[28] Kosloff, D.; Tal-Ezer, H., A modified Chebyshev pseudospectral method with an \(\cal{O} (N^{-1})\) time step restriction, J. Comput. Phys., 104, 457-469 (1993) · Zbl 0781.65082 · doi:10.1006/jcph.1993.1044
[29] Lyon, M., A fast algorithm for Fourier continuation, SIAM J. Sci. Comput., 33, 6, 3241-3260 (2012) · Zbl 1255.65253 · doi:10.1137/11082436X
[30] Matthysen, R.; Huybrechs, D., Fast algorithms for the computation of Fourier extensions of arbitrary length, SIAM J. Sci. Comput., 38, 2, A899-A922 (2016) · Zbl 1337.65181 · doi:10.1137/15M1030923
[31] Matthysen, R.; Huybrechs, D., Function approximation on arbitrary domains using Fourier frames, SIAM J. Numer. Anal., 56, 3, 1360-1385 (2018) · Zbl 1404.33019 · doi:10.1137/17M1134809
[32] Micchelli, CA; Rivlin, TJ; Turner, PR, Lectures on optimal recovery, Numerical Analysis Lancaster 1984. Lecture Notes in Mathematics (1985), Berlin: Springer, Berlin
[33] Pasquetti, R.; Elghaoui, M., A spectral embedding method applied to the advection-diffusion equation, J. Comput. Phys., 125, 464-476 (1996) · Zbl 0852.65086 · doi:10.1006/jcph.1996.0108
[34] Platte, R.; Trefethen, LN; Kuijlaars, A., Impossibility of fast stable approximation of analytic functions from equispaced samples, SIAM Rev., 53, 2, 308-318 (2011) · Zbl 1247.41001 · doi:10.1137/090774707
[35] Schaeffer, AC; Duffin, RJ, On some inequalities of for derivatives of S. Bernstein and W. Markoff polynomials, Bull. Am. Math. Soc., 44, 4, 289-297 (1938) · Zbl 0018.39503 · doi:10.1090/S0002-9904-1938-06747-X
[36] Shadrin, A.: Twelve proofs of the Markov inequality. In: Approximation Theory: A Volume Dedicated to Borislav Bojanov, pp. 233-298. Professor Marin Drinov Academic Publishing House, Sofia (2004)
[37] Temlyakov, V., Multivariate Approximation. Cambridge Monographs on Applied and Computational Mathematics (2018), Cambridge: Cambridge University Press, Cambridge · Zbl 1428.41001
[38] Temlyakov, VN, On approximate recovery of functions with bounded mixed derivative, J. Complex., 9, 1, 41-59 (1993) · Zbl 0784.41027 · doi:10.1006/jcom.1993.1004
[39] Trefethen, LN, Approximation Theory and Approximation Practice (2013), Philadelphia: Society for Industrial and Applied Mathematics, Philadelphia · Zbl 1264.41001
[40] Webb, M.; Coppé, V.; Huybrechs, D., Pointwise and uniform convergence of Fourier extensions, Constr. Approx., 52, 139-175 (2020) · Zbl 1444.42003 · doi:10.1007/s00365-019-09486-x
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.