Интеграция Монте-Карло - Monte Carlo integration

Иллюстрация интеграции Монте-Карло. В этом примере домен D - внутренний круг, а область E - квадрат. Поскольку площадь квадрата (4) легко вычисляется, площадь круга (π * 1,0²) можно оценить по отношению (0,8) точек внутри круга (40) к общему количеству точек (50), что дает приближение для площади круга 4 * 0,8 = 3,2 ≈ π.

В математика, Интеграция Монте-Карло это техника для численное интегрирование с помощью случайные числа. Это особый Метод Монте-Карло который численно вычисляет определенный интеграл. В то время как другие алгоритмы обычно оценивают подынтегральное выражение на регулярной сетке,^[1] Монте-Карло случайным образом выбирает точки, в которых вычисляется подынтегральное выражение.^[2] Этот метод особенно полезен для многомерных интегралов.^[3]

Существуют разные методы для выполнения интеграции Монте-Карло, такие как единообразный отбор проб, стратифицированная выборка, выборка по важности, последовательный Монте-Карло (также известный как фильтр твердых частиц), и методы частиц среднего поля.

Обзор

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

Проблема, которую решает интегрирование Монте-Карло, состоит в вычислении многомерный определенный интеграл

${\displaystyle I=\int _{\Omega }f({\overline {\mathbf {x} }})\,d{\overline {\mathbf {x} }}}$

где Ω, подмножество р^м, имеет объем

${\displaystyle V=\int _{\Omega }d{\overline {\mathbf {x} }}}$

Наивный подход Монте-Карло состоит в том, чтобы выбрать точки равномерно на Ω:^[4] данный N форменные образцы,

${\displaystyle {\overline {\mathbf {x} }}_{1},\cdots ,{\overline {\mathbf {x} }}_{N}\in \Omega ,}$

я можно приблизительно оценить

${\displaystyle I\approx Q_{N}\equiv V{\frac {1}{N}}\sum _{i=1}^{N}f({\overline {\mathbf {x} }}_{i})=V\langle f\rangle }$.

Это потому, что закон больших чисел гарантирует, что

${\displaystyle \lim _{N\to \infty }Q_{N}=I}$.

Учитывая оценку я из Q_N, планки ошибок Q_N можно оценить по выборочная дисперсия с использованием объективная оценка дисперсии.

${\displaystyle \mathrm {Var} (f)\equiv \sigma _{N}^{2}={\frac {1}{N-1}}\sum _{i=1}^{N}\left(f({\overline {\mathbf {x} }}_{i})-\langle f\rangle \right)^{2}.}$

что приводит к

${\displaystyle \mathrm {Var} (Q_{N})={\frac {V^{2}}{N^{2}}}\sum _{i=1}^{N}\mathrm {Var} (f)=V^{2}{\frac {\mathrm {Var} (f)}{N}}=V^{2}{\frac {\sigma _{N}^{2}}{N}}}$.

Пока последовательность

${\displaystyle \left\{\sigma _{1}^{2},\sigma _{2}^{2},\sigma _{3}^{2},\ldots \right\}}$

ограничена, эта дисперсия асимптотически убывает до нуля как 1 /N. Оценка погрешности Q_N таким образом

${\displaystyle \delta Q_{N}\approx {\sqrt {\mathrm {Var} (Q_{N})}}=V{\frac {\sigma _{N}}{\sqrt {N}}},}$

который убывает как ${\displaystyle {\tfrac {1}{\sqrt {N}}}}$. Это стандартная ошибка среднего умноженный на ${\displaystyle V}$. Этот результат не зависит от количества измерений интеграла, что является обещанным преимуществом интегрирования Монте-Карло по сравнению с большинством детерминированных методов, которые экспоненциально зависят от размерности.^[5] Важно отметить, что, в отличие от детерминированных методов, оценка ошибки не является строгой границей ошибки; случайная выборка может не раскрыть всех важных характеристик подынтегрального выражения, которые могут привести к недооценке ошибки.

В то время как наивный метод Монте-Карло работает для простых примеров, улучшение по сравнению с детерминированными алгоритмами может быть достигнуто только с помощью алгоритмов, использующих специфические для задачи распределения выборки. С соответствующим распределением выборок можно использовать тот факт, что почти все подынтегральные выражения более высокой размерности очень локализованы. и только небольшое подпространство дает заметный вклад в интеграл^[6].Большая часть литературы по Монте-Карло посвящена разработке стратегий для улучшения оценок ошибок. В частности, стратифицированная выборка - разделение региона на поддомены - и выборка по важности - выборка из неравномерных распределений - два таких метода.

Пример

Относительная ошибка как функция количества выборок, показывающая масштабирование ${\displaystyle {\tfrac {1}{\sqrt {N}}}}$

Парадигматическим примером интеграции Монте-Карло является оценка π. Рассмотрим функцию

${\displaystyle H\left(x,y\right)={\begin{cases}1&{\text{if }}x^{2}+y^{2}\leq 1\\0&{\text{else}}\end{cases}}}$

и множество Ω = [−1,1] × [−1,1] с V = 4. Обратите внимание, что

${\displaystyle I_{\pi }=\int _{\Omega }H(x,y)dxdy=\pi .}$

Таким образом, грубый способ вычисления значения π с помощью интегрирования Монте-Карло состоит в том, чтобы выбрать N случайные числа на Ω и вычислить

${\displaystyle Q_{N}=4{\frac {1}{N}}\sum _{i=1}^{N}H(x_{i},y_{i})}$

На рисунке справа относительная погрешность ${\displaystyle {\tfrac {Q_{N}-\pi }{\pi }}}$ измеряется как функция N, подтверждая ${\displaystyle {\tfrac {1}{\sqrt {N}}}}$.

Пример C

Имейте в виду, что следует использовать настоящий генератор случайных чисел.

int я, бросает = 99999, insideCircle = 0;двойной randX, похотливый, число Пи;srand(время(НОЛЬ));за (я = 0; я < бросает; ++я) {  randX = ранд() / (двойной) RAND_MAX;  похотливый = ранд() / (двойной) RAND_MAX;  если (randX * randX + похотливый * похотливый < 1) ++insideCircle;}число Пи = 4.0 * insideCircle / бросает;

Пример Wolfram Mathematica

Код ниже описывает процесс интеграции функции

${\displaystyle f(x)={\frac {1}{1+\sinh(2x)\log(x)^{2}}}}$

из ${\displaystyle 0.8<x<3}$ используя метод Монте-Карло в Mathematica:

func[Икс_]:=1/(1+Sinh[2*Икс]*(Бревно[Икс])^2);(* Образец из усеченного нормального распределения для ускорения сходимости *)Распределить[Икс_,средний_,var_]:=PDF[Нормальное распределение[средний,вар],1.1*Икс-0.1];п=10;RV=RandomVariate[TruncatedDistribution[{0.8,3},Нормальное распределение[1,0.399]],п];Int=1/пОбщий[func[RV]/Распределить[RV,1,0.399]]*Интегрировать[Распределить[Икс,1,0.399],{Икс,0.8,3}]NIntegrate[func[Икс],{Икс,0.8,3}](* Сравните с реальным ответом *)

Рекурсивная стратифицированная выборка

Смотрите также: Стратифицированная выборка

Иллюстрация рекурсивной стратифицированной выборки. В этом примере функция: ${\displaystyle f(x,y)={\begin{cases}1&x^{2}+y^{2}<1\\0&x^{2}+y^{2}\geq 1\end{cases}}}$
из приведенной выше иллюстрации был интегрирован в единичный квадрат с использованием предложенного алгоритма. Отобранные точки были записаны и нанесены на график. Ясно стратифицированный алгоритм выборки концентрирует точки в регионах, где вариация функции наибольшая.

Рекурсивная стратифицированная выборка является обобщением одномерного адаптивные квадратуры к многомерным интегралам. На каждом шаге рекурсии интеграл и ошибка оцениваются с помощью простого алгоритма Монте-Карло. Если оценка ошибки превышает требуемую точность, объем интегрирования делится на подтомы, и процедура рекурсивно применяется к подобъемам.

Обычная стратегия «деления на два» не работает для многомерных измерений, так как количество подтомов растет слишком быстро, чтобы их можно было отслеживать. Вместо этого оценивают, по какому измерению подразделение должно принести наибольшие дивиденды, и делят объем только по этому измерению.

Алгоритм стратифицированной выборки концентрирует точки выборки в регионах, где дисперсия функции наибольшая, таким образом уменьшая общую дисперсию и делая выборку более эффективной, как показано на рисунке.

Популярная процедура MISER реализует аналогичный алгоритм.

МИСЕР Монте-Карло

Алгоритм MISER основан на рекурсивном стратифицированная выборка. Этот метод направлен на уменьшение общей ошибки интеграции путем концентрации точек интегрирования в областях с наибольшей дисперсией.^[7]

Идея стратифицированной выборки начинается с наблюдения, что для двух непересекающийся регионы а и б с оценками Монте-Карло интеграла ${\displaystyle E_{a}(f)}$ и ${\displaystyle E_{b}(f)}$ и отклонения ${\displaystyle \sigma _{a}^{2}(f)}$ и ${\displaystyle \sigma _{b}^{2}(f)}$, дисперсия Var (ж) комбинированной оценки

${\displaystyle E(f)={\tfrac {1}{2}}\left(E_{a}(f)+E_{b}(f)\right)}$

дан кем-то,

${\displaystyle \mathrm {Var} (f)={\frac {\sigma _{a}^{2}(f)}{4N_{a}}}+{\frac {\sigma _{b}^{2}(f)}{4N_{b}}}}$

Можно показать, что эта дисперсия минимизируется путем распределения точек таким образом, что

${\displaystyle {\frac {N_{a}}{N_{a}+N_{b}}}={\frac {\sigma _{a}}{\sigma _{a}+\sigma _{b}}}}$

Следовательно, оценка наименьшей ошибки получается путем распределения точек выборки пропорционально стандартному отклонению функции в каждой подобласти.

Алгоритм MISER действует путем деления области интегрирования пополам вдоль одной координатной оси, чтобы получить две подобласти на каждом шаге. Направление выбирается путем изучения всех d возможные деления пополам и выбор того, который минимизирует комбинированную дисперсию двух субрегионов. Дисперсия в субрегионах оценивается путем выборки с использованием части от общего количества точек, доступных для текущего шага. Затем ту же процедуру рекурсивно повторяют для каждого из двух полупространств от наилучшего деления пополам. Остальные точки выборки распределяются по субрегионам с использованием формулы для N_а и N_б. Это рекурсивное распределение точек интеграции продолжается до заданной пользователем глубины, где каждая подобласть интегрируется с использованием простой оценки Монте-Карло. Эти отдельные значения и их оценки ошибок затем объединяются в большую сторону для получения общего результата и оценки его ошибки.

Выборка по важности

Основная статья: Выборка по важности

Существует множество алгоритмов выборки по важности, например

Алгоритм выборки по важности

Выборка по важности является очень важным инструментом для выполнения интеграции Монте-Карло.^[3][8] Основным результатом выборки по важности для этого метода является то, что единообразная выборка ${\displaystyle {\overline {\mathbf {x} }}}$ является частным случаем более общего выбора, когда образцы берутся из любого распределения ${\displaystyle p({\overline {\mathbf {x} }})}$. Идея в том, что ${\displaystyle p({\overline {\mathbf {x} }})}$ можно выбрать для уменьшения дисперсии измерения. Q_N.

Рассмотрим следующий пример, в котором нужно численно интегрировать гауссову функцию с центром в 0, с σ = 1, от -1000 до 1000. Естественно, если выборки нарисованы равномерно на интервале [-1000, 1000], только очень небольшая часть из них будет иметь значение для интеграла. Это можно улучшить, выбрав распределение, отличное от того, где выбираются выборки, например, путем выборки в соответствии с гауссовым распределением с центром в 0, с σ = 1. Конечно, «правильный» выбор сильно зависит от подынтегрального выражения.

Формально, учитывая набор образцов, выбранных из раздачи

${\displaystyle p({\overline {\mathbf {x} }}):\qquad {\overline {\mathbf {x} }}_{1},\cdots ,{\overline {\mathbf {x} }}_{N}\in V,}$

оценщик для я дан кем-то^[3]

${\displaystyle Q_{N}\equiv {\frac {1}{N}}\sum _{i=1}^{N}{\frac {f({\overline {\mathbf {x} }}_{i})}{p({\overline {\mathbf {x} }}_{i})}}}$

Интуитивно это говорит о том, что если мы выбираем конкретный образец в два раза больше, чем другие образцы, мы взвешиваем его вдвое меньше, чем другие образцы. Эта оценка, естественно, действительна для однородной выборки, когда ${\displaystyle p({\overline {\mathbf {x} }})}$ постоянно.

В Алгоритм Метрополиса-Гастингса один из наиболее часто используемых алгоритмов для генерации ${\displaystyle {\overline {\mathbf {x} }}}$ из ${\displaystyle p({\overline {\mathbf {x} }})}$,^[3] тем самым обеспечивая эффективный способ вычисления интегралов.

ВЕГАС Монте-Карло

Основная статья: Алгоритм VEGAS

Алгоритм VEGAS аппроксимирует точное распределение путем выполнения ряда проходов по области интегрирования, что создает гистограмму функции. ж. Каждая гистограмма используется для определения распределения выборки для следующего прохода. Асимптотически эта процедура сходится к желаемому распределению.^[9] Чтобы количество бинов гистограммы не увеличивалось, как K^d, распределение вероятностей аппроксимируется разделимой функцией:

${\displaystyle g(x_{1},x_{2},\ldots )=g_{1}(x_{1})g_{2}(x_{2})\ldots }$

так что количество требуемых ящиков только Kd. Это эквивалентно размещению пиков функции по проекциям подынтегрального выражения на оси координат. От правильности этого предположения зависит эффективность VEGAS. Это наиболее эффективно, когда пики подынтегрального выражения хорошо локализованы. Если подынтегральное выражение можно переписать в форме, которая приблизительно разделима, это повысит эффективность интеграции с VEGAS. VEGAS включает в себя ряд дополнительных функций и сочетает в себе как стратифицированную выборку, так и выборку по важности.^[9]

Смотрите также

• Вспомогательное поле Монте-Карло
• Метод Монте-Карло в статистической физике
• Метод Монте-Карло
• Снижение дисперсии

Примечания

1. Press et al, 2007, гл. 4.
2. Press et al, 2007, гл. 7.
3. Ньюман, 1999, гл. 2.
4. Ньюман, 1999, гл. 1.
5. Press et al, 2007
6. Маккей, Дэвид (2003). "Глава 4.4 Типичность и глава 29.1" (PDF). Теория информации, логические выводы и алгоритмы обучения. Издательство Кембриджского университета. С. 284–292. ISBN  978-0-521-64298-9. МИСТЕР  2012999.
7. Press, 1990, стр. 190-195.
8. Крозе, Д. П.; Taimre, T .; Ботев З.И. (2011). Справочник по методам Монте-Карло. Джон Вили и сыновья.
9. Лепаж, 1978

Рекомендации

• Кафлиш, Р. Э. (1998). «Монте-Карло и квази-Монте-Карло методы». Acta Numerica. 7: 1–49. Bibcode:1998AcNum ... 7 .... 1С. Дои:10.1017 / S0962492900002804.
• Weinzierl, S. (2000). «Введение в методы Монте-Карло». arXiv:hep-ph / 0006269.
• Press, W. H .; Фаррар, Г. Р. (1990). «Рекурсивная стратифицированная выборка для многомерной интеграции Монте-Карло». Компьютеры в физике. 4 (2): 190. Bibcode:1990ComPh ... 4..190P. Дои:10.1063/1.4822899.
• Лепаж, Г. П. (1978). «Новый алгоритм адаптивной многомерной интеграции». Журнал вычислительной физики. 27 (2): 192–203. Bibcode:1978JCoPh..27..192L. Дои:10.1016/0021-9991(78)90004-9.
• Лепаж, Г. П. (1980). «VEGAS: программа адаптивной многомерной интеграции». Препринт Корнелла CLNS 80-447.
• Hammersley, J.M .; Хандскомб, Д. К. (1964). Методы Монте-Карло. Метуэн. ISBN  978-0-416-52340-9.
• Нажмите, WH; Теукольский С.А.; Феттерлинг, штат Вашингтон; Фланнери, ВР (2007). Числовые рецепты: искусство научных вычислений (3-е изд.). Нью-Йорк: Издательство Кембриджского университета. ISBN  978-0-521-88068-8.
• Ньюман, MEJ; Баркема, GT (1999). Методы Монте-Карло в статистической физике. Кларендон Пресс.
• Роберт, CP; Казелла, Г. (2004). Статистические методы Монте-Карло (2-е изд.). Springer. ISBN  978-1-4419-1939-7.

внешняя ссылка

• Café Math: интеграция Монте-Карло : Статья в блоге, описывающая интеграцию Монте-Карло (принцип, гипотеза, доверительный интервал)
• Boost.Math: Наивная интеграция Монте-Карло: Документация по наивным процедурам Монте-Карло C ++
• Апплет Монте-Карло, применяемый в задачах статистической физики