Оглавление
- 1 Последовательность с низким уровнем расхождений
- 1.1 Последовательности с низким расхождением
- 1.2 Приложения квазислучайных чисел
- 1.3 Численное интегрирование
- 1.4 Определение несоответствия
- 1.5 Неравенство Коксмы-Главки
- 1.6 L2-версия неравенства Коксмы-Главки
- 1.7 Неравенство Эрдеша-Турана-Коксмы
- 1.8 Основные гипотезы
- 1.9 Нижние границы
- 1.10 Построение последовательностей с низким уровнем расхождений
- 1.11 Последовательности Ван дер Корпута, Холтона и Соболя
- 1.12 Случайные числа и квазислучайные числа
- 1.13 Аддитивное повторение
- 1.14 Ценность c
- 1.15 Последовательность ввода данных ван дер Корпа
- 1.16 Последовательность Хэлтона
- 1.17 Набор Хаммерсли
- 1.18 Последовательность действий Соболя
- 1.19 Выборка по диску Пуассона
- 1.20 Графические примеры
- 1.21 Дополнительные ресурсы
- 1.22 Полный текст статьи:
- 2 Последовательность с низким расхождением
Последовательность с низким уровнем расхождений
-
Последовательности с низким расхождением
- Последовательности с низким расхождением имеют подпоследовательности с низким расхождением для всех значений N.
- Несоответствие определяется как доля точек в последовательности, попадающих в произвольный набор B.
- Квазислучайные последовательности используются как замена равномерно распределенных случайных чисел.
-
Приложения квазислучайных чисел
- Быстрое и равномерное покрытие интересующей области.
- Нахождение характеристической функции и производной функции.
- Быстрое вычисление моментов более высокого порядка.
- Определение среднего значения, стандартного отклонения и других статистических параметров.
- Использование в детерминированных алгоритмах, таких как итерация Ньютона-Рафсона.
-
Численное интегрирование
- Методы численного интегрирования аппроксимируют интеграл через заданный промежуток времени.
- Правило прямоугольника использует точки с небольшим расхождением, но требует пересчета элементов при увеличении N.
- Метод Монте-Карло не требует пересчета, но не имеет минимального расхождения.
- Последовательности с низким расхождением стремятся к низкому расхождению и отсутствию повторных вычислений.
-
Определение несоответствия
- Несоответствие набора P определяется через меры Лебега и количество точек в B.
- Звездное несоответствие D_N^*(P) аналогично, но верхняя точка берется поверх множества прямоугольных коробок.
-
Неравенство Коксмы-Главки
- Качество правила численного интегрирования зависит только от несоответствия D_N^*(x_1, …, x_N).
- Формула Главки-Зарембы связывает несоответствие с функцией расхождения.
-
L2-версия неравенства Коксмы-Главки
- L2-версия неравенства Коксмы-Главки позволяет быстро вычислять расхождение для больших N и s.
-
Неравенство Эрдеша-Турана-Коксмы
- Дает верхнюю границу для расхождения больших наборов точек.
-
Основные гипотезы
- Гипотеза 1: Существует постоянная c_s, зависящая только от s, такая, что D_N^*(x_1, …, x_N) ≥ c_s для любого конечного множества точек.
- Гипотеза 2: Существует постоянная c’s, зависящая только от s, такая, что D_N^*(x_1, …, x_N) ≥ c’s(ln N)^s/N для бесконечного числа N и любой бесконечной последовательности x_1, x_2, x_3, …
-
Нижние границы
- Для s = 1: D_N^*(x_1, …, x_N) ≤ 1/N.
- Для s = 2: D_N^*(x_1, …, x_N) ≤ 1/(N^2).
- Для s > 1: D_N^*(x_1, …, x_N) ≤ 1/(N^t), где t = 0 для s = 2 и t = 1 для s > 2.
-
Построение последовательностей с низким уровнем расхождений
- Последовательности с низким уровнем расхождений могут быть построены на основе многомерного равномерного распределения.
- Известны конструкции последовательностей с наилучшим возможным порядком сходимости.
-
Последовательности Ван дер Корпута, Холтона и Соболя
- Методы построения обычно гарантируют только порядок сходимости
- Низкое расхождение достигается при большом N
- Анализ методом Монте-Карло с N=1000 точек может обеспечить незначительное повышение точности
-
Случайные числа и квазислучайные числа
- Последовательности квазислучайных чисел генерируются из случайных чисел с отрицательной корреляцией
- Один из способов: s_i = r_i для нечетных i и s_i = 0.5 + r_i для четных i
- Второй способ: случайное блуждание со смещением 0.5
-
Аддитивное повторение
- Последовательность с иррациональным α имеет расхождение, стремящееся к 1/N
- Показатель аппроксимации α равен 2, что дает оценку N^-1+ε
- Значения a и m выбраны равными 1, но не гарантируют независимость
-
Ценность c
- Наименьшее расхождение у дробной части золотого сечения
- Дробная часть серебряного сечения также почти так же хороша
- В нескольких измерениях используются отдельные квазислучайные числа
-
Последовательность ввода данных ван дер Корпа
- Последовательность удовлетворяет неравенству D_N^*, где D_N^* — несоответствие звезд
-
Последовательность Хэлтона
- Обобщение последовательности Ван дер Корпута на s-мерные последовательности
- Последовательность {x(n)}n≥1 имеет s-мерное расхождение
-
Набор Хаммерсли
- Определяется для s-мерных последовательностей с взаимно простыми числами b1, …, bs-1
-
Последовательность действий Соболя
- Генерирует числа от нуля до единицы в виде двоичных дробей длины w
- Использует биты кода Грея для выбора номеров направлений
-
Выборка по диску Пуассона
- Популярна в видеоиграх для быстрого размещения объектов
- Гарантирует, что каждые две точки разделены минимальным расстоянием
-
Графические примеры
- Точки на графике представляют первые 100, 1000 и 10000 элементов последовательности Sobol’
- Последовательность с низким расхождением сгенерирована алгоритмом TOMS 659
-
Дополнительные ресурсы
- Теория несоответствия
- Цепь Маркова Монте-Карло
- Метод Квазимонте-Карло
- Разреженная сетка
- Систематический отбор проб
- Записи
- Рекомендации
- Внешние ссылки