Metoda Monte Carlo, široka uporaba, računanje števila PI ...


Pronicljiv in duhovit grški filozof Demokrit je trdil:
"Vse se zgodi po naključju in nujnosti."
Kaj je torej življenje?

Metode Monte Carlo so simulacije resničnosti s pomočjo naključnih ali kvazinaključnih števil in velikega števila izračunov in ponavljanja omogočajo predvidevanje obnašanja realnih sistemov (recimo računanje površin in volumnov zapletenih oblik, integralov ..., vse to nam pomaga v znanosti, ekonomskih napovedih ...). Zato tudi ime Monte Carlo - v tem mestu je namreč veliko igralnic, kjer iščemo srečo v naključnem metanju kock, itn. Za metodo torej rabimo naključna števila, zato najprej beseda o random številih in primer računanja števila PI "preko metanja kocke". To je torej uvod v metodo Monte Carlo preko realnega in zelo poučnega primera.

Random števila med 0 in 1, 1 in 10, in izračun števila PI = 3.14159 26535 89793 23846 26433 83279 50288 41971 69399 37510 58209 74944 592...

VAJA 1:
S klikanjem na gumba I in II se prepričajmo, da so naključna števila enakomerno porazdeljena.
Med 0 in 1:

Med 1 in 10: | porazdelitev: st_1=, st_2= , st_3= , st_4= , st_5= , st_6= , st_7= , st_8= , st_9=
VAJA 2:

Kvdrat - koordinate X in Y, random (naključno) izbiranje točk med 0 in 1:
X:
Y:
Številu PI = 4*Nr/N (se bližamo z večanjem št. klikov):
- razlika do prave vrednosti cca: (razlika v procentih, cca: % )
Metoda Monte Carlo in računanje števila PI z velikim številom naključnih (random) točk na kvdratu in četrtini kroga (površina kvadrata S = 1x1 je sor. s št. vseh N točk, in površina četrtine kroga je Skr/4 = PI*1/4 je sor. s št. Nr rdečih točk, velja torej: PI = 4*Nr/N):
Tocke v četrini kroga s polmerom 1 (x*x + y*y <= 1), Nr =0 ( preverjanje za x*x + y*y < 1, Nr: 0)
Vse random točke (vsi kliki) so v kvadratu 1x1, N = 0

Brez klikanja do št. PI (brez utrujanja miške) pa vam omogoča zadnja vaja (spodaj), kjer samo vnesete koliko random št. želite za izračun!!!


VAJA 3:
Preprost primer računanja zapletene površine (Sx) na homogenem papirju je recimo, da stehtamo celoten papir (masa M), kateremu poznamo površino S = axb, potem izrežemo površino (Sx), ki ji želimo določiti površino in jo stehtamo (masa Mx). Razmerje mas je enako kar razmerju površin (Sx/S = Mx/M) - to je Monte Carlo po domače.
Tudi približek št. PI lahko dobimo s tehtanjem (PI = 4*Mx/M, če je površina kvadratna S = axa in je v njem vrisana četrina kroga r = a)!

* Primerjalni algoritem za PI iz volumna krogle pa je na random_stevila02.html

VAJA 4:
Kako pa bi kar se da preprosto s programiranjem določili neko površino? To ni zmeraj enostvno - a če sliko naredimo dovolj preprosto, se to da izračunati (narediti algoritem) relativno enostavno. Recimo, da je kvadrat bel, oblika, ki ji iščemo površino Ax, pa je modre barve - ki ima "Decimal Code (R,G,B) = (0,0,255)", slika spodaj. Sedaj z random x in y številkama iščemo, ali ima slikovni element (pixel) x in y vrednost modre barve (R,G,B) = (0,0,255) ali bele (R,G,B) = (255,255,255). Razmerje vsote vseh zadetkov z vrednostjo (R,G,B) = (0,0,255) in vsote vseh random števil znotraj 1x1 površine nam da razmerje površin. Metodo predlagal Z. V.


Slika x zapletene oblike, katere povrsino Ax lahko določimo z Monte Carlo metodo. Obliko, ki ji iščemo površino, obarvamo recimo modro - ta barva ima "Decimal Code (R,G,B) = (0,0,255)". Razmerje zadetkov z vrednostjo (R,G,B) = (0,0,255) in vseh zadetkov v kvadratu, je enako razmerju površin.

VAJA 5:


Podobno lahko določimo tudi volumne zapletenih oblik. Volumen računalniško razrežemo na tanke plasti debeline d. Določimo velikost površine Ai preko metode Monte Carlo na razdalji recimo Xi + d/2 in potem seštejemo vse volumne Ai*d in tako dobimo dober približek celotnega volumna. To je lahko volumen kake arheološke najdbe (v arheologiji je to seveda večinoma zelo enostavno storiti - potop eksponata v tekočino) ali volumen neugodnega tumorja (3D sliko tumorja dobimo preko računalniška tomografije - CT slikanja), ki mu tako lažje določimo dozo, količino obsevanja ... Med CT preiskavo se rentgenska cev vrti okrog pacienta, ki leži na preiskovalni mizi (izumil Anglež Sir Godfrey Hounsfield s sodelavci leta 1971). Moderne metode vključujejo tudi magnetno resonanco (MR).


Animacija slikanja možganov od vrha do dna (levo). MR angiogram pri prirojenih srčnih boleznih (desno).

Zorko Vičar
2017


Spodaj je tekst iz wiki.
Metode Monte Carlo so stohastične (deterministične) simulacijske metode ali algoritmi, ki s pomočjo naključnih ali kvazinaključnih števil in velikega števila izračunov in ponavljanja omogočajo predvidevanje obnašanja zapletenih matematičnih sistemov.
Prvotno so bile iznajdene v državnem laboratoriju v mestu Los Alamos v ZDA nedolgo po koncu 2. svetovne vojne. Takrat je bilo v ZDA ravno končan prvi elektronski računski stroj in znanstveniki v Los Alamosu so razmišljali o tem, kako bi se ga dalo najbolje izkoristiti za razvoj jedrskega orožja (vodikove bombe). Leta 1946 je Ulam predlagal uporabo naključnega vzorčenja za simulacijo potovanja nevtronov in von Neumann je predlog leta 1947 realiziral. S tem so bile omogočene simulacije preprostih razmer, ki pa so bile vseeno pomembne za uspešno izvedbo projekta. Ulam in Metropolis sta leta 1949 objavila članek, v katerem sta opisala svoje ideje, čemur je sledilo mnogo raziskav tekom 1950-ih let. Metode so dobile ime po glavnem mestu države Monako, ki je znano po svojih igralnicah in igrah na srečo (ime je predlagal Metropolis, eden od pionirjev te metode).

V ekonomiji se metoda uporabljajo za računanje poslovnega tveganja, spremembo vrednosti investicij, pri strateškem planiranju ipd.
V medicinski fiziki in radioterapiji se Monte Carlo uporablja za načrtovanje doze za obsevanje tumorjev.

Izjemna učinkovitost metode se kaže na relativno preprostem primeru računanja števila PI. Generatorji naključnih (random) števil pa so različno dobri - a algoritmi se izboljšujejo - recimo zelo soliden je Lehmerjev (D. H.) linearni kongruentni generator (LCG):
Xk+1 = (a*Xk + b) mod m

Xk+1 je torej ostanek pri deljenju števila (a*Xk + b) z m
m je modulus in je praštevilo (prime number), m > 0
a je multiplikator (m > a >= 2), želimo si, da a*X ni deljiv z m
b je korak (m > b >= 0), b in m sta tuji števili
n >= 0
Xo je osnova (seme - seed), ki je tuje število glede na m (m >= Xo > 0)

Recimo dobre vrednosti so: m = 232, b = 1013904223, a = 1664525
Tuji števili nimata skupnega delitelja razen 1 in -1!
Praštevílo je naravno število n > 1, če ima točno dva pozitivna delitelja (faktorja), število 1 in samega sebe kot edini prafaktor.


Uporaba metode Monte Carlo pri določanju približne vrednosti števila π. Po postavitvi 30000 random točk.




VAJA 6:
Še vaja, ko z enim klikom ocenimo št. PI, vnesi št. random (naključnih) točk.


Stevilo naključnih točk (nekje do 30000):
(lahko večkrat klikneš)
Kvdrat - koordinate X in Y, random (naključno) izbiranje točk med 0 in 1:
X:
Y:
Številu PI = 4*Nr/N (se bližamo z večanjem št. klikov):
- razlika do prave vrednosti cca: (razlika v procentih, cca: % )
Metoda Monte Carlo in računanje števila PI z velikim številom naključnih (random) točk na kvdratu in četrtini kroga (površina kvadrata S = 1x1 je sor. s št. vseh N točk, in površina četrtine kroga je Skr/4 = PI*1/4 je sor. s št. Nr rdečih točk, velja torej: PI = 4*Nr/N):
Tocke v četrini kroga s polmerom 1 (x*x + y*y <= 1), Nr =0 ( preverjanje za x*x + y*y < 1, Nr: 0)
Vse random točke (vsi kliki) so v kvadratu 1x1, N = 0

Z NEKAJ 10 000 random števili se približamo oceni pod 1 % natančnosti - to daje metodi verodostojnost.

Rezultate zbrišeš z opcijo Refresh ...!!!


  • VAJA 7:


    Primer numerične integracije
    (za vajo - vstavi recimo linearno funkcijo 5*x/4 - 3/4 ali 4*Math.sqrt(1-x*x) ...)!
    ------------------------------
    ORG stran (www.algorytm.org) ima napako z neg. vrednostmi!