Zagadnienia

15. Metody quasi-Monte Carlo

15.1. Co to są metody quasi-Monte Carlo?

Metody Monte Carlo potrafią pokonać przekleństwo wymiaru, mają jednak również swoje wady. Najważniejsze z nich to:

  • (i) niepewność wyniku (który ma charakter probablistyczny),

  • (ii) stosunkowo wolna zbieżność (praktycznie N-1/2),

  • (iii) konieczność stosowania (niekiedy skomplikowanych) generatorów liczb losowych.

Można powiedzieć, że skoro używamy z powodzeniem generatorów liczb pseudo-losowych, to implementacje Monte Carlo są w istocie deterministyczne. Dlatego, wybierając punkty deterministycznie, ale tak, aby w jakiś sposób ,,udawały” i ,,uśredniały” wybór losowy, powinniśmy dostać metodę deterministyczną o zbieżności co najmniej N-1/2. A przy okazji usunęlibyśmy dwie z wymienionych wad Monte Carlo.

Takie intuicyjne myślenie wydaje się nie mieć racjonalnych podstaw, bo przecież metody deterministyczne podlegają przekleństwu wymiaru. Pamiętajmy jednak, że twierdzenie 13.4 o przekleństwie zachodzi w klasie FrD funkcji różniczkowalnych r razy po każdej zmiennej. Zwróciliśmy na to uwagę już na początku rozdziału 14. Dlatego zasadne jest poszukiwanie pozytywnych rozwiązań dla funkcji o innej regularności.

Quasi-Monte Carlo jest deterministycznym odpowiednikiem klasycznej metody Monte Carlo dla aproksymacji całek na kostkach,

Idf:=Dfxdx,D=0,1d.
Definicja 15.1

Metoda quasi-Monte Carlo polega na przybliżeniu Idf średnią arytmetyczną,

QMCd,Nf=QMCd,Nt1,,tN:=1nj=1Nftj,

gdzie t1,t2,,tN są pewnymi szczególnymi punktami w D wybranymi w sposób deterministyczny.

Przez długi czas od swojego powstania uważano, że metody quasi-Monte Carlo są efektywne jedynie dla całek o niskich wymiarach. Dopiero pod koniec lat 90-tych ubiegłego wieku zauważono, że dają istotnie lepsze wyniki niż Monte Carlo w obliczaniu wartości niektórych instrumentów finansowych. Obecnie quasi-Monte Carlo jest powszchnie uznaną i bardzo popularną metodą, której znaczenie trudno przecenić mimo, że dotychczas nie udało się znaleźć pełnego teoretycznego wytłumaczenia jej efektywności.

15.2. Dyskrepancja

Rozważania na temat quasi-Monte Carlo zaczniemy od zdefiniowania pojęcia dyskrepancji, które odgrywa fundamentalną rolę w analizie efektywności tych metod.

Dla x=x1,,xdTD niech

0,x:=×0,x1××0,xd

oznacza d wymiarowy prostokąt w D, ,,zakotwiczony” w zerze. Zakładamy przy tym, że 0,0=.

Definicja 15.2

Dyskrepancją (z gwiazdką) danego zbioru N punktów tj0,1d, 1jN, nazywamy wielkość

DISCd*t1,,tN=supxDDISCdx;t1,,tN,

gdzie

DISCdx;t1,,tN=x1xd-#j:tj0,xN,

a #A oznacza liczbę elementów zbioru A.

Ponieważ x1xd jest d-wymiarową objętością prostokąta 0,x, dyskrepancja pokazuje jak dobrze danych N punktów aproksymuje objętości tych prostokątów. Równoważnie, oznaczając przez 10,x funkcję charakterystyczną prostokąta 0,x mamy

D10,xtdt=x1xdoraz1Nj=1N10,xtj=#j:tj0,xN.

Stąd dyskrepancję można również interpretować jako maksymalny błąd aproksymacji funkcji charakterystycznych prostokątów przez odpowiedni algorytm quasi-Monte Carlo.

Pojęcie dyskrepancji zilustrujemy najpierw na przykładzie jednowymiarowym d=1. Nietrudno pokazać, że dla dowolnych tj

DISC1*t1,,tN12N.(15.1)

Rzeczywiście, DISC1x;t1,,tN jako funkcja x ma na każdym z przedziałów 0,t1, tj-1,tj, 2jN, pochodną równą 1, oraz przyjmuje zero dla x=0. Zatem, jeśli dyskrepancja byłaby mniejsza od 1/2N to mielibyśmy

t1<12N,tj-tj-1<1N,2jN,

a stąd

tN=t1+j=2Ntj-tj-1<12N+N-1N= 1-12N.

Otrzymujemy sprzeczność, bo dla tN<x<1-1/2N

DISC1x;t1,,tN<1-12N-1=-12N.

Z dowodu wynika, że równość w (15.1) zachodzi jedynie dla równomiernego rozmieszczenia punktów,

tj*=j-1/2N,1jN.

W tym przypadku algorytm QMC1,N redukuje się do zasady punktu środkowego.

Z punktu widzenia praktycznych obliczeń dobrze byłoby mieć ciąg nieskończony

t1,t2,,tn,0,1

i konstruować kolejne aproksymacje używając N początkowych wyrazów tego ciągu. Ciekawe, że wtedy zbieżność N-1 nie może być zachowana. Dokładniej, można pokazać istnienie c>0 takiego, że dla każdego ciągu nierówność

DISC1*t1,,tNclnNN

zachodzi dla nieskończenie wielu N.

Analiza dyskrepancji w wymiarach d2 just dużo bardziej skomplikowana. Na razie ograniczymy się do zauważenia, że siatka równomierna jest fatalnym wyborem. Dokładniej, niech

tj1,,jd=tj1*,,tjd*T,1jin,1id,

będzie równomiernym rozkładem N=nd punktów w D. Rozpatrzenie prostokąta

0,12n×0,1××0,1d-1

wystarcza, aby się przekonać, że wtedy dyskrepancja wynosi co najmniej 12n=12N-1/d.

15.3. Błąd quasi-Monte Carlo

15.3.1. Formuła Zaremby

Jeśli f:0,1R jest funkcją różniczkowalną to dla każdego x mamy

fx=f1-x1ftdt=f1-011x,1tftdt.(15.2)

Wzór ten uogólnimy na przypadek funkcji wielu zmiennych w następujący sposób.

Najpierw wprowadzimy kilka niezbędnych oznaczeń. Dla podzbioru indeksów U,

U1,2,,d,

niech DU=0,1U, gdzie U jest liczbą elementów w U. Niech dalej xUDU będzie wektorem powstałym z wektora x=x1,x2,,xdTD poprzez usunięcie współrzędnych xj z jU, a xU;1D wektorem, którego j-ta współrzędna wynosi xj dla jU oraz wynosi 1 dla jU. Na przykład, jeśli d=5 i U=1,4 to dla x=x1,x2,x3,x4,x5T mamy xU=x1,x4T i xU;1=x1,1,1,x4,1T.

W końcu, niech

fU=UfjUuj

będzie skrótowym zapisem odpowiedniej pochodnej mieszanej funkcji f.

Lemat 15.1

Jeśli funkcja f:DR ma ciągłe pochodne cząstkowe mieszane fU dla wszystkich U1,2,,d to

fx=f1+U-1UDU1xU,1UzUfUzU;1dzU,xD(15.3)

(1=1,1,,1Rd).

Dowód

Dowód przeprowadzimy przez indukcję względem d. Dla d=1 równość (15.3) jest równoważna (15.2). Niech więc d2. Stosując założenie indukcyjne do f z ustaloną ostatnią współrzędną xd mamy

fx=fxd;1+V-1VDV1xV,1VzVfVzV,xd;1dzV,

gdzie sumowanie jest po wszystkich V1,2,,d-1. Stosując dalej wzór (15.2) ze względu na xd odpowiednio do fxd;1 i fVzV,xd;1 dostajemy

fx=f1-Dd1xd,1dzdfdzd;1dzd
+-1VDV1xV,1VzVfVzV;1dzV
+Vd-1VdDVd1xVd,1VdzVdfVdzVd;1dzVd.

Teraz wystarczy porównać otrzymaną formułę do prawej strony (15.3). Drugi składnik odpowiada U=d, trzeci składnik podzbiorom U do których nie należy d, a czwarty podzbiorom U takim, że dU i U2.

Zauważmy, że rozwijając fx i ftj zgodnie ze wzorem (15.3) mamy

Dfxdx=f1+U-1UDUD1xU,1UzUdxfUzU;1dzU,
1Nj=1Nftj=f1+U-1UDU1Nj=1N1tjU,1UzUfUzU;1dzU.

Ponieważ wartość funkcji charakterystycznej odcinka a,b w punkcie c jest równa wartości funkcji charakterystycznej odcinka 0,c w punkcie a to

D1xU,1UzUdx=DU10U,zUxUdxU=jUzj,
1Nj=1N1tjU,1UzU=1N#j:tjU0U,zU=1N#j:tj0,zU;1.

Stąd otrzymujemy następującą formułę Zaremby na błąd quasi-Monte Carlo:

Idf-QMCd,Nf=U-1UDUDISCdzU;1;t1,,tNfUzU;1dzU.(15.4)

15.3.2. Nierówność Koksmy-Hlawki

Oznaczmy przez VdD klasę funkcji f:DR, których pochodne mieszane fU istnieją i są ciągłe dla wszystkich U1,,d.

Definicja 15.3

Wahaniem (w sensie Hardy-Krause) funkcji fVdD nazywamy wielkość

Vdf:=UDUfUzU;1dzU.

Zauważmy, że dla d=1,

V1f=01fxdx=supj=1kfzj-fzj-1:k1,0=z0<z1<<zk=1

jest wahaniem funkcji w klasycznym sensie. Następujące bardzo ważne oszacowanie błędu metody quasi-Monte Carlo nosi nazwę nierówności Koksmy-Hlawki.

Twierdzenie 15.1

Jeśli fVdD to błąd metody quasi-Monte Carlo

QMCd,Nf=1Nj=1Nftj

dla aproksymacji całki Id=Dfxdx szacuje się przez

Idf-QMCd,NfDISCd*t1,,tNVdf.
Dowód

Nierówność wynika natychmiast z formuły Zaremby (15.4), bowiem

Idf-QMCd,NfUDUDISCdzU;1;t1,,tNfUzU;1dzU
DISCd*t1,,tNUDUfUzU;1dzU.

W nierówności Koksmy-Hlawki czynnik błędu Vdf zależny jedynie od funkcji jest oddzielony od czynnika błędu DISCd*t1,,tN zależnego od wyboru punktów. O ile nie mamy wpływu na wahanie funkcji, możemy starać się wybrać punkty tj tak, aby zminimalizować ich dyskrepancję. Zasadnicze pytanie brzmi: jak mała może być dyskrepacja? W szczególności, czy można wybrać nieskończony ciąg punktów tak, że oparte na nim algorytmy quasi-Monte Carlo pokonują przekleństwo wymiaru w klasie VdD?

Na miejscu jest teraz uwaga, że dzięki obecności pochodnych mieszanych rozumowanie analogiczne do tego z dowodu twierdzenia 13.4 prowadzi w klasie funkcji fVdD z Vf1 jedynie do oszacowania z dołu błędu przez cN-1 (a nie cN-r/d).

Okazuje się, że pełne odpowiedzi na zadane pytania nie są znane. Najlepsze ciągi nieskończone t1,t2,,tn, spełniają nierówność

DISCd*t1,,tNCdlndNN,N=1,2,3,,

gdzie Cd>0 nie zależy od N.

Wydaje się więc, że w klasie VdD metody quasi-Monte Carlo dają istotnie lepsze wyniki od Monte Carlo, bo błąd nie tylko jest deterministyczny, ale też dla fVdD zbiega do zera dużo szybciej, tzn. błąd jest rzędu N-1+ϵ dla dowolnego ϵ>0 w przypadku quasi-Monte Carlo, oraz N-1/2 w przypadku Monte Carlo. Nie do końca jest to prawdą. Zauważmy bowiem, że w praktycznych obliczeniach wnioski asymptotyczne nie mają zastosowania, gdy wymiar d jest bardzo duży. Wtedy czynnik CdlndN może mieć istotne znaczenie i wręcz sprawiać, że nierówność Koksmy-Hlawki staje się bezużyteczna. Dodatkowo, dobre oszacowanie Cd jest wyjątkowe trudne.

A jednak metody quasi-Monte Carlo są z powodzeniem stosowane w praktyce obliczeniowej nawet dla dużych wymiarów d. Istnieje wiele hipotez tworzonych w celu wyjaśnienia tego pozornego paradoksu. Jedna z najbardziej popularnych i już dość dobrze uzasadnionych teoretycznie mówi, że w praktyce mamy co prawda do czynienia z funkcjami bardzo wielu zmiennych, ale istotnych jest jedynie kilka zmiennych albo grupy kilku zmiennych. Matematycznie oznacza to, że w odpowiadających tym założeniom przestrzeniach zachodzą dużo mocniejsze odpowiedniki nierówności Koksmy-Hlawki.

15.4. Ciągi o niskiej dyskrepancji

Definicja 15.4

Ciąg nieskończony t1,t2,t3, nazywamy ciągem o niskiej dyskrepancji jeśli istnieje Cd>0 taka, że dla wszystkich N

DISCd*t1,,tNCdlndNN.

Istnieje bardzo dużo efektywnych konstrukcji ciągów punktów o niskiej dyskrepancji. Teraz poznamy jedynie kilka najbardziej popularnych z nich.

15.4.1. Ciąg Van der Corputa

Niech b2 będzie ustaloną liczbą naturalną. Wtedy dowolną liczbę naturalną n można jednoznacznie przedstawić w postaci

n=j=0ajnbj,

gdzie aj0,1,,b-1 i tylko dla skończonej liczby indeksów j mamy aj0. Mówiąc inaczej, aj są kolejnymi cyframi rozwinięcia liczby n w bazie b. Wykorzystując powyższe rozwinięcie funkcję radykalnej odwrotności ψb:0,1,2,0,1 definujemy jako

ψbn:=j=1ajnb-j+1.

Na przykład, dla bazy b=2 mamy 13=20+22+23=11012, czyli ψ213=12+18+116=1116.

Kolejne wartości radykalnej odwrotności,

ψb1,ψb2,,ψbn,,

tworzą jednowymiarowy ciąg Van der Corputa. Dla b=2 kolejne punkty ciągu wynoszą więc

12,14,34,18,58,38,78,116,916,516,1316,316,1116,716,1516,132,1732,

Ciąg Van der Corputa jest ciągiem o niskiej dyskrepancji dla dowolnie dobranej bazy b, tzn. dyskrepancja N początkowych wyrazów szacuje się z góry przez C1lnN/N. Zauważmy jednak, że dla N=bk-1, k1, dostajemy równomierne rozmieszczenie punktów, tzn. tworzą one zbiór j/N+1: 1jN, którego dyskrepancja wynosi N+1-1. Stąd, pożądane są raczej mniejsze bazy b; im większe b tym rzadziej ze względu na N osiągana jest dyskrepancja proporcjonalna do 1/N.

15.4.2. Konstrukcje Haltona i Sobol'a

Jednowymiarowy ciąg Van der Corputa jest podstawą konstrukcji wielu ciągów w wyższych wymiarach d. Jedna z nich prowadzi do ciągu Haltona hkk1, którego k-ty punkt wynosi

hk=ψb1k,ψb2k,,ψbdkT.

Liczby b1,,bd są tu danymi bazami. Od razu zauważamy, że wybór b1==bd nie jest dobry, bo prowadzi do siatki równomiernej w 0,1d, zob. rozdział 15.2. Jeśli jednak bi są liczbami pierwszymi to hkk1 jest już ciągiem o niskiej dyskrepancji.

Minusem konstrukcji Haltona jest to, że dla dużych wymiarów d bazy bd też są duże co, jak wcześniej zauważyliśmy, nie jest korzystne. Problemu tego unika bardziej skomplikowana konstrukcja Sobol'a, gdzie na każdej zmiennej pracujemy z tą samą bazą b=2.

Ideę konstrukcji ciągu Sobol'a skk1 przedstawimy najpierw zakładając d=1. Niech

ak=a0k,,ar-1kT

będzie wektorem kolejnych bitów w rozwinięciu dwójkowym liczby k,

k=a0k+2a1k++2r-1ar-1k.

Wtedy

sk=y1k2+y2k4++yrk2r,

gdzie

y1ky2kyrk=Va0ka1kar-1kmod 2,

a V jest specjalnie dobraną macierzą o elementach 0 i 1, zwaną macierzą generującą. (Zauważmy, że jeśli V jest identycznością to otrzymany ciąg jest ciągiem Van der Corputa.)

Oznaczając V=v1,,vr możemy równoważnie zapisać

yk=a0kv1ar-1kvr,

gdzie jest operacją XOR, czyli dodawaniem bitów modulo 2,

00=0,01=1,10=1,11=0.

Dla d2, kolejne współrzędne punktu sk wyliczane są według powyższej recepty, ale używając różnych macierzy generujących V. I właśnie problem wyboru macierzy generujących tak, aby otrzymać ciąg o niskiej dyskrepancji jest istotą konstrukcji Sobol'a. Dodajmy, że jest to problem wysoce nietrywialny.

15.4.3. Sieci t,m,d i ciągi t,d

Dla b2 definiujemy b-prostokąt w 0,1d jako

a1bj1,a1-1bj1××adbjd,ad-1bjd,

gdzie ji0,1,2,, ai0,1,,bji-1, 1id. Na przykład, jeśli d=1 i b=2 to przedziały 3/4,1 i 3/4,7/8b-prostokątami, ale nie jest nim 5/8,7/8. Zauważmy, że objętość b-prostokąta wynosi b-j1++jd.

Definicja 15.5

Niech b2 i 0tm. Siecią t,m,d w bazie b nazywamy zbiór bm punktów w 0,1d o własności, że w każdym b-prostokącie o objętości bt-m znajduje się dokładnie bt punktów tego zbioru.

Mówiąc inaczej, sieć t,m,d dokładnie pokazuje objętości b-prostokątów poprzez iloraz bt/bm liczby punktów, które należą do prostokąta do liczby wszystkich punktów.

Definicja 15.6

Ciąg nieskończony t1,t2, w 0,1d nazywamy ciągiem t,d w bazie b jeśli dla wszystkich m>t i j=0,1,2, segment

ti:jbm<ij+1bm

jest siecią t,m,d w bazie b.

Następujące twierdzenie jest podstawą wielu konstrukcji ciągów o niskiej dyskrepancji.

Twierdzenie 15.2

Każdy ciąg t,d w bazie b jest ciągiem o niskiej dyskrepancji.

Pokazanie konkretnych konstrukcji ciągów t,d wykracza poza ramy tego wykładu. Powiemy tylko, że szczególne wybory macierzy generujących w konstrukcji Sobol'a prowadzą do ciągów t,d. Inne konstrukcje należą do Faure'a, Niederreitera, Tezuki i in.

Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.

Projekt współfinansowany przez Unię Europejską w ramach Europejskiego Funduszu Społecznego.

Projekt współfinansowany przez Ministerstwo Nauki i Szkolnictwa Wyższego i przez Uniwersytet Warszawski.