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


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 ter ponavljanja. Metoda omogoča predvidevanje obnašanja realnih sistemov (recimo računanje površin in volumnov zapletenih oblik, integralov, verjetnosti, kriptografiji ..., vse to nam pomaga v znanosti, ekonomskih napovedih, socioloških študijah ...). Od tod tudi ime Monte Carlo - v tem mestu je namreč veliko igralnic, kjer mnogi iščejo smisel življenja v igrah na srečo, naključnem metanju kock, vrtenju koles - rulet, kartah, itn.
Za metodo torej potrebujemo 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 strani - 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 in ostalih spletnih strani!
    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.

    Kriptografske aplikacije seveda tudi uporabljajo naključna števila - tam pa se pokaže problem slabe varnosti generatorjev naključnih števil - na algoritem generiranja lahko večinoma sklepamo preko zaporedje števil ... Nekateri zato predlagajo kar uporabo radioaktivnih izotopov povezanih z računalniki (preko števca, ki šteje razpade) - na podlagi tega zares naključnega procesa pa se generira 'naključna števila' v pravem pomenu te besede - tako se izognemo algoritmom, ki se jih večinoma da dokaj hitro dešifrirati. Za generiranje random števil je uporaben tudi kozmični naključni radijski signal, kozmični delci ...

    Metoda Monte Carlo in čebele!
    Naključni dogodki in idealna uporabna geometrija prostora.
    Narava ima velikokrat metodo Monte Carlo vgrajeno v evolucijski proces. Recimo, ko čebele tvorijo izjemne šestkotne celice v satju iz voska. In - kako jih ta drobna bitja sploh naredijo - brez formalnega znanja geometrije, optimizacije? Najprej naredijo okrogle celice velikosti čebele, ki se dotikajo, nakar z randon (naključnim) brcanjem z zadnjimi nogami ob stene, počasi izoblikujejo vosek - izdelajo (praktično) idealne šestkotnike (temperatura voska je pri izoblikovanju heksagonov okrog 35 °C). V primeru, da ne bi izoblikovale heksagonov, bi med krožnimi celicami ostalo veliko prostora neizkoriščenega - glejte sliko. To - "Monte Carlo" naključno brcanje za oblikovanje heksagona - poteka seveda v večini celic bolj ali manj sočasno. Z. V.


    Proces izdelave šestkotnika v naravi - iz krogov v heksagone! Vir: splet. Notranji koti pravilnega šestkotnika (kjer so vse stranice in vsi koti enaki) so vsi enaki 120°. Podobno kot pri kvadratih in pravilnih trikotnikih, je tudi pravilne šestkotnike moč položiti enega ob drugega, da brez rež zapolnijo ravnino (v vsaki točki se srečujejo trije šestkotniki). Čebele zato za gradnjo svojih panjev, satnic, uporabljajo (izdelava poteka preko krožnih vdolbinic lastnih dimenzij in random brcanja vanje) pravilne šestkotnike, saj jim to omogoča učinkovito (optimalno) rabo prostora in gradbenega materiala za shranjevanje medu - torej zalog hrane, cvetnega prahu, zaroda v satnih celicah. Od narave smo se tudi ljudje veliko naučili - v resnici vse ...

    Razmerje med obsegom heksagona in njegovo ploščino (in s tem volumnom celice) je optimalno, saj porabimo najmanj voska pri dani debelini sten na koristno površino celice znotraj celotne satnice. Za razmerje obsega in konstantne ploščine (Ao) celic na celotni površini - ko se upošteva, da si posamezni heksagoni (celice) delijo stranice - velja:
    obseg/ploščina = (12)1/4/(Ao)1/2
    To je bolje, kot za kvadratne celice [ obseg/ploščina = 2/(Ao)1/2 ] ali recimo za enakostranične trikotne [ obseg/ploščina = (27)1/4/(Ao)1/2 ]. Narava torej teži k optimalnosti.
    Tudi prsti ali baloni, mehurčki (vse stisljive krožne strukture iz enake snovi), ki jih stisnemo skupaj, se dotikajo pod značilnimi koti 120 °. Izjemno zanimivo pa je tudi vprašanje, kako to optimalno heksagonalno obliko celice dosežejo čebele? Odgovor je maksimalno preprost - preko naključnega brcanja, v najprej okrogle stene celic iz voska, ki se tako preoblikujejo v heksagone (vosek čebele z lastno energijsko proizvodnjo segrejejo do okrog 35 °C, tako se ga da lažje preoblikovati).

    Če je krog najbolj optimalen glede razmeja med obsegom L in ploščino A [ obseg/ploščina = 4*pi/L = 2(pi)1/2/(A)1/2 ] pa je mreža celic, ki najbolje pokrijejo uporabno površino z danimi dimenizijami kar čebelji dom, satnica iz pravilnih šestkotnikov (heksagonov). Vsaka celica ima pričakovano dimenzijo velikosti čebele. Torej kar drži: "Vse se zgodi po naključju in nujnosti."


    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:

    INTEGRIRANJE .::.



    * Primer numerične integracije z metodo Monte Carlo
    (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!