Метод квази-Монте-Карло

Псевдослучайная последовательность

Последовательность Соболя квазислучайных чисел с низким расхождением , показывающая первые 10 (красный), 100 (красный + синий) и 256 (красный + синий + зеленый) точки из последовательности.

256 точек из источника псевдослучайных чисел и последовательности Соболя (красный=1,..,10, синий=11,..,100, зеленый=101,..,256). Точки из последовательности Соболя распределены более равномерно.

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

Аналогично формулируются методы Монте-Карло и квази-Монте-Карло.Задача состоит в том, чтобы аппроксимировать интеграл функции f как среднее значение функции, вычисленной в наборе точек x ₁ , ..., x _N :

$\int _{[0,1]^{s}}f(u)\,{\rm {d}}u\approx {\frac {1}{N}}\,\sum _{i=1}^{N}f(x_{i}).$

Поскольку мы интегрируем по s -мерному единичному кубу, каждый x _i является вектором из s элементов. Разница между квази-Монте-Карло и Монте-Карло заключается в способе x _i выбора . Квази-Монте-Карло использует последовательность с низким расхождением, такую ​​как последовательность Холтона , последовательность Соболя или последовательность Форе, тогда как Монте-Карло использует псевдослучайную последовательность. Преимущество использования последовательностей с низким расхождением заключается в более высокой скорости сходимости. Квази-Монте-Карло имеет скорость сходимости, близкую к O(1/ N ), тогда как скорость метода Монте-Карло равна O( N ^−0.5 ).

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

квази-Монте-

Погрешность аппроксимации метода квази-Монте-Карло ограничена членом, пропорциональным невязке множества x ₁ , ..., x _N . В частности, неравенство Коксмы – Главки утверждает, что ошибка

$\varepsilon =\left|\int _{[0,1]^{s}}f(u)\,{\rm {d}}u-{\frac {1}{N}}\,\sum _{i=1}^{N}f(x_{i})\right|$

ограничен

$|\varepsilon |\leq V(f)D_{N},$

где V ( f ) — вариация Харди – Краузе функции f (см. Морокофф и Кафлиш (1995) подробные определения). D _N представляет собой так называемую звездную невязку множества ( x ₁ ,..., x _N ) и определяется как

$D_{N}=\sup _{Q\subset [0,1]^{s}}\left|{\frac {{\text{number of points in }}Q}{N}}-\operatorname {volume} (Q)\right|,$

где Q — прямоугольное тело в [0,1] ^с со сторонами, параллельными осям координат. Неравенство $|\varepsilon |\leq V(f)D_{N}$ можно показать, что погрешность аппроксимации методом квазиМонте-Карло равна $O\left({\frac {(\log N)^{s}}{N}}\right)$, тогда как метод Монте-Карло имеет вероятностную ошибку $O\left({\frac {1}{\sqrt {N}}}\right)$. Таким образом, для достаточно больших $N$, квази-Монте-Карло всегда будет превосходить случайный Монте-Карло. Однако, $\log(N)^{s}$ экспоненциально быстро растет с увеличением размера, а это означает, что плохо выбранная последовательность может быть намного хуже, чем Монте-Карло в больших измерениях. На практике почти всегда можно выбрать подходящую последовательность с низким расхождением или применить подходящее преобразование к подынтегральной функции, чтобы гарантировать, что квази-Монте-Карло работает по крайней мере так же хорошо, как Монте-Карло (а часто и намного лучше).

Карло для многомерной

Известно , что для одномерного интегрирования квадратурные методы, такие как правило трапеций , правило Симпсона или формулы Ньютона-Котеса , эффективны, если функция гладкая. Эти подходы также можно использовать для многомерного интегрирования путем повторения одномерных интегралов по нескольким измерениям. Однако количество оценок функции растет экспоненциально по мере увеличения s , количества измерений. метод, который сможет преодолеть это проклятие размерности Следовательно, для многомерной интеграции следует использовать . Стандартный метод Монте-Карло часто используется, когда квадратурные методы сложны или дороги в реализации. Методы Монте-Карло и квази-Монте-Карло точны и относительно быстры, когда размерность высока, до 300 и выше.

Мороков и Кафлиш изучил эффективность методов интегрирования Монте-Карло и квази-Монте-Карло. В статье сравниваются последовательности Холтона, Соболя и Фора для квази-Монте-Карло со стандартным методом Монте-Карло с использованием псевдослучайных последовательностей. Они обнаружили, что последовательность Холтона лучше всего работает для размерностей примерно до 6; последовательность Соболя лучше всего работает для более высоких измерений; а последовательность Фора, хотя и уступает двум другим, по-прежнему работает лучше, чем псевдослучайная последовательность.

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

Недостатки квази-

Лемье упомянул недостатки квази-Монте-Карло:

• Для того, чтобы $O\left({\frac {(\log N)^{s}}{N}}\right)$ быть меньше, чем $O\left({\frac {1}{\sqrt {N}}}\right)$, $s$ должен быть небольшим и $N$ должен быть большим (например, $N>2^{s}$). При больших s , в зависимости от значения N , невязка набора точек из генератора с малой невязкой может быть не меньше, чем для случайного набора.
• Для многих функций, возникающих на практике, $V(f)=\infty$ (например, если используются гауссовы переменные).
• Мы знаем только верхнюю границу ошибки (т. е. ε ≤ V ( f ) D _N ), и ее трудно вычислить. $D_{N}^{*}$ и $V(f)$.

Чтобы преодолеть некоторые из этих трудностей, мы можем использовать рандомизированный метод квази-Монте-Карло.

квази-Монте

Поскольку последовательности с низким расхождением не случайны, а детерминированы, метод квази-Монте-Карло можно рассматривать как детерминированный алгоритм или дерандомизированный алгоритм. В этом случае у нас есть только граница (например, ε ≤ V ( f ) D _N ) для ошибки, и ошибку трудно оценить. Чтобы восстановить нашу способность анализировать и оценивать дисперсию, мы можем рандомизировать метод ( «Рандомизация общую идею см. в разделе »). Полученный метод называется рандомизированным методом квази-Монте-Карло, и его также можно рассматривать как метод уменьшения дисперсии для стандартного метода Монте-Карло. Среди нескольких методов простейшей процедурой преобразования является случайное смещение. Пусть { x ₁ ,..., x _N } будет набором точек из последовательности с низким расхождением. Мы выбираем s -мерный случайный вектор U и смешиваем его с { x ₁ , ..., x _N }. Подробно, для каждого x _j создайте

$y_{j}=x_{j}+U{\pmod {1}}$

и используйте последовательность $(y_{j})$ вместо $(x_{j})$. Если у нас есть R репликаций для Монте-Карло, выберите s-мерный случайный вектор U для каждой репликации. Рандомизация позволяет дать оценку дисперсии, используя при этом квазислучайные последовательности. По сравнению с чистым квази-Монте-Карло количество выборок квазислучайной последовательности будет делиться на R для эквивалентных вычислительных затрат, что снижает теоретическую скорость сходимости. По сравнению со стандартным Монте-Карло, дисперсия и скорость вычислений немного лучше по экспериментальным результатам в Таффине (2008).

См. также

• Метод Монте-Карло – вероятностный алгоритм решения задач
• Методы Монте-Карло в финансах – Вероятностные методы измерения
• Методы квазимонте-карло в финансах
• Биологический метод Монте-Карло - Метод моделирования ионного транспорта.
• Вычислительная физика - Численное моделирование физических проблем с помощью компьютеров.
• Последовательности с низким расхождением — тип математической последовательности. Страницы, отображающие краткие описания целей перенаправления.
• Теория несоответствия - Теория неравномерностей распределения
• Цепь Маркова Монте-Карло - Класс алгоритмов зависимой выборки

Ссылки

• RE Caflisch , Методы Монте-Карло и квази-Монте-Карло , Acta Numerica vol. 7, Издательство Кембриджского университета, 1998, стр. 1–49.
• Йозеф Дик и Фридрих Пиллихшаммер, Цифровые сети и последовательности. Теория несоответствия и интеграция квази-Монте-Карло , Издательство Кембриджского университета, Кембридж, 2010, ISBN   978-0-521-19159-3
• Гюнтер Леобахер и Фридрих Пиллихшаммер, Введение в интеграцию и приложения квази-Монте-Карло , Компактные учебники по математике, Биркхойзер, 2014, ISBN   978-3-319-03424-9
• Майкл Дрмота и Роберт Ф. Тичи, Последовательности, несоответствия и приложения , Конспекты лекций по математике, 1651 г. , Springer, Берлин, 1997 г., ISBN   3-540-62606-9
• Уильям Дж. Морокофф и Рассел Э. Кафлиш , Квазислучайные последовательности и их расхождения , SIAM J. Sci. Вычислить. 15 (1994), вып. 6, 1251–1279 (на CiteSeer : [2] )
• Харальд Нидеррайтер . Генерация случайных чисел и методы квази-Монте-Карло. Общество промышленной и прикладной математики, 1992. ISBN   0-89871-295-5
• Харальд Г. Нидеррайтер , Квази-Монте-Карло методы и псевдослучайные числа , Bull. Матем. 84 (1978), вып. 6, 957-1041.
• Ото Штраух и Штефан Порубский, Распределение последовательностей: сэмплер , Издательство Peter Lang, Франкфурт-на-Майне, 2005 г., ISBN   3-631-54013-2

Внешние ссылки

• Страница Wiki MCQMC содержит множество бесплатных онлайн-материалов по методам Монте-Карло и квази-Монте-Карло.
• Очень интуитивно понятное и всестороннее введение в методы квази-Монте-Карло.