[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Quadrature for Self-affine Distributions on \({\mathbb R}^d\)

  • Published:
Foundations of Computational Mathematics Aims and scope Submit manuscript

Abstract

This article presents a systematic treatment of quadrature problems for self-similar probability distributions. We introduce explicit deterministic and randomized algorithms and study their errors for integrands of fractional smoothness of Hölder–Lipschitz type. Conversely, we derive lower bounds for worst-case errors of arbitrary integration schemes that prove optimality of our algorithms in many cases. In particular, we see that the effective dimension of the quadrature problem for functions of smoothness \(q>0\) is given by the quantization dimension of order \(q\) of the fractal measure.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. D. H. Bailey, J. M. Borwein, R. E. Crandall, and M. G. Rose. Expectations on fractal sets. Appl. Math. Comput., 220:695–721, 2013.

    Article  MathSciNet  Google Scholar 

  2. C. Bayer and J. Teichmann. The proof of Tchakaloff’s theorem. Proc. Amer. Math. Soc., 134(10):3035–3040, 2006.

    Article  MATH  MathSciNet  Google Scholar 

  3. G. Chen and P.J. Olver. Dispersion of discontinuous periodic waves. Proc. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci., 469:20120407, 21, 2013.

  4. V. Chousionis, M.B. Erdoğan, and N. Tzirakis. Fractal solutions of linear and nonlinear dispersive partial differential equations. http://arxiv.org/pdf/1406.3283.pdf, 2014.

  5. R. Crandall. On the fractal distribution of brain synapses. In Computational and Analytical Mathematics, volume 50 of Springer Proceedings in Mathematics & Statistics, pages 325–348. 2013.

  6. S. Dineen. Complex Analysis on Infinite Dimensional Spaces. Springer, London, 1999.

    Book  MATH  Google Scholar 

  7. K. Falconer. Techniques in fractal geometry. John Wiley & Sons Ltd., Chichester, 1997.

    MATH  Google Scholar 

  8. K. Falconer. Fractal geometry. John Wiley & Sons, Inc., Hoboken, NJ, second edition, 2003.

    Book  MATH  Google Scholar 

  9. S. Graf and H. Luschgy. Asymptotics of the quantization errors for self-similar probabilities. Real Anal. Exchange, 26(2):795–810, 2000/01.

  10. J. E. Hutchinson. Fractals and self-similarity. Indiana Univ. Math. J., 30(5):713–747, 1981.

    Article  MATH  MathSciNet  Google Scholar 

  11. B. B. Mandelbrot. The fractal geometry of nature. W. H. Freeman and Co., San Francisco, Calif., 1982.

    MATH  Google Scholar 

  12. G. Mastroianni and G. V. Milovanović. Interpolation processes. Springer Monographs in Mathematics. Springer-Verlag, Berlin, 2008. Basic theory and applications.

    Book  Google Scholar 

  13. E. Novak. Deterministic and stochastic error bounds in numerical analysis, volume 1349 of Lecture Notes in Mathematics. Springer-Verlag, Berlin, 1988.

    Google Scholar 

  14. E. Novak and H. Woźniakowski. Tractability of multivariate problems. Vol. 1: Linear information, volume 6 of EMS Tracts in Mathematics. European Mathematical Society (EMS), Zürich, 2008.

  15. E. Novak and H. Woźniakowski. Tractability of multivariate problems. Volume II: Standard information for functionals, volume 12 of EMS Tracts in Mathematics. European Mathematical Society (EMS), Zürich, 2010.

  16. E. Novak and H. Woźniakowski. Tractability of multivariate problems. Volume III: Standard information for operators, volume 18 of EMS Tracts in Mathematics. European Mathematical Society (EMS), Zürich, 2012.

  17. P. J. Olver. Dispersive quantization. Amer. Math. Monthly, 117:599–610, 2010.

    Article  MathSciNet  Google Scholar 

  18. K. Ritter. Average-case analysis of numerical problems, volume 1733 of Lecture Notes in Mathematics. Springer-Verlag, Berlin, 2000.

    Google Scholar 

  19. A. Schief. Separation properties for self-similar sets. Proc. Amer. Math. Soc., 122:111–115, 1994.

    Article  MATH  MathSciNet  Google Scholar 

  20. V. Tchakaloff. Formules de cubatures mécaniques à coefficients non négatifs. Bull. Sci. Math. (2), 81:123–134, 1957.

    MathSciNet  Google Scholar 

Download references

Acknowledgments

This work was supported by the Deutsche Forschungsgemeinschaft (DFG) within the Priority Programme 1324. We thank Erich Novak for pointing out the bound (4) to us. We are also thankful to the Editorial Board of JoFoCM for mentioning a potential application of our methods in the context of solutions of dispersive partial differential equations. We furthermore thank two anonymous referees for their valuable comments, which improved the presentation of the material.

Author information

Authors and Affiliations

  1. Fachbereich 10: Mathematik und Informatik, Institut für Mathematische Statistik, Westfälische Wilhelms-Universität Münster, Einsteinstr. 62, 48149, Münster, Germany

    Steffen Dereich

  2. Fakultät für Informatik und Mathematik, Universität Passau, Innstraße 33, 94032, Passau, Germany

    Thomas Müller-Gronbach

Authors
  1. Steffen Dereich
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Thomas Müller-Gronbach
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Thomas Müller-Gronbach.

Additional information

Communicated by Lan Sloan.

Appendix: Moments of Self-affine Measures

Appendix: Moments of Self-affine Measures

We provide a recursion formula for the computation of moments of \(P\) in the case of affine linear contractions

$$\begin{aligned} S_j(x) = A_j x + b_j \end{aligned}$$

with \(A_j\in {\mathbb R}^{d\times d}\) and \(b_j\in {\mathbb R}^d\) for \(j=1,\dots ,m\).

Put \(V={\mathbb R}^d\) and consider a \(d\)-dimensional random vector \(X\) with

$$\begin{aligned} X \sim P. \end{aligned}$$

For every \(\ell \in {\mathbb N}\), the mapping

$$\begin{aligned} V^\ell \ni (v_1,\dots ,v_\ell )\mapsto {\mathbb E}(v_1^{\mathrm {T}}X \cdots v_\ell ^{\mathrm {T}}X) \in {\mathbb R}\end{aligned}$$

is multilinear, and hence, it defines a real-valued linear mapping \(M_\ell \) on the \(\ell \)-th tensor power \(V^{\otimes \ell }\) via

$$\begin{aligned} M_\ell (v_1\otimes \dots \otimes v_\ell )= {\mathbb E}(v_1^{\mathrm {T}}X \cdots v_\ell ^{\mathrm {T}}X). \end{aligned}$$

Proposition 10

For every \(\ell \in {\mathbb N}\), the mapping

$$\begin{aligned} {\mathrm {id}}_{V^{\otimes l}}-\sum _{j=1}^m \rho _j\,(A_j^{\mathrm {T}})^{\otimes \ell }:V^{\otimes l}\rightarrow V^{\otimes l} \end{aligned}$$

is a bijection, and for every \(\mathbf v = v_1\otimes \dots \otimes v_\ell \in V^{\otimes l}\), we have

$$\begin{aligned} M_\ell \Bigl ({\mathrm {id}}_{V^{\otimes l}} -\sum _{j=1}^m \rho _j\,(A_j^{\mathrm {T}})^{\otimes \ell }\Bigr ) (\mathbf v)&= \sum _{j=1}^m \rho _j \Bigl (\prod _{i=1}^\ell v_i^{\mathrm {T}}b_j \\&+ \, \sum _{\emptyset \ne I \subsetneq \{1,\dots ,\ell \} } \Bigl ( \prod _{i\in I^c} v_i^{\mathrm {T}}b_j \Bigr ) \,M_{\# I} \Bigl (\bigotimes _{i\in I} A_j^{\mathrm {T}}v_i\Bigr )\Bigr ). \end{aligned}$$

Proof

Let \(\ell \in {\mathbb N}\) and \(v_1,\dots ,v_\ell \in V\). By the self-similarity of \(P\) and the particular form of the contractions \(S_j\), we have

$$\begin{aligned} {\mathbb E}(v_1^{\mathrm {T}}X \cdots v_\ell ^{\mathrm {T}}X)&=\sum _{j=1}^m \rho _j \,{\mathbb E}(v_1^{\mathrm {T}}S_j X \cdots v_\ell ^{\mathrm {T}}S_j X)\\&= \sum _{j=1}^m \rho _j \,\sum _{I \subset \{1,\dots ,l\}} \Bigl (\prod _{i\in I^c} v_i^{\mathrm {T}}b_j\Bigr ) \ {\mathbb E}\Bigl ( \prod _{i\in I} v_i^{\mathrm {T}}A_j X \Bigr ), \end{aligned}$$

which implies the recursion formula.

Consider any norm \(\Vert \cdot \Vert _{V^{\otimes l}}\) on \(V^{\otimes l}\) such that \(\Vert v_1\otimes \dots \otimes v_\ell \Vert _{V^{\otimes l}} = \Vert v_1\Vert \cdots \Vert v_\ell \Vert \) for \(v_1,\dots ,v_\ell \in V\). Then, \(v_1\otimes \dots \otimes v_\ell = \sum _{j=1}^m \rho _j (A_j^{\mathrm {T}}v_1\otimes \dots \otimes A_j^{\mathrm {T}}v_\ell )\) implies

$$\begin{aligned} \Vert v_1\Vert \cdots \Vert v_\ell \Vert&= \Bigl \Vert \sum _{j=1}^m \rho _j(A_j^{\mathrm {T}}v_1\otimes \dots \otimes A_j^{\mathrm {T}}v_\ell )\Bigr \Vert _{V^{\otimes l}}\\&\le \sum _{j=1}^m \rho _j \Vert A_j^{\mathrm {T}}v_1\Vert \cdots \Vert A_j^{\mathrm {T}}v_\ell \Vert \le \Vert v_1\Vert \cdots \Vert v_\ell \Vert \sum _{j=1}^m \rho _j r_j^\ell , \end{aligned}$$

and, consequently, \(v_1 \otimes \dots \otimes v_\ell = 0\). Hence, the mapping \({\mathrm {id}}_{V^{\otimes l}}-\sum _{j=1}^m \rho _j\,(A_j^{\mathrm {T}})^{\otimes \ell }\) is injective, which completes the proof. \(\square \)

Remark 9

The recursion formula in Proposition 10 simplifies significantly in the case of \(d=1\). Taking \(v_1=\dots =v_\ell =1\), we immediately obtain

$$\begin{aligned} {\mathbb E}(X^\ell ) = \left( 1-\sum _{j=1}^m \rho _j A_j^l\right) ^{-1}\sum _{j=1}^m \rho _j \sum _{k=0}^{l-1} {l\atopwithdelims ()k} b_j^{l-k} \,A_j^k\,{\mathbb E}(X^k). \end{aligned}$$

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Dereich, S., Müller-Gronbach, T. Quadrature for Self-affine Distributions on \({\mathbb R}^d\) . Found Comput Math 15, 1465–1500 (2015). https://doi.org/10.1007/s10208-014-9233-9

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10208-014-9233-9

Keywords

Mathematics Subject Classification

Search

Navigation