Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Representation of functions as Walsh series to different bases and an application to the numerical integration of high-dimensional Walsh series

Authors: Gerhard Larcher, Wolfgang Ch. Schmid and Reinhard Wolf
Journal: Math. Comp. 63 (1994), 701-716
MSC: Primary 65D30; Secondary 11K45, 42C10
MathSciNet review: 1254146
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We will prove the following theorem on Walsh series, and we will derive from this theorem an effective and constructive method for the numerical integration of Walsh series by number-theoretic methods. Further, concrete computer calculations are given.

Theorem. For base $ b \geq 2$, dimension $ s \geq 1$, and $ \alpha > 1,c > 0\;(b,s \in \mathbb{N};c,\alpha \in \mathbb{R})$, let $ _b\overline E _s^\alpha (c)$ be the class of all functions $ f:[0,1)^s \to \mathbb{C}$ which are representable by absolutely convergent Walsh series to base b with Walsh coefficients $ \hat W({h_1}, \ldots ,{h_s})$ with the following property: $ \vert\hat W({h_1}, \ldots ,{h_s})\vert \leq c \cdot {({\overline h _1} \cdots {\overline h _s})^{ - \alpha }}$ for all $ {h_1}, \ldots ,{h_s}$, where $ \overline h : = \max (1,\vert h\vert)$. We show that if $ f \in {\,_2}\overline E _s^\alpha (c)$, then $ f \in {\,_{{2^h}}}\overline E _s^{\alpha - {\beta _h}}(c \cdot {2^{hs\alpha }})$ for all $ h \geq 2$, provided that $ \alpha > 1 + {\beta _h}$, where

$\displaystyle {\beta _h} = \frac{{h - 1}}{{2h}} + \frac{{\sum\nolimits_{k = 0}^... ...h}{2}]}} - 1}}{{3 \cdot {2^{k + 1}}}}} \right\}} \right)} }}{{h \cdot \log 2}}.$

The "exponent" $ \alpha - {\beta _h}$ is best possible for all h, and $ {\beta _h}$ is monotonically increasing with

$\displaystyle \beta : = \mathop {\lim }\limits_{h \to \infty } {\beta _h} = \frac{1}{2} + \frac{{\log \sin \frac{{5\pi }}{{12}}}}{{\log 2}} = 0.4499 \ldots .$

References [Enhancements On Off] (What's this?)

  • [1] T. Hansen, G. L. Mullen, and H. Niederreiter, Good parameters for a class of node sets in quasi-Monte Carlo integration, Math. Comp. 61 (1993), 225-234. MR 1182244 (94e:11088)
  • [2] G. Larcher, A class of low-discrepancy point-sets and its application to numerical integration by number-theoretical methods, Österreichisch-Ungarisch-Slowakisches Kolloquium über Zahlentheorie (F. Halter-Koch and R. Tichy, eds.), Grazer Math. Ber., vol. 318, Karl-Franzens-Univ. Graz, Graz, 1993, pp. 69-80. MR 1227403 (94e:11089)
  • [3] G. Larcher and C. Traunfellner, On the numerical integration of Walsh series by number-theoretic methods, Math. Comp. 63 (1994), 277-291. MR 1234426 (94j:65030)
  • [4] H. Niederreiter, Low-discrepancy and low-dispersion sequences, J. Number Theory 30 (1988), 51-70. MR 960233 (89k:11064)
  • [5] -, Orthogonal arrays and other combinatorial aspects in the theory of uniform point distributions in unit cubes, Discrete Math. 106/107 (1992), 361-367. MR 1181933 (94f:11070)
  • [6] -, Point sets and sequences with small discrepancy, Monatsh. Math. 104 (1987), 273-337. MR 918037 (89c:11120)
  • [7] W. Ch. Schmid, Zur numerischen Integration von Walshreihen, Diplomarbeit, Universität Salzburg, 1993.
  • [8] I. M. Sobol, The distribution of points in a cube and the approximate evaluation of integrals, Zh. Vychisl. Mat. i Mat. Fiz. 7 (1967), 784-802. (Russian) MR 0219238 (36:2321)
  • [9] -, Multidimensional quadrature formulas and Haar functions, "Nauka", Moscow, 1969. (Russian) MR 0422968 (54:10952)
  • [10] C. Traunfellner, Zahlentheoretische Methoden zur numerischen Integration von Walshreihen, Diplomarbeit, Universität Salzburg, 1991.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65D30, 11K45, 42C10

Retrieve articles in all journals with MSC: 65D30, 11K45, 42C10

Additional Information

Article copyright: © Copyright 1994 American Mathematical Society

American Mathematical Society