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

Иллюстрация интеграции Монте-Карло. В этом примере область 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}}}}$

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

${\ 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}$.

Учитывая оценку 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}}},}$

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

Хотя наивный метод Монте-Карло работает для простых примеров, улучшение по сравнению с детерминированными алгоритмами может быть достигнуто только с помощью алгоритмов, использующих распределения выборки для конкретных задач. При соответствующем распределении выборки можно использовать тот факт, что почти все подынтегральные выражения более высокой размерности очень локализованы и только небольшое подпространство вносит заметный вклад в интеграл. ^[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})}$

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

Пример C [ править ]

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

int  i ,  throws  =  99999 ,  insideCircle  =  0 ; двойной  randX ,  randY ,  pi ;srand ( время ( NULL ));for  ( я  =  0 ;  я  <  бросает ;  ++ я )  {  randX  =  rand ()  /  ( двойной )  RAND_MAX ;  randY  =  rand ()  /  ( двойной )  RAND_MAX ;  если  ( randX  *  randX  +  randY  *  randY  <  1 )  ++ insideCircle ; }pi  =  4.0  *  insideCircle  /  throws ;

Пример Wolfram Mathematica [ править ]

В приведенном ниже коде описан процесс интеграции функции.

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

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

func [ x_ ] : = 1 / ( 1 + Sinh [ 2 * x ] * ( Log [ x ]) ^ 2 );    (* Пример из усеченного нормального распределения для ускорения сходимости *)Distrib [ X_ , average_ , var_ ] : = PDF [ NormalDistribution [ средняя , вар ], 1,1 * х - 0,1 ];        n = 10 ;  RV = RandomVariate [ TruncatedDistribution [{ 0.8 , 3 }, NormalDistribution [ 1 , 0.399 ]], n ];      Int = 1 / n Всего [ func [ RV ] / Distrib [ RV , 1 , 0.399 ]] * Интегрировать [ Distrib [ x , 1 , 0,399 ], { x , 0.8 , 3 }]          NIntegrate [ func [ x ], { x , 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]

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

${\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 _a и N _b.. Это рекурсивное распределение точек интеграции продолжается до заданной пользователем глубины, где каждая подобласть интегрируется с использованием простой оценки Монте-Карло. Эти отдельные значения и их оценки ошибок затем объединяются вверх, чтобы дать общий результат и оценку его ошибки.

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

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

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

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

Рассмотрим следующий пример, в котором нужно численно интегрировать гауссову функцию с центром в 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,}$

оценка для I дается формулой ^[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} }})}$

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

ВЕГАС Монте-Карло [ править ]

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

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

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

См. Также [ править ]

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

Заметки [ править ]

Ссылки [ править ]

• Кафлиш, RE (1998). «Монте-Карло и квази-Монте-Карло методы». Acta Numerica . 7 : 1–49. Bibcode : 1998AcNum ... 7 .... 1C . DOI : 10.1017 / S0962492900002804 .
• Weinzierl, S. (2000). «Введение в методы Монте-Карло». arXiv : hep-ph / 0006269 .
• Нажмите, WH; Фаррар, GR (1990). «Рекурсивная стратифицированная выборка для многомерной интеграции Монте-Карло» . Компьютеры в физике . 4 (2): 190. Bibcode : 1990ComPh ... 4..190P . DOI : 10.1063 / 1.4822899 .
• Лепаж, ГП (1978). «Новый алгоритм адаптивной многомерной интеграции». Журнал вычислительной физики . 27 (2): 192–203. Bibcode : 1978JCoPh..27..192L . DOI : 10.1016 / 0021-9991 (78) 90004-9 .
• Лепаж, ГП (1980). «VEGAS: программа адаптивной многомерной интеграции». Препринт Корнелла CLNS 80-447 .
• Хаммерсли, Дж. М.; Хэндскомб, округ Колумбия (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: Monte Carlo Integration  : статья в блоге, описывающая интеграцию Монте-Карло (принцип, гипотеза, доверительный интервал)
• Boost.Math: Наивная интеграция Монте-Карло: Документация по наивным процедурам Монте-Карло C ++
• Апплет Монте-Карло, применяемый в задачах статистической физики