Monte Carlo Methods参考.ppt

Parallel Programmingin C with MPI and OpenMP Michael J. Quinn Chapter 10 Monte Carlo Methods Chapter Objectives Introduce Monte Carlo methods Introduce techniques for parallel random number generation Outline Monte Carlo method Sequential random number generators Parallel random number generators Generating non-uniform random numbers Monte Carlo case studies Monte Carlo Method Solve a problem using statistical sampling Name comes from Monaco’s gambling resort city First important use in development of atomic bomb during World War II Applications of Monte Carlo Method Evaluating integrals of arbitrary functions of 6+ dimensions Predicting future values of stocks Solving partial differential equations Sharpening satellite images Modeling cell populations Finding approximate solutions to NP-hard problems Example of Monte Carlo Method Example of Monte Carlo Method Absolute Error Absolute error is a way to measure the quality of an estimate The smaller the error, the better the estimate a: actual value e: estimated value Absolute error = |e-a|/a Increasing Sample Size Reduces Error Mean Value Theorem Estimating Mean Value Why Monte Carlo Works Why Monte Carlo is Effective Error in Monte Carlo estimate decreases by the factor 1/n1/2 Rate of convergence independent of integrand’s dimension Deterministic numerical integration methods do not share this property Hence Monte Carlo superior when integrand has 6 or more dimensions Parallelism in Monte Carlo Methods Monte Carlo methods often amenable to parallelism Find an estimate about p times faster OR Reduce error of estimate by p1/2 Random versus Pseudo-random Virtually all computers have “random number” generators Their operation is deterministic Sequences are predictable More accurately called “pseudo-random number” generators In this chapter “random” is shorthand for “pseudo-random” “RNG” means “random number generator” Properties of an Ideal RNG Uniformly distributed Uncorrelated Never cycles Satisfies any statistica