Monte Carlo and quasi-Monte Carlo methods

Acta Numerica - Tập 7 - Trang 1-49 - 1998
Russel E. Caflisch1
1Mathematics Department, UCLA, Los Angeles, CA 90095-1555, USA E-mail:

Tóm tắt

Monte Carlo is one of the most versatile and widely used numerical methods. Its convergence rate, O(N−1/2), is independent of dimension, which shows Monte Carlo to be very robust but also slow. This article presents an introduction to Monte Carlo methods for integration problems, including convergence theory, sampling methods and variance reduction techniques. Accelerated convergence for Monte Carlo quadrature is attained using quasi-random (also called low-discrepancy) sequences, which are a deterministic alternative to random or pseudo-random sequences. The points in a quasi-random sequence are correlated to provide greater uniformity. The resulting quadrature method, called quasi-Monte Carlo, has a convergence rate of approximately O((logN)kN−1). For quasi-Monte Carlo, both theoretical error estimates and practical limitations are presented. Although the emphasis in this article is on integration, Monte Carlo simulation of rarefied gas dynamics is also discussed. In the limit of small mean free path (that is, the fluid dynamic limit), Monte Carlo loses its effectiveness because the collisional distance is much less than the fluid dynamic length scale. Computational examples are presented throughout the text to illustrate the theory. A number of open problems are described.

Từ khóa


Tài liệu tham khảo

10.1145/198429.198436

10.1016/0041-5553(76)90154-3

10.1016/0021-9991(78)90004-9

10.1063/1.4823101

Feller, 1971, An Introduction to Probability Theory and its Applications: Vol. I

Goldstein, 1988, Rarefied Gas Dynamics: Theoretical and Computational Techniques, 118, 100

10.4064/aa-73-1-87-102

10.1137/1036002

10.1145/240896.240909

Press, 1992, Numerical Recipes in C: The Art of Scientific Computing

10.1080/00411459308203842

10.1007/978-1-4612-1039-9

10.1007/BF01055714

10.1016/0377-0427(90)90332-T

10.1137/S0036142994277468

10.21314/JCF.1997.005

Chapman, 1970, The Mathematical Theory of Non-Uniform Gases

10.1137/S0036142994268090

10.1002/cpa.3160460503

10.1016/0021-9991(92)90143-M

Bird, 1976, Molecular Gas Dynamics

10.1006/jcph.1995.1209

Nanbu, 1986, Proceedings of the 15th International Symposium on Rarefied Gas Dynamics, I, 369

10.1080/00949657908810333

10.1007/BF01026608

10.1007/BF00155857

Acworth, 1997, Monte Carlo and Quasi-Monte Carlo Methods 1996

Owen, 1998, Scrambled net variance for integrals of smooth functions, Ann. Statist.

10.1137/1010056

10.1146/annurev.fl.10.010178.000303

10.1137/0915077

10.1090/S0025-5718-1961-0146960-1

Kuipers, 1974, Uniform Distribution of Sequences

10.4064/aa-41-4-337-351

10.1007/BF01386213

10.1137/0730081

Caflisch, 1983, Nonequilibrium Phenomena I: The Boltzmann equation, 10, 193

10.1090/S0025-5718-98-00894-1

Jin S. , Pareschi L. and Toscani G. (1998), ‘Diffusive relaxation schemes for discrete-velocity kinetic equations’. Preprint.

10.1002/cpa.3160420810

10.1016/0021-9991(87)90170-7

10.1002/9783527617395

Karatzas, 1991, Brownian Motion and Stochastic Calculus

Sobol, 1967, The distribution of points in a cube and the accurate evaluation of integrals, Zh. Vychisl. Mat. Mat. Fiz., 7, 784

10.1080/00411458408211656

10.1137/S0036142995287768

10.1016/0895-7177(96)00038-6

10.1007/978-1-4612-2552-2_19

Hammersley, 1965, Monte Carlo Methods

Kennedy, 1980, Statistical Computing

Hua, 1981, Applications of Number Theory to Numerical Analysis

10.1090/S0273-0979-1991-15985-9

10.1137/1.9781611970081

Hogg, 1995, Introduction to Mathematical Statistics

10.1063/1.865826

Thông tin
Thông tin xuất bản

Acta Numerica

Tập 7

1-49

Thông tin tác giả