Metoda quasi-Monte Carlo - Quasi-Monte Carlo method

Sekwencja pseudolosowa

Sobol sekwencja o niskiej rozbieżności liczb pseudo-losowych, pokazano pierwsze 10 (czerwony), 100 (czerwony + niebieski) i 256 (czerwony + niebieskie + zielony) punktów od sekwencji.

256 punktów ze źródła liczb pseudolosowych, sekwencji Haltona i sekwencji Sobola (czerwony = 1, .., 10, niebieski = 11, .., 100, zielony = 101, .., 256). Punkty z sekwencji Sobola są rozłożone bardziej równomiernie.

W analizie numerycznej The sposób quasi Monte Carlo jest sposób numerycznego i rozwiązywania pewnych problemów za pomocą innych sekwencji niskiej rozbieżności (znany także jako sekwencje losowe lub pseudo-losowych sekwencji podgrupy). Jest to przeciwieństwo zwykłej metody Monte Carlo lub integracji Monte Carlo , która opiera się na sekwencjach liczb pseudolosowych .

Metody Monte Carlo i quasi-Monte Carlo są określane w podobny sposób. Problem polega na przybliżeniu całki funkcji f jako średniej z funkcji obliczonej na zbiorze punktów x ₁ , ..., x _N :

${\ Displaystyle \ int _ {[0,1] ^ {s}} f (u) \, {\ rm {d}} u \ około {\ Frac {1} {N}} \, \ sum _ {i = 1} ^ {N} f (x_ {i}).}$

Ponieważ całkujemy po s- wymiarowej kostce jednostkowej, każde x _i jest wektorem s elementów. Różnica między quasi-Monte Carlo a Monte Carlo polega na sposobie wyboru x _i . Quasi Monte Carlo używa sekwencji niskiej rozbieżności takie jak sekwencja Halton , w sekwencji Sobol lub sekwencji Faure, a Monte Carlo używa sekwencji pseudolosowego. Zaletą stosowania sekwencji o niskiej rozbieżności jest szybsza konwergencja. Quasi-Monte Carlo ma współczynnik konwergencji bliski O (1 / N ), podczas gdy dla metody Monte Carlo jest to O ( N ^−0,5 ).

Metoda quasi-Monte Carlo stała się ostatnio popularna w dziedzinie finansów matematycznych lub finansów obliczeniowych . W tych obszarach często występują wielowymiarowe całki numeryczne, w których całka powinna być oceniana w granicach progu ε. Stąd metoda Monte Carlo i metoda quasi-Monte Carlo są korzystne w takich sytuacjach.

Przybliżone granice błędu quasi-Monte Carlo

Błąd aproksymacji metody quasi-Monte Carlo jest ograniczony przez określony proporcjonalna do różnicy zestawu x ₁ , ..., x _N . W szczególności nierówność Koksmy – Hławka stwierdza, że ​​błąd

${\ Displaystyle \ varepsilon = \ lewo | \ int _ {[0,1] ^ {s}} f (u) \, {\ rm {d}} u - {\ frac {1} {N}} \, \ sum _ {i = 1} ^ {N} f (x_ {i}) \ right |}$

jest ograniczony

${\ Displaystyle | \ varepsilon | \ równoważnik V (f) D_ {N},}$

gdzie V ( f ) jest odmianą Hardy'ego-Krause'a funkcji f (szczegółowe definicje podano w Morokoff i Caflisch (1995)). D _N to tak zwana rozbieżność gwiazd zbioru ( x ₁ , ..., x _N ) i jest zdefiniowana jako

${\ Displaystyle D_ {N} = \ sup _ {Q \ podzbiór [0,1] ^ {s}} \ lewo | {\ Frac {{\ tekst {liczba punktów w}} Q} {N}} - \ nazwa operatora {wolumin} (Q) \ right |,}$

gdzie Q jest prostokątną bryłą w [0,1] ^s o bokach równoległych do osi współrzędnych. Nierówność można wykorzystać do wykazania, że ​​błąd aproksymacji metodą quasi-Monte Carlo wynosi , natomiast w metodzie Monte Carlo błąd probabilistyczny wynosi . Choć możemy jedynie określić górną granicę błędu aproksymacji, w praktyce stopień zbieżności metody quasi-Monte Carlo jest zwykle znacznie szybszy niż jej teoretyczna granica. Stąd, ogólnie rzecz biorąc, dokładność metody quasi-Monte Carlo rośnie szybciej niż metody Monte Carlo. Jednak ta zaleta jest gwarantowana tylko wtedy, gdy N jest dostatecznie duże, a zmienność jest skończona. ${\ Displaystyle | \ varepsilon | \ równoważnik V (f) D_ {N}}$${\ Displaystyle O \ lewo ({\ Frac {(\ log N) ^ {s}} {N}} \ prawo)}$${\ Displaystyle O \ lewo ({\ Frac {1} {\ sqrt {N}}} \ prawej)}$

Monte Carlo i quasi-Monte Carlo dla integracji wielowymiarowych

Do integracji jednowymiarowej metody kwadraturowe takie jak trapezów , Metoda Simpsona lub wzorów Newton Cotes są znane jako skuteczne, jeżeli funkcja nie jest gładka. Podejścia te mogą być również wykorzystywane do integracji wielowymiarowych poprzez powtarzanie całek jednowymiarowych w wielu wymiarach. Jednakże ilość oceny funkcji rośnie wykładniczo  s , liczby wymiarów, zwiększa się. Stąd metoda, która może przezwyciężyć tę klątwę wymiarowości, powinna być używana do wielowymiarowych integracji. Standardowa metoda Monte Carlo jest często stosowana, gdy metody kwadraturowe są trudne lub drogie do wdrożenia. Metody Monte Carlo i quasi-Monte Carlo są dokładne i stosunkowo szybkie, gdy wymiar jest duży, do 300 lub więcej.

Morokoff i Caflisch badali wydajność integracji metod Monte Carlo i quasi-Monte Carlo. W artykule sekwencje Haltona, Sobola i Faure'a dla quasi-Monte Carlo porównano ze standardową metodą Monte Carlo przy użyciu sekwencji pseudolosowych. Okazało się, że sekwencja Haltona działa najlepiej dla wymiarów do około 6; sekwencja Sobola działa najlepiej w przypadku wyższych wymiarów; a sekwencja Faure'a, chociaż jest lepsza od pozostałych dwóch, nadal działa lepiej niż sekwencja pseudolosowa.

Jednak Morokoff i Caflisch podali przykłady, w których przewaga quasi-Monte Carlo jest mniejsza niż oczekiwano teoretycznie. Mimo to w przykładach badanych przez Morokoffa i Caflischa metoda quasi-Monte Carlo przyniosła dokładniejszy wynik niż metoda Monte Carlo z taką samą liczbą punktów. Morokoff i Caflisch zauważyć, że korzyść sposobu quasi Monte Carlo jest większa czy podcałkową jest gładka i liczbę wymiarów s całki jest mała.

Wady quasi-Monte Carlo

Lemieux wspomniał o wadach quasi-Monte Carlo:

• Aby być mniejszym niż , musi być mały i musi być duży (np .). Dla dużych s i praktycznych wartości N rozbieżność zbioru punktów z generatora małej rozbieżności może być nie mniejsza niż dla zbioru losowego. ${\ Displaystyle O \ lewo ({\ Frac {(\ log N) ^ {s}} {N}} \ prawo)}$${\ Displaystyle O \ lewo ({\ Frac {1} {\ sqrt {N}}} \ prawej)}$${\ displaystyle s}$${\ displaystyle N}$${\ displaystyle N> 2 ^ {s}}$
• Dla wielu funkcji pojawiających się w praktyce (np. Gdy używane są zmienne Gaussa). ${\ Displaystyle V (f) = \ infty}$
• Znamy tylko górną granicę błędu (tj. Ε ≤ V ( f ) D _N ) i trudno jest obliczyć i . ${\ Displaystyle D_ {N} ^ {*}}$${\ Displaystyle V (f)}$

Aby przezwyciężyć niektóre z tych trudności, możemy użyć randomizowanej metody quasi-Monte Carlo.

Randomizacja quasi-Monte Carlo

Ponieważ sekwencje o niskiej rozbieżności nie są losowe, ale deterministyczna, metoda quasi-Monte Carlo może być postrzegana jako deterministyczny algorytm lub algorytm zderandomizowany. W tym przypadku mamy tylko granicę (np. Ε ≤ V ( f ) D _N ) błędu, a błąd jest trudny do oszacowania. Aby odzyskać naszą zdolność do analizy i oszacowania wariancji, możemy randomizować metodę ( ogólne pojęcie można znaleźć w randomizacji ). Otrzymana metoda nosi nazwę randomizowanej metody quasi-Monte Carlo i może być również postrzegana jako technika redukcji wariancji dla standardowej metody Monte Carlo. Spośród kilku metod najprostszą procedurą transformacji jest losowe przesuwanie. Niech { x ₁ , ..., x _N } będzie punktem wyznaczonym z ciągu niskiej rozbieżności. My objętych próbą s wymiarową wektor losowej U i wymieszać ją z { x ₁ , ..., x _N }. W szczegółach, dla każdego x _j utwórz

${\ displaystyle y_ {j} = x_ {j} + U {\ pmod {1}}}$

i użyj sekwencji zamiast . Jeśli mamy replikacje R dla metody Monte Carlo, próbka losowego wektora s-wymiarowego U dla każdej replikacji. Randomizacja pozwala oszacować wariancję przy jednoczesnym wykorzystaniu sekwencji quasi-losowych. W porównaniu z czystym quasi-Monte-Carlo, liczba próbek sekwencji quasi-losowej zostanie podzielona przez R, aby uzyskać równoważny koszt obliczeniowy, co zmniejsza teoretyczny współczynnik konwergencji. W porównaniu ze standardowym Monte-Carlo wariancja i szybkość obliczeń są nieco lepsze od wyników eksperymentalnych w Tuffin (2008) ${\ displaystyle (y_ {j})}$${\ displaystyle (x_ {j})}$

Zobacz też

• Metoda Monte Carlo
• Metody Monte Carlo w finansach
• Metody quasi-Monte Carlo w finansach
• Biologia metoda Monte Carlo
• Fizyka obliczeniowa
• Sekwencje o niskiej rozbieżności
• Teoria rozbieżności
• Sieć Markowa Monte Carlo

Bibliografia

• RE Caflisch , metody Monte Carlo i quasi-Monte Carlo , Acta Numerica vol. 7, Cambridge University Press, 1998, s. 1–49.
• Josef Dick i Friedrich Pillichshammer, Digital Nets and Sequences. Teoria rozbieżności i integracja quasi-Monte Carlo , Cambridge University Press, Cambridge, 2010, ISBN   978-0-521-19159-3
• Gunther Leobacher i Friedrich Pillichshammer, Wprowadzenie do integracji i zastosowań quasi-Monte Carlo , Compact Textbooks in Mathematics, Birkhäuser, 2014, ISBN   978-3-319-03424-9
• Michael Drmota i Robert F. Tichy, Sekwencje, rozbieżności i zastosowania , Lecture Notes in Math., 1651 , Springer, Berlin, 1997, ISBN   3-540-62606-9
• William J. Morokoff i Russel E. Caflisch , Quasi-losowe sekwencje i ich rozbieżności , SIAM J. Sci. Comput. 15 (1994), nr. 6, 1251–1279 (w CiteSeer : [2] )
• Harald Niederreiter . Generowanie liczb losowych i metody quasi-Monte Carlo. Towarzystwo Matematyki Przemysłowej i Stosowanej, 1992. ISBN   0-89871-295-5
• Harald G. Niederreiter , Metody quasi-Monte Carlo i liczby pseudolosowe , Bull. Amer. Matematyka. Soc. 84 (1978), nie. 6, 957–1041
• Oto Strauch i Štefan Porubský, Distribution of Sequences: A Sampler , Peter Lang Publishing House, Frankfurt nad Menem 2005, ISBN   3-631-54013-2

Linki zewnętrzne

• Strona MCQMC Wiki zawiera wiele bezpłatnych materiałów online na temat metod Monte Carlo i quasi-Monte Carlo
• Bardzo intuicyjne i kompleksowe wprowadzenie do metod quasi-Monte Carlo