Abstract
We study polynomial interpolation on a d-dimensional cube, where d is large. We suggest to use the least solution at sparse grids with the extrema of the Chebyshev polynomials. The polynomial exactness of this method is almost optimal. Our error bounds show that the method is universal, i.e., almost optimal for many different function spaces. We report on numerical experiments for d = 10 using up to 652 065 interpolation points.
Similar content being viewed by others
References
D. Berthold, W. Hoppe and B. Silbermann, A fast algorithm for solving the generalized airfoil equation, J. Comput. Appl. Math. 43 (1992) 185–219.
R. Cools, Integration over an hypercube, Unpublished manuscript (1998).
C. de Boor and A. Ron, The least solution for the polynomial interpolation problem, Math. Z. 210 (1992) 347–378.
C. de Boor and A. Ron, Computational aspects of polynomial interpolation in several variables, Math. Comp. 58 (1992) 705–727.
F.-J. Delvos, d-variate Boolean interpolation, J. Approx. Theory 34 (1982) 99–114.
V.K. Dzjadyk and V.V. Ivanov, On asymptotics and estimates for the uniform norms of the Lagrange interpolation polynomials corresponding to the Chebyshev nodal points, Anal. Math. 9 (1983) 85–97.
H. Ehlich and K. Zeller, Auswertung der Normen von Interpolationsoperatoren, Math. Ann. 164 (1966) 105–112.
K. Frank and S. Heinrich, Computing discrepancies of Smolyak quadrature rules, J. Complexity 12 (1996) 287–314.
A.C. Genz, Testing multidimensional integration routines, in: Tools, Methods, and Languages for Scientific and Engineering Computation, eds. B. Ford, J.C. Rault and F. Thomasset (North-Holland, Amsterdam, 1984) pp. 81–94.
A.C. Genz, A package for testing multiple integration subroutines, in: Numerical Integration, eds. P. Keast and G. Fairweather (Kluwer, Dordrecht, 1987) pp. 337–340.
Th. Gerstner and M. Griebel, Numerical integration using sparse grids, Numer. Algorithms 18 (1998) 209–232.
G. Mastroianni and P. Vertesi, Weighted Lp error of Lagrange interpolation, J. Approx. Theory 82 (1995) 321–339.
E. Novak and K. Ritter, High dimensional integration of smooth functions over cubes, Numer. Math. 75 (1996) 79–97.
E. Novak and K. Ritter, The curse of dimension and a universal method for numerical integration, in: Multivariate Approximation and Splines, eds. G. Nürnberger, J. W. Schmidt and G. Walz, International Series of Numerical Mathematics, Vol. 125 (Birkhäuser, Basel, 1997) pp. 177–187.
E. Novak and K. Ritter, Simple cubature formulas with high polynomial exactness, Constr. Approx. 15 (1999) 499–522.
E. Novak, K. Ritter, R. Schmitt and A. Steinbauer, On a recent interpolatory method for high dimensional integration, J. Comput. Appl. Math. (1997, to appear).
E. Novak, K. Ritter and A. Steinbauer, A multiscale method for the evaluation of Wiener integrals, in: Approximation Theory IX, Vol. 2, eds. C.K. Chui and L.L. Schumaker (Nashville, TN, 1998) pp. 251–258.
J. Prestin, Lagrange interpolation on extended generalized Jacobi nodes, Numer. Algorithms 5 (1993) 179–190.
Th. Sauer, Polynomial interpolation of minimal degree, Numer. Math. 78 (1997) 59–85.
I.H. Sloan and S. Joe, Lattice Methods for Multiple Integration (Clarendon Press, Oxford, 1994).
S.A. Smolyak, Quadrature and interpolation formulas for tensor products of certain classes of functions, Soviet Math. Dokl. 4 (1963) 240–243.
F. Sprengel, Interpolation and wavelets on sparse Gauss–Chebyshev grids, in: Multivariate Approximation, eds. W. Haussmann et al., Mathematical Research, Vol. 101 (Akademie Verlag, Berlin, 1997) pp. 269–286.
F. Sprengel, A unified approach to error estimates for interpolation on full and sparse Gauß– Chebyshev grids, Rostocker Math. Kolloq. 51 (1997) 51–64.
V.N. Temlyakov, Approximation of Periodic Functions (Nova Science, New York, 1993).
G.W. Wasilkowski and H. Wózniakowski, Explicit cost bounds of algorithms for multivariate tensor product problems, J. Complexity 11 (1995) 1–56.
G.W.Wasilkowski and H. Wózniakowski, Weighted tensor-product algorithms for linear multivariate problems, J. Complexity 15 (1999) 402–447.
H. Wózniakowski, Tractability and strong tractability of linear multivariate problems, J. Complexity 10 (1994) 96–128.
H. Wózniakowski, Tractability and strong tractability of multivariate tensor product problems, J. Comput. Inform. 4 (1994) 1–19.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Barthelmann, V., Novak, E. & Ritter, K. High dimensional polynomial interpolation on sparse grids. Advances in Computational Mathematics 12, 273–288 (2000). https://doi.org/10.1023/A:1018977404843
Issue Date:
DOI: https://doi.org/10.1023/A:1018977404843