On the Halton quasi-random sequences randomization

Abstract

Рассматривается вопрос об оценке погрешности методов квази Монте-Карло с помощью рандомизации. Известное неравенство Коксмы-Хлавки позволяет судить об асимптотике погрешности, но совсем не пригодно для практического использования в процессе вычислений, так как вычисление входящих в него величин - вариации функции и дискрепанса последовательности чрезвычайно трудоемки и практически неосуществимы. По этой причине имеются многочисленные попытки использовать средства теории вероятностей для решения указанной задачи. Одним из распространенных подходов является случайный сдвиг точек псевдослучайной последовательности. Известны случаи практического использования этого подхода, но теоретически он мало исследован.В данной работе показано, что полученные таким образом оценки являются оценками сверху, установлена связь с теорий кубатурных формул с одним случайным узлом. Подробно рассмотрен случай последовательностей Холтона. Анализируется преобразование Ван дер Корпута последовательности натуральных чисел, с помощью которого строятся точки Холтона. Показано, что кубатурная формула с одним свободным узлом, соответствующая последовательности Холтона, точна для некоторого класса ступенчатых функций. Класс явно описан. Полученные результаты позволят более эффективно использовать указанные последовательности при вычислении интегралов и поиске экстремума, а также могут служить отправной точкой для дальнейших теоретических исследований в области квазислучайных методов. Библиогр. 6 назв. Ил. 1. Табл. 1.