Monte Carlo metode

Monte Carlo metoder (MMC) er en gruppe af numeriske metoder til at studere tilfældige processer . Essensen af metoden er som følger: Processen er beskrevet af en matematisk model ved hjælp af en tilfældig variabel generator , modellen beregnes gentagne gange, baseret på de opnåede data, de sandsynlige egenskaber for den betragtede proces beregnes. For eksempel, for at finde ud af ved Monte Carlo-metoden, hvad der vil være den gennemsnitlige afstand mellem to tilfældige punkter i en cirkel, skal du tage koordinaterne for et stort antal tilfældige par af punkter inden for grænserne af en given cirkel, beregne afstand for hvert par, og beregn derefter det aritmetiske middelværdi for dem .

Metoder bruges til at løse problemer inden for forskellige områder inden for fysik , kemi , matematik , økonomi , optimering , kontrolteori mv.

Navnet på metoden kommer fra området Monte Carlo , der er berømt for sine kasinoer.

Historie

Buffons metode til at bestemme Pi

Tilfældige variable er blevet brugt til at løse forskellige anvendte problemer i lang tid. Et eksempel er metoden til at bestemme tallet Pi , som blev foreslået af Buffon tilbage i 1777 . Essensen af metoden var at kaste en nål lang på et plan tegnet af flere parallelle lige linjer placeret i en afstand fra hinanden. Sandsynligheden (under betingelsen eller på anden måde ) for at linjestykket skærer linjen er relateret til pi: $L$ $r$ $r>L$

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

hvor

$EN$ - afstanden fra begyndelsen af nålen til den lige linje nærmest den;
$\theta$ - nålens vinkel i forhold til de lige linjer.

Dette integral er let at tage: (forudsat at ), derfor, ved at tælle andelen af segmenter, der skærer linjer, kan vi omtrent bestemme dette tal. Efterhånden som antallet af forsøg stiger, vil nøjagtigheden af resultatet stige. $p={\frac {2L}{r\pi \,}}$ $r>L$

I 1864 gennemførte kaptajn Fox, der kom sig over et sår, for på en eller anden måde at beskæftige sig selv, et eksperiment med at kaste en nål [1] . Resultaterne er præsenteret i følgende tabel: [2]

	Antal kast	Antal kryds	Nåle længde	Afstand mellem lige linjer	Rotation	Pi værdi	Fejl
Første forsøg	500	236	3	fire	mangler	3,1780	+3,6⋅10 -2
Andet forsøg	530	253	3	fire	til stede	3,1423	+7,0⋅10 -4
Tredje forsøg	590	939	5	2	til stede	3,1416	+4,7⋅10 -5

Kommentarer:

Længder er i tommer.
Planrotation blev anvendt (og som resultaterne viser - med succes) for at reducere den systematiske fejl [2] .
I det tredje forsøg var nålens længde større end afstanden mellem linjerne, hvilket gjorde det muligt, uden at øge antallet af kast, effektivt at øge antallet af begivenheder og forbedre nøjagtigheden (flere skæringspunkter kunne forekomme i et kast) .

Forholdet mellem stokastiske processer og differentialligninger

Skabelsen af det matematiske apparat for stokastiske metoder begyndte i slutningen af det 19. århundrede. I 1899 viste Lord Rayleigh , at en endimensionel tilfældig gang på et uendeligt gitter kan give en omtrentlig løsning af én slags parabolsk differentialligning [3] . Andrei Nikolaevich Kolmogorov i 1931 gav en stor impuls til udviklingen af stokastiske tilgange til at løse forskellige matematiske problemer, da han var i stand til at bevise, at Markov-kæder er relateret til visse integro-differentialligninger . I 1933 viste Ivan Georgievich Petrovsky , at en tilfældig gåtur , der danner en Markov-kæde , er asymptotisk relateret til løsningen af en elliptisk partiel differentialligning . Efter disse opdagelser blev det klart, at stokastiske processer kan beskrives ved differentialligninger og følgelig undersøges ved hjælp af veludviklede matematiske metoder til at løse disse ligninger på det tidspunkt.

Fødslen af Monte Carlo-metoden i Los Alamos

Først Enrico Fermi i 1930'erne i Italien, og derefter John von Neumann og Stanislaw Ulam i 1940'erne ved Los Alamos , foreslog, at det var muligt at bruge forbindelsen mellem stokastiske processer og differentialligninger "i den modsatte retning". De foreslog at bruge en stokastisk tilgang til at tilnærme multidimensionelle integraler i de transportligninger, der opstod i forbindelse med problemet med neutronbevægelser i et isotropt medium.

Ideen blev udviklet af Ulam, som, mens han spillede kabale , mens han kom sig over en sygdom, undrede sig over, hvad sandsynligheden var for, at kabale ville fungere. I stedet for at bruge de sædvanlige kombinatoriske overvejelser til sådanne problemer , foreslog Ulam, at man simpelthen kunne køre eksperimentet et stort antal gange og ved at tælle antallet af vellykkede resultater estimere sandsynligheden. Men på grund af behovet for at udføre et stort antal af den samme type eksperimentelle handlinger, blev metoden ikke udbredt.

Med fremkomsten af den første elektroniske computer , ENIAC , som kunne generere pseudo-tilfældige tal med stor hastighed og bruge dem i matematiske modeller, var der fornyet interesse for stokastiske metoder. Stanisław Ulam diskuterede sine ideer med John von Neumann , som til sidst brugte ENIAC til Ulams foreslåede statistiske udvælgelsesmetode til at løse forskellige problemer med neutrontransport [4] . På grund af behovet for at slukke ENIAC i en længere periode i slutningen af 1946, udviklede Enrico Fermi endda en specialiseret analog computer til at fortsætte forskningen i neutronernes bevægelse , som fik navnet FERMIAC (i analogi med ENIAC, men med en indikation af Fermis forfatterskab), som også var på et mekanisk niveau, er Monte Carlo-metoden implementeret.

Efter begyndelsen af brugen af computere var der et stort gennembrud, og Monte Carlo-metoden blev anvendt i mange problemer, hvor den stokastiske tilgang viste sig at være mere effektiv end andre matematiske metoder. Brugen af en sådan teknik havde dog også sine begrænsninger på grund af behovet for et meget stort antal beregninger for at opnå resultater med høj nøjagtighed.

Fødselsåret for udtrykket "Monte Carlo-metoden" anses for at være 1949, da artiklen "Monte Carlo-metoden" af Metropolis og Ulam blev offentliggjort. Navnet på metoden kommer fra navnet på kommunen i Fyrstendømmet Monaco , der er kendt for sine mange kasinoer , da roulette er en af de mest kendte tilfældige talgeneratorer . Stanislav Ulam skriver i sin selvbiografi The Adventures of a Mathematician, at navnet blev foreslået af Nicholas Metropolis til ære for sin onkel, der var en gambler.

Videreudvikling og modernitet

I 1950'erne blev metoden brugt til beregninger i udviklingen af brintbomben. De vigtigste fordele i udviklingen af metoden på dette tidspunkt tilhører de ansatte i laboratorierne i det amerikanske luftvåben og RAND-selskabet . De sovjetiske fysikere A. A. Varfolomeev og I. A. Svetlolobov [5] var blandt de første til at bruge Monte Carlo-metoden til at beregne partikelbyger .

I 1970'erne , i et nyt felt af matematik - teorien om beregningsmæssig kompleksitet , blev det vist, at der er en klasse af problemer, hvis kompleksitet (antallet af beregninger, der kræves for at opnå et nøjagtigt svar) vokser eksponentielt med problemets dimension . Nogle gange er det muligt, for at ofre nøjagtigheden, at finde en algoritme, hvis kompleksitet vokser langsommere, men der er et stort antal problemer, som dette ikke kan gøres for (for eksempel problemet med at bestemme volumenet af en konveks krop i n -dimensional Euklidisk rum, og hvis det generaliseres, så generelt er beregningen af n - dimensionelle integraler) og Monte Carlo-metoden den eneste måde at opnå et tilstrækkeligt præcist svar på inden for rimelig tid.

I øjeblikket er forskernes hovedindsats rettet mod at skabe effektive Monte Carlo-algoritmer til forskellige fysiske, kemiske og sociale processer til parallelle computersystemer .

Monte Carlo integration

Antag, at vi skal tage integralet af en eller anden funktion. Vi vil bruge en uformel geometrisk beskrivelse af integralet og forstå det som arealet under denne funktions graf.

For at bestemme dette område kan du bruge en af de sædvanlige numeriske integrationsmetoder : opdel segmentet i undersegmenter, beregn arealet under grafen for funktionen på hver af dem og tilføj. Antag, at for funktionen vist i figur 2 er det nok at opdele i 25 segmenter og derfor beregne 25 funktionsværdier. Forestil dig nu, vi har at gøre med -dimensionel funktion. Så skal vi bruge segmenter og det samme antal beregninger af funktionsværdien. Når dimensionen af funktionen er større end 10, bliver opgaven enorm. Da man støder på højdimensionelle rum, især i problemer med strengteori , såvel som mange andre fysiske problemer, hvor der er systemer med mange frihedsgrader, er det nødvendigt at have en løsningsmetode, hvis beregningsmæssige kompleksitet ikke vil afhænge så meget på dimension. Dette er Monte Carlo-metodens egenskab. $n$ $25^{n}$

Den sædvanlige Monte Carlo integrationsalgoritme

Antag, at du vil beregne et bestemt integral

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

Betragt en tilfældig variabel ensartet fordelt på integrationsintervallet . Så vil det også være en tilfældig variabel, og dens matematiske forventning er udtrykt som $u$ $[a,b]$ $f(u)$

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

hvor er fordelingstætheden af den stokastiske variabel , som er lig med . Det ønskede integral er således udtrykt som $\varphi(x)$ $u$ ${\frac {1}{ba}}$ $[a,b]$

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

men den matematiske forventning til en tilfældig variabel kan let estimeres ved at modellere denne tilfældige variabel og beregne stikprøvegennemsnittet. $f(u)$

Så vi kaster point ensartet fordelt på , for hvert punkt vi beregner . Derefter beregner vi stikprøvegennemsnittet: . Som et resultat opnår vi estimatet af integralet: $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_{ jeg}).

Estimationsnøjagtigheden afhænger kun af antallet af point . $N$

Denne metode har også en geometrisk fortolkning. Det minder meget om den deterministiske metode beskrevet ovenfor, med den forskel, at i stedet for ensartet at opdele integrationsregionen i små intervaller og opsummere arealerne af de resulterende "kolonner", kaster vi tilfældige punkter på integrationsregionen, på hver af disse. vi bygger den samme "søjle", bestemmer dens bredde som , og summerer deres arealer. ${\frac {ba}{N}}$

Geometrisk algoritme til Monte Carlo-integration

For at bestemme arealet under funktionsgrafen kan du bruge følgende stokastiske algoritme:

vi begrænser funktionen til et rektangel (et n - dimensionelt parallelepipedum i tilfælde af mange dimensioner), hvis areal let kan beregnes; enhver side af rektanglet indeholder mindst 1 punkt af funktionens graf, men skærer den ikke; $S_{{par}}$
"skrive" ind i dette rektangel (parallellepipedum) et bestemt antal punkter ( stykker), hvis koordinater vi vil vælge tilfældigt; $N$
bestemme antallet af punkter ( stykker), der falder ind under funktionens graf; $K$
arealet af området afgrænset af funktionen og koordinatakserne er givet af $S$ $S=S_{{par}}{\frac {K}{N}}$

For et lille antal dimensioner af den integrerbare funktion er ydelsen af Monte Carlo-integration meget lavere end ydelsen af deterministiske metoder. Men i nogle tilfælde, når funktionen er specificeret implicit, men det er nødvendigt at bestemme området specificeret i form af komplekse uligheder, kan den stokastiske metode være mere at foretrække.

Brug af signifikanssampling

Med det samme antal tilfældige punkter kan nøjagtigheden af beregninger øges ved at bringe området, der begrænser den ønskede funktion, tættere på selve funktionen. For at gøre dette er det nødvendigt at bruge tilfældige variable med en fordeling, hvis form er så tæt som muligt på formen af den integrerbare funktion. En af metoderne til at forbedre konvergensen i Monte Carlo-beregninger er baseret på dette: signifikansprøvetagning .

Optimering

Forskellige variationer af Monte Carlo-metoden kan bruges til at løse optimeringsproblemer. For eksempel annealing simuleringsalgoritmen .

Ansøgninger i fysik

Computersimulering spiller en vigtig rolle i moderne fysik, og Monte Carlo-metoden er en af de mest almindelige på mange områder fra kvantefysik til faststoffysik, plasmafysik og astrofysik.

Metropolis algoritme

Traditionelt er Monte Carlo-metoden blevet brugt til at bestemme forskellige fysiske parametre for systemer i termodynamisk ligevægt. Antag, at der er et sæt af mulige tilstande i det fysiske system . For at bestemme gennemsnitsværdien af en vis mængde , er det nødvendigt at beregne , hvor summeringen udføres over alle tilstande fra , er sandsynligheden for tilstanden . $W(S)$ $S$ $\overline {A}$ $EN$ $\overline {A}=\sum _{{S}}A(S)P(S)$ $S$ $W(S)$ $P(S)$ $S$

Dynamisk (kinetisk) formulering

Direkte Monte Carlo-simulering

Direkte Monte Carlo-simulering af enhver fysisk proces involverer modellering af adfærden af individuelle elementære dele af et fysisk system. I det væsentlige er denne direkte modellering tæt på at løse problemet ud fra de første principper , men normalt, for at fremskynde beregninger, er det tilladt at bruge enhver fysisk tilnærmelse. Et eksempel er beregningen af forskellige processer ved hjælp af metoden molekylær dynamik : på den ene side beskrives systemet gennem opførselen af dets elementære komponenter, på den anden side er det anvendte interaktionspotentiale ofte empirisk .

Eksempler på direkte Monte Carlo-simulering:

Simulering af bestråling af faste stoffer med ioner ved tilnærmelse af binære kollisioner.
Direkte Monte Carlo-simulering af forædlede gasser.
De fleste kinetiske Monte Carlo-modeller er blandt de direkte (især studiet af molekylær stråleepitaxi ).

Quantum Monte Carlo metode

Kvante Monte Carlo-metoden er meget brugt til at studere komplekse molekyler og faste stoffer. Dette navn kombinerer flere forskellige metoder. Den første af disse er den variationelle Monte Carlo-metode , som i det væsentlige er den numeriske integration af multidimensionelle integraler, der opstår ved løsning af Schrödinger-ligningen . At løse et problem, der involverer 1000 elektroner, kræver at man tager 3000-dimensionelle integraler, og ved at løse sådanne problemer har Monte Carlo-metoden en enorm ydeevnefordel i forhold til andre numeriske integrationsmetoder . En anden variation af Monte Carlo metoden er diffusions Monte Carlo metoden .

Se også

Feynman-Katz formel
Pseudo-tilfældige tal generatorer
Las Vegas (algoritme)
Prøveudtagning
AQUA@home
QMC@Home
QuantumFire
Buffons nålekastningsproblem
Entropisk modelleringsmetode
Wang-Landau algoritme
Brug af Monte Carlo-metoden til at søge i træet, mens du spiller Go.

Noter

↑ Math Surprises: An Example Arkiveret 30. januar 2012 på Wayback Machine
↑ 1 2 A.Hall. Om en eksperimentel bestemmelse af Pi // The Messenger of Mathematics. - 1872. - Bd. 2. - S. 113-114.
↑ Fishman, 1996 , s. 344.
↑ Nicholas; metropol. Monte Carlo-metoden (engelsk) // Journal of the American Statistical Association : tidsskrift. - 1949. - Bd. 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 s. - ( Populære foredrag om matematik ). - 79.000 eksemplarer.
Artikel "Modellerliv", forfatter Andrey Teplyakov
Metropolis, N. , Ulam, S. The Monte Carlo Method, - Journal of the American Statistical Association 1949 44 nr. 247 335-341.
Alex F Bielajew . Fundamentalerne i Monte Carlo-metoden til neutral og ladet partikeltransport. 2001
WMC Foulkes, L. Mitas, RJ Needs og G. Rajagopal Quantum Monte Carlo simuleringer af faste stoffer, — Reviews of Modern Physics 73 (2001) 33.
Artikel "Metropolis, Monte Carlo og MANIAC"
Fishman, George S. Monte Carlo: koncepter, algoritmer og applikationer. - Springer, 1996. - ISBN 0-387-94527-X .

Ordbøger og encyklopædier	Flot dansk Fantastisk catalansk stor kinesisk Fantastisk norsk Stor russer Britannica (online)
I bibliografiske kataloger	GND : 4240945-7 J9U : 987007543534905171 LCCN : sh85087032 NDL : 00567842 NKC : ph122780

Optimeringsmetoder _
Endimensionel	gyldne snit metode Modsætning Parabel metode Netsøgning Ensartet bloksøgningsmetode Fibonacci metode Ternær søgning Piyavsky metode Strongin metode
Nul orden	Gauss metode Nelder-Mead metode Hook-Jeeves metode Rosenbrock metode Powell metode
Første ordre	gradient nedstigning Zeutendijk metode Koordinat nedstigning Konjugeret gradientmetode Kvasi-newtonske metoder Levenberg-Marquardt algoritme
anden orden	Newtons metode Newton-Raphson metode Broyden-Fletcher-Goldfarb-Shanno-algoritme (BFGS)
Stokastisk	Monte Carlo metode Simuleret udglødning Evolutionære algoritmer differentiel evolution Myre-algoritme Partikelsværmmetode Algorithme for bikoloni Tilfældig gå-metode
Lineære programmeringsmetoder _	Enkel metode Gomoris algoritme Ellipsoid metode Potentielle metode
Ikke-lineære programmeringsmetoder	Sekventiel kvadratisk programmering