Введение

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

В численном анализе квазиметод Монте-Карло — это метод численного интегрирования и решения некоторых других задач, использующий последовательности с низкой дисперсией (также называемые квазислучайными или субслучайными последовательностями) для снижения дисперсии. Это отличается от обычного метода Монте-Карло или численного интегрирования Монте-Карло, которые основаны на последовательностях псевдослучайных чисел. Методы Монте-Карло и квази-Монте-Карло формулируются схожим образом. Задача состоит в том, чтобы аппроксимировать интеграл функции f как среднее значение функции, вычисленное в наборе точек x1, …, xN:

Поскольку мы интегрируем по s-мерному единичному кубу, каждый xi является вектором из s элементов. Различие между квази-Монте-Карло и Монте-Карло заключается в способе выбора xi. Квази-Монте-Карло использует последовательность с низкой дисперсией, такую как последовательность Халтона, последовательность Соболя или последовательность Фауре, в то время как Монте-Карло использует псевдослучайную последовательность. Преимущество использования последовательностей с низкой дисперсией — более высокая скорость сходимости. Квази-Монте-Карло имеет скорость сходимости, близкую к O(1/N), в то время как для метода Монте-Карло она составляет O(N−0.5). Метод квази-Монте-Карло в последнее время стал популярен в области математических или вычислительных финансов. Методы Монте-Карло и квази-Монте-Карло точны и относительно быстры при высокой размерности, до 300 и выше. Морокофф и Кафлиш
Для того чтобы было меньше , должно быть малым, а должно быть большим (например, ). Для больших s, в зависимости от значения N, дисперсия множества точек от генератора с низкой дисперсией может оказаться не меньше, чем для случайного множества. Для многих функций, возникающих на практике (например, при использовании гауссовских переменных). Мы знаем только верхнюю границу ошибки (т.е. ε ≤ V(f) DN), и вычислить и сложно. Чтобы преодолеть некоторые из этих трудностей, можно использовать рандомизированный квазиметод Монте-Карло.

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

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

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