Phương pháp Monte Carlo

Các phương pháp Monte Carlo là một lớp các thuật toán để giải quyết nhiều bài toán trên máy tính theo kiểu không tất định, thường bằng cách sử dụng các số ngẫu nhiên (thường là các số giả ngẫu nhiên), ngược lại với các thuật toán tất định. Một ứng dụng  cổ điển của phương pháp này là việc tính tích phân xác định, đặc biệt là các tích phân nhiều chiều với các điều kiện biên phức tạp.

Phương pháp Monte Carlo có một vị trí hết sức quan trọng trong vật lý tính toán và nhiều ngành khác, có ứng dụng bao trùm nhiều lĩnh vực, từ tính toán trong sắc động lực học lượng tử, mô phỏng hệ spin có tương tác mạnh, đến thiết kế vỏ bọc nhiệt hay hình dáng khí động lực học. Các phương pháp này đặc biệt hiệu quả khi giải quyết các phương trình vi-tích phân; ví dụ như trong mô tả trường bức xạ hay trường ánh sáng trong mô phỏng hình ảnh 3 chiều trên máy tính, có ứng dụng trong trò chơi điện tử, kiến trúc, thiết kế, phim tạo từ máy tính, các hiệu ứng đặc biệt trong điện ảnh, hay trong nghiên cứu khí quyển, và các ứng dụng nghiên cứu vật liệu bằng laser...

Trong toán học, thuật toán Monte Carlo là phương pháp tính bằng số hiệu quả cho nhiều bài toán liên quan đến nhiều biến số mà không dễ dàng giải được bằng các phương pháp khác, chẳng hạn bằng tính tích phân. Hiệu quả của phương pháp này, so với các phương pháp khác, tăng lên khi số chiều của bài toán tăng. Monte-Carlo cũng được ứng dụng cho nhiều lớp bài toán tối ưu hóa, như trong ngành tài chính.

Nhiều khi, phương pháp Monte Carlo được thực hiện hiệu quả hơn với số giả ngẫu nhiên, thay cho số ngẫu nhiên thực thụ, vốn rất khó tạo ra được bởi máy tính. Các số giả ngẫu nhiên có tính tất định, tạo ra từ chuỗi giả ngẫu nhiên có quy luật, có thể sử dụng để chạy thử, hoặc chạy lại mô phỏng theo cùng điều kiện như trước. Các số giả ngẫu nhiên trong các mô phỏng chỉ cần tỏ ra "đủ mức ngẫu nhiên", nghĩa là chúng theo phân bố đều hay theo một phân bố định trước, khi số lượng của chúng lớn.
 
Phương pháp Monte Carlo thường thực hiện lặp lại một số lượng rất lớn các bước đơn giản, song song với nhau; một phương pháp phù hợp cho máy tính. Kết quả của phương pháp này càng chính xác (tiệm cận về kết quả đúng) khi số lượng lặp các bước tăng.

Lịch sử

Tính tích phân

Xem thêm

Các phương pháp kiểu Monte-Carlo
 Monte Carlo lượng tử
 Phương pháp mô phỏng Monte Carlo
 Phương pháp động học Monte Carlo
 Xích Markov

Tối ưu hóa
 Ống ngẫu nhiên (Stochastic tunneling)
 Mô phỏng luyện thép (Simulated annealing)
 Thuật toán di truyền
 Xáo trộn song song (Parallel tempering)

Tích phân
 Tích phân Monte-Carlo
 Lấy mẫu có trọng tâm 
 Lấy mẫu phân tầng
 Lấy mẫu phân tầng lặp
 Thuật toán VEGAS
 Bước ngẫu nhiên Monte Carlo
 Thuật toán Metropolis-Hastings
 Lấy mẫu Gibbs

Ứng dụng
Monte Carlo cho tài chính
LURCH
Monte Carlo cho quan hệ nhiều lớp

Tham khảo

(bằng tiếng Anh)
Gamerman, D. Markov Chain Monte Carlo: Stochastic Simulation for Bayesian Inference. Boca Raton, FL: CRC Press, 1997. 
Gilks, W. R.; Richardson, S.; and Spiegelhalter, D. J. (Eds.). Markov Chain Monte Carlo in Practice. Boca Raton, FL: Chapman & Hall, 1996. 
Harvey Gould & Jan Tobochnik, An Introduction to Computer Simulation Methods, Part 2, Applications to Physical Systems, 1988, ISBN 0-201-16504-X
Hoffman, P. The Man Who Loved Only Numbers: The Story of Paul Erdos and the Search for Mathematical Truth. New York: Hyperion, pp. 238–239, 1998. 
Kuipers, L. and Niederreiter, H. Uniform Distribution of Sequences. New York: Wiley, 1974. 
Manno, I. Introduction to the Monte Carlo Method. Budapest, Hungary: Akadémiai Kiadó, 1999. 
MacKeown, P.K., Stochastic Simulation in Physics, 1997, ISBN 981-3083-26-3
Metropolis, N. and Ulam, S. "The Monte Carlo Method." J. Amer. Stat. Assoc. 44, 335-341, 1949. 
Metropolis, N. "The Beginning of the Monte Carlo Method." Los Alamos Science, No. 15, p. 125. http://jackman.stanford.edu/mcmc/metropolis1.pdf . 
Mikhailov, G. A. Parametric Estimates by the Monte Carlo Method. Utrecht, Netherlands: VSP, 1999. 
Niederreiter, H. and Spanier, J. (Eds.). Monte Carlo and Quasi-Monte Carlo Methods 1998, Proceedings of a Conference held at the Claremont Graduate University, Claremont, California, USA, June 22-26, 1998. Berlin: Springer-Verlag, 2000. 
 C.P. Robert and G. Casella. "Monte Carlo Statistical Methods" (second edition). New York: Springer-Verlag, 2004, ISBN 0-387-21239-6
Sobol, I. M. A Primer for the Monte Carlo Method. Boca Raton, FL: CRC Press, 1994.

Thuật toán
Số ngẫu nhiên
Vật lý tính toán
Cơ học thống kê
Phương pháp số
Phương pháp Monte Carlo
Lý thuyết xác suất
Giải tích số
Phân tích rủi ro
Quản lý rủi ro