Metode Monte Carlo: Perbedaan antara revisi
kTidak ada ringkasan suntingan |
|||
(36 revisi perantara oleh 25 pengguna tidak ditampilkan) | |||
Baris 1: | Baris 1: | ||
[[File:Pi 30K.gif|thumb|right| Perhitungan nilai {{pi}} dengan menggunakan metode Monte Carlo.]] |
|||
'''Metode Monte Carlo''' adalah [[ |
'''Metode Monte Carlo''' adalah [[algoritme]] [[komputasi]] untuk [[simulasi|mensimulasikan]] berbagai perilaku sistem fisika dan matematika. Penggunaan klasik metode ini adalah untuk mengevaluasi [[integral definit]], terutama integral multidimensi dengan syarat dan batasan yang rumit. |
||
<!--They are distinguished from other simulation methods (such as [[molecular dynamics]]) by being [[stochastic]], that is [[nondeterministic]] in some manner - usually by using [[random number]]s (or more often [[pseudo-random number]]s) - as opposed to [[deterministic algorithm]]s. --> |
<!--They are distinguished from other simulation methods (such as [[molecular dynamics]]) by being [[stochastic]], that is [[nondeterministic]] in some manner - usually by using [[random number]]s (or more often [[pseudo-random number]]s) - as opposed to [[deterministic algorithm]]s. --> |
||
Metode Monte Carlo sangat penting dalam [[fisika komputasi]] dan bidang terapan lainnya, dan memiliki aplikasi yang beragam mulai dari perhitungan [[kromodinamika kuantum]] esoterik hingga perancangan aerodinamika. Metode ini terbukti efisien dalam memecahkan persamaan diferensial integral medan radians, sehingga metode ini digunakan dalam perhitungan [[iluminasi global]] yang menghasilkan gambar-gambar fotorealistik model tiga dimensi, dimana diterapkan dalam [[video games]], [[arsitektur]], [[perancangan]], [[film]] yang dihasilkan oleh komputer, efek-efek khusus dalam film, bisnis, ekonomi, dan bidang lainnya. |
Metode Monte Carlo sangat penting dalam [[fisika komputasi]] dan bidang terapan lainnya, dan memiliki aplikasi yang beragam mulai dari perhitungan [[kromodinamika kuantum]] esoterik hingga perancangan aerodinamika. Metode ini terbukti efisien dalam memecahkan persamaan diferensial integral medan radians, sehingga metode ini digunakan dalam perhitungan [[iluminasi global]] yang menghasilkan gambar-gambar fotorealistik model tiga dimensi, dimana diterapkan dalam [[video games]], [[arsitektur]], [[perancangan]], [[film]] yang dihasilkan oleh komputer, efek-efek khusus dalam film, bisnis, ekonomi, dan bidang lainnya. |
||
<!--Interestingly, the Monte Carlo method does not require truly random numbers to be useful. Much of the most useful techniques use deterministic, pseudo-random sequences, making it easy to test and re-run simulations. The only quality usually necessary to make good [[simulation]]s is for the pseudo-random sequence to appear "random enough" in a certain sense. That is that they must either be [[uniform distribution|uniformly distributed]] or follow another desired distribution when a large enough number of elements of the sequence are considered.--> |
<!--Interestingly, the Monte Carlo method does not require truly random numbers to be useful. Much of the most useful techniques use deterministic, pseudo-random sequences, making it easy to test and re-run simulations. The only quality usually necessary to make good [[simulation]]s is for the pseudo-random sequence to appear "random enough" in a certain sense. That is that they must either be [[uniform distribution|uniformly distributed]] or follow another desired distribution when a large enough number of elements of the sequence are considered.--> |
||
Karena |
Karena algoritme ini memerlukan pengulangan (repetisi) dan perhitungan yang amat kompleks, metode Monte Carlo pada umumnya dilakukan menggunakan [[komputer]], dan memakai berbagai teknik [[simulasi komputer]]. |
||
''' |
'''Algoritme Monte Carlo''' adalah metode Monte Carlo numerik yang digunakan untuk menemukan solusi problem matematis (yang dapat terdiri dari banyak variabel) yang susah dipecahkan, misalnya dengan [[kalkulus integral]], atau metode numerik lainnya. |
||
== Sejarah == |
== Sejarah == |
||
Baris 16: | Baris 17: | ||
Penggunaannya yang cukup dikenal adalah oleh [[Enrico Fermi]] pada tahun [[1930]], ketika ia menggunakan metode acak untuk menghitung sifat-sifat [[neutron]] yang waktu itu baru saja ditemukan. Metode Monte Carlo merupakan simulasi inti yang digunakan dalam [[Manhattan Project]], meski waktu itu masih menggunakan oleh peralatan komputasi yang sangat sederhana. Sejak digunakannya komputer elektronik pada tahun [[1945]], Monte Carlo mulai dipelajari secara mendalam. Pada tahun 1950-an, metode ini digunakan di Laboratorium Nasional [[Los Alamos National Laboratory|Los Alamos]] untuk penelitian awal pengembangan [[bom hidrogen]], dan kemudian sangat populer dalam bidang [[fisika]] dan [[riset operasi]]. ''Rand Corporation]]''an [[Angkatan Udara AS]] merupakan dua institusi utama yang bertanggung jawab dalam pendanaan dan penyebaran informasi mengenai Monte Carlo waktu itu, dan mereka mulai menemukan aplikasinya dalam berbagai bidang. |
Penggunaannya yang cukup dikenal adalah oleh [[Enrico Fermi]] pada tahun [[1930]], ketika ia menggunakan metode acak untuk menghitung sifat-sifat [[neutron]] yang waktu itu baru saja ditemukan. Metode Monte Carlo merupakan simulasi inti yang digunakan dalam [[Manhattan Project]], meski waktu itu masih menggunakan oleh peralatan komputasi yang sangat sederhana. Sejak digunakannya komputer elektronik pada tahun [[1945]], Monte Carlo mulai dipelajari secara mendalam. Pada tahun 1950-an, metode ini digunakan di Laboratorium Nasional [[Los Alamos National Laboratory|Los Alamos]] untuk penelitian awal pengembangan [[bom hidrogen]], dan kemudian sangat populer dalam bidang [[fisika]] dan [[riset operasi]]. ''Rand Corporation]]''an [[Angkatan Udara AS]] merupakan dua institusi utama yang bertanggung jawab dalam pendanaan dan penyebaran informasi mengenai Monte Carlo waktu itu, dan mereka mulai menemukan aplikasinya dalam berbagai bidang. |
||
Penggunaan metode Monte Carlo memerlukan sejumlah besar [[bilangan acak]], dan hal tersebut semakin mudah dengan perkembangan [[pembangkit bilangan pseudoacak]], yang jauh lebih cepat dan praktis dibandingkan dengan metode sebelumnya yang |
Penggunaan metode Monte Carlo memerlukan sejumlah besar [[bilangan acak]], dan hal tersebut semakin mudah dengan perkembangan [[pembangkit bilangan pseudoacak]], yang jauh lebih cepat dan praktis dibandingkan dengan metode sebelumnya yang menggunakn tabel bilangan acak untuk sampling statistik. |
||
<!-- |
<!-- |
||
== Perhitungan integral == |
== Perhitungan integral == |
||
Deterministic methods of [[numerical integration]] operate by taking a number of evenly spaced samples from a function. In general, this works very well for functions of one variable. However, for functions of [[vector space|vector]]s, deterministic quadrature methods can be very inefficient. To numerically integrate a function of a two-dimensional vector, equally spaced grid points over a two-dimensional surface are required. For instance a 10x10 grid requires 100 points. If the vector has 100 dimensions, the same spacing on the grid would require 10<sup>100</sup> points |
Deterministic methods of [[numerical integration]] operate by taking a number of evenly spaced samples from a function. In general, this works very well for functions of one variable. However, for functions of [[vector space|vector]]s, deterministic quadrature methods can be very inefficient. To numerically integrate a function of a two-dimensional vector, equally spaced grid points over a two-dimensional surface are required. For instance a 10x10 grid requires 100 points. If the vector has 100 dimensions, the same spacing on the grid would require 10<sup>100</sup> points – that's far too many to be computed. 100 [[dimension]]s is by no means unreasonable, since in many physical problems, a "dimension" is equivalent to a [[degrees of freedom (physics and chemistry)|degree of freedom]]. |
||
Monte Carlo methods provide a way out of this exponential time-increase. As long as the function in question is reasonably [[well-behaved]], it can be estimated by randomly selecting points in 100-dimensional space, and taking some kind of average of the function values at these points. By the [[central limit theorem]], this method will display <math>1/\sqrt{N}</math> convergence |
Monte Carlo methods provide a way out of this exponential time-increase. As long as the function in question is reasonably [[well-behaved]], it can be estimated by randomly selecting points in 100-dimensional space, and taking some kind of average of the function values at these points. By the [[central limit theorem]], this method will display <math>1/\sqrt{N}</math> convergence – i.e. quadrupling the number of sampled points will halve the error, regardless of the number of dimensions. |
||
A refinement of this method is to somehow make the points random, but more likely to come from regions of high contribution to the integral than from regions of low contribution. In other words, the points should be drawn from a distribution similar in form to the integrand. Understandably, doing this precisely is just as difficult as solving the integral in the first place, but there are approximate methods available: from simply making up an integrable function thought to be similar, to one of the adaptive routines discussed in the topics listed below. |
A refinement of this method is to somehow make the points random, but more likely to come from regions of high contribution to the integral than from regions of low contribution. In other words, the points should be drawn from a distribution similar in form to the integrand. Understandably, doing this precisely is just as difficult as solving the integral in the first place, but there are approximate methods available: from simply making up an integrable function thought to be similar, to one of the adaptive routines discussed in the topics listed below. |
||
Baris 50: | Baris 51: | ||
== Inverse Problems and Monte Carlo methods == |
== Inverse Problems and Monte Carlo methods == |
||
Probabilistic formulation of inverse problems leads to the definition of a probability distribution in the model space. This probability distribution combines a priori information with new information obtained by measuring some observable parameters (data). As, in the general case, the theory linking data with model parameters is nonlinear, the a posteriori probability in the model space may not be easy to describe (it may be multimodal, some moments may not be defined, etc.). When analyzing an inverse problem, obtaining a maximum likelihood model is usually not sufficient, as we normally also wish to have information on the resolution power of the data. In the general case we may have a large number of model parameters, and an inspection of the marginal probability densities of interest may be impractical, or even useless. But it is possible to pseudorandomly generate a large collection of models according to the posterior probability distribution and to analyze and display the models in such a way that information on the relative likelihoods of model properties is conveyed to the spectator. This can be accomplished by means of an efficient Monte Carlo method, even in cases where no explicit formula for the a priori distribution is available. The most well known importance sampling method, the Metropolis algorithm, can be generalized, and this gives a method that allows analysis of (possibly highly nonlinear) inverse problems with complex a priori information and data with an arbitrary noise distribution. For details, see Mosegaard and Tarantola (1995) [http://www.ipgp.jussieu.fr/~tarantola/Files/Professional/Papers_PDF/MonteCarlo_latex.pdf] |
Probabilistic formulation of inverse problems leads to the definition of a probability distribution in the model space. This probability distribution combines a priori information with new information obtained by measuring some observable parameters (data). As, in the general case, the theory linking data with model parameters is nonlinear, the a posteriori probability in the model space may not be easy to describe (it may be multimodal, some moments may not be defined, etc.). When analyzing an inverse problem, obtaining a maximum likelihood model is usually not sufficient, as we normally also wish to have information on the resolution power of the data. In the general case we may have a large number of model parameters, and an inspection of the marginal probability densities of interest may be impractical, or even useless. But it is possible to pseudorandomly generate a large collection of models according to the posterior probability distribution and to analyze and display the models in such a way that information on the relative likelihoods of model properties is conveyed to the spectator. This can be accomplished by means of an efficient Monte Carlo method, even in cases where no explicit formula for the a priori distribution is available. The most well known importance sampling method, the Metropolis algorithm, can be generalized, and this gives a method that allows analysis of (possibly highly nonlinear) inverse problems with complex a priori information and data with an arbitrary noise distribution. For details, see Mosegaard and Tarantola (1995) [http://www.ipgp.jussieu.fr/~tarantola/Files/Professional/Papers_PDF/MonteCarlo_latex.pdf], or Tarantola (2005) [http://www.ipgp.jussieu.fr/~tarantola/Files/Professional/SIAM/index.html] . |
||
== Other methods == |
== Other methods == |
||
Baris 67: | Baris 68: | ||
=== Aplikasi metode Monte Carlo === |
=== Aplikasi metode Monte Carlo === |
||
* Grafis, terutama untuk ''[[ray tracing]]'' |
* Grafis, terutama untuk ''[[ray tracing]]'' |
||
* |
* Pemodelan transportasi ringan dalam jaringan multi lapis / ''multi-layered tissues (MCML)'' |
||
* [[Metode Monte Carlo dalam bidang finansial]] |
* [[Metode Monte Carlo dalam bidang finansial]] |
||
* Simulasi prediksi struktur protein |
* Simulasi prediksi struktur protein |
||
* Dalam riset peralatan semikonduktor, untuk memodelkan transportasi pembawa arus |
* Dalam riset peralatan semikonduktor, untuk memodelkan transportasi pembawa arus |
||
* [[Peta genetik|Pemetaan genetik]] yang melibatkan ratusan [[penanda genetik]] dan analisis [[lokus sifat kuantitatif|QTL]] |
|||
* Distribusi potensial listrik.<ref>Analisis distribusi potensial listrik dalam koordinat kartesian tiga dimensi dengan metode Monte Carlo, Suyoso & [[Hary Gunarto]], [https://repository.ugm.ac.id/55424/ Thesis S2, Univ. Gadjah Mada,] 1994.</ref> |
|||
== Referensi == |
== Referensi == |
||
Baris 77: | Baris 80: | ||
* Harvey Gould & Jan Tobochnik, ''An Introduction to Computer Simulation Methods, Part 2, Applications to Physical Systems'', [[1988]], ISBN 0-201-16504-X |
* Harvey Gould & Jan Tobochnik, ''An Introduction to Computer Simulation Methods, Part 2, Applications to Physical Systems'', [[1988]], ISBN 0-201-16504-X |
||
* C.P. Robert and G. Casella. "Monte Carlo Statistical Methods" (second edition). New York: Springer-Verlag, [[2004]], ISBN 0-387-21239-6 |
* C.P. Robert and G. Casella. "Monte Carlo Statistical Methods" (second edition). New York: Springer-Verlag, [[2004]], ISBN 0-387-21239-6 |
||
* Pembuat paket komersial yang mengimplementasikan |
* Pembuat paket komersial yang mengimplementasikan algoritme Monte Carlo algorithms, [http://www.palisade.com Palisade Corporation (@Risk)], [http://www.decisioneering.com Decisioneering (Crystal Ball)] dan [http://www.vanguardsw.com/decisionpro/monte-carlo-simulation-software.htm Vanguard Software (DecisionPro)] {{Webarchive|url=https://web.archive.org/web/20060313045548/http://www.vanguardsw.com/decisionpro/monte-carlo-simulation-software.htm |date=2006-03-13 }} |
||
* Mosegaard, Klaus., and Tarantola, Albert, 1995. Monte Carlo sampling of solutions to inverse problems. J. Geophys. Res., 100, B7, 12431-12447. |
* Mosegaard, Klaus., and Tarantola, Albert, 1995. Monte Carlo sampling of solutions to inverse problems. J. Geophys. Res., 100, B7, 12431-12447. |
||
* Tarantola, Albert, ''Inverse Problem Theory'' ([http://www.ipgp.jussieu.fr/~tarantola/Files/Professional/SIAM/index.html versi PDF bebas]), Society for Industrial and Applied Mathematics, 2005. ISBN |
* Tarantola, Albert, ''Inverse Problem Theory'' ([http://www.ipgp.jussieu.fr/~tarantola/Files/Professional/SIAM/index.html versi PDF bebas]), Society for Industrial and Applied Mathematics, 2005. ISBN 0-89871-572-5 |
||
== Rujukan == |
|||
{{reflist}} |
|||
[[Kategori:Analisis numerik]] |
[[Kategori:Analisis numerik]] |
||
[[Kategori:Statistika]] |
[[Kategori:Statistika]] |
||
[[de:Monte-Carlo-Algorithmus]] |
|||
[[en:Monte Carlo method]] |
|||
[[es:Método de Monte Carlo]] |
|||
[[fr:Méthode de Monte-Carlo]] |
|||
[[it:Metodo Monte Carlo]] |
|||
[[he:שיטת מונטה קרלו]] |
|||
[[nl:Monte-Carlosimulatie]] |
|||
[[ja:モンテカルロ法]] |
|||
[[ko:몬테카를로 방법]] |
|||
[[pl:Metoda Monte Carlo]] |
|||
[[pt:Método Monte Carlo]] |
|||
[[su:Metoda Monte Carlo]] |
|||
[[vi:Phương pháp Monte Carlo]] |
|||
[[zh:蒙特•卡罗方法]] |
|||
[[ru:Метод Монте-Карло]] |
Revisi terkini sejak 17 Agustus 2021 02.50
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/84/Pi_30K.gif/220px-Pi_30K.gif)
Metode Monte Carlo adalah algoritme komputasi untuk mensimulasikan berbagai perilaku sistem fisika dan matematika. Penggunaan klasik metode ini adalah untuk mengevaluasi integral definit, terutama integral multidimensi dengan syarat dan batasan yang rumit.
Metode Monte Carlo sangat penting dalam fisika komputasi dan bidang terapan lainnya, dan memiliki aplikasi yang beragam mulai dari perhitungan kromodinamika kuantum esoterik hingga perancangan aerodinamika. Metode ini terbukti efisien dalam memecahkan persamaan diferensial integral medan radians, sehingga metode ini digunakan dalam perhitungan iluminasi global yang menghasilkan gambar-gambar fotorealistik model tiga dimensi, dimana diterapkan dalam video games, arsitektur, perancangan, film yang dihasilkan oleh komputer, efek-efek khusus dalam film, bisnis, ekonomi, dan bidang lainnya.
Karena algoritme ini memerlukan pengulangan (repetisi) dan perhitungan yang amat kompleks, metode Monte Carlo pada umumnya dilakukan menggunakan komputer, dan memakai berbagai teknik simulasi komputer.
Algoritme Monte Carlo adalah metode Monte Carlo numerik yang digunakan untuk menemukan solusi problem matematis (yang dapat terdiri dari banyak variabel) yang susah dipecahkan, misalnya dengan kalkulus integral, atau metode numerik lainnya.
Sejarah
[sunting | sunting sumber]Metode Monte Carlo digunakan dengan istilah sampling statistik. Penggunaan nama Monte Carlo, yang dipopulerkan oleh para pioner bidang tersebut (termasuk Stanislaw Marcin Ulam, Enrico Fermi, John von Neumann dan Nicholas Metropolis), merupakan nama kasino terkemuka di Monako. Penggunaan keacakan dan sifat pengulangan proses mirip dengan aktivitas yang dilakukan pada sebuah kasino. Dalam autobiografinya Adventures of a Mathematician, Stanislaw Marcin Ulam menyatakan bahwa metode tersebut dinamakan untuk menghormati pamannya yang seorang penjudi, atas saran Metropolis.
Penggunaannya yang cukup dikenal adalah oleh Enrico Fermi pada tahun 1930, ketika ia menggunakan metode acak untuk menghitung sifat-sifat neutron yang waktu itu baru saja ditemukan. Metode Monte Carlo merupakan simulasi inti yang digunakan dalam Manhattan Project, meski waktu itu masih menggunakan oleh peralatan komputasi yang sangat sederhana. Sejak digunakannya komputer elektronik pada tahun 1945, Monte Carlo mulai dipelajari secara mendalam. Pada tahun 1950-an, metode ini digunakan di Laboratorium Nasional Los Alamos untuk penelitian awal pengembangan bom hidrogen, dan kemudian sangat populer dalam bidang fisika dan riset operasi. Rand Corporation]]an Angkatan Udara AS merupakan dua institusi utama yang bertanggung jawab dalam pendanaan dan penyebaran informasi mengenai Monte Carlo waktu itu, dan mereka mulai menemukan aplikasinya dalam berbagai bidang.
Penggunaan metode Monte Carlo memerlukan sejumlah besar bilangan acak, dan hal tersebut semakin mudah dengan perkembangan pembangkit bilangan pseudoacak, yang jauh lebih cepat dan praktis dibandingkan dengan metode sebelumnya yang menggunakn tabel bilangan acak untuk sampling statistik.
Aplikasi metode Monte Carlo
[sunting | sunting sumber]- Grafis, terutama untuk ray tracing
- Pemodelan transportasi ringan dalam jaringan multi lapis / multi-layered tissues (MCML)
- Metode Monte Carlo dalam bidang finansial
- Simulasi prediksi struktur protein
- Dalam riset peralatan semikonduktor, untuk memodelkan transportasi pembawa arus
- Pemetaan genetik yang melibatkan ratusan penanda genetik dan analisis QTL
- Distribusi potensial listrik.[1]
Referensi
[sunting | sunting sumber]- Bernd A. Berg, Markov Chain Monte Carlo Simulations and Their Statistical Analysis (With Web-Based Fortran Code), World Scientific 2004, ISBN 981-238-935-0.
- P. Kevin MacKeown, 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 0-201-16504-X
- C.P. Robert and G. Casella. "Monte Carlo Statistical Methods" (second edition). New York: Springer-Verlag, 2004, ISBN 0-387-21239-6
- Pembuat paket komersial yang mengimplementasikan algoritme Monte Carlo algorithms, Palisade Corporation (@Risk), Decisioneering (Crystal Ball) dan Vanguard Software (DecisionPro) Diarsipkan 2006-03-13 di Wayback Machine.
- Mosegaard, Klaus., and Tarantola, Albert, 1995. Monte Carlo sampling of solutions to inverse problems. J. Geophys. Res., 100, B7, 12431-12447.
- Tarantola, Albert, Inverse Problem Theory (versi PDF bebas), Society for Industrial and Applied Mathematics, 2005. ISBN 0-89871-572-5
Rujukan
[sunting | sunting sumber]- ^ Analisis distribusi potensial listrik dalam koordinat kartesian tiga dimensi dengan metode Monte Carlo, Suyoso & Hary Gunarto, Thesis S2, Univ. Gadjah Mada, 1994.