Abstract
We investigate numerical differentiation formulas on irregular centers in two or more variables that are exact for polynomials of a given order and minimize an absolute seminorm of the weight vector. Error bounds are given in terms of a growth function that carries the information about the geometry of the centers. Specific forms of weighted \(\ell _1\) and weighted least squares minimization are proposed that produce numerical differentiation formulas with particularly good performance in numerical experiments. The results are of interest in particular for meshless generalized finite difference methods as they provide a consistency error analysis for such methods.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Adams, R., Fournier, J.: Sobolev Spaces, 2nd edn. Academic Press, Amsterdam (2003)
Bauer, F.L., Stoer, J., Witzgall, C.: Absolute and monotonic norms. Numer. Math. 3(1), 257–264 (1961)
Beatson, R., Davydov, O., Levesley, J.: Error bounds for anisotropic RBF interpolation. J. Approx. Theory 162, 512–527 (2010)
Benito, J., Ureña, F., Gavete, L., Alvarez, R.: An h-adaptive method in the generalized finite differences. Comput. Methods Appl. Mech. Eng. 192(5–6), 735–759 (2003)
Caliari, M., Marchi, S.D., Vianello, M.: Bivariate polynomial interpolation on the square at new nodal sets. Appl. Math. Comput. 165(2), 261–274 (2005)
Ciarlet, P.G., Raviart, P.A.: General lagrange and hermite interpolation in RN with applications to finite element methods. Arch. Ration. Mech. Anal. 46(3), 177–199 (1972)
Conn, A.R., Scheinberg, K., Vicente, L.N.: Geometry of sample sets in derivative-free optimization: polynomial regression and underdetermined interpolation. IMA J. Numer. Anal. 28(4), 721–748 (2008)
Davydov, O.: On the approximation power of local least squares polynomials. In: Levesley, J., Anderson, I.J., Mason, J.C. (eds.) Algorithms for Approximation IV, pp. 346–353. University of Huddersfield, Huddersfield (2002)
Davydov, O.: Error bound for radial basis interpolation in terms of a growth function. In: Cohen, A., Merrien, J.L., Schumaker, L.L. (eds.) Curve and Surface Fitting: Avignon 2006, pp. 121–130. Nashboro Press, Brentwood (2007)
Davydov, O., Oanh, D.T.: Adaptive meshless centres and RBF stencils for Poisson equation. J. Comput. Phys. 230, 287–304 (2011)
Davydov, O., Oanh, D.T.: On the optimal shape parameter for Gaussian radial basis function finite difference approximation of the Poisson equation. Comput. Math. Appl. 62, 2143–2161 (2011)
Davydov, O., Prasiswa, J., Reif, U.: Two-stage approximation methods with extended B-splines. Math. Comput. 83, 809–833 (2014)
Davydov, O., Schaback, R.: Error bounds for kernel-based numerical differentiation. Numer. Math. 132(2), 243–269 (2016)
Davydov, O., Schaback, R.: Optimal stencils in Sobolev spaces. IMA J. Numer. Anal. https://doi.org/10.1093/imanum/drx076
Davydov, O., Zeilfelder, F.: Scattered data fitting by direct extension of local polynomials to bivariate splines. Adv. Comput. Math. 21(3–4), 223–271 (2004)
Fasshauer, G.F.: Meshfree Approximation Methods with MATLAB, volume 6 of Interdisciplinary Mathematical Sciences. World Scientific Publishers, Singapore (2007)
Fornberg, B., Flyer, N.: A Primer on Radial Basis Functions with Applications to the Geosciences. Society for Industrial and Applied Mathematics, Philadelphia (2015)
Foucart, S., Rauhut, H.: A Mathematical Introduction to Compressive Sensing. Birkhäuser, Basel (2013)
Jetter, K., Stöckler, J., Ward, J.: Error estimates for scattered data interpolation on spheres. Math. Comput. 68, 733–747 (1999)
Liszka, T., Orkisz, J.: The finite difference method at arbitrary irregular grids and its application in applied mechanics. Comput. Struct. 11, 83–95 (1980)
Oanh, D.T., Davydov, O., Phu, H.X.: Adaptive RBF-FD method for elliptic problems with point singularities in 2D. Appl. Math. Comput. 313, 474–497 (2017)
Ostermann, I., Kuhnert, J., Kolymbas, D., Chen, C.-H., Polymerou, I., Šmilauer, V., Vrettos, C., Chen, D.: Meshfree generalized finite difference methods in soil mechanics—part I: theory. GEM Int. J. Geomath. 4(2), 167–184 (2013)
Schaback, R.: Error analysis of nodal meshless methods. In: Griebel, M., Schweitzer, M.A. (eds.) Meshfree Methods for Partial Differential Equations VIII, pp. 117–143. Springer, Berlin (2017)
Seibold, B.: M-Matrices in Meshless Finite Difference Methods. Dissertation, University of Kaiserslautern (2006)
Seibold, B.: Minimal positive stencils in meshfree finite difference methods for the Poisson equation. Comput. Methods Appl. Mech. Eng. 198(3–4), 592–601 (2008)
Seibold, B.: Performance of algebraic multigrid methods for non-symmetric matrices arising in particle methods. Numer. Linear Algebra Appl. 17, 433–451 (2010)
Stetter, H.J.: Analysis of Discretization Methods for Ordinary Differential Equations. Springer, New York (1973)
Stewart, G.: Matrix Algorithms. SIAM, Philadelphia (1998)
Wendland, H.: Scattered Data Approximation. Cambridge University Press, Cambridge (2005)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Davydov, O., Schaback, R. Minimal numerical differentiation formulas. Numer. Math. 140, 555–592 (2018). https://doi.org/10.1007/s00211-018-0973-3
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00211-018-0973-3