×

Monte Carlo methods for applied scientists. (English) Zbl 1140.65008

Hackensack, NJ: World Scientific (ISBN 978-981-02-2329-8/hbk; 978-981-277-989-2/ebook). xv, 291 p. (2008).
Monte Carlo methods are a powerful tool in many fields of mathematics, physics and engineering. The algorithms based on this method give statistical estimations for any linear functional of the solution by performing random sampling of a certain random variable (r.v.) whose mathematical expectation is the desired functional.
In the introduction of the book the essence of the Monte Carlo method (MCM) is presented. This method is characterized as a method which uses r.v. or random processes to find an approximate solution to some problems of different branches of science. Some basic notions of the MC theory as the mathematical expectation \(E\xi,\) the variance \(D\xi,\) the standard deviation \(\sigma \xi\) of r.v. \(\xi,\) the probability error of approximate calculations are introduced. Some historical remarks about the origin and development of MCM are presented. Some general considerations about the advantage of MCM are given. The two main directions in the development and study of MCM- the Monte Carlo simulations and Monte Carlo numerical algorithms to solve deterministic problems by modelling r.v.s or random fields, are discussed. Some important problems of the theory of terminated Markov chains are described.
In chapter 2 some basic facts about Monte Carlo integration are considered. In section 2.1 the convergence and error analysis of MCM are discussed. The expectation of continuous and discrete r.v. with respect to the probability density function is given. The concept of the central limit theorem is presented. In section 2.2 two basic Monte Carlo algorithms for multidimensional integration – the plain MC and the geometric MC – are considered. The computational complexity of these methods are compared. In section 2.3 the techniques for reduction of variance are considered. Several classical algorithms as a separation of the principal part, an integration on a subdomain, a symmetrization of the integrand, an importance sampling algorithm and a weight functions approach are considered. Theorems concerning estimations of variance are proved. In section 2.4 superconvergence MC algorithms are considered. The concept of MC algorithm with a superconvergence probable error is given. The problem to obtain results for the convergence of the algorithms for functions which are only continuous is considered. Two results for estimation of the probable error in the terms of the averaged modulus of smoothness are presented. In section 2.5 a superconvergence adaptive algorithm for practical computations is developed. Adaptive MC algorithms which yield a priori and a posteriori information obtained during calculations are presented. In Theorem 2.7 and 2.8 estimations of the probable error are given. In section 2.6 it is shown how a random interpolation quadratures can be defined. In section 2.7 some basic facts about quasi-Monte Carlo methods are given. The notion of uniformly distributed sequences, \(\Pi_{\tau}\)-sequences of Sobol and some applications are presented. In section 2.8 exercises about the considered methods are presented.
In chapter 3 an optimal MCM for numerical integration of multidimensional integrals of smooth functions is proposed and studied. In section 3.1 the functional class \(W^{k}(\| f \|; [0,1)^{d})= W^{k}\) (\(d \geq 1\) denotes the dimension) is introduced. Two algorithms – deterministic and stochastic – for numerical integration of the class \(W^{k}\) are presented. Two results (Theorems 3.1 and 3.2) of Bakhvalov establish lower bounds for the integration error in both algorithms. In section 3.2 the methods for numerical integration are described. The notion of the mean square error is defined. Theorem 3.3 gives estimations of the error and the mean square error of the integration in the class \(W^{k}.\) The concept of the Hölder class of functions \(H_{\lambda}^{k}(\alpha, [0,1)^{d})\) is presented. Theorem 3.4 gives estimations of the error and the mean square error of the integration in the class \(H_{\lambda}^{k}(\alpha, [0,1)^{d}).\) In section 3.3 estimates of the computation complexity of both considered algorithms of numerical integration of a function from \(W^{k}\) are given. In section 3.4 some numerical tests showing the computation efficiency of the considered algorithms are presented.
In chapter 4 iterative stationary linear MC algorithms are considered. The systematic and stochastic errors of these methods are analyzed. These algorithms find an approximation of a functional of powers of linear operators. On two kinds of linear operators – integral operators and matrices – is focused. In section 4.1 a general description of iterative MC algorithms is given. The solution to the problem of recursive construction of sequences is given as truncated Neumann series. The theory of integral iterations is developed. In section 4.2 the problems of solving linear systems and matrix inversion are presented. In section 4.3 MC algorithms to solve linear systems of equations and matrix inversion are considered in the case when the corresponding Neumann series does not converges, or converges slowly. Theorem 4.1 and 4.2 from section 4.4 are results related to the convergence of algorithms for systems of linear algebraic equations. In section 4.5 the problem of comparing the stochastic and systematic error of MC algorithms is considered. In section 4.6 some estimations of the number of realizations \(N\) and the mathematical expectation for the length of the Markov chain \(T\) for MC matrix inversion are obtained. In section 4.7 a refined approach to the iterative MC algorithms for matrix inversion problems is presented. Three algorithms are given and the obtained numerical results are discussed.
In chapter 5 a MC approach to evaluate the eigenvalues of real symmetric matrices is studied. Algorithms for both dominants and smallest by magnitude eigenvalue are considered. In section 5.1 the problem of evaluating eigenvalues of a matrix is described. The details of the so-called power method for an estimation for the dominant eigenvalues are developed. In section 5.2 the almost optimal Markov chain MC algorithms for computing bilinear forms of matrix power and extremal eigenvalues of real symmetric matrices are developed. The details of robust and interpolation MC algorithms are presented. The structure of the variance of these algorithms is shown. In section 5.3 estimations of the computational complexity of MC almost optimal (MAO) algorithms are given. In section 5.4 an applicability and acceleration of MAO algorithms is considered.
In chapter 6 two approaches to numerically solving elliptic equations, the so-called grid approach and grid-free approach are considered. In section 6.1 the linear boundary value problem is introduced. The definition of ellipticity is given. MC algorithms calculating linear functionals of the solution of the elliptic problem are developed. In sections 6.2 and 6.3 the details of grid MC algorithm and grid-free MC algorithms are presented. Some simple numerical examples for performing grid and grid-free MC algorithms are considered. In Theorem 6.1 a majorant function is given in an explicit form. A parallel implementation of the grid-free algorithm is presented.
In chapter 7 the possibility of applying spline-functions to create superconvergent MC algorithms is used. The problem of an estimation of an unknown density function of a r.v. using a given number of its realizations is considered. This problem is solved by using specially created superconvergent MC algorithms for estimating the coefficients in the \(B\)-spline approximation of the unknown density. In section 7.1 the theoretical base of this problem is developed. A \(B\)-spline of \(k\)th degree is constructed in explicit form. In section 7.2 the problem of estimating the error of the density function, using \(N\) realizations of r.v. is developed. The probable error is studied for two special cases, when splines of degree \(k \geq 2\) and splines of degree \(k \geq 3\) are used for modelling densities. Theorems 7.1 and 7.3 give the orders of the probable error in the case of using \(B\)-spline of degree \(k \geq 2\) and \(B\)-spline of degree \(k \geq 3.\) In section 7.3 the problem of balancing both symmetric and stochastic errors is considered.
In chapter 8 algorithms for solving nonlinear equations with a polynomial nonlinearly are considered. MC iterations corresponding to a branching stochastic process are used to calculate linear functionals of the solutions of nonlinear integral equations of Fredholm type. A branching stochastic process is a Markov process that models a population in which each individual in generation produces some random number of individuals in generation. In section 8.1 the mathematical base of the evaluating of an inner product as a unique solution of the Fredholm integral equation in an operator form is developed. In section 8.2 a MC method which is applied to the Fredholm integral equation is described. In section 8.3 an efficient algorithm that optimizes the method described in section 8.2 is developed. The problem of optimizing the MC algorithms consists in minimization of the standard deviation. In Theorems 8.2 and 8.3 the forms of the density functions that minimizes the second moments of a given r.v. are presented. In section 8.4 the developed algorithms are tested by numerical examples.
In section 9.1 in order to estimate how the MC algorithms depend on different computer architectures four models are considered. In section 9.2 an iterative MC algorithm that uses Markov chains for calculation of the required r.v. is developed. In section 9.3 algorithms for boundary value problems are presented. The computational complexity of these algorithms is studied. The grid algorithm, the random jumps on mesh points algorithm, the grid-free algorithm, the vector MC algorithms are used. There are examples that are solved and the obtained practical results are discussed.
In chapter 10 algorithms for modelling transport phenomena in semiconductors and nanowire are presented. The basic algorithms for simulations of the semiclassical Boltzmann equation are discussed from the point of view of the numerical MC method. Such an approach is a base to develop models for solving equations generating the Boltzmann equation towards quantum transport. It is used to solve purely quantum problems, e.g. the Wigner equation. A convergency proof for each corresponding algorithm is presented. A number of numerical experiments is performed. A grid application to modelling carrier transport in nanowires is presented. Numerical results based on this grid applications are discussed.
The book finishes with three appendices, where some necessary calculations are made.

MSC:

65C05 Monte Carlo methods
11K36 Well-distributed sequences and other variations
11K45 Pseudo-random numbers; Monte Carlo methods
65C10 Random number generation in numerical analysis
65C20 Probabilistic models, generic numerical methods in probability and statistics
65C30 Numerical solutions to stochastic differential and integral equations
65C40 Numerical analysis or methods applied to Markov chains
65C50 Other computational problems in probability (MSC2010)
65C60 Computational problems in statistics (MSC2010)
35J25 Boundary value problems for second-order elliptic equations
82D37 Statistical mechanics of semiconductors
65F05 Direct numerical methods for linear systems and matrix inversion
65F15 Numerical computation of eigenvalues and eigenvectors of matrices
45G10 Other nonlinear integral equations
82B80 Numerical methods in equilibrium statistical mechanics (MSC2010)
82C80 Numerical methods of time-dependent statistical mechanics (MSC2010)
81S30 Phase-space methods including Wigner distributions, etc. applied to problems in quantum mechanics
82C40 Kinetic theory of gases in time-dependent statistical mechanics
65-02 Research exposition (monographs, survey articles) pertaining to numerical analysis
00A06 Mathematics for nonmathematicians (engineering, social sciences, etc.)
60J22 Computational methods in Markov chains
60F05 Central limit and other weak theorems
65R20 Numerical methods for integral equations
PDFBibTeX XMLCite
Full Text: DOI