Názov:

Kvazi monte carlo integrovanie a pseudo náhodné generátory

Partneri:

·          Matematický ústav Slovenská akadémie Vied, Bratislava (O. Strauch)

·          Slovenská technická univerzita v Bratislave, Fakulta chemickej a potravinárskej technológie, Oddelenie informatizácie a riadenie procesov (V. Baláž)

·          Bulharská Akadémia Vied, Ústav Matematiky a Informatiky, Sofia, Bulharsko (S.S. Stailova)

·          Juho – zapadá univerzita “Neophit Rilsky” , Fakulta Prírodných vied a matematiky, Katedra matematiky, Blagoevgrad, Bulharsko (V. Grozdanov)

Čas riešenia: 2008-2009

 Anotácia:

Pokúsime sa nájsť nový odhad chyby v numerickom integrovaní pre vyššie dimenzie, diskrepanciu a diafóniu pre nové typy sieti, nové kombinácie pseudo-náhodných generátorov a nové koncepty hustôt pre prirodzené čísla.

Klúčové slová:

Teória rovnomerného rozdelenia, kvazi-Monte Carlo integrovanie, generátory náhodných čísel, siete, diskrepancia a diafónia, hustoty na prirodzených číslach.

Ciele projektu:

Cieľ projektu je v úzkej medzinárodnej spolupráci nájsť výsledky v teórii rovnomerných postupností, ktorá sa datuje do 1916 pionierskou prácou H. Weyla. Doteraz vyšlo 8 základných monografií, napríklad:

[KN] K. Kuipers-H. Niederreiter: Uniform Distribution of Sequences (1974);

[DT] M.Drmota-R.F.Tichy: Sequences, Discrepancies and Applications (1996);

[SP] O.Strauch-Š.Porubský: Distribution of Sequences; A Sampler (2005).

Hlavný výsledok tejto teórie je prenesenie metód Monte Carlo do metód kvasi-Monte Carlo. Napríklad v numerickom integrovaní Monte Carlo metóda dáva pravdepodobnostný chybový člen, ktorý je daný ako súčin V(f)D_N Hardy-Krausovej variácie V(f) z integrovateľnej funkcie f(x) a D_N znamená diskrepanciu použitej deterministickej postupnosti x_n , pozri Koksma-Hlawkovu vetu [SP, p. 1-66]. Nedávno Sloan and Wozniakowski [SW], When are quasi-Monte Carlo algorithms efficient for high dimensional integrals ..., J. Complexity, 14 (1998), 1-33, Dick and Pillichshammer [DP], Multivariate integration in weighted Hilbert spaces based on Walsh functions and weighted Sobolev spaces, J. Complexity, 21 (2005), 149-195 a mnoho ďalších prác zaviedlo tak zvané súradnicové váhy ako charakteristiku závislosť funkcie a jej argumentov. Vo vážených Hilbertovych priestoroch špeciálne vo vážených Korobovovych priestoroch a vážených Sobolevovych priestoroch Koksma-Hlawkova veta je platná. Tiež v ďalších aplikáciách metód Monte Carlo náhodné postupnosti môžu byť nahradené pseudonáhodnými postupnosťami.

Generátorom náhodných čísel nazývame každý fyzikálny proces merania, pri ktorom každé ďalšie meranie je nezávislé. Pseudonáhodná postupnosť čísel je postupnosť počítaná podľa nejakého algoritmu, t. j. je deterministická, a navyše spĺňa niektoré ďalšie vlastnosti, ktoré nie sú presne určené, teda jej definícia nie je exaktná. Môže byť nekonečná (t. j. výpočet môžeme prevádzať teoreticky bez obmedzenia) alebo konečná (t. j. po konečnom počte krokov sa začína opakovať). Od nekonečnej pseudonáhodnej postupnosti v intervale požadujeme, aby bola rovnomerne rozdelená, ale aj jej dvojice, trojice, atď. t. j. aby bola úplne rovnomerne rozdelená (Knuthova podmienka pre pseudonáhodnosť).

Najdôležitejšie pseudonáhodné postupnosti sú kongruentné (lineárne, kvadratické, mocninné). Ďalej (t, m, s) – siete so základom b je príklad sieti s veľmi dobrým rozdelením ich bodov v [0, 1)^s. Prakticky, všetky konkrétne konštrukcie (t, m, s)–sieti so základom b sú založené na obecnej schéme konštrukcii „digitálnych bodových sieti”. Larcher, Niederreiter and Schmid [LNS] Digital nets and sequences constructed over finite rings and their applications to quasi-Monte Carlo integration, Monatsh. Math. 121 (1996) 231-253 predstavili algebraickú metódu konštrukcie digitálnych (t, m, s)- sieti nad konečnými grupami a okruhmi. Owen [O] Monte Carlo variance of scrambled net quadrature, SIAM J. Numer. Anal. 34 (5) (1997), 1884-1910 uviedol naviac triedu dobre distribuovaných sieti – tak zvaných (λ, t, m, s)–sieti so základom b a ukázal efektívny analytický algoritmus konštrukcie digitálnych (λ, t, m, s)–sieti. Nedávno Dick [D] Walsh spaces containing smooth functions and quasi-Monte Carlo rules of arbitrary high order (in press) definoval špeciálne digitálne siete, tzv. (t,α,β,σ.n,m,s)–siete nad Z_{b} a ich použitie pre Monte Carlo integrovanie v Sobolevovych priestoroch.

Pod hustotou na množine prirodzených čísel rozumieme každú nezápornú mieru. Základnou hustotou je tzv. asymptotická hustota, Buckova hustota, rovnomerná hustota, logaritmická hustota, váhové hustoty, hustoty vzhľadom k sumačným metódam, špeciálne hustoty vzhľadom k maticovým sumačným metódam a ďalšie. Poznáme tiež tzv. Abelovu hustotu, zeta hustotu, Schnirelmanovu hustotu. Pomocou týchto hustôt môžeme definovať rôzne typy rovnomerného rozdelenia. Pomocou hustoty môžeme definovať aj konvergenciu. To je prípad tzv. I- konvergencie podľa ideálu I, napríklad podľa ideálu nulových množín v zmysle nejakej hustoty. Konkrétne tak dostaneme štatistické konvergenciu, Iu konvergenciu prislúchajúcu k rovnomernej hustote u, atď. Ďalším typom konvergencií sú almost konvergencia, strong p–Ceasaro konvergencia, φ–konvergencia atď. Medzi množinami takto konvergujúcich postupnosti sú študované inklúzie z hľadiska kategórie a topológie.
V danom projekte sa budeme zaoberať nasledujúcimi problémami:

1. Koksma-Hlawkova veta pre postupnosti s malou diskrepanciou nie je vhodná pre kvasi-Monte Carlo integrovanie v prípade veľkých dimenzií. Z tohto dôvodu budeme študovať postupnosti, kde ohraničenie pre diskrepanciu závisí od štvorca dimenzie (pozri S. Heinrich, E. Novak, G.W. Wasilkowski and Wozniakowski [Acta Arith. 96(2001), no. 3, 279--302; MR1814282(2002b:11103)]). Tiež budeme študovať redukciu dimenzie integrovateľnej funkcie f(x).

2. Budeme študovať váženú b-adickú diaphony ľubovoľnej siete bodov v [0,1)^s a tiež špeciálnu (t,m,s)-sieť s malou diskrepanciou (cf. [SP,1-23]) aby sme získali horné ohraničenie váženej b-adickej diaphony (cf. [SP, p. 1-75]).

3. Kombinácie pseudonáhodných postupnosti, problém je nájsť nové pseudonáhodné generátory. Najskôr budeme kombinovať kvadratický generátor s van der Corputovou postupnosťou (ktorá je pseudonáhodná).

4. Náš cieľ je nájsť nové vzťahy medzi rovnomerne rozdelenými postupnosťami vzhľadom k rôznym hustotám a tiež nájsť nové vzťahy medzi rôznymi typmi množín konvegencie.