Алгоритм Вегаса

Алгоритм VEGAS , предложенный Дж. Питером Лепажем , ^[1]^[2]^[3] — это метод уменьшения ошибки в моделировании Монте-Карло за счет использования известной или приближенной функции распределения вероятностей для концентрации поиска в тех областях подынтегрального выражения , которые вносят наибольший вклад в окончательный интеграл .

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

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

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

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

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

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

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

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

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

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

См. также

Ссылки

^ Лепаж, врач общей практики (май 1978 г.). «Новый алгоритм адаптивной многомерной интеграции». Журнал вычислительной физики . 27 (2): 192–203. Бибкод : 1978JCoPh..27..192L . дои : 10.1016/0021-9991(78)90004-9 .
^ Лепаж, врач общей практики (март 1980 г.). «VEGAS: Адаптивная программа многомерной интеграции». Корнеллский препринт . КЛНС 80-447.
^ Оль, Т. (июль 1999 г.). «Возврат в Вегас: адаптивная интеграция Монте-Карло за пределами факторизации». Компьютерная физика. Коммуникации . 120 (1): 13–19. arXiv : hep-ph/9806432 . Бибкод : 1999CoPhC.120...13O . дои : 10.1016/S0010-4655(99)00209-X . S2CID 18194240 .

Эта вычислительной физике статья, посвященная , незавершена . Вы можете помочь Википедии, расширив ее .

[Lepage1978-1] Лепаж, врач общей практики (май 1978 г.). «Новый алгоритм адаптивной многомерной интеграции». Журнал вычислительной физики . 27 (2): 192–203. Бибкод : 1978JCoPh..27..192L . дои : 10.1016/0021-9991(78)90004-9 .

[Lepage1980-2] Лепаж, врач общей практики (март 1980 г.). «VEGAS: Адаптивная программа многомерной интеграции». Корнеллский препринт . КЛНС 80-447.

[Ohl1999-3] Оль, Т. (июль 1999 г.). «Возврат в Вегас: адаптивная интеграция Монте-Карло за пределами факторизации». Компьютерная физика. Коммуникации . 120 (1): 13–19. arXiv : hep-ph/9806432 . Бибкод : 1999CoPhC.120...13O . дои : 10.1016/S0010-4655(99)00209-X . S2CID 18194240 .

[1]

[2]

[3]