Algorytm VEGASA

Algorytm VEGAS , opracowany przez G. Petera Lepage'a , jest metodą zmniejszania błędów w symulacjach Monte Carlo poprzez wykorzystanie znanej lub przybliżonej funkcji rozkładu prawdopodobieństwa w celu skoncentrowania wyszukiwania na tych obszarach całki , które mają największy udział w całce końcowej .

Algorytm VEGAS opiera się na próbkowaniu ważności . Próbkuje punkty z rozkładu prawdopodobieństwa opisanego funkcją ${\ Displaystyle | f |,}$ tak, że punkty są skoncentrowane w regionach, które mają największy udział w całce. Biblioteka naukowa GNU (GSL) udostępnia procedurę VEGAS.

Metoda próbkowania

Ogólnie rzecz biorąc, jeśli całka Monte Carlo $jest$ objętości $g}$ z punktami rozłożonymi zgodnie z rozkładem prawdopodobieństwa opisanym przez funkcję otrzymujemy Ω $displaystyle$ oszacować mi $\ Displaystyle \ operatorname {E} _ {g} (f; N)}$

{\ Displaystyle \ operatorname {E} _ {g} (f; N) = {1 \ ponad N} \ suma _ {i} ^ {N} {f (x_ {i})} / g (x_ {i} ).}

Wariancja nowego oszacowania wynosi wtedy

{\ Displaystyle \ operatorname {Var} _ {g} (f; N) = \ operatorname {Var} (f / g; N) }

gdzie $)$ wariancją ${\ Displaystyle \ operatorname {Var} (f; N) = \ operatorname {E} (f ^ {2}; N) - (\ operatorname {E} (f; N)) ^ {2}.}$

Jeśli rozkład prawdopodobieństwa zostanie wybrany jako ${\ Displaystyle g = | f |/\ textstyle \ int _ {\ Omega} | f (x) | dx}$ wtedy można wykazać, że wariancja ${\ Displaystyle \ operatorname {Var} _{g}(f;N)}$ zniknie, a błąd oszacowania wyniesie zero. W praktyce nie jest możliwe pobieranie próbek z dokładnego rozkładu g dla dowolnej funkcji, dlatego algorytmy próbkowania ważności mają na celu uzyskanie wydajnych przybliżeń do pożądanego rozkładu.

Aproksymacja rozkładu prawdopodobieństwa

Algorytm VEGAS aproksymuje dokładny rozkład, wykonując pewną liczbę przejść przez region integracji podczas tworzenia histogramu funkcji f. Każdy histogram służy do zdefiniowania rozkładu próbkowania dla następnego przebiegu. Asymptotycznie ta procedura jest zbieżna do pożądanego rozkładu. Aby uniknąć wzrostu liczby przedziałów histogramu, jak z wymiarem $rozkład$ prawdopodobieństwa jest aproksymowany funkcją rozdzielną: ${\ Displaystyle g (x_ {1}, x_ {2}, \ ldots) = g_ {1} (x_ {1}) g_ {2} (x_ {2})\cdots }$ tak, aby liczba wymaganych pojemników wynosiła tylko Kd . Jest to równoważne z lokalizowaniem pików funkcji na podstawie rzutów całki na osie współrzędnych. Skuteczność VEGAS zależy od słuszności tego założenia. Jest najbardziej wydajny, gdy szczyty całki są dobrze zlokalizowane. Jeśli całkę można zapisać w postaci, która jest w przybliżeniu rozdzielna, zwiększy to efektywność integracji z VEGAS.

Zobacz też