Monte-Karlo metodas  

Monte Karlo metodas – skaičiavimo algoritmas, pagrįstas statistiniu modeliavimu ir gautų rezultatų apdorojimu statistiniais metodais; dažniausiai naudojamas fizikinių ir matematinių sistemų modeliavimui, kai neįmanoma gauti tikslių rezultatų naudojant deterministinį algoritmą.

Norint atlikti labai sudėtingą skaičiavimą, reikalaujantį apdoroti didelę duomenų imtį, galima tą patį skaičiavimą atlikti tik su keletu atsitiktinai pasirinktų duomenų. Atsitiktinai parinkti duomenys dažniausiai būna „tipiški“, todėl natūralu tikėtis, kad ir atliktas skaičiavimas ne itin daug skirsis nuo tikslaus. Pavyzdžiui, nežinodami kaip apskaičiuoti skritulio, nubrėžto kompiuterio ekrane, plotą, galėtume ekrane atsitiktinai išdėlioti keliasdešimt taškų. Suskaičiavę, kokia dalis taškų pateko į apskritimą, galėtume apytiksliai pasakyti ir skritulio plotą.

Šiuolaikinė Monte-Karlo metodo versija sukurta A. Ulamo 5-o dešimtm. pabaigoje jam dirbant su branduolinių ginklų projektais Los Alamos laboratorijoje. Jis sveikdamas po ligos dėliojo pasjansą ir iškėlė klausimą, kokia tikimybė, kad pasjansas susidėlios. Jis spėjo, kad reikia pabandyti daug kartų ir taip įvertinti tą tikimybę. O pavadinimą suteikė Nicholas Metropolis (1915-1999), nes S. Ulamo dėdė dažnai lankėsi Monte Karlo kazino (jiedu straipsnį apie metodą paskelbė 1949 m.). Jo svarbą netrukus suprato Dž. fon Neimanas užprogramavęs ENIAC paskaičiavimams pagal Monte Karlo metodą.
Tiesa, dar 4-e dešimtm. E. Fermi eksperimentavo su Monte-Karlo metodu, kai nagrinėjo neutronų difuziją, tačiau nieko nepaskelbė ta tema.

Su azartiniais žaidimais jis susijęs nebent suprantant plačiausia prasme. Monte-Karlo metodai yra būdas spręsti sudėtingus uždavinius netikėčiausiu būdu. Jie buvo sukurti kai kurių atominės bombos kūrimo metu kilusių uždavinių sprendimui. O pirmąkart šis metodas aprašytas A. Holo 1872 m.
Vis tik išgirdus apie atsitiktinių skaičių naudojimą kompiuteriuose, pirma mintis būna apie kompiuterinius žaidimus. Juk visai nebūtų įdomu, jei kiekvieną kartą žaidimas kartotų ankstesnius.

Archetipiniu pavyzdžiu yra lošimų kauliuko programavimas. Dažniausiai naudojama speciali atsitiktinio skaičiaus tarp 0 ir 1 generavimo funkcija (dažnai vadinama rnd). Pavyzdžiams naudosime JavaScript kalbą. Tada atsitiktiniui sveikam skaičiui 1..6 generuoti komanda būtų:
Math.floor(Math.random()*6)+1

Šis pavyzdys 6 kartus „išmeta“ kauliuką:

<SCRIPT Language='JavaScript'>
var kaulas;
for (var k=1; k<=6; k++) {
   kaulas = Math.floor(Math.random()*6)+1;
   document.write ('<br>Kauliukas:' + kaulas);
}
</SCRIPT>

Pamėtykite patys  >>>>>

Dažna pradedančiųjų klaida yra praleidžiant „+1”. Kadangi funkcija niekada negražina reikšmės 1, tai be „+1” gauname skaičius 0..5

Atkreipiame dėmesį, kad atsitiktinius dydžius suskaidome į lygaus dydžio intervalus, taigi rezultatas yra yra su vienoda tikimybe. Tad mūsų „kauliuko“ mėtymas yra korektiškas.

Suprantama, kad jei įvykiai nevienodų tikimybių, tada reikia imti nevienodo pločio intervalus – proporcingai tikimybėms.

Viskas tarsi ir aišku, tačiau čia yra kiek sudėtingesnė problema generuojant atsitiktines reikšmes galimyų reikšmių kontinuume. random funkcija gražina „vienodai pasiskirsčiusias“ reikšmes intervale 0..1. Kartais reikalingi kitokie pasiskirstymai ir tam yra gausus technikų pasirinkimas. Pvz., jei norime normaliojo pasiskirstymo, tai visa, ko mums reikia, tai gauti kelias atsitiktines reikšmes ir paskaičiuoti jų vidurkį. Tada apytikslis pasiskirstymas bus apie 0.5 reikšmę.

Pvz., paskaičiuojami 6-i vidurkiai iš 5 atsitiktinių reikšmių:

var vidurkis;
for (var k=1; k<=6; k++) {
   vidurkis = (Math.random()+Math.random()+Math.random()+Math.random()+Math.random())/5;
   document.write ('<br>vidurkis:' + vidurkis);
}

Po šios įžangos pats laikas grįžti prie Monte-Karlo metodo. Nesunku sugalvoti uždavinį, simuliuojantį atsitiktinį procesą (pvz., degalinės darbo priklausomybę nuo kolonėlių skaičiaus). Suprantama, kad tokia simuliacija neduos tikslaus atsakymo – kiekvienas jos įvykdymas bus skirtingas. Tačiau mes galime įvesti tikėtinas įvykių tikimybes, kurioms esant rezultatas tam tikrame intervale bus su didele tikimybe. Pvz., 90% atvejų eilė bus iš 8-11 laukiančių mašinų.

Štai čia ir braunasi susirūpinimas. Ir nors yra 90% tikėtinumas, kad eilė bus tokio dydžio, tačiau lieka 10% tikėtinumas, kad taip nebus. Ir apie tai reikia rūpintis.

Naudojant kompiuterius tikimasi tiksliai išspręsti uždavinį. Pvz., skaičiuojant netaisyklingos figūros plotą, galime ją suskaidyti į daugelį stačiakampių ir gauti apytikslę ploto reikšmę. Ji nėra tiksli, tačiau galime stačiakampius mažinti ir rezultatą tikslinti.

Plotų skaičiavimas (matematiškai, funkcijų integravimas) labai svarbus fizikoje ir inžinerijoje. Jis iškilo ir atominės bombos projekte. To meto kompiuteriai nebuvo pakankamai spartūs. Džonas fon Neimanas mąstė, kaip tai padaryti paprasčiau panaudojant atsitiktinius skaičius.

Kad tai suprastume, įsivaizduokime šautuvą, atsitiktinai šaudantį į taikinį. Pataikymų kiekis yra proporcingas taikinio plotui. Tai ir yra Monte-Karlo metodo esmė.

Tarkime, reikia paskaičiuoti skritulio plotą. Mums tereikia generuoti atsitiktines taškų (x,y) koordinates ir paskaičiuoti, kiek taškų patenka į skritulį, ir kiek ne. Jei tai padarysime pakankamą kartų kiekį, rezultatas apsistos ties apskritimo ploto santykiu su srities plotu.

Atrodytų, kad toks uždavinio „apvertimas žemyn galva“ yra keistas, tačiau reikia atsižvelgti į tai, kad atsitiktinių skaičių porų generavimas, o taip pat „pataikymo“ patikrinimas yra greiti. Ir tai buvo priežastis, kodėl atominės bombos kūrime buvo naudojami atsitiktiniai skaičiai.

Vis tik, ploto paskaičiavimas nedaro jums didelio įspūdžio, tačiau pasižiūrėkime į p reikšmės suradimą. Juk jei paimsime skritulį, kurio spindulys yra 1, tai jo plotas bus tiksliai p! Ir tada p galima lengvai paskaičiuoti naudojant atsitiktinius skaičius...

Šią idėją 18 a. iškėlė prancūzų gamtininkas, Bufono kunigaikštis Georges-Louis Leclerc'as. Jis klausė – kokia tikimybė, kad ant grindų numesta adata pataikys į plyšį tarp lentų, kurių plotis yra pusė jos ilgio (1777). Atsakymas į šį klausimą buvo 1/p. Tai buvo praktiškai išbandyta 1901 m. (Mario Lazzarini atliko 3408 metimus) ir gauta reikšmė 355/113 nėra labai bloga p aproksimacija – atsižvelgiant į tai, tebuvo mėtoma adata paskaičiuojant, kiek kartų ji pataiko į tarpą tarp lentų.

Tačiau kas toliau? Ogi tai, kad galite įvertinti bet kokio paskaičiavimo rezultatus naudodami vien atsitiktinius skaičius. Vienintelė problema – paaiškinimas, kodėl tai suveikia, veda gilyn į matematiką.

Tarkim, Monte-Karlo metodas leidžia spręsti tiesinių lygčių sistemą Ax=b, kur b yra reikšmių vektorius, o A - matrica.

Paprastai ji sprendžiama skaičiavimo metodų metodais, tačiau atvirkštinės matricos suradimui reikia didelių skaičiavimo sąnaudų. Tam mums reikia paskaičiuoti sandaugą y=Ab. Tai atliekama sumuojant kiekvienos eilutės sandaugą su vektoriaus reikšme.

Pvz. - šios lygčių sistemos atsakymas yra (9, -1),

var j, b = new Array(4,2);
var A = new Array(), Y = new Array();
A[0] = new Array(1,5); A[1] = new Array(2,4);

for (var i=0; i<2; i++) {
   Y[i] = 0;       
   for (j=0; j<2;j++) {
      Y[i] += A[i][j] * b[j];
   }
   document.write ('<br>Y['+i+']=' + Y[i]);
}

Rezultatas:
Y[0]=14
Y[1]=16

Tarkim, kad visos matricos reikšmės teigiamos ir mažesnės už 1, o kiekvienos eilutės reikšmių suma lygi 1. tai leidžia mus eilutes laikyti kaip kažkokių įvykių tikimybes.
Tarkim, kad A = ( (0.5, 0.3, 0.2), (0.2, 0.1, 0.7) ), o b = (4.3, 6.2, 3.2).
Tada mes turim: a) sukurti atsitiktinių skaičių generatorių R(1), kuris 4.3 pateiktų su 0.5 tikimybe, 6.2 – su 0.3 tikimybe, 3.2 – su 0.2 tikimybe;
b) ir R(2) generatorių, kuris tas pačias reikšmes pateikia su antroje eilutėje nurodytomis tikimybėmis.

O tai galima nesunkiai pasiekti anksčiau aprašytais būdais! Generuojame atsitiktinius skaičius ir skaičiuojame jų vidurkius – jų sudarytas vektorius yra ieškomo atsakymo aproksimacija.

Lieka tik klausimas – kam gi reikalingi kvantiniai kompiuteriai, jei turime Monte-Karlo metodą, kurį galime panaudoti sudėtingų skaičiavimų aproksimacijai?

Matroidai
Loterijų matematika
Algebra akimirksniu
Pi keliai ir klystkeliai
Ar įrodytas abc teiginys?
Kur viešpatauja chaosas?
Revoliucija mazgų teorijoje
Izingo modelis įmagnetinimui
Skaičiai: apžvalga/pradmenys
Pagrindinės statistinės sąvokos
Mokslininkui nereikia matematikos!
Nepaprasti skaičiai: skaičius 42
Kombinatorika, polinomai, tikimybės
Šriodingerio katinų dresiravimas: kvantiniai kompiuteriai
Kita skaičiavimo metodų istorijos pusė
Ultimatyvi logika: Iki begalybės ir toliau
Geriausios alternatyvos parinkimas
Žvaigždžių virš Babilono funkcija
Šiuolaikiniai iškilūs matematikai
Žaidimų teorijos panaudojimas
Iniciatyva: Matematikos keliu
Nepaprasti Visatos skaičiai
Visata kaip kompiuteris
Matematiniai anekdotai
Laplasas. Dėl tikimybių
Dygios eilutės
Perkoliacija
Parabolė
Vartiklis