Введение
Тип последовательности в численном анализе
Последовательности Соболя (также называемые LPτ-последовательностями или (t, s)-последовательностями в двоичной системе счисления) являются примером квазислучайных последовательностей с низкой дисперсией. Они были впервые введены российским математиком Ильей М. Соболем (Илья Меерович Соболь) в 1967 году. Эти последовательности используют основание два для формирования последовательно более мелких равномерных разбиений единичного интервала, а затем переупорядочивают координаты в каждом измерении.
Хорошее распределение в гиперкубе с-мерной единицы
Пусть Is = [0,1]s будет s-мерным единичным гиперкубом, а f – действительнозначной интегрируемой функцией на Is. Исходная мотивация Соболя заключалась в построении последовательности xn в Is такой, чтобы
и сходимость была как можно более быстрой. Достаточно ясно, что для того, чтобы сумма сходилась к интегралу, точки xn должны заполнять Is, минимизируя пустоты. Хорошим свойством также было бы, чтобы проекции xn на подпространства меньшей размерности Is оставляли как можно меньше пустот. Следовательно, однородное заполнение Is не подходит, поскольку в меньших размерностях многие точки будут совпадать, что делает их бесполезными для оценки интеграла. Эти хорошие распределения называются (t,m,s)-сетями и (t,s)-последовательностями в базе b. Для их определения сначала определим элементарный s-интервал в базе b как подмножество Is вида
где aj и dj – неотрицательные целые числа, и для всех j из {1, …, s}. При заданных двух целых числах, (t,m,s)-сеть в базе b – это последовательность xn из bm точек Is такая, что для всех элементарных интервалов P в базе b гиперобъем λ(P) = bt−m. (t,s)-последовательность в базе b – это бесконечная последовательность точек xn такая, что для всех целых чисел, последовательность является (t,m,s)-сетью в базе b. В своей статье Соболь описал сетки Πτ и последовательности LPτ, которые соответственно являются (t,m,s)-сетями и (t,s)-последовательностями в базе 2. Термины (t,m,s)-сети и (t,s)-последовательности в базе b (также называемые последовательностями Нидеррайтера) были введены в 1988 году Харальдом Нидеррайтером. Термин «последовательности Соболя» был введен в более поздних англоязычных работах в сравнении с последовательностями Халтона, Фауре и другими последовательностями с малой дисперсией.
Быстрый алгоритм
Более эффективная реализация кода Грея была предложена Антоновым и Салеевым. Что касается генерации чисел Соболя, использование кода Грея вместо числа *n* для построения *n*-го элемента последовательности явно облегчает этот процесс. Предположим, мы уже сгенерировали все элементы последовательности Соболя до *n* − 1 и сохранили в памяти значения x<sub>n−1,j</sub> для всех необходимых размерностей. Поскольку код Грея G(*n*) отличается от предыдущего кода Грея G(*n* − 1) только одним битом, скажем, *k*-м (который является самым правым нулевым битом числа *n* − 1), для перехода от x<sub>n−1</sub> к x<sub>n</sub> требуется выполнить операцию XOR для каждой размерности. То есть,
Инициализация номеров Соболя
Для построения последовательности Соболя необходимо выбрать набор чисел направлений vi,j. Существует определенная свобода в выборе начальных чисел направлений. Поэтому можно получить различные реализации последовательности Соболя для заданных размерностей. Неудачный выбор начальных чисел может существенно снизить эффективность последовательностей Соболя при использовании в вычислениях. Вероятно, самый простой способ инициализации – установить l-й крайний левый бит в единицу, а все остальные биты обнулить, то есть mk,j = 1 для всех k и j. Такая инициализация обычно называется единичной инициализацией. Однако последовательность, полученная таким образом, не проходит проверку на свойства A и A’ даже для небольших размерностей, и поэтому данная инициализация является неэффективной.
Реализация и доступность
Некоторые авторы приводят хорошие числа для инициализации для различных размерностей. Например, Соболь предоставляет числа инициализации для размерностей до 51. Тот же набор чисел инициализации используется Брэтли и Фоксом. Числа инициализации для высоких размерностей доступны у Джо и Куо. Питер Якель приводит числа инициализации до размерности 32 в своей книге "Методы Монте-Карло в финансах". Другие реализации доступны в виде программ на C, Fortran 77 или Fortran 90 в составе программного пакета Numerical Recipes. Бесплатная реализация с открытым исходным кодом, поддерживающая до 1111 размерностей и основанная на числах инициализации Джо и Куо, доступна на C, а также до 21201 размерности в Python и Julia. Другая бесплатная реализация с открытым исходным кодом, поддерживающая до 1111 размерностей, доступна для C++, Fortran 90, Matlab и Python. Коммерческие генераторы последовательностей Соболя доступны, например, в библиотеке NAG. Компания BRODA Ltd. предлагает генераторы последовательностей Соболя и перемешанных последовательностей Соболя с дополнительными свойствами однородности A и A' до максимальной размерности 131072. Эти генераторы были разработаны совместно с проф. И. Соболь. MATLAB содержит генераторы последовательностей Соболя до размерности 1111 как часть Statistics Toolbox.