10. Monte Carlo hermanir

Chaos is found in greatest abundance wherever order is being sought. It always defeats order, because it is better organized. – Terry Pratchett, Interesting Times: The Play

10.1. Inngangur

Hér ætlum við að skoða hvernig hægt er að nota slembitölur til þess að heilda tölulega og leysa verkefni tengd hermun.

Við munum ekki skoða hvernig slembitölur eru fundnar í tölvum og hversu slembnar þær í raun og veru eru. Það er töluvert efni um þetta á netinu og í bókum.

Í Matlab og Octave gefa skipanirnar rand, randn og randi slembitölur með mismunandi eiginleika. rand gefur jafndreifðar slembitölur á bilinu \([0,1]\), randn gefur normaldreifðar rauntölur og randi gefur heiltölur á ákveðnu bili.

10.1.1. Nálgun á pi

Byrjum á að skoða einfalt verkefni. Við ætlum að nota flatarmál hringskífu til að nálga \(pi\). Við vitum að flatarmál hringskífu með geisla \(r\) er \(\pi r^2\). Setjum \(r=1\) og punkt af handahófi í rétthyrningnum \([-1,1]\times[-1,1]\), þá eru líkurnar á að hann lendi á hringskífunni \(p=\pi/4\). Þannig að ef við getum fundið líkurnar \(p\) þá finnum við gildið á \(\pi\). Líkurnar er hægt að herma með því að velja marga punkta af handahófi og athuga hversu hátt hlutfall þeirra lendir á skífunni. Af samhverfuástæðum er nóg fyrir okkur að skoða fyrsta fjórðung þannig að við veljum punkta \((x_1,y_1),\ldots,(x_n,y_n) \in [0,1]\times[0,1]\) af handahófi og skilgreinum \(S_n\) sem fjölda þeirra punkta sem lenda innan hringskífunnar og þá mun

\[\lim_{n \to \infty} \frac{S_n}{n} = \frac{\pi}{4}.\]

10.2. Heildi í einni breytistærð

10.2.1. Nálgun á heildi

Það er lítill vandi að nálga heildi með þessari aðferð. Meðalgildi falls \(f\) á bilinu \([a,b]\) er skilgreint sem

\[\overline f = \frac{1}{b-a} \int_a^b f(x)\, dx,\]

þannig að ef við getum fundið nálgun á meðalgildinu þá getum við nálgað heildið. Ef við veljum af handahófi punkta \(x_1,x_2,\ldots,x_n \in [a,b]\) þá er eðlilegt að ætla að meðaltal fallgildanna í þessum punktum stefni á meðalgildi fallsins, það er

\[\lim_{n\to \infty} \frac 1n \sum_{i=1}^n f(x_i) = \overline f.\]

10.3. Margföld heildi og rúmmál

10.3.1. Margföld heildi

Aðferðin hér að ofan er ekki mjög góð til þess að nálga heildi, skekkjan er af stærðargráðunni \(1/\sqrt n\) samanborið við \(1/n^2\) í samsettu trapisureglunni. Helstu kostir þess að nota slembni til að nálga heildi koma fram þegar við þurfum að reikna heildi í mörgum breytistærðum. Þá þurfa hefðbundnar aðferðir eins og samsetta trapisureglan \(n^d\) punkta, þar sem \(d\) er fjöldi breytistærða. En helsti kostur Monte Carlo heildunar er að það er auðvelt að heilda yfir flókin svæði. Hefðbundnar aðferðir þurfa stikun á svæðinu til þess að ákvarða mörkin á heildunum en Monte Carlo þarf bara að geta ákvarðað hvort tiltekinn punktur er innan svæðisins eða ekki.

10.3.2. Margföld heildi: Dæmi

Reiknum rúmmál hlutarins \(S \subset \mathbb R^3\) sem samanstendur af öllum punktum í \([0,1]^3\) sem uppfylla eftirfarandi ójöfnur

\[\begin{split}\begin{aligned} x^2 + \sin(y) &\leq z \\ x-z+\exp(y) \leq 1 \end{aligned}\end{split}\]

Rúmmálið, \(V\), fæst með því að reikna eftirfarandi heildi

\[V = \int \int \int_S 1\, dx\, dy\, dz.\]

10.4. Hermun

Skoðum að lokum einfalt dæmi sem er ekki auðvelt að leysa beint, en er auðvelt að herma með því að nota sömu hugmyndir og hér að ofan.

10.4.1. Nál Buffons

Nál af einingarlengd er hent af handahófi á blað með tveimur samsíða línum og lengdin á milli línanna er 1. Gefið að miðja nálarinnar lendi á milli línanna, hverjar eru líkurnar á að nálin öll lendi á milli línanna?