Monte Carlo metoden

Monte Carlo-metoder (MMC) är en grupp numeriska metoder för att studera slumpmässiga processer . Kärnan i metoden är som följer: processen beskrivs av en matematisk modell med hjälp av en slumpmässig variabel generator , modellen beräknas upprepade gånger, baserat på erhållna data, beräknas de probabilistiska egenskaperna för den aktuella processen. Till exempel, för att ta reda på med Monte Carlo-metoden vad som kommer att vara det genomsnittliga avståndet mellan två slumpmässiga punkter i en cirkel, måste du ta koordinaterna för ett stort antal slumpmässiga par av punkter inom gränserna för en given cirkel, beräkna avstånd för varje par, och beräkna sedan det aritmetiska medelvärdet för dem .

Metoder används för att lösa problem inom olika områden inom fysik , kemi , matematik , ekonomi , optimering , kontrollteori m.m.

Namnet på metoden kommer från området Monte Carlo , känt för sina kasinon.

Historik

Buffons metod för att bestämma Pi

Slumpvariabler har använts för att lösa olika tillämpade problem under lång tid. Ett exempel är metoden för att bestämma talet Pi , som föreslogs av Buffon redan 1777 . Kärnan i metoden var att kasta en nål lång på ett plan ritat av flera parallella räta linjer placerade på avstånd från varandra. Sannolikheten (under villkor eller på annat sätt ) att linjesegmentet skär linjen är relaterad till pi: $L$ $r$ $r>L$

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

var

$A$ - avståndet från början av nålen till den raka linjen närmast den;
$\theta$ - nålens vinkel relativt de raka linjerna.

Denna integral är lätt att ta: (förutsatt att ), därför, genom att räkna andelen segment som skär linjer, kan vi ungefär bestämma detta antal. När antalet försök ökar, kommer noggrannheten i resultatet att öka. $p={\frac {2L}{r\pi \,}}$ $r>L$

År 1864 genomförde kapten Fox, som återhämtade sig från ett sår, för att på något sätt sysselsätta sig själv, ett experiment med att kasta en nål [1] . Resultaten presenteras i följande tabell: [2]

	Antal kast	Antal korsningar	Nållängd	Avstånd mellan raka linjer	Rotation	Pi-värde	Fel
Första försöket	500	236	3	fyra	saknas	3,1780	+3,6⋅10 -2
Andra försöket	530	253	3	fyra	närvarande	3,1423	+7,0⋅10 -4
Tredje försöket	590	939	5	2	närvarande	3,1416	+4,7⋅10 -5

Kommentarer:

Längder är i tum.
Planrotation tillämpades (och som resultaten visar - framgångsrikt) för att minska det systematiska felet [2] .
I det tredje försöket var nålens längd större än avståndet mellan linjerna, vilket gjorde det möjligt att, utan att öka antalet kast, effektivt öka antalet händelser och förbättra noggrannheten (flera skärningar kunde inträffa i ett kast) .

Samband mellan stokastiska processer och differentialekvationer

Skapandet av den matematiska apparaten för stokastiska metoder började i slutet av 1800-talet. 1899 visade Lord Rayleigh att en endimensionell slumpmässig vandring på ett oändligt gitter kan ge en ungefärlig lösning av en typ av parabolisk differentialekvation [3] . Andrei Nikolaevich Kolmogorov 1931 gav en stor impuls till utvecklingen av stokastiska metoder för att lösa olika matematiska problem, eftersom han kunde bevisa att Markov-kedjor är relaterade till vissa integro-differentialekvationer . 1933 visade Ivan Georgievich Petrovsky att en slumpmässig promenad , som bildar en Markov-kedja , är asymptotiskt relaterad till lösningen av en elliptisk partiell differentialekvation . Efter dessa upptäckter blev det klart att stokastiska processer kan beskrivas med differentialekvationer och följaktligen undersökas med hjälp av välutvecklade matematiska metoder för att lösa dessa ekvationer vid den tiden.

Monte Carlo-metodens födelse i Los Alamos

Först Enrico Fermi på 1930 -talet i Italien, och sedan John von Neumann och Stanislaw Ulam på 1940 -talet i Los Alamos , föreslog att det var möjligt att använda kopplingen mellan stokastiska processer och differentialekvationer "i motsatt riktning". De föreslog att man skulle använda ett stokastiskt tillvägagångssätt för att approximera flerdimensionella integraler i transportekvationerna som uppstod i samband med problemet med neutronrörelser i ett isotropiskt medium.

Idén utvecklades av Ulam, som, medan han spelade patiens medan han återhämtade sig från en sjukdom, undrade vad sannolikheten var att patiens skulle fungera. Istället för att använda de vanliga kombinatoriska övervägandena för sådana problem , föreslog Ulam att man helt enkelt kunde köra experimentet ett stort antal gånger och, genom att räkna antalet framgångsrika resultat, uppskatta sannolikheten. Men på grund av behovet av att utföra ett stort antal av samma typ av experimentella åtgärder, användes metoden inte i stor utsträckning.

Med tillkomsten av den första elektroniska datorn , ENIAC , som kunde generera pseudoslumptal i hög hastighet och använda dem i matematiska modeller, uppstod ett nytt intresse för stokastiska metoder. Stanisław Ulam diskuterade sina idéer med John von Neumann , som så småningom använde ENIAC för Ulams föreslagna statistiska urvalsmetod för att lösa olika problem med neutrontransport [4] . På grund av behovet av att stänga av ENIAC under en betydande tid i slutet av 1946, utvecklade Enrico Fermi till och med en specialiserad analog dator för att fortsätta forskningen om neutroners rörelse , som fick namnet FERMIAC (i analogi med ENIAC, men med en indikation på Fermis författarskap), som också var på en mekanisk nivå, implementeras Monte Carlo-metoden.

Efter början av användningen av datorer skedde ett stort genombrott, och Monte Carlo-metoden tillämpades i många problem, för vilka det stokastiska tillvägagångssättet visade sig vara mer effektivt än andra matematiska metoder. Användningen av en sådan teknik hade dock också sina begränsningar på grund av behovet av ett mycket stort antal beräkningar för att få resultat med hög noggrannhet.

Födelseåret för termen "Monte Carlo-metoden" anses vara 1949, då artikeln "Monte Carlo-metoden" av Metropolis och Ulam publicerades. Namnet på metoden kommer från namnet på kommunen i Furstendömet Monaco , allmänt känd för sina många kasinon , eftersom roulette är en av de mest kända slumptalsgeneratorerna . Stanislav Ulam skriver i sin självbiografi The Adventures of a Mathematician att namnet föreslogs av Nicholas Metropolis för att hedra sin farbror som var en spelare.

Vidareutveckling och modernitet

På 1950 -talet användes metoden för beräkningar vid utvecklingen av vätebomben. De viktigaste fördelarna med utvecklingen av metoden vid denna tidpunkt tillhör de anställda vid laboratorierna i det amerikanska flygvapnet och RAND-företaget . De sovjetiska fysikerna A. A. Varfolomeev och I. A. Svetlolobov [5] var bland de första som använde Monte Carlo-metoden för att beräkna partikelskurar .

På 1970 -talet , inom ett nytt matematikfält - teorin om beräkningskomplexitet , visades det att det finns en klass av problem vars komplexitet (antalet beräkningar som krävs för att få ett exakt svar) växer exponentiellt med problemets dimension . Ibland är det möjligt, för att offra noggrannhet, att hitta en algoritm vars komplexitet växer långsammare, men det finns ett stort antal problem för vilka detta inte kan göras (till exempel problemet med att bestämma volymen av en konvex kropp i n -dimensionell Det euklidiska rummet, och om det är generaliserat, då i allmänhet beräkningen av n -dimensionella integraler) och Monte Carlo-metoden är det enda sättet att få ett tillräckligt korrekt svar inom rimlig tid.

För närvarande är forskarnas huvudsakliga ansträngningar inriktade på att skapa effektiva Monte Carlo-algoritmer för olika fysiska, kemiska och sociala processer för parallella datorsystem .

Monte Carlo integration

Anta att vi måste ta integralen av någon funktion. Vi kommer att använda en informell geometrisk beskrivning av integralen och förstå den som arean under grafen för denna funktion.

För att bestämma detta område kan du använda en av de vanliga numeriska integrationsmetoderna : dela upp segmentet i undersegment, beräkna arean under grafen för funktionen på var och en av dem och lägg till. Antag att för funktionen som visas i figur 2 räcker det att dela upp i 25 segment och därför beräkna 25 funktionsvärden. Föreställ dig nu, vi har att göra med -dimensionell funktion. Då behöver vi segment och samma antal beräkningar av funktionsvärdet. När dimensionen på funktionen är större än 10 blir uppgiften enorm. Eftersom högdimensionella utrymmen påträffas, i synnerhet i problem med strängteori , såväl som många andra fysiska problem där det finns system med många frihetsgrader, är det nödvändigt att ha en lösningsmetod vars beräkningskomplexitet inte skulle bero så mycket på dimension. Detta är egenskapen hos Monte Carlo-metoden. $n$ $25^{n}$

Den vanliga Monte Carlo-integreringsalgoritmen

Anta att du vill beräkna en bestämd integral

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

Betrakta en slumpvariabel likformigt fördelad på integrationsintervallet . Då blir det också en slumpvariabel, och dess matematiska förväntan uttrycks som $u$ $[a,b]$ $f(u)$

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

var är fördelningsdensiteten för den slumpmässiga variabeln , som är lika med . Således uttrycks den önskade integralen som $\varphi(x)$ $u$ ${\frac {1}{ba}}$ $[a,b]$

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

men den matematiska förväntningen på en slumpvariabel kan lätt uppskattas genom att modellera denna slumpvariabel och beräkna urvalets medelvärde. $f(u)$

Så vi kastar poäng jämnt fördelade på , för varje poäng vi beräknar . Sedan beräknar vi stickprovets medelvärde: . Som ett resultat får vi uppskattningen av integralen: $N$ $[a,b]$ $u_{i}$ $f(u_{i})$ ${\frac {1}{N}}\sum _{{i=1}}^{{N}}f(u_{i})$

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

Uppskattningens noggrannhet beror endast på antalet poäng . $N$

Denna metod har också en geometrisk tolkning. Det är mycket likt den deterministiska metoden som beskrivs ovan, med skillnaden att istället för att enhetligt dela upp integrationsregionen i små intervall och summera områdena för de resulterande "kolumnerna", kastar vi slumpmässiga punkter på integrationsregionen, på var och en av dem vi bygger samma "kolumn", bestämmer dess bredd som , och summerar deras områden. ${\frac {ba}{N}}$

Geometrisk algoritm för Monte Carlo-integration

För att bestämma arean under funktionsdiagrammet kan du använda följande stokastiska algoritm:

vi begränsar funktionen till en rektangel (en n - dimensionell parallellepiped i fallet med många dimensioner), vars area lätt kan beräknas; vilken sida av rektangeln som helst innehåller minst 1 punkt i grafen för funktionen, men skär den inte; $Mast}}$
"klottra" i denna rektangel (parallellepipedum) ett visst antal punkter ( bitar), vars koordinater vi kommer att välja slumpmässigt; $N$
bestämma antalet punkter ( bitar) som faller under funktionens graf; $K$
området för regionen som begränsas av funktionen och koordinataxlarna ges av $S$ $S=S_{{par}}{\frac {K}{N}}$

För ett litet antal dimensioner av den integrerbara funktionen är prestandan för Monte Carlo-integration mycket lägre än prestandan för deterministiska metoder. Men i vissa fall, när funktionen är specificerad implicit, men det är nödvändigt att bestämma arean specificerad i form av komplexa ojämlikheter, kan den stokastiska metoden vara mer att föredra.

Användning av signifikanssampling

Med samma antal slumpmässiga poäng kan noggrannheten i beräkningarna ökas genom att föra området som begränsar den önskade funktionen närmare själva funktionen. För att göra detta är det nödvändigt att använda slumpvariabler med en fördelning vars form är så nära som möjligt formen på den integrerbara funktionen. En av metoderna för att förbättra konvergensen i Monte Carlo-beräkningar bygger på detta: signifikanssampling .

Optimering

Olika varianter av Monte Carlo-metoden kan användas för att lösa optimeringsproblem. Till exempel glödgningssimuleringsalgoritmen .

Tillämpningar i fysik

Datorsimulering spelar en viktig roll i modern fysik och Monte Carlo-metoden är en av de vanligaste inom många områden från kvantfysik till fasta tillståndets fysik, plasmafysik och astrofysik.

Metropolis algoritm

Traditionellt har Monte Carlo-metoden använts för att bestämma olika fysikaliska parametrar för system i termodynamisk jämvikt. Antag att det finns en uppsättning möjliga tillstånd i det fysiska systemet . För att bestämma medelvärdet av en viss kvantitet , är det nödvändigt att beräkna , där summeringen utförs över alla tillstånd från , är sannolikheten för tillståndet . $W(S)$ $S$ $\overline {A}$ $A$ $\overline {A}=\summa _{{S}}A(S)P(S)$ $S$ $W(S)$ $P(S)$ $S$

Dynamisk (kinetisk) formulering

Direkt Monte Carlo-simulering

Direkt Monte Carlo-simulering av någon fysisk process involverar modellering av beteendet hos enskilda elementära delar av ett fysiskt system. I huvudsak är denna direkta modellering nära att lösa problemet från första principer , men vanligtvis, för att påskynda beräkningar, är det tillåtet att använda alla fysiska approximationer. Ett exempel är beräkningen av olika processer med metoden för molekylär dynamik : å ena sidan beskrivs systemet genom beteendet hos dess elementära komponenter, å andra sidan är interaktionspotentialen som används ofta empirisk .

Exempel på direkt Monte Carlo-simulering:

Simulering av bestrålning av fasta ämnen med joner i approximationen av binära kollisioner.
Direkt Monte Carlo-simulering av förtärnade gaser.
De flesta kinetiska Monte Carlo-modeller är bland de direkta (särskilt studien av molekylär strålepitaxi ).

Quantum Monte Carlo-metoden

Kvantmetoden Monte Carlo används ofta för att studera komplexa molekyler och fasta ämnen. Detta namn kombinerar flera olika metoder. Den första av dessa är den variationsmässiga Monte Carlo-metoden , som i huvudsak är den numeriska integrationen av flerdimensionella integraler som uppstår när man löser Schrödinger-ekvationen . Att lösa ett problem som involverar 1000 elektroner kräver att man tar 3000-dimensionella integraler, och för att lösa sådana problem har Monte Carlo-metoden en enorm prestandafördel jämfört med andra numeriska integrationsmetoder . En annan variant av Monte Carlo - metoden är diffusions - Monte Carlo - metoden .

Se även

Feynman-Katz formel
Pseudo-slumptalsgeneratorer
Las Vegas (algoritm)
Provtagning
AQUA@home
QMC@Home
QuantumFire
Buffons nålkastningsproblem
Entropisk modelleringsmetod
Wang-Landau algoritm
Använder Monte Carlo-metoden för att söka i trädet medan du spelar Go.

Anteckningar

↑ Math Surprises: Ett exempel arkiverat 30 januari 2012 på Wayback Machine
↑ 1 2 A.Hall. Om en experimentell bestämning av Pi // The Messenger of Mathematics. - 1872. - Vol. 2. - S. 113-114.
↑ Fishman, 1996 , sid. 344.
↑ Nicholas; metropol. Monte Carlo-metoden (engelska) // Journal of the American Statistical Association : tidskrift. - 1949. - Vol. 44 , nr. 247 . - s. 335-341 . — ISSN 0162-1459 . - doi : 10.2307/2280232 .
↑ Varfolomeev A.A., Svetlolobov I.A. ZhETF. 1959. V.36. s.1263-1270

Litteratur

Sobol I. M. Monte Carlo-metoden . — M .: Nauka, 1968. — 64 sid. - ( Populära föreläsningar om matematik ). - 79 000 exemplar.
Artikel "Modellliv", författare Andrey Teplyakov
Metropolis, N. , Ulam, S. Monte Carlo-metoden, - Journal of the American Statistical Association 1949 44 nr 247 335-341.
Alex F Bielajew . Grunderna i Monte Carlo-metoden för neutral och laddad partikeltransport. 2001
WMC Foulkes, L. Mitas, RJ Needs och G. Rajagopal Quantum Monte Carlo simuleringar av fasta ämnen, — Reviews of Modern Physics 73 (2001) 33.
Artikel "Metropolis, Monte Carlo och MANIAC"
Fishman, George S. Monte Carlo: koncept, algoritmer och tillämpningar. - Springer, 1996. - ISBN 0-387-94527-X .

Ordböcker och uppslagsverk	Stor dansk Stor katalanska stor kines Stor norsk Stor ryss Britannica (online)
I bibliografiska kataloger	GND : 4240945-7 J9U : 987007543534905171 LCCN : sh85087032 NDL : 00567842 NKC : ph122780

Optimeringsmetoder _
En-dimensionell	gyllene snittmetoden Dikotomi Parabolmetoden Rutnätssökning Enhetlig blocksökningsmetod Fibonacci-metoden Ternär sökning Piyavsky-metoden Strongin metod
Noll ordning	Gauss metod Nelder-Mead metod Hook-Jeeves metod Rosenbrock-metoden Powell metod
Första beställning	lutning nedstigning Zeutendijk-metoden Koordinera nedstigning Konjugerad gradientmetod Kvasi-newtonska metoder Levenberg-Marquardts algoritm
andra beställning	Newtons metod Newton-Raphson-metoden Broyden-Fletcher-Goldfarb-Shanno-algoritm (BFGS)
Stokastisk	Monte Carlo metoden Simulerad glödgning Evolutionära algoritmer differentiell evolution Myralgoritm Partikelsvärmmetod Algoritm för bikoloni Random walk-metod
Linjära programmeringsmetoder _	Enkel metod Gomoris algoritm Ellipsoid metod Potentiell metod
Icke -linjära programmeringsmetoder	Sekventiell kvadratisk programmering