Последовательность Соболя - Sobol sequence

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

Последовательности Соболя (также называется LPτ последовательности или (т, s) последовательности в базе 2) являются примером квазислучайных последовательности с низким расхождением. Впервые их ввел русский математик. Илья Михайлович Соболь (Илья Меерович Соболь) в 1967 году.[1]

Эти последовательности используют основание из двух, чтобы последовательно формировать более тонкие однородные части единичного интервала, а затем переупорядочивать координаты в каждом измерении.

Хорошие раздачи в s-мерный единичный гиперкуб

Позволять яs = [0,1]s быть s-мерный единичный гиперкуб, и ж действительная интегрируемая функция над яs. Первоначальной мотивацией Соболя было построить последовательность Иксп в яs так что

и сходимость должна быть максимально быстрой.

Более-менее ясно, что для схождения суммы к интегралу точки Иксп должен заполнить яs минимизация отверстий. Еще одно хорошее свойство - проекции Иксп на низкоразмерной грани яs оставьте очень мало дырок. Следовательно, однородное заполнение яs не подходит, потому что в более низких измерениях многие точки будут в одном и том же месте, поэтому они бесполезны для интегральной оценки.

Эти хорошие дистрибутивы называются (т,м,s) -сети и (т,s) -последовательности в базе б. Чтобы представить их, сначала определите элементарный s-интервал в базе б подмножество яs формы

куда аj и dj неотрицательные целые числа, и для всех j в {1, ..., s}.

Учитывая 2 целых числа , а (т,м,s) -сеть в базе б это последовательность Иксп из бм точки яs такой, что для всего элементарного интервала п в базе б гиперобъема λ(п) = бт-м.

Учитывая неотрицательное целое число т, а (т,s) -последовательность в базе б бесконечная последовательность точек Иксп так что для всех целых чисел , последовательность это (т,м,s) -сеть в базе б.

В своей статье Соболь описал Πτ-сетки и LPτ последовательности, которые (т,м,s) -сети и (т,s) -последовательности в базе 2 соответственно. Условия (т,м,s) -сети и (т,s) -последовательности в базе б (также называемые последовательностями Нидеррайтера) были придуманы в 1988 г. Харальд Нидеррайтер.[2] Период, термин Последовательности Соболя был введен в англоязычных изданиях позднего периода по сравнению с Halton, Форе и другие последовательности с малым расхождением.

Быстрый алгоритм

Более эффективный Код Грея реализация была предложена Антоновым и Салеевым.[3]

Что касается генерации чисел Соболя, им явно помогает использование кода Грея. вместо п для строительства п-я точка розыгрыша.

Предположим, мы уже сгенерировали все отрисовки последовательности Соболя до п - 1 и сохранил в памяти значения Иксп−1,j для всех необходимых размеров. Поскольку код Грея грамм(п) отличается от предыдущего грамм(п - 1) всего одним, скажем, k-th, бит (крайний правый бит п - 1), все, что нужно сделать, это один XOR операции для каждого измерения, чтобы распространить все Иксп−1 к Иксп, т.е.

Дополнительные свойства однородности

Соболь ввел дополнительные условия однородности, известные как свойства A и A ’.[4]

Определение
Говорят, что последовательность с низким расхождением удовлетворяет Свойство А если для любого двоичного сегмента (не произвольного подмножества) d-мерная последовательность длины 2d в каждых двух есть ровно одна ничьяd гиперкубы, возникающие в результате деления единичного гиперкуба вдоль каждого его удлинения пополам.
Определение
Говорят, что последовательность с низким расхождением удовлетворяет Свойство A ’ если для любого двоичного сегмента (не произвольного подмножества) d-мерная последовательность длины 4d на каждые 4d гиперкубы, которые образуются в результате разделения единичного гиперкуба вдоль каждого его удлинения на четыре равные части.

Существуют математические условия, которые гарантируют свойства A и A '.

Теорема
В d-мерная последовательность Соболя обладает свойством A тогда и только тогда, когда
куда Vd это d × d двоичная матрица, определяемая
с vk,j,м обозначая м-я цифра после двоичной точки номера направления vk,j = (0.vk,j,1vk,j,2...)2.
Теорема
В d-мерная последовательность Соболя обладает свойством A 'тогда и только тогда, когда
куда Ud это 2d × 2d двоичная матрица, определяемая
с vk,j,м обозначая м-я цифра после двоичной точки номера направления vk,j = (0.vk,j,1vk,j,2...)2.

Тесты на свойства A и A ’независимы. Таким образом, можно построить последовательность Соболя, которая удовлетворяет обоим свойствам A и A ’или только одному из них.

Инициализация чисел Соболя

Чтобы построить последовательность Соболя, набор номеров направлений vя,j нужно выбрать. Есть некоторая свобода выбора начальных номеров направлений.[примечание 1] Следовательно, можно получить разные реализации последовательности Соболя для выбранных размеров. Плохой выбор начальных чисел может значительно снизить эффективность последовательностей Соболя при их использовании для вычислений.

Возможно, самый простой выбор для номеров инициализации - просто иметь л-й крайний левый бит установлен, а все остальные биты равны нулю, т.е. мk,j = 1 для всех k и j. Эта инициализация обычно называется инициализация устройства. Однако такая последовательность не проходит проверку на свойства A и A ’даже для малых размеров, и, следовательно, такая инициализация плохая.

Реализация и доступность

Хорошие номера инициализации для разного количества измерений предоставлены несколькими авторами. Например, Sobol предоставляет номера инициализации для размеров до 51.[5] Тот же набор номеров инициализации используется Брэтли и Фокс.[6]

Номера инициализации для больших измерений доступны на Джо и Куо.[7] Петер Якель приводит в своей книге числа инициализации до 32 "Методы Монте-Карло в финансах ".[8]

Другие реализации доступны как подпрограммы C, Fortran 77 или Fortran 90 в Числовые рецепты сборник программного обеспечения.[9] А бесплатно / с открытым исходным кодом реализация до 1111 измерений, на основе номеров инициализации Джо и Куо, доступна в C[10]и до 21201 измерения в Python[11] и Юля[12]. Доступна другая реализация с бесплатным / открытым исходным кодом до 1111 измерений для C ++, Фортран 90, Matlab, и Python.[13]

Наконец, коммерческие генераторы последовательностей Соболя доступны, например, в Библиотека NAG,[14]. Версия доступна в Британо-Российском агентстве оффшорного развития (BRODA).[15][16] MATLAB также содержит реализацию[17] как часть его панели инструментов статистики.

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

Примечания

  1. ^ Эти номера обычно называют номера инициализации.

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

  1. ^ Соболь, И. М. (1967), "Распределение точек в кубе и приближенное вычисление интегралов". Ж. Выч. Мат. Мат. Физ. 7: 784–802; U.S.S.R Comput. Математика. Математика. Phys. 7: 86–112 (на английском языке).
  2. ^ Нидеррайтер, Х. (1988). «Низкодисперсионные и низкодисперсные последовательности», Журнал теории чисел 30: 51–70.
  3. ^ Антонов, И.А. и Салеев В. (1979) «Экономический метод вычисления LP.τ-последовательности ». Ж. Выч. Мат. Мат. Физ. 19: 243–245; U.S.S.R. Comput. Математика. Математика. Phys. 19: 252–256 (на английском языке).
  4. ^ Соболь И. М. (1976) «Равномерно распределенные последовательности с дополнительным свойством однородности». Ж. Выч. Мат. Мат. Физ. 16: 1332–1337; U.S.S.R. Comput. Математика. Математика. Phys. 16: 236–242 (на английском языке).
  5. ^ Соболь И.М., Левитан Ю.Л. (1976). «Производство точек, равномерно распределенных в многомерном кубе» Tech. Реп.40, Институт прикладной математики АН СССР. (на русском).
  6. ^ Братли П. и Фокс Б. Л. (1988), "Алгоритм 659: Реализация генератора квазислучайных последовательностей Соболя". ACM Trans. Математика. Программного обеспечения 14: 88–100.
  7. ^ «Генератор последовательности Соболя». Университет Нового Южного Уэльса. 2010-09-16. Получено 2013-12-20.
  8. ^ Jäckel, P. (2002) "Методы Монте-Карло в финансах". Нью-Йорк: Джон Уайли и сыновья. (ISBN  0-471-49741-X.)
  9. ^ Press, W.H., Teukolsky, S.A., Vetterling, W. T., and Flannery, B.P. (1992) "Числовые рецепты в Fortran 77: Искусство научных вычислений, 2-е изд." Издательство Кембриджского университета, Кембридж, Великобритания
  10. ^ C реализация последовательности Соболя в Библиотека NLopt (2007).
  11. ^ Империале, Г. "pyscenarios: Python Scenario Generator".
  12. ^ Sobol.jl пакет: Юля реализация последовательности Соболя.
  13. ^ Квазислучайная последовательность Соболя, код для C ++ / Fortran 90 / Matlab / Python от Дж. Буркардта
  14. ^ «Группа численных алгоритмов». Nag.co.uk. 2013-11-28. Получено 2013-12-20.
  15. ^ И. Соболь, Д. Асоцкий, А. Крейнин, С. Кучеренко (2011). «Построение и сравнение многомерных генераторов Соболя» (PDF). Уилмотт Журнал. Ноя: 64–79.CS1 maint: несколько имен: список авторов (связь)
  16. ^ "Брода". Брода. 2004-04-16. Получено 2013-12-20.
  17. ^ справочная страница sobolset. Проверено 24 июля 2017.

внешняя ссылка