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

Тип последовательности в численном анализе

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

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

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

Хорошие распределения в s -мерном единичном гиперкубе

Пусть I ^s = [0,1] ^s — s -мерный единичный гиперкуб, а f — вещественная интегрируемая функция над I ^s . Первоначальной мотивацией Соболя было построить последовательность x _n в I ^s так, чтобы

${\displaystyle \lim _{n\to \infty }{\frac {1}{n}}\sum _{i=1}^{n}f(x_{i})=\int _{I^{s}}f}$

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

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

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

${\displaystyle \prod _{j=1}^{s}\left[{\frac {a_{j}}{b^{d_{j}}}},{\frac {a_{j}+1}{b^{d_{j}}}}\right],}$

где a _j и d _j — неотрицательные целые числа и для всех j из {1,...,s}. ${\displaystyle a_{j}<b^{d_{j}}}$

Учитывая 2 целых числа , a ( t , m , s )-сеть в базе b — это последовательность x _n из b ^m точек I ^s такая, что для всех элементарных интервалов P в базе b гиперобъема λ ( P ) = b ^t−m . ${\displaystyle 0\leq t\leq m}$ ${\displaystyle \operatorname {Card} P\cap \{x_{1},...,x_{b^{m}}\}=b^{t}}$

Учитывая неотрицательное целое число t , ( t , s )-последовательность в базе b представляет собой бесконечную последовательность точек x _n такую, что для всех целых чисел последовательность является ( t , m , s )-сетью в базе b . ${\displaystyle k\geq 0,m\geq t}$ ${\displaystyle \{x_{kb^{m}},...,x_{(k+1)b^{m}-1}\}}$

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

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

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

Что касается генерации чисел Соболя, то им явно помогает использование кода Грея вместо n для построения n -й точки. ${\displaystyle G(n)=n\oplus \lfloor n/2\rfloor }$

Предположим, мы уже сгенерировали все отрисовки последовательности Соболя до n  − 1 и сохранили в памяти значения x _{n −1, j} для всех необходимых размерностей. Поскольку код Грея G ( n ) отличается от кода предыдущего G ( n  − 1) всего на один, скажем, k -й бит (который является крайним правым нулевым битом n  − 1), все, что необходимо Необходимо выполнить одну операцию XOR для каждого измерения, чтобы распространить все x _{n −1} на x _n , т.е.

${\displaystyle x_{n,i}=x_{n-1,i}\oplus v_{k,i}.}$

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

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

Определение

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

Определение

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

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

Теорема

d - мерная последовательность Соболя обладает свойством A тогда и только тогда, когда

${\displaystyle \det(\mathbf {V} _{d})\equiv 1(\mod 2),}$

где V ^d — двоичная матрица размера d  ×  d , определяемая формулой

${\displaystyle \mathbf {V} _{d}:={\begin{pmatrix}{v_{1,1,1}}&{v_{2,1,1}}&{\dots }&{v_{d,1,1}}\\{v_{1,2,1}}&{v_{2,2,1}}&{\dots }&{v_{d,2,1}}\\{\vdots }&{\vdots }&{\ddots }&{\vdots }\\{v_{1,d,1}}&{v_{2,d,1}}&{\dots }&{v_{d,d,1}}\end{pmatrix}},}$

где v _{k , j , m} обозначает m -ю цифру после двоичной точки номера направления v _{k , j} = (0. v _{k , j ,1} v _{k , j ,2} ...) ₂ .

Теорема

d - мерная последовательность Соболя обладает свойством А' тогда и только тогда, когда

${\displaystyle \det(\mathbf {U} _{d})\equiv 1\mod 2,}$

где U ^d — двоичная матрица размером 2 d  × 2 d , определяемая формулой

${\displaystyle \mathbf {U} _{d}:={\begin{pmatrix}{v_{1,1,1}}&{v_{1,1,2}}&{v_{2,1,1}}&{v_{2,1,2}}&{\dots }&{v_{d,1,1}}&{v_{d,1,2}}\\{v_{1,2,1}}&{v_{1,2,2}}&{v_{2,2,1}}&{v_{2,2,2}}&{\dots }&{v_{d,2,1}}&{v_{d,2,2}}\\{\vdots }&{\vdots }&{\vdots }&{\vdots }&{\ddots }&{\vdots }&{\vdots }\\{v_{1,2d,1}}&{v_{1,2d,2}}&{v_{2,2d,1}}&{v_{2,2d,2}}&{\dots }&{v_{d,2d,1}}&{v_{d,2d,2}}\end{pmatrix}},}$

где v _{k , j , m} обозначает m -ю цифру после двоичной точки номера направления v _{k , j} = (0. v _{k , j ,1} v _{k , j ,2} ...) ₂ .

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

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

_{Для построения} последовательности Соболя необходимо выбрать набор номеров направлений vi _{, j .} Имеется некоторая свобода в выборе начальных номеров направлений. ^{[примечание 1]} Следовательно, можно получить разные реализации последовательности Соболя для выбранных измерений. Неправильный выбор начальных чисел может значительно снизить эффективность использования последовательностей Соболя для вычислений.

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

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

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

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

Другие реализации доступны в виде подпрограмм C, Fortran 77 или Fortran 90 в коллекции программного обеспечения Numerical Recipes . ^[9] Бесплатная реализация с открытым исходным кодом , имеющая до 1111 измерений, основанная на числах инициализации Джо и Куо, доступна в C, ^[10] и до 21201 измерений в Python ^{[11] [12]} и Julia . ^[13] Другая бесплатная реализация с открытым исходным кодом, поддерживающая до 1111 измерений, доступна для C++ , Fortran 90 , Matlab и Python . ^[14]

Коммерческие генераторы последовательностей Соболя доступны, например, в библиотеке NAG . ^[15] ООО «БРОДА» ^{[16] [17]} предоставляет генераторы Соболя и скремблированных последовательностей Соболя с дополнительными свойствами однородности A и A' до максимальной размерности 131072. Эти генераторы были разработаны совместно с профессором И. Соболь. MATLAB ^[18] содержит генераторы последовательностей Соболя до размерности 1111 как часть своего набора инструментов статистики.

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

• Последовательности с низким расхождением
• Метод квази-Монте-Карло

Примечания

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

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

1. Соболь, И.М. (1967), "Распределение точек в кубе и приближенное вычисление интегралов". Ж. Выч. Мат. Мат. Физ. 7 : 784–802 (на русском языке); СССР Компьютер. Математика. Математика. Физ. 7 : 86–112 (на английском языке).
2. Нидеррайтер, Х. (1988). «Последовательности с низким расхождением и низкой дисперсией», Журнал теории чисел 30 : 51–70.
3. Антонов И.А. и Салеев В.М. (1979) «Экономический метод вычисления LP _τ -последовательностей». Ж. Выч. Мат. Мат. Физ. 19 : 243–245 (на русском языке); СССР Компьютер. Математика. Математика. Физ. 19 : 252–256 (на английском языке).
4. Соболь, И. М. (1976) "Равномерно распределенные последовательности с дополнительным свойством однородности". Ж. Выч. Мат. Мат. Физ. 16 : 1332–1337 (на русском языке); СССР Компьютер. Математика. Математика. Физ. 16 : 236–242 (на английском языке).
5. Соболь И.М. и Левитан Ю.Л. (1976). «Производство точек, равномерно распределенных в многомерном кубе» Тех. Отчет 40, Институт прикладной математики АН СССР .
6. Брэтли, П. и Фокс, Б.Л. (1988), «Алгоритм 659: реализация генератора квазислучайных последовательностей Соболя». АКМ Транс. Математика. Программное обеспечение 14 : 88–100.
7. "Генератор последовательностей Соболь" . Университет Нового Южного Уэльса . 16 сентября 2010 г. Проверено 20 декабря 2013 г.
8. Якель, П. (2002) «Методы Монте-Карло в финансах». Нью-Йорк: Джон Уайли и сыновья . ( ISBN 0-471-49741-X .) 
9. Пресс, В.Х., Теукольский, С.А., Веттерлинг, В.Т. и Фланнери, Б.П. (1992) «Численные рецепты на Фортране 77: Искусство научных вычислений, 2-е изд.». Издательство Кембриджского университета, Кембридж, Великобритания
10. Реализация последовательности Соболя на языке C в библиотеке NLopt (2007).
11. «Справочник по API SciPy: scipy.stats.qmc.Sobol» .
12. Империале, Г. «pyscenarios: генератор сценариев Python».
13. Пакет Sobol.jl: Реализация последовательности Соболь в Julia.
14. Квазислучайная последовательность Соболя, код для C++/Fortran 90/Matlab/Python Дж. Буркардта
15. "Группа численных алгоритмов" . Nag.co.uk. 28 ноября 2013 г. Проверено 20 декабря 2013 г.
16. И. Соболь, Д. Асоцкий, А. Крейнин, С. Кучеренко (2011). «Построение и сравнение крупногабаритных генераторов Соболь» (PDF) . Уилмотт Журнал . Ноябрь (56): 64–79. дои : 10.1002/wilm.10056.{{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )
17. "Брода". Брода. 23 января 2024 г. Проверено 23 января 2024 г.
18. справочная страница sobolset. Проверено 24 июля 2017 г.

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

• Сборник алгоритмов АКМ (см. алгоритмы 647, 659 и 738).
• Сборник программных кодов генератора последовательностей Соболя
• Бесплатный C++-генератор последовательности Соболя