×

zbMATH — the first resource for mathematics

On the approximation of smooth functions using generalized digital nets. (English) Zbl 1182.65024
Authors’ abstract: The authors study an approximation algorithm which firstly approximates certain Walsh coefficients of the function under consideration and consequently uses a Walsh polynomial to approximate the function. A similar approach has previously been used for approximating periodic functions, using lattice rules (and Fourier polynomials), and for approximating functions in Walsh Korobov spaces, using digital nets. Here, the key ingredient is the use of generalized digital nets (which have recently been shown to achieve higher order convergence rates for the integration of smooth functions). This allows us to approximate functions with square integrable mixed partial derivatives of order \(\alpha >1\) in each variable. The approximation error is studied in the worst case setting in the \(L_{2}\) norm. They also discuss tractability of their proposed approximation algorithm, investigate its computational complexity, and present numerical examples.

MSC:
65D15 Algorithms for approximation of functions
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Chrestenson, H.E., A class of generalized Walsh functions, Pacific J. math., 5, 17-31, (1955) · Zbl 0065.05302
[2] Larcher, G.; Traunfellner, C., On the numerical integration of Walsh series by number-theoretic methods, Math. comp., 63, 277-291, (1994) · Zbl 0806.65013
[3] Walsh, J.L., A closed set of normal orthogonal functions, Amer. J. math., 45, 5-24, (1923) · JFM 49.0293.03
[4] Dick, J., Walsh spaces containing smooth functions and quasi-Monte Carlo rules of arbitrary high order, SIAM J. numer. anal., 46, 1519-1553, (2008) · Zbl 1189.42012
[5] J. Dick, The decay of the Walsh coefficients of smooth functions, Bull. Austral. Math. Soc. (2009) (in press) · Zbl 1183.42027
[6] Dick, J., Explicit constructions of quasi-Monte Carlo rules for the numerical integration of high-dimensional periodic functions, SIAM J. numer. anal., 45, 2141-2176, (2007) · Zbl 1158.65007
[7] Korobov, N.M., Number-theoretic methods in approximate analysis, (1963), Fizmatgiz Moscow · Zbl 0115.11703
[8] Kuo, F.Y.; Sloan, I.H.; Woźniakowski, H., Lattice rules for multivariate approximation in the worst case setting, (), 289-330 · Zbl 1097.65133
[9] Niederreiter, H., ()
[10] Sloan, I.H.; Joe, S., Lattice methods for multiple integration, (1994), Clarendon Press Oxford, UK · Zbl 0855.65013
[11] Dick, J.; Kritzer, P.; Kuo, F.Y., Approximation of functions using digital nets, (), 275-297 · Zbl 1153.65314
[12] Kuo, F.Y.; Sloan, I.H.; Woźniakowski, H., Lattice rules for multivariate approximation in the average case setting, J. complexity, 24, 283-323, (2008) · Zbl 1141.65012
[13] Kuo, F.Y.; Wasilkowski, G.W.; Woźniakowski, H., Multivariate \(L_\infty\) approximation in the worst case setting over reproducing kernel Hilbert spaces, J. approx. theory, 152, 135-160, (2008) · Zbl 1154.41016
[14] Kuo, F.Y.; Wasilkowski, G.W.; Woźniakowski, H., On the power of standard information for multivariate approximation in the worst case setting, J. approx. theory, 158, 97-125, (2009) · Zbl 1181.41038
[15] Li, D.; Hickernell, F.J., Trigonometric spectral collocation methods on lattices, Contemp. math., 330, 121-132, (2003) · Zbl 1036.65093
[16] X. Zeng, P. Kritzer, F.J. Hickernell, Spline methods using low discrepancy designs (2008) (submitted for publication)
[17] Zeng, X.; Leung, K.; Hickernell, F.J., Error analysis of splines for periodic problems using lattice designs, (), 501-514 · Zbl 1097.65027
[18] Liu, K.I.; Dick, J.; Hickernell, F.J., A multivariate fast discrete Walsh transform with an application to function interpolation, Math. comp., 78, 1573-1591, (2009) · Zbl 1200.42017
[19] Niederreiter, H., Point sets and sequences with small discrepancy, Monatsh. math., 104, 273-337, (1987) · Zbl 0626.10045
[20] Faure, H., Discrépance de suites associées à un système de numération (en dimension \(s\)), Acta arith., 41, 337-351, (1982) · Zbl 0442.10035
[21] Niederreiter, H., Constructions of \((t, m, s)\)-nets and \((t, s)\)-sequences, Finite fields appl., 11, 578-600, (2005) · Zbl 1087.11051
[22] Niederreiter, H., Nets, \((t, s)\)-sequences and codes, (), 83-100 · Zbl 1196.11110
[23] Niederreiter, H.; Xing, C.P., Global function fields with many rational places and their applications, (), 87-111 · Zbl 0960.11033
[24] Sobol, I.M., Distribution of points in a cube and approximate evaluation of integrals, Z. vyčisl. mat. i mat. fiz., 7, 784-802, (1967)
[25] J. Dick, J. Baldeaux, Equidistribution Properties of Generalized Nets and Sequences, in: P. L’Ecuyer and A.B. Owen (eds.), Monte Carlo and quasi-Monte Carlo methods 2008, Springer Verlag, 2010 (in press) · Zbl 1228.65007
[26] J. Baldeaux, J. Dick, QMC rules of arbitrary high order: Reproducing kernel Hilbert space approach, Constr. Approx. (2009) (in press) · Zbl 1186.65005
[27] J. Dick, P. Kritzer, Duality theory and propagation rules for generalized digital nets, Math. Comp. (2010) (in press) · Zbl 1219.11115
[28] Sloan, I.H.; Woźniakowski, H., When are quasi-Monte Carlo algorithms efficient for high dimensional integrals?, J. complexity, 14, 1-33, (1998) · Zbl 1032.65011
[29] Dick, J.; Pillichshammer, F., Multivariate integration in weighted Hilbert spaces based on Walsh functions and weighted Sobolev spaces, J. complexity, 21, 149-195, (2005) · Zbl 1085.41021
[30] Dick, J.; Pillichshammer, F., Strong tractability of multivariate integration of arbitrary high order using digitally shifted polynomial lattice rules, J. complexity, 23, 436-453, (2007) · Zbl 1130.65005
[31] Novak, E.; Sloan, I.H.; Woźniakowski, H., Tractability of approximation for weighted korobov spaces on classical and quantum computers, Found. comput. math., 4, 121-156, (2004) · Zbl 1072.81014
[32] Wang, X., Strong tractability of multivariate integration using quasi-Monte Carlo algorithms, Math. comp., 72, 823-838, (2002) · Zbl 1025.65010
[33] Novak, E.; Woźniakowski, H., ()
[34] Traub, J.F.; Wasilkowski, G.W.; Woźniakowski, H., Information-based complexity, (1988), Academic Press New York · Zbl 0674.68039
[35] Wasilkowski, G.W.; Woźniakowski, H., Weighted tensor product algorithms for linear multivariate problems, J. complexity, 15, 402-447, (1999) · Zbl 0939.65079
[36] Wasilkowski, G.W.; Woźniakowski, H., On the power of standard information for weighted approximation, Found. comput. math., 1, 417-434, (2001) · Zbl 1001.41013
[37] Hickernell, F.J.; Niederreiter, H., The existence of good extensible rank-1 lattices, J. complexity, 19, 286-300, (2003) · Zbl 1029.65004
[38] Niederreiter, H.; Xing, C.P., ()
[39] Pirsic, G., A software implementation of Niederreiter-xing sequences, (), 434-445 · Zbl 1112.65304
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.