Metoda Monte Carlo

Metody Monte Carlo (MMC) jsou skupinou numerických metod pro studium náhodných procesů . Podstata metody je následující: proces je popsán matematickým modelem pomocí generátoru náhodných veličin , model je opakovaně vypočítáván, na základě získaných dat jsou vypočteny pravděpodobnostní charakteristiky uvažovaného procesu. Chcete-li například metodou Monte Carlo zjistit, jaká bude průměrná vzdálenost mezi dvěma náhodnými body v kruhu, musíte vzít souřadnice velkého počtu náhodných dvojic bodů v hranicích daného kruhu, vypočítat vzdálenost pro každý pár a poté pro ně vypočítejte aritmetický průměr .

Metody se používají k řešení problémů v různých oblastech fyziky , chemie , matematiky , ekonomie , optimalizace , teorie řízení atd.

Název metody pochází z oblasti Monte Carlo , která je známá svými kasiny.

Historie

Buffonova metoda pro stanovení Pi

Náhodné proměnné se již dlouhou dobu používají k řešení různých aplikovaných problémů. Příkladem je metoda pro určení čísla Pi , kterou navrhl Buffon již v roce 1777 . Podstatou metody bylo hodit dlouhou jehlu na rovinu nakreslenou několika rovnoběžnými přímkami umístěnými ve vzdálenosti od sebe. Pravděpodobnost (za podmínky nebo jinak ), že úsečka protíná přímku, souvisí s pí: $L$ $r$ $r>L$

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

kde

$A$ - vzdálenost od začátku jehly k nejbližší přímce;
$\theta$ - úhel jehly vzhledem k přímkám.

Tento integrál je snadné vzít: (za předpokladu, že ), takže spočítáním podílu úseček protínajících úsečky můžeme toto číslo přibližně určit. S rostoucím počtem pokusů se zvyšuje přesnost výsledku. $p={\frac {2L}{r\pi \,}}$ $r>L$

V roce 1864 provedl kapitán Fox, zotavující se ze zranění, aby se nějak zaměstnal, experiment s házením jehly [1] . Výsledky jsou uvedeny v následující tabulce: [2]

	Počet hodů	Počet křižovatek	Délka jehly	Vzdálenost mezi přímkami	Otáčení	Hodnota pí	Chyba
První pokus	500	236	3	čtyři	chybějící	3,1780	+3,6⋅10 -2
Druhý pokus	530	253	3	čtyři	současnost, dárek	3,1423	+7,0⋅10 -4
Třetí pokus	590	939	5	2	současnost, dárek	3,1416	+4,7⋅10 -5

komentáře:

Délky jsou v palcích.
Rotace roviny byla aplikována (a jak ukazují výsledky - úspěšně) za účelem snížení systematické chyby [2] .
Ve třetím pokusu byla délka jehly větší než vzdálenost mezi čarami, což umožnilo bez zvýšení počtu hodů efektivně zvýšit počet událostí a zlepšit přesnost (při jednom hodu mohlo dojít k několika průsečíkům) .

Vztah mezi stochastickými procesy a diferenciálními rovnicemi

Vytváření matematického aparátu stochastických metod začalo na konci 19. století. V roce 1899 Lord Rayleigh ukázal, že jednorozměrná náhodná procházka po nekonečné mřížce může poskytnout přibližné řešení jednoho druhu parabolické diferenciální rovnice [3] . Andrei Nikolaevich Kolmogorov v roce 1931 dal velký impuls k rozvoji stochastických přístupů k řešení různých matematických problémů, protože byl schopen dokázat, že Markovovy řetězce souvisí s určitými integro-diferenciálními rovnicemi . V roce 1933 Ivan Georgievich Petrovsky ukázal, že náhodná procházka , tvořící Markovův řetězec , asymptoticky souvisí s řešením eliptické parciální diferenciální rovnice . Po těchto objevech se ukázalo, že stochastické procesy lze popsat diferenciálními rovnicemi a v souladu s tím je zkoumat pomocí v té době dobře vyvinutých matematických metod řešení těchto rovnic.

Zrození metody Monte Carlo v Los Alamos

Nejprve Enrico Fermi ve 30. letech v Itálii a poté John von Neumann a Stanislaw Ulam ve 40. letech v Los Alamos navrhli, že je možné použít spojení mezi stochastickými procesy a diferenciálními rovnicemi „v opačném směru“. Navrhli použít stochastický přístup k aproximaci vícerozměrných integrálů v transportních rovnicích, které vyvstaly v souvislosti s problémem pohybu neutronů v izotropním prostředí.

Nápad byl vyvinut Ulamem, který při hraní solitaire , když se zotavoval z nemoci, přemýšlel, jaká je pravděpodobnost, že solitaire vyjde. Namísto použití obvyklých kombinatorických úvah pro takové problémy , Ulam navrhl, že by bylo možné experiment jednoduše spustit mnohokrát a počítáním počtu úspěšných výsledků odhadnout pravděpodobnost. Ale kvůli potřebě provádět velké množství stejného typu experimentálních akcí, metoda nebyla široce používána.

S příchodem prvního elektronického počítače , ENIAC , který mohl generovat pseudonáhodná čísla velkou rychlostí a používat je v matematických modelech, tam byl obnovený zájem o stochastické metody. Stanisław Ulam diskutoval o svých nápadech s Johnem von Neumannem , který nakonec použil ENIAC pro Ulamovu navrhovanou metodu statistického výběru při řešení různých problémů transportu neutronů [4] . Kvůli potřebě vypnout ENIAC na značnou dobu na konci roku 1946 Enrico Fermi dokonce vyvinul specializovaný analogový počítač pro pokračování výzkumu pohybu neutronů , který dostal jméno FERMIAC (analogicky s ENIAC, ale s označení Fermiho autorství), které bylo i na mechanické úrovni, je implementována metoda Monte Carlo.

Po začátku používání počítačů došlo k velkému průlomu a metoda Monte Carlo byla aplikována v mnoha problémech, u kterých se stochastický přístup ukázal jako efektivnější než jiné matematické metody. Použití takové techniky však mělo také svá omezení kvůli nutnosti velmi velkého počtu výpočtů pro získání výsledků s vysokou přesností.

Za rok zrodu termínu „metoda Monte Carlo“ je považován rok 1949, kdy byl publikován článek „Metoda Monte Carlo“ od Metropolis a Ulam. Název metody pochází z názvu obce v Monackém knížectví , která je široce známá svými četnými kasiny , protože ruleta je jedním z nejznámějších generátorů náhodných čísel . Stanislav Ulam ve své autobiografii The Adventures of a Matematician píše, že jméno navrhl Nicholas Metropolis na počest svého strýce, který byl hazardním hráčem.

Další vývoj a modernost

V 50. letech 20. století byla metoda použita pro výpočty při vývoji vodíkové bomby. Hlavní zásluhy na vývoji metody mají v této době pracovníci laboratoří amerického letectva a korporace RAND . Sovětští fyzici A. A. Varfolomeev a I. A. Svetlolobov [5] byli jedni z prvních, kteří použili metodu Monte Carlo pro výpočet sprch částic .

V 70. letech 20. století se v novém oboru matematiky – v teorii výpočetní složitosti – ukázalo, že existuje třída problémů, jejichž složitost (počet výpočtů potřebných k získání přesné odpovědi) roste exponenciálně s rozměrem problému . Někdy je možné, obětovat přesnost, najít algoritmus, jehož složitost roste pomaleji, ale existuje velké množství problémů, pro které to nelze udělat (například problém určení objemu konvexního tělesa v n - rozměrném Euklidovský prostor, a pokud se to zobecní, pak obecně výpočet n - rozměrných integrálů) a metoda Monte Carlo je jediný způsob, jak získat dostatečně přesnou odpověď v rozumném čase.

V současnosti je hlavní úsilí výzkumníků zaměřeno na vytvoření účinných Monte Carlo algoritmů pro různé fyzikální, chemické a sociální procesy pro paralelní výpočetní systémy .

Integrace Monte Carlo

Předpokládejme, že potřebujeme vzít integrál nějaké funkce. Použijeme neformální geometrický popis integrálu a budeme jej chápat jako plochu pod grafem této funkce.

K určení této oblasti můžete použít jednu z obvyklých metod numerické integrace : rozdělte segment na dílčí segmenty, vypočítejte oblast pod grafem funkce na každém z nich a sečtěte. Předpokládejme, že pro funkci znázorněnou na obrázku 2 stačí rozdělit na 25 segmentů, a proto vypočítat 25 funkčních hodnot. Představte si nyní, máme co do činění s -dimenzionální funkcí. Pak potřebujeme segmenty a stejný počet výpočtů funkční hodnoty. Když je dimenze funkce větší než 10, úloha se stává obrovskou. Vzhledem k tomu, že se s vysokorozměrnými prostory setkáváme zejména v problémech teorie strun , stejně jako v mnoha dalších fyzikálních problémech, kde existují systémy s mnoha stupni volnosti, je nutné mít metodu řešení, jejíž výpočetní složitost by tolik nezávisela. na dimenzi. To je vlastnost metody Monte Carlo. $n$ $25^{n}$

Obvyklý integrační algoritmus Monte Carlo

Předpokládejme, že chcete vypočítat určitý integrál

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

Uvažujme náhodnou veličinu rovnoměrně rozloženou na integračním intervalu . Pak to bude také náhodná veličina a její matematické očekávání je vyjádřeno jako $u$ $[a,b]$ $f(u)$

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

kde je hustota distribuce náhodné veličiny , která se rovná . Požadovaný integrál je tedy vyjádřen jako $\varphi(x)$ $u$ ${\frac {1}{ba}}$ $[a,b]$

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

ale matematické očekávání náhodné veličiny lze snadno odhadnout modelováním této náhodné veličiny a výpočtem výběrového průměru. $f(u)$

Házíme tedy body rovnoměrně rozložené na , pro každý bod vypočítáme . Poté vypočteme výběrový průměr: . Výsledkem je odhad integrálu: $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\cca {\frac {ba}{N}}\sum _{i=1}^{N}f(u_{ i}).

Přesnost odhadu závisí pouze na počtu bodů . $N$

Tato metoda má také geometrickou interpretaci. Je velmi podobná výše popsané deterministické metodě, s tím rozdílem, že místo jednotného rozdělení integrační oblasti na malé intervaly a sečtení ploch výsledných „sloupců“ házíme na integrační oblast náhodné body, na které každý z nich postavíme stejný "sloupec", určíme jeho šířku jako , a sečteme jejich plochy. ${\frac {ba}{N}}$

Geometrický algoritmus pro integraci Monte Carlo

Chcete-li určit oblast pod grafem funkcí, můžete použít následující stochastický algoritmus:

omezíme funkci na obdélník ( v případě mnoha rozměrů n - rozměrný rovnoběžnostěn), jehož plochu lze snadno vypočítat; libovolná strana obdélníku obsahuje alespoň 1 bod grafu funkce, ale neprotíná jej; $Živec}}$
„načmárat“ do tohoto obdélníku (rovnoběžníku) určitý počet bodů ( kusů), jejichž souřadnice náhodně vybereme; $N$
určit počet bodů ( kusů), které spadají pod graf funkce; $K$
plocha oblasti ohraničená funkcí a souřadnicovými osami je dána $S$ $S=S_{{par}}{\frac {K}{N}}$

Pro malý počet dimenzí integrovatelné funkce je výkon integrace Monte Carlo mnohem nižší než výkon deterministických metod. V některých případech, kdy je funkce specifikována implicitně, ale je nutné určit oblast zadanou ve formě komplexních nerovností, může být výhodnější stochastická metoda.

Použití vzorkování významnosti

Při stejném počtu náhodných bodů lze zvýšit přesnost výpočtů přiblížením oblasti, která omezuje požadovanou funkci, k funkci samotné. K tomu je nutné použít náhodné veličiny s rozdělením, jehož tvar se co nejvíce blíží tvaru integrovatelné funkce. Jedna z metod pro zlepšení konvergence ve výpočtech Monte Carlo je založena na tomto: vzorkování významnosti .

Optimalizace

K řešení optimalizačních problémů lze použít různé varianty metody Monte Carlo. Například algoritmus simulace žíhání .

Aplikace ve fyzice

Počítačová simulace hraje v moderní fyzice důležitou roli a metoda Monte Carlo je jednou z nejběžnějších v mnoha oblastech od kvantové fyziky po fyziku pevných látek, fyziku plazmatu a astrofyziku.

Metropolisův algoritmus

Tradičně se pro stanovení různých fyzikálních parametrů systémů v termodynamické rovnováze používá metoda Monte Carlo. Předpokládejme, že existuje množina možných stavů fyzického systému . Pro určení průměrné hodnoty určité veličiny je nutné vypočítat , kde se provádí sčítání přes všechny stavy od , je pravděpodobnost stavu . $W(S)$ $S$ $\overline {A}$ $A$ $\overline {A}=\sum _{{S}}A(S)P(S)$ $S$ $W(S)$ $P(S)$ $S$

Dynamická (kinetická) formulace

Přímá simulace Monte Carlo

Přímá Monte Carlo simulace jakéhokoli fyzikálního procesu zahrnuje modelování chování jednotlivých elementárních částí fyzikálního systému. Toto přímé modelování se v podstatě blíží vyřešení problému od prvních principů , ale obvykle je pro urychlení výpočtů povoleno použít libovolné fyzikální aproximace. Příkladem je výpočet různých procesů metodou molekulární dynamiky : na jedné straně je systém popsán prostřednictvím chování jeho elementárních složek, na druhé straně je použitý interakční potenciál často empirický .

Příklady přímé simulace Monte Carlo:

Simulace ozařování pevných látek ionty při aproximaci binárních srážek.
Přímá Monte Carlo simulace zředěných plynů.
Většina kinetických modelů Monte Carlo patří mezi přímé (zejména studium epitaxe molekulárního svazku ).

Metoda Quantum Monte Carlo

Kvantová metoda Monte Carlo je široce používána ke studiu složitých molekul a pevných látek. Tento název kombinuje několik různých metod. První z nich je variační metoda Monte Carlo , která je v podstatě numerickou integrací vícerozměrných integrálů, které vyvstávají při řešení Schrödingerovy rovnice . Řešení problému zahrnujícího 1000 elektronů vyžaduje použití 3000rozměrných integrálů a při řešení takových problémů má metoda Monte Carlo obrovskou výkonnostní výhodu oproti jiným metodám numerické integrace . Další variací metody Monte Carlo je difúzní metoda Monte Carlo .

Viz také

Feynman-Katzův vzorec
Generátory pseudonáhodných čísel
Las Vegas (algoritmus)
Vzorkování
AQUA@home
QMC@Home
QuantumFire
Buffonův problém házení jehlou
Metoda entropického modelování
Wang-Landauův algoritmus
Pomocí metody Monte Carlo prohledávejte strom při hraní Go.

Poznámky

↑ Matematická překvapení: Příklad archivovaný 30. ledna 2012 na Wayback Machine
↑ 1 2 A.Hall. O experimentálním určení Pi // The Messenger of Mathematics. - 1872. - Sv. 2. - S. 113-114.
↑ Fishman, 1996 , str. 344.
↑ Mikuláš; metropole. The Monte Carlo Method (anglicky) // Journal of the American Statistical Association : journal. - 1949. - Sv. 44 , č. 247 . - str. 335-341 . — ISSN 0162-1459 . - doi : 10.2307/2280232 .
↑ Varfolomeev A.A., Svetlolobov I.A. ZhETF. 1959. V.36. s.1263-1270

Literatura

Metoda Sobol I. M. Monte Carlo . — M .: Nauka, 1968. — 64 s. - ( Populární přednášky o matematice ). - 79 000 výtisků.
Článek „Modelování života“, autor Andrey Teplyakov
Metropolis, N. , Ulam, S. Metoda Monte Carlo, - Journal of the American Statistical Association 1949 44 č. 247 335-341.
Alex F Bielajew . Základy metody Monte Carlo pro transport neutrálních a nabitých částic. 2001
WMC Foulkes, L. Mitas, RJ Needs a G. Rajagopal Quantum Monte Carlo simulace pevných látek, — Reviews of Modern Physics 73 (2001) 33.
Článek "Metropolis, Monte Carlo a MANIAK"
Fishman, George S. Monte Carlo: koncepty, algoritmy a aplikace. - Springer, 1996. - ISBN 0-387-94527-X .

Slovníky a encyklopedie	Velká dánština Velká Katalánština velká čínština Skvělý norský Velký Rus Britannica (online)
V bibliografických katalozích	GND : 4240945-7 J9U : 987007543534905171 LCCN : sh85087032 NDL : 00567842 NKC : ph122780

Optimalizační metody
Jednorozměrný	metoda zlatého řezu Dichotomie Parabolová metoda Vyhledávání v mřížce Jednotná metoda vyhledávání bloků Fibonacciho metoda Ternární hledání Piyavského metoda Stronginovou metodou
Nulové pořadí	Gaussova metoda Metoda Nelder-Mead Hook-Jeevesova metoda Rosenbrockova metoda Powellova metoda
První objednávka	gradientní sestup Zeutendijkova metoda Souřadnicový sestup Metoda konjugovaného gradientu Kvazi-newtonské metody Levenberg-Marquardtův algoritmus
druhá objednávka	Newtonova metoda Newton-Raphsonova metoda Algoritmus Broyden-Fletcher-Goldfarb-Shanno (BFGS)
Stochastické	Metoda Monte Carlo Simulované žíhání Evoluční algoritmy diferenciální evoluce Algoritmus mravenců Metoda roje částic Algoritmus včelstva Metoda náhodné chůze
Metody lineárního programování	Simplexní metoda Gomoriho algoritmus Elipsoidní metoda Potenciální metoda
Metody nelineárního programování	Sekvenční kvadratické programování