Квази-Монте-Карло метод - Quasi-Monte Carlo method

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

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

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

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

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

${\ Displaystyle \ int _ {[0,1] ^ {s}} е (и) \, {\ rm {d}} и \ приблизительно {\ гидроразрыва {1} {N}} \, \ сумма _ {я = 1} ^ {N} f (x_ {i}).}$

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

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

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

Ошибка аппроксимации метода квази-Монте - Карло ограничена член , пропорциональный невязки множества х ₁ , ..., х _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)). D _N - это так называемая звездная невязка множества ( x ₁ , ..., x _N ) и определяется как

${\ displaystyle D_ {N} = \ sup _ {Q \ subset [0,1] ^ {s}} \ left | {\ frac {{\ text {количество точек в}} Q} {N}} - \ имя оператора {объем} (Q) \ right |,}$

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

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

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

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

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

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

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

• Чтобы быть меньше чем , он должен быть маленьким и должен быть большим (например ). Для больших 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 (е) = \ infty}$
• Нам известна только верхняя граница ошибки (т. Е. Ε ≤ V ( f ) D _N ), и вычислить и трудно . ${\ displaystyle D_ {N} ^ {*}}$${\ Displaystyle V (е)}$

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

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

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

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

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

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

• Метод Монте-Карло
• Методы Монте-Карло в финансах
• Квази-Монте-Карло методы в финансах
• Биология метод Монте-Карло
• Вычислительная физика
• Последовательности с низким расхождением
• Теория несоответствия
• Цепь Маркова Монте-Карло

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

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

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

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