Диссертация (1150625), страница 5
Текст из файла (страница 5)
. . , . При этом асимптотикаубывания остатка полностью определяется величиной стар-дискрепанса * , поэтому вопрос оприменимости метода квази-Монте-Карло во многом сводится к вопросу отыскания и исследования оптимальных последовательностей.Более современный взгляд (например, Хиккернелл Ф., [28], Дик Дж. и Пиллишхаммер Ф.,[29]) на неравенство Коксмы-Хлавки преподносится с точки зрения функционального анализа. Если рассмотреть некоторое гильбертово пространство, состоящее из вещественнозначныхфункций на , то остаток квадратурной формулы является линейным функционалом. Если онограничен, то аналог неравенства Коксмы-Хлавки можно получить как неравенство нормы этого функционала.
Такой подход обширно применяется для получения обобщённых характеристикнаборов точек (ℒ -дискрепанс и другие) и результатов для различных классов функций.Как отмечается многими авторами, неравенство (1.28) не может служить основой для конструктивной оценки ошибки интегрирования в практических приложениях. С одной стороны,определение стар-дискрепанса произвольного набора есть -сложная задача (Гневух М.
идр., [30]). С другой стороны, оценка вариации Харди-Краузе также представляет собой сложнуювычислительную задачу. Более того, для некоторых практических задач ( ) = ∞ (примерыможно найти у Лемьё К. в [31]). В связи с этим в практических приложениях практически всегда используется рандомизированный вариант квази-Монте-Карло, о котором речь пойдёт далее.Существует достаточно большое количество квазислучайных последовательностей, обладающих минимально известным порядком убывания дискрепанса(ln )(︂)︂.(1.30)Такие последовательности имеют название low-discrepancy последовательностей; срединих самыми широко распространёнными являются последовательности Холтона Дж.
(Haltonsequence, [16]), Соболя И.М. (Sobol sequence, [15]), Форе Х. (Faure sequence, [32]) и Нидеррейтера Х. (Niederreiter sequence, [33]).4Строгое определение вариации в смысле Харди-Краузе может быть найдено у Нидеррейтера Х. в [17].21Помимо вышеуказанных частных конструкций, существуют и более общие категории lowdiscrepancy наборов. В частности, алгоритмы построения таких наборов могут быть двух разныхтипов:– Закрытого типа: строится конечный -точечный набор, определяемый значением и пересчитываемый заново для разных .– Открытого типа: используются первые точек из бесконечной последовательности, поэтому для оценки с увеличенным можно использовать полученные ранее значения.Числовые сети и последовательности, рассматриваемые далее, являются алгоритмами закрытого и открытого типа, соответственно.
Необходимо отметить, что существует и другой популярный раздел квази-Монте-Карло: решёточные правила (lattice rules). Истоками этого направленияявляются работы Коробова Н.М. (например, книга [34]), более новые результаты указаны в работе Слоана И. и Джоуи С., [35]. Сравнение современных алгоритмов построения решёточныхправил и числовых сетей и последовательностей проведено в статье Нюенса Д. и Куулса Р. [36].Далее нас будут интересовать только числовые сети и последовательности, которые мы обсудимподробнее.1.1.6Числовые сети и последовательностиОсновная идея квази-Монте-Карло состоит в том, чтобы получить хорошо распределённые(в некотором смысле) наборы точек в гиперкубе = [0,1) .
Идея построения (,,)-сетизаключается в размещении точек таким образом, чтобы их количество было пропорциональнообъёму подмножеств гиперкуба определённого вида.Определение 3. Пусть > 0, > 1, > 1, > 2 – натуральные числа, при этом 6 . (,,)сетью по основанию называется такой набор из точек, что произвольное элементарноеподмножество вида)︂ [︂∏︁ + 1, =1(1.31)для любых натуральных > 0, 0 6 < , где 1 + . . . + = − , содержит в точности точек из .Отметим один тривиальный факт, непосредственно вытекающий из определения: любая(,,)-сеть автоматически является ( + 1,,)-сетью.
В частности, любой набор из точекпредставляет собой (,,)-сеть. В связи с этим для фиксированных , и возникает вопрособ отыскании такой сети, чтобы параметр был минимально возможным. В этом контексте также часто носит название параметра качества.Аналогичная идея стоит и за понятием (,)-последовательности.22Определение 4.
Пусть > 0, > 1, > 2 – натуральные числа. (,)-последовательностью пооснованию называется такой бесконечный набор = ( 1 , 2 , . . .), что для любых натуральных > и > 0 произвольный отрезок, состоящий из точек набора , вида , . . . , (+1) −1(1.32)является (,,)-сетью по основанию .Вышеупомянутое рассуждение о минимизации параметра также справедливо и для (,)последовательностей. Для практических задач рекомендуется выбирать такие сети и последовательности, у которых параметр качества является наименьшим из возможных.
Такие оптимальные параметры указаны в онлайн базе данных MinT (Шюрер Р. и Шмидт У., [37]). Там жеприводятся конструктивные методы построения таких квазислучайных наборов.1.1.7Последовательность ХолтонаПоследовательность Холтона, построенная Холтоном Дж. в [16], стала одной из первых квазислучайных последовательностей, для которой теоретически получено свойство lowdiscrepancy. Чтобы ввести определение точек Холтона, для произвольного целого неотрицательного рассмотрим его -ичное разложение вида=∞∑︁ () ,(1.33)=0которое для произвольного целого основания > 2 всегда единственно с учётом двух требований: во-первых, () ∈ {0, 1, .
. . , − 1}, во-вторых, для достаточно большого 0 все () = 0при > 0 (то есть разложение не содержит бесконечного числа ненулевых слагаемых). Теперьпусть функция () определена как () =∞∑︁ ()−−1 .(1.34)=0Такое преобразование () действует на число , отображая его в отрезок [0,1).Пусть для данной размерности зафиксированы взаимно простые основания 1 , . . .
, . Последовательность Холтона по основаниям 1 , . . . , определяется как (1 , 2 , . . .), где = (1 (), . . . , ()).(1.35)Точки Холтона обладают тем преимуществом, что алгоритм их построения крайне прост.Однако с ростом размерности при наличии достаточно близких оснований и становится всё более актуальной проблема сильной положительной коррелированности между парамикоординат с номерами и .
Существует несколько различных приёмов, направленных на борь-23бу с этим эффектом, основанных на перемешивании координат или пропуске некоторых точекпоследовательности.1.000.750.500.250.000.000.250.500.751.00Рисунок 1.2: Точки ХолтонаНа рисунке 1.2 изображены первые 32 точки двумерной последовательности Холтона пооснованиям 1 = 2, 2 = 3.
Довольно легко увидеть, что точки Холтона не образуют (,)последовательность, поэтому на практике в методе квази-Монте-Карло более широкое распространение имеет последовательность Соболя.1.1.8Последовательность СоболяПоследовательность Соболя, построенная Соболем И.М. в [15], является первой известнойконструкцией, которая является (,)-последовательностью в смысле определения 4. Она определяется следующим образом: пусть 1 , .
. . , ∈ F2 () – примитивные многочлены, упорядоченные в порядке неубывания степеней. Так, для 1 6 6 пусть () = + 1, −1 + . . . + −1, + 1.(1.36)24Возьмём произвольные нечётные натуральные числа 1, , . . . , , , такие что , < 2 для1 6 6 . Для всех > числа , определяются рекурсивно при помощи побитовогооператора XOR (исключающего или), обозначаемого ⊕:, = 21, −1, ⊕ 22 2, −2, ⊕ .
. . ⊕ 2 −1 −1, − +1, ⊕ 2 − , ⊕ − , .(1.37)Далее, определим направляющие числа , как, =,.2(1.38)Наконец, для произвольного ∈ N0 , имеющего двоичное разложение = 0 +21 +. . .+2−1 −1 ,-тая соболевская координата -ной точки последовательности имеет вид, = 0 1, ⊕ 1 2, ⊕ . . . ⊕ −1 , .(1.39)Таким образом, последовательность Соболя определяется как совокупность (0 , 1 , .
. .), где = (,1 , . . . , ).Широко известен эффективный приём, предложенный Антоновым И.А. и Салеевым В.М.в [38]. А именно, для последовательной генерации точек Соболя можно воспользоваться кодамиГрея () = ⊕ ⌊/2⌋. Учитывая тот факт, что коды Грея для чисел и + 1 всегда отличаютсятолько одним битом (пусть он имеет номер ), достаточно положить+1, = , ⊕ , .(1.40)Как видно из алгоритма построения последовательности Соболя, ключевое значение имеютнаправляющие числа {, }. Поиск оптимальных (с точки зрения качества конечной последовательности) наборов направляющих чисел представляет собой отдельную задачу.
Самим Соболем И.М. предложены такие наборы до размерности = 51, работа Джоуи С. и Куо Ф. [39]предоставляет таблицы для размерностей вплоть до = 21201.Рисунок 1.3 представляет 32 точки из последовательности Соболя и свойства их распределённости. Все отмеченные прямоугольники имеют левый нижний угол в точке (0,0) и, являясьэлементарными множествами в смысле определения 3, содержат ровно по одной точке.Как известно, последовательность Соболя не является оптимальной в смысле минимальновозможного (см.
Дик и Нидеррейтер [40]). Вообще говоря, всё дальнейшее изложение справедливо относительно произвольной (,)-последовательности, но мы будем использовать именнопоследовательность Соболя по трём причинам. Во-первых, потому что последовательность Соболя изначально базируется на системах Хаара, и распределённость точек по бинарным отрезкамизучена самим Соболем И.М.
в [15]. Во-вторых, описанная выше алгоритмическая модификацияАнтонова И.А. и Салеева В.М. позволяет быстро получать подряд идущие точки из последовательности Соболя. И в-третьих, существует несколько эффективных реализаций соболевских251.000.750.500.250.000.000.250.500.751.00Рисунок 1.3: Точки Соболя как (0,2)-последовательность по основанию 2генераторов, распространяемых под свободными лицензиями. Одна из таких реализаций использована нами для реализации предлагаемого метода и получения всех численных результатов (описание алгоритма дано у Брэтли и Фокса в [41], реализация библиотеки HIntLib [42], [23]выполнена Шюрером Р.).1.1.9Рандомизированный метод квази-Монте-КарлоКак уже обсуждалось ранее, практическое применение квази-Монте-Карло ограничиваетсянеконструктивностью оценки (1.28).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
