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

Процесс численного интегрирования

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

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

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

${\displaystyle \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 ). ^[1]

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

Границы погрешности аппроксимации квази-Монте-Карло

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

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

ограничен

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

где V ( f ) — вариация Харди–Краузе функции f ( подробные определения см . в Morokoff and Caflisch (1995) ^{[2] ).} D _N представляет собой так называемую звездную невязку множества ( x ₁ ,..., x _N ) и определяется как

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

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

Монте-Карло и квази-Монте-Карло для многомерной интеграции

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

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

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

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

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

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

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

Рандомизация квази-Монте-Карло

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

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

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

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

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

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

1. Сорен Асмуссен и Питер В. Глинн, Стохастическое моделирование: алгоритмы и анализ , Springer, 2007, 476 страниц.
2. Уильям Дж. Морокофф и Рассел Э. Кафлиш , Интеграция квази-Монте-Карло , J. Comput. Физ. 122 (1995), вып. 2, 218–230. (В CiteSeer : [1])
3. Рудольф Шюрер, Сравнение методов (квази-) Монте-Карло и кубатурных правил для решения многомерных задач интеграции , Математика и компьютеры в моделировании, том 62, выпуски 3–6, 3 марта 2003 г., 509–517
4. Кристиан Лемье, Выборка Монте-Карло и квази-Монте-Карло , Springer, 2009, ISBN  978-1441926760
5. Моше Дрор, Пьер Л'Экуайер и Ференц Сидаровски, Моделирование неопределенности: исследование стохастической теории, методов и приложений , Springer 2002, стр. 419-474
6. Бруно Таффин, Рандомизация методов квази-Монте-Карло для оценки ошибок: опрос и нормальное приближение , Методы Монте-Карло и их приложения mcma. Том 10, выпуск 3–4, страницы 617–628, ISSN (онлайн) 1569–3961, ISSN (печать) 0929–9629, doi : 10.1515/mcma.2004.10.3–4.617, май 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 содержит множество бесплатных онлайн-материалов по методам Монте-Карло и квази-Монте-Карло.
• Очень интуитивно понятное и всестороннее введение в методы квази-Монте-Карло.