Алгоритм VEGAS

редактировать

Алгоритм

алгоритм VEGAS, в связи с G. Питер Лепаж, представляет собой метод уменьшения ошибки в моделировании Монте-Карло с помощью известной или приближенной функции распределения вероятностей для концентрации поиска в этих областях. от подынтегрального выражения, которые вносят наибольший вклад в окончательный интеграл.

Алгоритм VEGAS основан на выборке по важности. Он выбирает точки из распределения вероятностей, описываемого функцией $| f |, {\ displaystyle | f |,}$ ${\ displaystyle | f |,}$ , чтобы точки концентрировались в областях, которые вносят наибольший вклад в интеграл. Научная библиотека GNU (GSL) предоставляет процедуру VEGAS.

Содержание

1 Метод выборки
2 Аппроксимация вероятностного распределения
3 См. Также
4 Ссылки

Метод выборки

Как правило, если интеграл Монте-Карло $f {\ displaystyle f}$ $f$ по объему $Ω {\ displaystyle \ Omega}$ $\ Omega$ выбирается с точками, распределенными в соответствии с распределением вероятностей, описываемым функцией $g, {\ displaystyle g,}$ ${\ displaystyle g,}$ , мы получаем оценку $E g (f; N), { \ Displaystyle \ mathrm {E} _ {g} (f; N),}$ ${\ displaystyle \ mathrm {E} _ {g} (f; N),}$

E g (f; N) = 1 N ∑ я N f (xi) / g (xi). {\ displaystyle \ mathrm {E} _ {g} (f; N) = {1 \ over N} \ sum _ {i} ^ {N} {f (x_ {i})} / g (x_ {i}).}

{\ displaystyle \ mathrm {E} _ {g} (f; N) = {1 \ over N} \ sum _ {i} ^ {N } {е (x_ {i})} / g (x_ {i}).}

Тогда дисперсия новой оценки равна

V arg (f; N) = V ar (f / g; N) {\ displaystyle \ mathrm {Var} _ { g} (f; N) = \ mathrm {Var} (f / g; N)}

{\ displaystyle \ mathrm {Var} _ {g} (f; N) = \ mathrm {Var} (f / g; N)}

где $V ar (f; N) {\ displaystyle \ mathrm {Var} (f; N)}$ ${\ displaystyle \ mathrm {Var} (f; N)}$ - дисперсия исходной оценки, $V ar (f; N) = E (f 2; N) - (E (f; N)) 2. {\ displaystyle \ mathrm {Var} (f; N) = \ mathrm {E} (f ^ {2}; N) - (\ mathrm {E} (f; N)) ^ {2}.}$ ${\ displaystyle \ mathrm {Var} (f; N) = \ mathrm {E} (f ^ {2}; N) - (\ mathrm {E} (f; N)) ^ {2}.}$

Если распределение вероятностей выбрано как $g = | f | / ∫ Ω | f (x) | dx {\ displaystyle g = | f | / \ textstyle \ int _ {\ Omega} | f (x) | dx}$ ${\ displaystyle g = | f | / \ textstyle \ int _ {\ Omega} | f (x) | dx}$ то можно показать, что дисперсия $V arg (f; N) {\ displaystyle \ mathrm {Var} _ {g} (f; N)}$ ${\ displaystyle \ mathrm {Var} _ {g} (f; N)}$ исчезает, и ошибка в оценке будет равна нулю. На практике невозможно выполнить выборку из точного распределения g для произвольной функции, поэтому алгоритмы выборки по важности нацелены на получение эффективных приближений к желаемому распределению.

Аппроксимация вероятностного распределения

Алгоритм VEGAS аппроксимирует точное распределение путем выполнения ряда проходов по области интегрирования при гистограмме функции f. Каждая гистограмма используется для определения распределения выборки для следующего прохода. Асимптотически эта процедура сходится к желаемому распределению. Во избежание увеличения количества ячеек гистограммы, например $K d {\ displaystyle K ^ {d}}$ ${\ displaystyle K ^ {d}}$ с размером d, распределение вероятностей аппроксимируется разделяемой функцией: $g (x 1, Икс 2,…) знак равно г 1 (Икс 1) г 2 (Икс 2) ⋯ {\ Displaystyle g (x_ {1}, x_ {2}, \ ldots) = g_ {1} (x_ {1}) g_ {2} (x_ {2}) \ cdots}$ ${\ displaystyle g (x_ {1}, x_ {2}, \ ldots) = g_ {1} (x_ {1}) g_ {2 } (x_ {2}) \ cdots}$ , так что количество требуемых интервалов составляет всего Kd. Это эквивалентно размещению пиков функции из проекций подынтегрального выражения на оси координат. От правильности этого предположения зависит эффективность VEGAS. Это наиболее эффективно, когда пики подынтегрального выражения хорошо локализованы. Если подынтегральное выражение можно переписать в форме, которая приблизительно разделяется, это повысит эффективность интеграции с VEGAS.

См. Также

Ссылки