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.
7 trang |
Chia sẻ: lylyngoc | Lượt xem: 1963 | Lượt tải: 2
Bạn đang xem nội dung tài liệu Giải vật lý thống kê với Phương pháp Monte Carlo, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
Giải vật lý thống kê với 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.
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
Hoàng Trần Minh
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
Tích phân Monte Carlo là một phương pháp tìm giá trị số của tích phân, đặc
biệt là các tích phân đa chiều có dạng:
trên một miền không gian đa chiều V sử dụng một số hữu hạn các lần gọi
hàm f.
Các phương pháp tích phân Monte-Carlo bao gồm phương pháp cơ bản,
phương pháp lấy mẫu có trọng tâm, ... Các phương pháp này cũng cho biết
ước lượng sai số thống kê của phép tính, tuy rằng ước lượng này có thể
không chính xác do việc khảo sát ngẫu nhiên hàm số trên miền không gian đa
chiều có thể không cho thấy hết mọi biểu hiện của hàm.
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
Tích phân Monte Carlo cơ bản
Tích phân một chiều
Ở dạng cơ bản nhất, giá trị của tích phân một chiều:
được dự đoán là tổng:
trong đó
V là thể tích mở rộng của miền tích phân
xi là các giá trị lấy ngẫu nhiên đều trong khoảng [a, b].
N là tổng số lần lấy mẫu xi
Sai số của dự đoán được tính bằng căn của phương sai của giá trị trung bình:
Khi số lần lấy mẫu, N, tăng, phương sai giảm theo 1/N, tức là sai số của phép
tính giảm theo .
Tích phân đa chiều
Phương pháp trên được mở rộng cho tích phân đa chiều:
với:_{i=1}^N f^2(x_i)
N.
Lấy mẫu có trọng tâm
Tích phân một chiều
Nếu biết hàm cần tích phân f(x) cư xử như nào, ta có thể chọn được một hàm
g(x) có giá trị biến đổi gần giống |f(x)| trên miền cần tích phân, ta có thể biến
đổi tích phân thành:
với:
và g(x) thỏa mãn điều kiện chuẩn hóa:
Lúc này có thể lấy các điểm xi ngẫu nhiên trong khoảng [a, b] theo phân bố
xác suất g(x') để tìm giá trị tích phân:
Hàm g(x) càng giống f(x) thì phương sai của f(x)/g(x) càng nhỏ và sai số của
phép tính càng nhỏ.
Một bất lợi của phương pháp này là sai số có thể lớn nếu hàm g(x) được chọn
gần bằng 0 tại những điểm mà f(x) khác 0. Lúc đó, phương sai của f(x)/g(x)
có thể lớn đến vô cùng. Lỗi này có thể khó phát hiện khi miền giá trị tại đó
g(x) bằng 0 là rất nhỏ.