Metoda Monte Carlo

métodeu  Monte Carlo nyaéta algoritma keur ngaréngsékeun rupa-rupa masalah dina itung-itungan make komputer ngagunakeun wilangan acak (atawa leuwih sering disebut wilangan bayangan), mangrupa hal sabalikna tina algoritma deterministik. métodeu  Monte Carlo penting kacida dina komputasi fisik sarta aplikasi nu pakait, jeung bisa dipaké dina rupa-rupa itungan kromodinamika kuantum keur ngarancang pamisah panas sarta bentuk aerodinamika. métodeu  ieu geus kabuktian efisien keur ngarengsekeun persamaan integro-differential di kondisi medan radian, sarta métodeu  ieu geus digunakeun keur "itungan" iluminasi global nu ngahasilkeun photo-réalistic images of virtual 3d modéls, digunakeun dina video games, arsitektur, disain, animasi komputer dina film sarta efek hususna, sarta widang-widang séjénna.

Monte Carlo, kawentar keur kasino, nginjeum istilahna sabab métodeu  ieu ngagunakeun kaayaan acak sarta ngagunakeun "pengulangan" keur manggihkeun solusi nu panghadéna. Narikna,  métodeu  Monte Carlo teu merlukeun random numbers nu sabenerna keur digunakeun dina "perhitungan".  téhnik ieu leuwih gampang dipaké tinimbang deterministik, sekuen pseudo-random, gampang keur diuji sarta simulasi ulang.  Sakadar kualitas nu penting keur nyieun simulasi nu hadé keur nyieun sekuen pseudo-random deukeut kana kaayaan "acak" nu dipikahayang.  métodeu  ieu bakal kasebar seragam atawa nuturkeun sebaran nu dipikahayang lamun jumlah wilanganna gedé tina sekuen nu ditempo.

Sabab merlukeun algoritma "pengulangan" sarta number nu loba keur kaperluan perhitungan, Monte Carlo mangrupa métodeu  penyeimbang keur komputasi maké komputer, maké sababaraha téhnik simulasi komputer.

Algoritma Monte Carlo nyaéta bentuk numeris métodeu  Monte Carlo nu dipaké keur manggihkeun solusi dina masalah mathematika (nu mibanda variabel loba) nu harese direngsekeun, contona,  maké kalkulus integral, atawa métodeu  numeris séjénna.  métodeu  ieu leuwih hadé tinimbang métodeu  séjénna lamun dimensi tina masalah leuwih loba.

Sajarah

métodeu  Monte Carlo asalna tina "pemakaian" praktis dina ngaran nu leuwih umum saperti "statistical sampling". Sabaraha ahli nyebutkeun yén "Monte Carlo" mangrupa referensi kawentar dina kasino, sarta dipopulerkeun ku ahlina dina widang éta saperti Stanislaw Marcin Ulam, Enrico Fermi, John von Neumann sarta Nicholas Metropolis. Ahli séjénna nyebutkeun yén métodeu  ieu mimiti didiskusikeun ku ahli nu hadir dina konferensi di Monte Carlo.

métodeu  ngitung random mimiti loba nu maké dina mangsa pre-electronic computing. métodeu  ieu beuki kawentar sanggeus digunakeun Fermi dina 1930, waktu anjeunna maké métodeu  random keur ngitung sifat anyar neutron. métodeu  Monte Carlo jadi inti simulations nu diperlukeun dina Manhattan Project. Sanajan kitu, sanggeus komputer elektronik dijieun (mimiti taun 1945) métodeu  Monte Carlo mimiti ditalungtik leuwih jero.

Integrasi

métodeu  deterministic numerical integration dipaké ku cara nyokot sajumlah kajadian dina ruang sampel tina hiji fungsi. Sacara umum, hasil tina pagawéan ieu hadé keur fungsi hiji variabel. ku sabab kitu, keur fungsi vectors, métodeu  deterministic quadrature teu efisien. Keur integrsi numerik vektor dua-dimensi, diperlukeun ruang titik grid anu sarua dina "permukaan" dua dimensi. Contona keur grid 10x10 diperlukeun 100 titik. Lamun vektor mibanda 100 dimensi, jarak grid nu sarua merlukeun 10100 titik – hal ieu taya alesan keur bisa diitung. 100 dimensions hartina teu mungkin keur diitung, saperti dina loba masalah fisik, "dimension" sarua jeung degree of freedom, sarta dina simulasi tilu-dimensi, di dinya aya tilu degrees of freedom per partikel.

métodeu  Monte Carlo nunjukkeun cara maké exponential time-increase. Saperti fungsi anu mibanda alesan well-behaved, hal ieu bisa di-estimasi ku milih sacara random tina ruang 100-dimensi, sarta nyokot sababaraha tipe average. maké central limit theorem, métodeu  ieu bakal ditempokeun ku konvergen-na  – contona titik sampel lipat opat bakal boga satengah kasalahan, gumantung kana jumlah dimenasi.

Perbaikan tina métodeu  ieu nyaéta cara nyieun atawa milih titik random, tapi leuwih dipikaresep datangna kana integral ti wewengkon nu konsentrasi loba tinimbang ti wewengkon nu konsentrasi saeutik. Dina basa séjén, titik sahenteuna ngagambarkeun bentuk nu hampir sarua jeung integrand. Teu salawasna dina pemodélan komputer méré hasil nu nyugemakeun dina integrasi mimiti, sanajan kitu aya métodeu  séjén keur masalah ieu; dimimitian ku nyieun fungsi integrasi anu sederhana, salah sahijina bakal didiskusikeun dina topik di handap ieu.

Pendekatan anu ampir sarua ngagunakeun low-discrepancy sequences ku quasi-Monte Carlo method.  métodeu  Quasi-Monte Carlo sok leuwih efisien dina integrasi numeris sabab sekuen "ngeusi" wewengkon leuwih hadé dina rasa sarta sampel penting nu dijieun tina simulasi konvergen keur ngahasilkeun solusi jadi leuwih gancang.

Metoda Integrasi
 métodeu  sampling langsung
 Importance sampling 
 Stratified sampling
 Recursive stratified sampling
 VEGAS algorithm
 Random walk Monte Carlo kaasup Markov chains
 Metropolis-Hastings algorithm

Optimisasi

Hal séjén anu kuat sarta kawentar dina aplikasi keur random numbers dina simulasi numeris nyaéta numerical optimisation. Masalah ieu salawasna maké fungsi nga-minimal-keun vektor dina dimensi anu gedé. Loba masalah anu bisa direngsekeun ku cara ieu; contona program computer chess geus nunjukkeun kumaha carana langkah nu optimal keur meunangkeun tarung, sebutkeun, 10 langkah nu ngahasilkeun evaluasi panghadéna ka tahap ahir. Traveling salesman problem contoh lain dina masalah optimasi.  di dieu ogé aya sababaraha conto aplikasi dina masalah désain rekayasa, saperti multidisciplinary design optimization.

Lolobana optimasi Monte Carlo didasarkeun kana random walks. Intina, program ieu bakal dijieun dina wanda ruang multi-dimensi, condong pindah ti fungsi luhur ka fungsi handap, sanajan kitu kadang-kadang pindahna tibalik tina gradient.

Metoda Optimasi

 Stochastic tunneling
 simulated annealing
 genetic algorithms
 Parallel Tempering

Metoda sejen

 Diffusion and quantum Monte Carlo
 Semiconductor charge transport and the like
 Quasi-random numbers and self avoiding walks
 Assorted random modéls, e.g. self-organised criticality

Tempo oge
LURCH
Quasi-Monte Carlo method

Tumbu kaluar jeung sumber séjén
 P. Kevin MacKéown, Stochastic Simulation in Physics, 1997, ISBN 981-3083-26-3
 Harvey Gould & Jan Tobochnik, An Introduction to Computer Simulation Methods, Part 2, Applications to Physical Systems, 1988, ISBN 020116504X

Kategori:Matematika