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

f⁢x⁢=⁢f⁢1-∫x1f′⁢t⁢⁢d⁢t⁢=⁢f⁢1-∫011x,1⁢t⁢⁢f′⁢t⁢⁢d⁢t.

(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,

∅⁢≠⁢U⁢⊆⁢1,2,…,d,

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

W końcu, niech

fU′⁢=⁢∂U⁡f∏j∈U∂⁡uj

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

Zauważmy, że rozwijając f⁢x→ i f⁢t→j zgodnie ze wzorem (15.3) mamy

∫Df⁢x→⁢⁢d⁢x→⁢=⁢f⁢1→+∑U-1U⁢∫DU∫D1x→U,1→U⁢z→U⁢⁢d⁢x→⁢⁢fU′⁢z→U;1⁢⁢d⁢z→U,

1N⁢⁢∑j=1Nf⁢t→j⁢=⁢f⁢1→+∑U-1U⁢∫DU1N⁢∑j=1N1t→jU,1→U⁢z→U⁢⁢fU′⁢z→U;1⁢⁢d⁢z→U.

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

∫D1x→U,1→U⁢z→U⁢⁢d⁢x→⁢=⁢∫DU10→U,z→U⁢x→U⁢⁢d⁢x→U⁢=⁢∏j∈Uzj,

1N⁢⁢∑j=1N1t→jU,1→U⁢z→U⁢=⁢1N⁢⁢#⁢j⁢:⁢t→jU∈0→U,z→U⁢=⁢1N⁢⁢#⁢j⁢:⁢t→j∈0→,z→U;1.

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

Id⁢f-QMCd,N⁢f⁢=⁢∑U-1U⁢∫DUDISCd⁢z→U;1;t→1,…,t→N⋅fU′⁢z→U;1⁢⁢d⁢z→U.

(15.4)

Oznaczmy przez Vd⁢D klasę funkcji f:D→R, których pochodne mieszane fU′ istnieją i są ciągłe dla wszystkich ∅≠U⊆1,…,d.

Zauważmy, że dla d=1,

V1⁢f⁢=⁢∫01f′⁢x⁢⁢d⁢x⁢=⁢sup⁡⁢∑j=1kf⁢zj-f⁢zj-1⁢:⁢k≥1,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.

W nierówności Koksmy-Hlawki czynnik błędu Vd⁢f zależny jedynie od funkcji jest oddzielony od czynnika błędu DISCd*⁢t→1,…,t→N zależnego od wyboru punktów. O ile nie mamy wpływu na wahanie funkcji, możemy starać się wybrać punkty t→j 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 Vd⁢D?

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 f∈Vd⁢D z V⁢f≤1 jedynie do oszacowania z dołu błędu przez c⁢N-1 (a nie c⁢N-r/d).

Okazuje się, że pełne odpowiedzi na zadane pytania nie są znane. Najlepsze ciągi nieskończone t→1⁢,t→2⁢,…,t→n⁢,… spełniają nierówność

DISCd*⁢t→1⁢,…,t→N⁢⁢≤⁢Cd⁢⁢lnd⁡NN,⁢N=1,2,3,…,

gdzie Cd>0 nie zależy od N.

Wydaje się więc, że w klasie Vd⁢D metody quasi-Monte Carlo dają istotnie lepsze wyniki od Monte Carlo, bo błąd nie tylko jest deterministyczny, ale też dla f∈Vd⁢D 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 Cd⁢lnd⁡N 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.

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

n⁢=⁢∑j=0∞aj⁢n⁢⁢bj,

gdzie aj∈0,1,…,b-1 i tylko dla skończonej liczby indeksów j mamy aj≠0. 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

ψb⁢n⁢:=⁢∑j=1∞aj⁢n⁢⁢b-j+1.

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

Kolejne wartości radykalnej odwrotności,

ψb⁢1,ψb⁢2,…,ψb⁢n,…,

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 C1⁢ln⁡N/N. Zauważmy jednak, że dla N=bk-1, k≥1, dostajemy równomierne rozmieszczenie punktów, tzn. tworzą one zbiór j/N+1: 1≤j≤N, 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.

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 h→kk≥1, którego k-ty punkt wynosi

h→k⁢=⁢ψb1⁢k,ψb2⁢k,…,ψbd⁢kT.

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 h→kk≥1 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 s→kk≥1 przedstawimy najpierw zakładając d=1. Niech

a→⁢k=a0⁢k,…,ar-1⁢kT

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

k⁢=⁢a0⁢k+2⁢a1⁢k+⋯+2r-1⁢ar-1⁢k.

Wtedy

sk⁢=⁢y1⁢k2+y2⁢k4+⋯+yr⁢k2r,

gdzie

y1⁢ky2⁢k⋮yr⁢k⁢=⁢V⋅a0⁢ka1⁢k⋮ar-1⁢k⁢⁢mod⁢ 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=v→1,…,v→r możemy równoważnie zapisać

y→⁢k⁢=⁢a0⁢k⋅v→1⊕⋯⊕ar-1⁢k⋅v→r,

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

0⊕0=0,⁢0⊕1=1,⁢1⊕0=1,⁢1⊕1=0.

Dla d≥2, kolejne współrzędne punktu s→k 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.

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

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

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

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.

Następujące twierdzenie jest podstawą wielu konstrukcji ciągów 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.