Metoda Monte Carlo

Metodele Monte Carlo (MMC) sunt un grup de metode numerice pentru studierea proceselor aleatorii . Esența metodei este următoarea: procesul este descris printr-un model matematic folosind un generator de variabile aleatoare , modelul este calculat în mod repetat, pe baza datelor obținute, sunt calculate caracteristicile probabilistice ale procesului luat în considerare. De exemplu, pentru a afla prin metoda Monte Carlo care va fi distanța medie dintre două puncte aleatorii dintr-un cerc, trebuie să luați coordonatele unui număr mare de perechi aleatoare de puncte în limitele unui cerc dat, să calculați distanța pentru fiecare pereche și apoi calculați media aritmetică pentru ele .

Metodele sunt folosite pentru rezolvarea problemelor din diverse domenii ale fizicii , chimiei , matematicii , economiei , optimizarii , teoria controlului etc.

Numele metodei provine din zona Monte Carlo , renumită pentru cazinourile sale.

Istorie

Metoda lui Buffon pentru determinarea Pi

Variabile aleatorii au fost folosite pentru a rezolva diverse probleme aplicate de mult timp. Un exemplu este metoda de determinare a numărului Pi , care a fost propusă de Buffon încă din 1777 . Esența metodei a fost de a arunca un ac lung pe un plan trasat de mai multe linii drepte paralele situate la distanță unele de altele. Probabilitatea (cu condiția sau altfel ) ca segmentul de dreaptă să intersecteze linia este legată de pi: $L$ $r$ $r>L$

p=\int \limits _{0}^{\pi }\int \limits _{0}^{l\sin {\theta }}{\frac {1}{r\pi }}dAd\ theta,

Unde

$A$ - distanta de la inceputul acului pana la linia dreapta cea mai apropiata de acesta;
$\theta$ - unghiul acului fata de liniile drepte.

Această integrală este ușor de luat: (cu condiția ca ), prin urmare, numărând proporția segmentelor care intersectează liniile, putem determina aproximativ acest număr. Pe măsură ce numărul de încercări crește, acuratețea rezultatului va crește. $p={\frac {2L}{r\pi \,}}$ $r>L$

În 1864, căpitanul Fox, recuperându-se după o rană, pentru a se ocupa cumva, a pus în aplicare un experiment de aruncare a acului [1] . Rezultatele sunt prezentate în următorul tabel: [2]

	Numărul de aruncări	Numărul de intersecții	Lungimea acului	Distanța dintre liniile drepte	Rotație	Valoarea Pi	Eroare
Prima încercare	500	236	3	patru	dispărut	3,1780	+3,6⋅10 -2
A doua încercare	530	253	3	patru	prezent	3,1423	+7,0⋅10 -4
A treia încercare	590	939	5	2	prezent	3,1416	+4,7⋅10 -5

Comentarii:

Lungimile sunt în inci.
S-a aplicat rotația planului (și după cum arată rezultatele - cu succes) pentru a reduce eroarea sistematică [2] .
În a treia încercare, lungimea acului a fost mai mare decât distanța dintre linii, ceea ce a făcut posibilă, fără a crește numărul de aruncări, creșterea efectivă a numărului de evenimente și îmbunătățirea preciziei (mai multe intersecții puteau să apară într-o singură aruncare) .

Relația dintre procesele stocastice și ecuațiile diferențiale

Crearea aparatului matematic al metodelor stocastice a început la sfârșitul secolului al XIX-lea. În 1899, Lord Rayleigh a arătat că o mers aleatorie unidimensională pe o rețea infinită poate oferi o soluție aproximativă a unui tip de ecuație diferențială parabolică [3] . Andrei Nikolaevich Kolmogorov în 1931 a dat un mare impuls dezvoltării abordărilor stocastice pentru rezolvarea diferitelor probleme matematice, deoarece a putut demonstra că lanțurile Markov sunt legate de anumite ecuații integro-diferențiale . În 1933, Ivan Georgievich Petrovsky a arătat că o mers aleatorie , care formează un lanț Markov , este legată asimptotic de soluția unei ecuații diferențiale parțiale eliptice . După aceste descoperiri, a devenit clar că procesele stocastice pot fi descrise prin ecuații diferențiale și, în consecință, investigate folosind metode matematice bine dezvoltate pentru rezolvarea acestor ecuații la acel moment.

Nașterea metodei Monte Carlo la Los Alamos

Mai întâi Enrico Fermi în anii 1930 în Italia, iar apoi John von Neumann și Stanislaw Ulam în anii 1940 la Los Alamos , au sugerat că este posibil să se folosească legătura dintre procesele stocastice și ecuațiile diferențiale „în direcția opusă”. Ei au sugerat utilizarea unei abordări stocastice pentru a aproxima integralele multidimensionale în ecuațiile de transport care au apărut în legătură cu problema mișcării neutronilor într- un mediu izotrop .

Ideea a fost dezvoltată de Ulam, care, în timp ce juca solitaire în timp ce se recupera de o boală, s-a întrebat care este probabilitatea ca solitaire să iasă. În loc să folosească considerațiile obișnuite de combinatorie pentru astfel de probleme , Ulam a sugerat că s-ar putea pur și simplu rula experimentul de un număr mare de ori și, prin numărarea numărului de rezultate de succes, estima probabilitatea. Dar, din cauza necesității de a efectua un număr mare de acțiuni experimentale de același tip, metoda nu a fost utilizată pe scară largă.

Odată cu apariția primului computer electronic, ENIAC , care putea genera numere pseudoaleatoare cu mare viteză și le putea folosi în modele matematice, a apărut un reînnoit interes pentru metodele stocastice. Stanisław Ulam a discutat ideile sale cu John von Neumann , care a folosit în cele din urmă ENIAC pentru metoda de selecție statistică propusă de Ulam în rezolvarea diferitelor probleme de transport de neutroni [4] . Datorită necesității de a opri ENIAC pentru o perioadă semnificativă de timp la sfârșitul anului 1946, Enrico Fermi a dezvoltat chiar și un computer analog specializat pentru a continua cercetările privind mișcarea neutronilor , căruia i s-a dat numele FERMIAC (prin analogie cu ENIAC, dar cu un indicând paternitatea lui Fermi), care era și la nivel mecanic, este implementată metoda Monte Carlo.

După începutul utilizării computerelor, a avut loc o mare descoperire, iar metoda Monte Carlo a fost aplicată în multe probleme, pentru care abordarea stocastică s-a dovedit a fi mai eficientă decât alte metode matematice. Cu toate acestea, utilizarea unei astfel de tehnici a avut și limitările sale din cauza necesității unui număr foarte mare de calcule pentru a obține rezultate cu precizie ridicată.

Anul nașterii termenului „Metoda Monte Carlo” este considerat a fi 1949, când a fost publicat articolul „Metoda Monte Carlo” de Metropolis și Ulam. Denumirea metodei provine de la numele comunei din Principatul Monaco , cunoscută pentru numeroasele sale cazinouri , deoarece ruleta este unul dintre cei mai cunoscuti generatori de numere aleatoare . Stanislav Ulam scrie în autobiografia sa Aventurile unui matematician că numele a fost sugerat de Nicholas Metropolis în onoarea unchiului său, care era un jucător de noroc.

Dezvoltare ulterioară și modernitate

În anii 1950 , metoda a fost folosită pentru calcule în dezvoltarea bombei cu hidrogen. Principalele merite în dezvoltarea metodei în acest moment aparțin angajaților laboratoarelor US Air Force și ale corporației RAND . Fizicienii sovietici A. A. Varfolomeev și I. A. Svetlolobov [5] au fost printre primii care au folosit metoda Monte Carlo pentru calcularea ploilor de particule .

În anii 1970 , într-un nou domeniu al matematicii - teoria complexității computaționale , s-a demonstrat că există o clasă de probleme a căror complexitate (numărul de calcule necesare pentru obținerea unui răspuns exact) crește exponențial odată cu dimensiunea problemei . Uneori este posibil, sacrificând acuratețea, să găsim un algoritm a cărui complexitate crește mai lent, dar există un număr mare de probleme pentru care acest lucru nu se poate face (de exemplu, problema determinării volumului unui corp convex în n - dimensionale) . Spațiul euclidian, iar dacă este generalizat, atunci în general calculul integralelor n -dimensionale) și metoda Monte Carlo este singura modalitate de a obține un răspuns suficient de precis într-un timp rezonabil.

În prezent, principalele eforturi ale cercetătorilor vizează crearea de algoritmi Monte Carlo eficienți pentru diferite procese fizice, chimice și sociale pentru sisteme de calcul paralele .

Integrare Monte Carlo

Să presupunem că trebuie să luăm integrala unei funcții. Vom folosi o descriere geometrică informală a integralei și o vom înțelege ca aria de sub graficul acestei funcții.

Pentru a determina această zonă, puteți utiliza una dintre metodele obișnuite de integrare numerică : împărțiți segmentul în subsegmente, calculați aria de sub graficul funcției pe fiecare dintre ele și adăugați. Să presupunem că pentru funcția prezentată în Figura 2, este suficient să se împartă în 25 de segmente și, prin urmare, să se calculeze 25 de valori ale funcției. Imaginați-vă acum, avem de-a face cu funcția -dimensională. Apoi avem nevoie de segmente și același număr de calcule ale valorii funcției. Când dimensiunea funcției este mai mare de 10, sarcina devine uriașă. Întrucât spațiile dimensionale înalte se întâlnesc, în special, în problemele de teoria corzilor , precum și în multe alte probleme fizice în care există sisteme cu multe grade de libertate, este necesar să existe o metodă de rezolvare a cărei complexitate de calcul nu ar depinde atât de mult. pe dimensiune. Aceasta este proprietatea metodei Monte Carlo. $n$ $25^{n}$

Algoritmul obișnuit de integrare Monte Carlo

Să presupunem că doriți să calculați o integrală definită

\int \limits _{{a}}^{{b}}f(x)\,dx

Se consideră o variabilă aleatoare distribuită uniform pe intervalul de integrare . Atunci va fi, de asemenea, o variabilă aleatoare, iar așteptarea sa matematică este exprimată ca $u$ $[a,b]$ $f(u)$

\mathbb {E} f(u)=\int \limits _{a}^{b}f(x)\varphi (x)\,dx,

unde este densitatea de distribuție a variabilei aleatoare , care este egală cu . Astfel, integrala dorită este exprimată ca $\varphi(x)$ $u$ ${\frac {1}{ba}}$ $[a,b]$

\int \limits _{a}^{b}f(x)\,dx=(ba)\mathbb {E} f(u),

dar așteptarea matematică a unei variabile aleatoare poate fi estimată cu ușurință prin modelarea acestei variabile aleatoare și calculând media eșantionului. $f(u)$

Deci, aruncăm puncte distribuite uniform pe , pentru fiecare punct pe care îl calculăm . Apoi calculăm media eșantionului: . Ca rezultat, obținem estimarea integralei: $N$ $[a,b]$ $tu_{i}$ $f(u_{i})$ ${\frac {1}{N}}\sum _{{i=1}}^{{N}}f(u_{i})$

\int \limits _{a}^{b}f(x)\,dx\aprox {\frac {ba}{N}}\sum _{i=1}^{N}f(u_{ i}).

Precizia estimării depinde numai de numărul de puncte . $N$

Această metodă are și o interpretare geometrică. Este foarte asemănătoare cu metoda deterministă descrisă mai sus, cu diferența că în loc să împărțim uniform regiunea de integrare în intervale mici și să însumăm ariile „coloanelor” rezultate, aruncăm puncte aleatorii pe regiunea de integrare, pe fiecare dintre acestea. construim aceeași „coloană”, determinând lățimea acesteia ca , și însumăm ariile acestora. ${\frac {ba}{N}}$

Algoritm geometric pentru integrarea Monte Carlo

Pentru a determina aria de sub graficul funcției, puteți utiliza următorul algoritm stocastic:

restrângem funcția la un dreptunghi (un paralelipiped n - dimensional în cazul mai multor dimensiuni), a cărui zonă poate fi calculată cu ușurință; orice latură a dreptunghiului conține cel puțin 1 punct din graficul funcției, dar nu îl intersectează; $S_{{par}}$
„Scrieți” în acest dreptunghi (paralelepiped) un anumit număr de puncte ( piese), ale căror coordonate le vom alege aleatoriu; $N$
determinați numărul de puncte ( piese) care se încadrează sub graficul funcției; $K$
aria regiunii delimitate de funcție și axele de coordonate este dată de $S$ $S=S_{{par}}{\frac {K}{N}}$

Pentru un număr mic de dimensiuni ale funcției integrabile, performanța integrării Monte Carlo este mult mai mică decât performanța metodelor deterministe. Totuși, în unele cazuri, când funcția este specificată implicit, dar este necesară determinarea ariei specificate sub formă de inegalități complexe, metoda stocastică poate fi mai de preferat.

Utilizarea eșantionării semnificației

Cu același număr de puncte aleatoare, precizia calculelor poate fi mărită prin apropierea zonei care limitează funcția dorită de funcția în sine. Pentru a face acest lucru, este necesar să folosiți variabile aleatoare cu o distribuție a cărei formă este cât mai apropiată de forma funcției integrabile. Una dintre metodele de îmbunătățire a convergenței în calculele Monte Carlo se bazează pe aceasta: eșantionarea semnificației .

Optimizare

Diverse variante ale metodei Monte Carlo pot fi folosite pentru a rezolva probleme de optimizare. De exemplu, algoritmul de simulare de recoacere .

Aplicații în fizică

Simularea pe computer joacă un rol important în fizica modernă, iar metoda Monte Carlo este una dintre cele mai comune în multe domenii, de la fizica cuantică la fizica stării solide, fizica plasmei și astrofizică.

Algoritmul Metropolis

În mod tradițional, metoda Monte Carlo a fost folosită pentru a determina diferiți parametri fizici ai sistemelor în echilibru termodinamic. Să presupunem că există un set de stări posibile ale sistemului fizic . Pentru a determina valoarea medie a unei anumite cantități , este necesar să se calculeze , unde se efectuează însumarea pentru toate stările din , este probabilitatea stării . $W(S)$ $S$ $\overline {A}$ $A$ $\overline {A}=\sum _{{S}}A(S)P(S)$ $S$ $W(S)$ $P(S)$ $S$

Formulare dinamică (cinetică)

Simulare Monte Carlo directă

Simularea Monte Carlo directă a oricărui proces fizic implică modelarea comportamentului părților elementare individuale ale unui sistem fizic. În esență, această modelare directă este aproape de a rezolva problema de la primele principii , dar de obicei, pentru a accelera calculele, este permisă utilizarea oricăror aproximări fizice. Un exemplu este calculul diferitelor procese prin metoda dinamicii moleculare : pe de o parte, sistemul este descris prin comportamentul componentelor sale elementare, pe de altă parte, potențialul de interacțiune utilizat este adesea empiric .

Exemple de simulare Monte Carlo directă:

Simularea iradierii solidelor de către ioni în aproximarea coliziunilor binare.
Simulare Monte Carlo directă a gazelor rarefiate.
Cele mai multe modele cinetice Monte Carlo sunt printre cele directe (în special, studiul epitaxiei fasciculului molecular ).

Metoda Monte Carlo cuantică

Metoda cuantică Monte Carlo este utilizată pe scară largă pentru a studia molecule complexe și solide. Acest nume combină mai multe metode diferite. Prima dintre acestea este metoda variațională Monte Carlo , care este în esență integrarea numerică a integralelor multidimensionale care apar la rezolvarea ecuației Schrödinger . Rezolvarea unei probleme care implică 1000 de electroni necesită luarea de integrale de 3000 dimensionale, iar în rezolvarea unor astfel de probleme, metoda Monte Carlo are un avantaj uriaș de performanță față de alte metode de integrare numerică . O altă variantă a metodei Monte Carlo este metoda Monte Carlo de difuzie .

Vezi și

Formula Feynman-Katz
Generatoare de numere pseudo-aleatoare
Las Vegas (algoritm)
Prelevarea de probe
AQUA@home
QMC@Home
QuantumFire
Problema cu aruncarea acului lui Buffon
Metoda de modelare entropică
algoritmul Wang-Landau
Folosind metoda Monte Carlo pentru a căuta copacul în timp ce jucați Go.

Note

↑ Math Surprises: An Example Arhivat la 30 ianuarie 2012 la Wayback Machine
↑ 1 2 A.Sala. Pe o determinare experimentală a lui Pi // The Messenger of Mathematics. - 1872. - Vol. 2. - P. 113-114.
↑ Fishman, 1996 , p. 344.
↑ Nicolae; metropolă. Metoda Monte Carlo (engleză) // Jurnalul Asociației Americane de Statistică : jurnal. - 1949. - Vol. 44 , nr. 247 . - P. 335-341 . — ISSN 0162-1459 . - doi : 10.2307/2280232 .
↑ Varfolomeev A.A., Svetlolobov I.A. ZhETF. 1959. V.36. s.1263-1270

Literatură

Metoda Sobol I. M. Monte Carlo . — M .: Nauka, 1968. — 64 p. - ( Prelegeri populare despre matematică ). - 79.000 de exemplare.
Articolul „Modelarea vieții”, autor Andrey Teplyakov
Metropolis, N. , Ulam, S. Metoda Monte Carlo, - Journal of the American Statistical Association 1949 44 nr.247 335-341.
Alex F Bielajew . Fundamentele metodei Monte Carlo pentru transportul particulelor neutre și încărcate. 2001
WMC Foulkes, L. Mitas, RJ Needs și G. Rajagopal Quantum Monte Carlo simulations of solides, — Reviews of Modern Physics 73 (2001) 33.
Articolul „Metropolis, Monte Carlo și MANIAC”
Fishman, George S. Monte Carlo: concepte, algoritmi și aplicații. - Springer, 1996. - ISBN 0-387-94527-X .

Dicționare și enciclopedii	mare danez Mare catalană mare chinezesc Mare norvegian Rusă mare Britannica (online)
În cataloagele bibliografice	GND : 4240945-7 J9U : 987007543534905171 LCCN : sh85087032 NDL : 00567842 NKC : ph122780

Metode de optimizare
Unidimensional	metoda secțiunii de aur Dihotomie Metoda parabolelor Căutare în grilă Metoda de căutare uniformă a blocurilor Metoda Fibonacci Căutare ternară metoda Piyavsky Metoda Strongin
Comanda zero	metoda Gauss Metoda Nelder-Mead Metoda Hook-Jeeves metoda Rosenbrock metoda Powell
Prima comanda	coborâre în gradient Metoda Zeutendijk Coordonarea coborârii Metoda gradientului conjugat Metode cvasi-newtoniene Algoritmul Levenberg-Marquardt
a doua comanda	metoda lui Newton Metoda Newton-Raphson Algoritmul Broyden-Fletcher-Goldfarb-Shanno (BFGS)
Stochastic	Metoda Monte Carlo Recoacere simulată Algoritmi evolutivi evolutie diferentiala Algoritmul furnicilor Metoda roiului de particule Algoritmul coloniilor de albine Metoda de mers aleatoriu
Metode de programare liniară	Metoda simplex algoritmul lui Gomori Metoda elipsoidă Metoda potențială
Metode de programare neliniară	Programare secvenţială pătratică