Skip to main content

2015 | OriginalPaper | Buchkapitel

4. Quasi-Monte Carlo Methods

verfasst von : Harald Niederreiter, Arne Winterhof

Erschienen in: Applied Number Theory

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

There are many scientific as well as real-world applications where we run into the problem of computing a definite integral. In calculus courses you are taught that a definite integral \(\int _{a}^{b}f(u)du\) is evaluated by the fundamental theorem of integral calculus which says that
$$\displaystyle{ \int _{a}^{b}f(u)du = F(b) - F(a), }$$
(4.1)
where the function F is an antiderivative of the integrand f. What you are often not told is that there are many cases where F cannot be expressed in finite terms by means of elementary functions, and in such situations the formula (4.1) is useless for computational purposes. Examples are \(\int _{0}^{1}e^{-u^{2} }du\) and \(\int _{0}^{1}(\sin u)(u + 1)^{-1}du\). We then have to settle for numerical approximations of \(\int _{a}^{b}f(u)du\). The process of approximately computing definite integrals with a sufficient degree of precision is called numerical integration.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literatur
7.
Zurück zum Zitat N.S. Bakhvalov, Approximate computation of multiple integrals. Vestnik Moskov. Univ. Ser. Mat. Mekh. Astr. Fiz. Khim. 1959(4), 3–18 (1959) [Russian]MathSciNet N.S. Bakhvalov, Approximate computation of multiple integrals. Vestnik Moskov. Univ. Ser. Mat. Mekh. Astr. Fiz. Khim. 1959(4), 3–18 (1959) [Russian]MathSciNet
9.
Zurück zum Zitat J. Beck, Probabilistic Diophantine approximation. I. Kronecker sequences. Ann. Math. (2) 140, 449–502 (1994) J. Beck, Probabilistic Diophantine approximation. I. Kronecker sequences. Ann. Math. (2) 140, 449–502 (1994)
14.
Zurück zum Zitat H. Brass, K. Petras, Quadrature Theory: The Theory of Numerical Integration on a Compact Interval (American Mathematical Society, Providence, 2011)CrossRef H. Brass, K. Petras, Quadrature Theory: The Theory of Numerical Integration on a Compact Interval (American Mathematical Society, Providence, 2011)CrossRef
34.
Zurück zum Zitat P.J. Davis, P. Rabinowitz, Methods of Numerical Integration, 2nd edn. (Academic Press, New York, 1984)MATH P.J. Davis, P. Rabinowitz, Methods of Numerical Integration, 2nd edn. (Academic Press, New York, 1984)MATH
37.
38.
Zurück zum Zitat J. Dick, F. Pillichshammer, Digital Nets and Sequences: Discrepancy Theory and Quasi-Monte Carlo Integration (Cambridge University Press, Cambridge, 2010)CrossRef J. Dick, F. Pillichshammer, Digital Nets and Sequences: Discrepancy Theory and Quasi-Monte Carlo Integration (Cambridge University Press, Cambridge, 2010)CrossRef
40.
Zurück zum Zitat M. Drmota, R.F. Tichy, Sequences, Discrepancies and Applications. Lecture Notes in Mathematics, vol. 1651 (Springer, Berlin, 1997) M. Drmota, R.F. Tichy, Sequences, Discrepancies and Applications. Lecture Notes in Mathematics, vol. 1651 (Springer, Berlin, 1997)
41.
Zurück zum Zitat R. Eckhardt, Stan Ulam, John von Neumann, and the Monte Carlo method, in From Cardinals to Chaos: Reflections on the Life and Legacy of Stanislaw Ulam, ed. by N.G. Cooper (Cambridge University Press, Cambridge, 1989), pp. 131–137 R. Eckhardt, Stan Ulam, John von Neumann, and the Monte Carlo method, in From Cardinals to Chaos: Reflections on the Life and Legacy of Stanislaw Ulam, ed. by N.G. Cooper (Cambridge University Press, Cambridge, 1989), pp. 131–137
48.
Zurück zum Zitat H. Faure, Discrépance de suites associées à un système de numération (en dimension s). Acta Arith. 41, 337–351 (1982) [French] H. Faure, Discrépance de suites associées à un système de numération (en dimension s). Acta Arith. 41, 337–351 (1982) [French]
49.
Zurück zum Zitat H. Faure, P. Kritzer, New star discrepancy bounds for (t, m, s)-nets and (t, s)-sequences. Monatsh. Math. 172, 55–75 (2013) H. Faure, P. Kritzer, New star discrepancy bounds for (t, m, s)-nets and (t, s)-sequences. Monatsh. Math. 172, 55–75 (2013)
50.
Zurück zum Zitat G.S. Fishman, Monte Carlo: Concepts, Algorithms, and Applications (Springer, New York, 1996)CrossRefMATH G.S. Fishman, Monte Carlo: Concepts, Algorithms, and Applications (Springer, New York, 1996)CrossRefMATH
54.
Zurück zum Zitat P. Glasserman, Monte Carlo Methods in Financial Engineering (Springer, New York, 2004)MATH P. Glasserman, Monte Carlo Methods in Financial Engineering (Springer, New York, 2004)MATH
57.
Zurück zum Zitat J.H. Halton, On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals. Numer. Math. 2, 84–90 (1960); Erratum. ibid. 2, 196 (1960) J.H. Halton, On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals. Numer. Math. 2, 84–90 (1960); Erratum. ibid. 2, 196 (1960)
58.
59.
62.
Zurück zum Zitat E. Hlawka, Funktionen von beschränkter Variation in der Theorie der Gleichverteilung. Ann. Mat. Pura Appl. (IV) 54, 325–333 (1961) [German] E. Hlawka, Funktionen von beschränkter Variation in der Theorie der Gleichverteilung. Ann. Mat. Pura Appl. (IV) 54, 325–333 (1961) [German]
63.
Zurück zum Zitat E. Hlawka, Zur angenäherten Berechnung mehrfacher Integrale. Monatsh. Math. 66, 140–151 (1962) [German] E. Hlawka, Zur angenäherten Berechnung mehrfacher Integrale. Monatsh. Math. 66, 140–151 (1962) [German]
65.
Zurück zum Zitat R. Hofer, H. Niederreiter, A construction of (t, s)-sequences with finite-row generating matrices using global function fields. Finite Fields Appl. 21, 97–110 (2013) R. Hofer, H. Niederreiter, A construction of (t, s)-sequences with finite-row generating matrices using global function fields. Finite Fields Appl. 21, 97–110 (2013)
75.
83.
Zurück zum Zitat J.F. Koksma, Een algemeene stelling uit de theorie der gelijkmatige verdeeling modulo 1. Math. B (Zutphen) 11, 7–11 (1942/1943) [Dutch] J.F. Koksma, Een algemeene stelling uit de theorie der gelijkmatige verdeeling modulo 1. Math. B (Zutphen) 11, 7–11 (1942/1943) [Dutch]
84.
Zurück zum Zitat N.M. Korobov, The approximate computation of multiple integrals. Dokl. Akad. Nauk SSSR 124, 1207–1210 (1959) [Russian]MathSciNetMATH N.M. Korobov, The approximate computation of multiple integrals. Dokl. Akad. Nauk SSSR 124, 1207–1210 (1959) [Russian]MathSciNetMATH
85.
Zurück zum Zitat N.M. Korobov, Properties and calculation of optimal coefficients. Dokl. Akad. Nauk SSSR 132, 1009–1012 (1960) [Russian]MathSciNet N.M. Korobov, Properties and calculation of optimal coefficients. Dokl. Akad. Nauk SSSR 132, 1009–1012 (1960) [Russian]MathSciNet
86.
Zurück zum Zitat N.M. Korobov, Number-Theoretic Methods in Approximate Analysis (Fizmatgiz, Moscow, 1963) [Russian]MATH N.M. Korobov, Number-Theoretic Methods in Approximate Analysis (Fizmatgiz, Moscow, 1963) [Russian]MATH
88.
Zurück zum Zitat P. Kritzer, Improved upper bounds on the star discrepancy of (t, m, s)-nets and (t, s)-sequences. J. Complexity 22, 336–347 (2006) P. Kritzer, Improved upper bounds on the star discrepancy of (t, m, s)-nets and (t, s)-sequences. J. Complexity 22, 336–347 (2006)
90.
Zurück zum Zitat L. Kuipers, H. Niederreiter, Uniform Distribution of Sequences (Wiley, New York, 1974). Reprint, Dover Publications, Mineola, NY, 2006 L. Kuipers, H. Niederreiter, Uniform Distribution of Sequences (Wiley, New York, 1974). Reprint, Dover Publications, Mineola, NY, 2006
93.
Zurück zum Zitat C.F. Laywine, G.L. Mullen, Discrete Mathematics Using Latin Squares (Wiley, New York, 1998)MATH C.F. Laywine, G.L. Mullen, Discrete Mathematics Using Latin Squares (Wiley, New York, 1998)MATH
96.
Zurück zum Zitat C. Lemieux, Monte Carlo and Quasi-Monte Carlo Sampling (Springer, New York, 2009)MATH C. Lemieux, Monte Carlo and Quasi-Monte Carlo Sampling (Springer, New York, 2009)MATH
97.
Zurück zum Zitat G. Leobacher, F. Pillichshammer, Introduction to Quasi-Monte Carlo Integration and Applications (Birkhäuser/Springer, Heidelberg, 2014)CrossRefMATH G. Leobacher, F. Pillichshammer, Introduction to Quasi-Monte Carlo Integration and Applications (Birkhäuser/Springer, Heidelberg, 2014)CrossRefMATH
118.
Zurück zum Zitat T. Müller-Gronbach, E. Novak, K. Ritter, Monte Carlo-Algorithmen (Springer, Berlin, 2012) [German]CrossRefMATH T. Müller-Gronbach, E. Novak, K. Ritter, Monte Carlo-Algorithmen (Springer, Berlin, 2012) [German]CrossRefMATH
123.
Zurück zum Zitat H. Niederreiter, Methods for estimating discrepancy, in Applications of Number Theory to Numerical Analysis, ed. by S.K. Zaremba (Academic Press, New York, 1972), pp. 203–236 H. Niederreiter, Methods for estimating discrepancy, in Applications of Number Theory to Numerical Analysis, ed. by S.K. Zaremba (Academic Press, New York, 1972), pp. 203–236
126.
132.
Zurück zum Zitat H. Niederreiter, Low-discrepancy point sets obtained by digital constructions over finite fields. Czechoslovak Math. J. 42, 143–166 (1992)MathSciNetMATH H. Niederreiter, Low-discrepancy point sets obtained by digital constructions over finite fields. Czechoslovak Math. J. 42, 143–166 (1992)MathSciNetMATH
133.
Zurück zum Zitat H. Niederreiter, Random Number Generation and Quasi-Monte Carlo Methods (SIAM, Philadelphia, 1992)CrossRefMATH H. Niederreiter, Random Number Generation and Quasi-Monte Carlo Methods (SIAM, Philadelphia, 1992)CrossRefMATH
143.
Zurück zum Zitat H. Niederreiter, I.H. Sloan, Quasi-Monte Carlo methods with modified vertex weights, in Numerical Integration IV, ed. by H. Braß, G. Hämmerlin. International Series of Numerical Mathematics, vol. 112 (Birkhäuser, Basel, 1993), pp. 253–265 H. Niederreiter, I.H. Sloan, Quasi-Monte Carlo methods with modified vertex weights, in Numerical Integration IV, ed. by H. Braß, G. Hämmerlin. International Series of Numerical Mathematics, vol. 112 (Birkhäuser, Basel, 1993), pp. 253–265
145.
Zurück zum Zitat H. Niederreiter, C.P. Xing, Low-discrepancy sequences and global function fields with many rational places. Finite Fields Appl. 2, 241–273 (1996)MathSciNetCrossRefMATH H. Niederreiter, C.P. Xing, Low-discrepancy sequences and global function fields with many rational places. Finite Fields Appl. 2, 241–273 (1996)MathSciNetCrossRefMATH
146.
Zurück zum Zitat H. Niederreiter, C.P. Xing, Rational Points on Curves over Finite Fields: Theory and Applications (Cambridge University Press, Cambridge, 2001)CrossRef H. Niederreiter, C.P. Xing, Rational Points on Curves over Finite Fields: Theory and Applications (Cambridge University Press, Cambridge, 2001)CrossRef
148.
153.
Zurück zum Zitat D. Nuyens, R. Cools, Fast algorithms for component-by-component construction of rank-1 lattice rules in shift-invariant reproducing kernel Hilbert spaces. Math. Comput. 75, 903–920 (2006)MathSciNetCrossRefMATH D. Nuyens, R. Cools, Fast algorithms for component-by-component construction of rank-1 lattice rules in shift-invariant reproducing kernel Hilbert spaces. Math. Comput. 75, 903–920 (2006)MathSciNetCrossRefMATH
157.
Zurück zum Zitat S.H. Paskov, J.F. Traub, Faster valuation of financial derivatives. J. Portf. Manag. 22(1), 113–120 (1995)CrossRef S.H. Paskov, J.F. Traub, Faster valuation of financial derivatives. J. Portf. Manag. 22(1), 113–120 (1995)CrossRef
160.
Zurück zum Zitat G. Pirsic, J. Dick, F. Pillichshammer, Cyclic digital nets, hyperplane nets, and multivariate integration in Sobolev spaces. SIAM J. Numer. Anal. 44, 385–411 (2006)MathSciNetCrossRefMATH G. Pirsic, J. Dick, F. Pillichshammer, Cyclic digital nets, hyperplane nets, and multivariate integration in Sobolev spaces. SIAM J. Numer. Anal. 44, 385–411 (2006)MathSciNetCrossRefMATH
167.
Zurück zum Zitat R.D. Richtmyer, The evaluation of definite integrals, and a quasi-Monte-Carlo method based on the properties of algebraic numbers, Report LA-1342, Los Alamos Scientific Laboratory, Los Alamos, NM, 1951CrossRef R.D. Richtmyer, The evaluation of definite integrals, and a quasi-Monte-Carlo method based on the properties of algebraic numbers, Report LA-1342, Los Alamos Scientific Laboratory, Los Alamos, NM, 1951CrossRef
171.
173.
Zurück zum Zitat M.Yu. Rosenbloom, M.A. Tsfasman, Codes for the m-metric. Probl. Inf. Transm. 33, 45–52 (1997)MATH M.Yu. Rosenbloom, M.A. Tsfasman, Codes for the m-metric. Probl. Inf. Transm. 33, 45–52 (1997)MATH
176.
Zurück zum Zitat W.M. Schmidt, Irregularities of distribution. VII, Acta Arith. 21, 45–50 (1972) W.M. Schmidt, Irregularities of distribution. VII, Acta Arith. 21, 45–50 (1972)
185.
Zurück zum Zitat V. Sinescu, S. Joe, Good lattice rules with a composite number of points based on the product weighted star discrepancy, in Monte Carlo and Quasi-Monte Carlo Methods 2006, ed. by A. Keller, S. Heinrich, H. Niederreiter (Springer, Berlin, 2008), pp. 645–658CrossRef V. Sinescu, S. Joe, Good lattice rules with a composite number of points based on the product weighted star discrepancy, in Monte Carlo and Quasi-Monte Carlo Methods 2006, ed. by A. Keller, S. Heinrich, H. Niederreiter (Springer, Berlin, 2008), pp. 645–658CrossRef
188.
Zurück zum Zitat I.H. Sloan, S. Joe, Lattice Methods for Multiple Integration (Clarendon Press, Oxford, 1994)MATH I.H. Sloan, S. Joe, Lattice Methods for Multiple Integration (Clarendon Press, Oxford, 1994)MATH
189.
Zurück zum Zitat I.M. Sobol’, Distribution of points in a cube and approximate evaluation of integrals. USSR Comput. Math. Math. Phys. 7(4), 86–112 (1967) I.M. Sobol’, Distribution of points in a cube and approximate evaluation of integrals. USSR Comput. Math. Math. Phys. 7(4), 86–112 (1967)
196.
Zurück zum Zitat J.G. van der Corput, Verteilungsfunktionen I, II. Nederl. Akad. Wetensch. Proc. Ser. B 38, 813–821, 1058–1066 (1935) [German] J.G. van der Corput, Verteilungsfunktionen I, II. Nederl. Akad. Wetensch. Proc. Ser. B 38, 813–821, 1058–1066 (1935) [German]
200.
Zurück zum Zitat H. Weyl, Über die Gleichverteilung von Zahlen mod. Eins. Math. Ann. 77, 313–352 (1916) [German] H. Weyl, Über die Gleichverteilung von Zahlen mod. Eins. Math. Ann. 77, 313–352 (1916) [German]
203.
Zurück zum Zitat C.P. Xing, H. Niederreiter, A construction of low-discrepancy sequences using global function fields. Acta Arith. 73, 87–102 (1995)MathSciNetMATH C.P. Xing, H. Niederreiter, A construction of low-discrepancy sequences using global function fields. Acta Arith. 73, 87–102 (1995)MathSciNetMATH
204.
205.
Zurück zum Zitat S.K. Zaremba, Some applications of multidimensional integration by parts, Ann. Polon. Math. 21, 85–96 (1968)MathSciNetMATH S.K. Zaremba, Some applications of multidimensional integration by parts, Ann. Polon. Math. 21, 85–96 (1968)MathSciNetMATH
206.
Zurück zum Zitat S.K. Zaremba, La méthode des “bons treillis” pour le calcul des intégrales multiples, in Applications of Number Theory to Numerical Analysis, ed. by S.K. Zaremba (Academic Press, New York, 1972), pp. 39–119 [French] S.K. Zaremba, La méthode des “bons treillis” pour le calcul des intégrales multiples, in Applications of Number Theory to Numerical Analysis, ed. by S.K. Zaremba (Academic Press, New York, 1972), pp. 39–119 [French]
Metadaten
Titel
Quasi-Monte Carlo Methods
verfasst von
Harald Niederreiter
Arne Winterhof
Copyright-Jahr
2015
DOI
https://doi.org/10.1007/978-3-319-22321-6_4