Discrepancy of sequences and error estimates for the quasi-Monte Carlo method
2020 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE credits
Student thesisAlternative title
Diskrepansen hos talföljder och feluppskattningar för kvasi-Monte Carlo metoden (Swedish)
Abstract [en]
We present the notions of uniform distribution and discrepancy of sequences contained in the unit interval, as well as an important application of discrepancy in numerical integration by way of the quasi-Monte Carlo method. Some fundamental (and other interesting) results with regards to these notions are presented, along with some detalied and instructive examples and comparisons (some of which not often provided by the literature). We go on to analytical and numerical investigations of the asymptotic behaviour of the discrepancy (in particular for the van der Corput-sequence), and for the general error estimates of the quasi-Monte Carlo method. Using the discoveries from these investigations, we give a conditional proof of the van der Corput theorem. Furthermore, we illustrate that by using low discrepancy sequences (such as the vdC-sequence), a rather fast convergence rate of the quasi-Monte Carlo method may still be achieved, even for situations in which the famous theoretical result, the Koksma inequality, hasbeen rendered unusable.
Abstract [sv]
Vi presenterar begreppen likformig distribution och diskrepans hos talföljder på enhetsintervallet, såväl som en viktig tillämpning av diskrepans inom numerisk integration via kvasi-Monte Carlo metoden. Några fundamentala (och andra intressanta) resultat presenteras med avseende på dessa begrepp, tillsammans med några detaljerade och instruktiva exempel och jämförelser (varav några sällan presenterade i litteraturen). Vi går vidare med analytiska och numeriska undersökningar av det asymptotiska beteendet hos diskrepansen (särskilt för van der Corput-följden), såväl som för den allmänna feluppskattningen hos kvasi-Monte Carlo metoden. Utifrån upptäckterna från dessa undersökningar ger vi ett villkorligt bevis av van der Corput's sats, samt illustrerar att man genom att använda lågdiskrepanstalföljder (som van der Corput-följden) fortfarande kan uppnå tämligen snabb konvergenshastighet för kvasi-Monte Carlo metoden. Detta även för situationer där de kända teoretiska resultatet, Koksma's olikhet, är oandvändbart.
Place, publisher, year, edition, pages
2020. , p. 36
Keywords [en]
discrepancy, low discrepancy sequences, van der Corput, quasi-Monte Carlo, Koksma inequality, error estimates
Keywords [sv]
diskrepans, lågdiskrepanstalföljder, van der Corput, kvasi-Monte Carlo, Koksmas olikhet, feluppskattningar
National Category
Mathematics
Identifiers
URN: urn:nbn:se:kau:diva-78525OAI: oai:DiVA.org:kau-78525DiVA, id: diva2:1443767
Subject / course
Mathematics
Supervisors
Examiners
2020-06-222020-06-182020-06-22Bibliographically approved