Диссертация (1150625), страница 6
Текст из файла (страница 6)
В этом свете естественной представляется идея ввести рандомизацию в детерминированную процедуру квази-Монте-Карло с целью построения доверительного интервала по аналогии с методом Монте-Карло.Рандомизированный квази-Монте-Карло (randomized quasi-Monte Carlo, RQMC) в простейшем случае состоит в следующем. Пусть = {1 , . . . , } – некий детерминированныйlow-discrepancy набор, из которого мы построим независимых рандомизированных наборов ˜1 , . .
. , ˜ . Более строго, под рандомизацией мы будем подразумевать преобразование˜ = Ψ( , ), так что конечный набор ˜ порождается случайной величиной и обладает теми же квазислучайными свойствами, что и исходный набор ˜ . При это мы говорим, что ран-26домизированные наборы ˜1 , . . . , ˜ независимы, если независимы порождающие их случайныевеличины 1 , .
. . , . Мы приводим примеры подходящих преобразований Ψ далее.∑︀Для удобства мы будем пользоваться обозначением ( ), подразумевая под ним суммузначений функции во всех точках, входящих в набор . Для каждого из рандомизированныхнаборов построим квази-Монте-Карло оценку, аналогичную (1.23): ,=1 ∑︁ ˜ ( ),(1.41)а в качестве общей рандомизированного квази-Монте-Карло оценки возьмём их среднее: =1 ∑︁ . =1 ,(1.42) Если мы выберем преобразование Ψ таким образом, что каждая из оценок ,обладает свойством несмещённости (∀ E(,) = ), то и общая оценка также будет несмещённой: ) = .E(Относительно дисперсий (1.41) и (1.42) можно сказать, что они связаны выражением Var()= )Var(,,(1.43)что справедливо для любого в силу независимости рандомизаций.
Если в случае дисперсиинаивного Монте-Карло в числителе (1.5) стоит дисперсия подынтегральной функции (1.4), чтовыполнялось в силу независимости всех векторов, то в случае рандомизированного квази ), вообще говоря, не равна 2 . Это происходит потому, что вМонте-Карло величина Var(,рамках одного набора ˜ входящих в него векторов независимыми в общем случае не являют-ся, потому что они порождены рандомизацией Ψ над детерминированным набором .Мы можем контролировать точность оценки (1.42) при помощи доверительного интервала,построенного на основе следующей оценки дисперсии:̂︂ ) =Var()︁2∑︁ (︁ 1 ,− .( − 1) =1(1.44)Легко показать, что оценка (1.44) является несмещённой оценкой для дисперсии (1.43).Желательно, чтобы метод рандомизации Ψ не нарушал low-discrepancy свойств исходного набора . Так, например, если исходное множество является (,,)-сетью или (,)последовательностью, то естественно стараться подобрать Ψ таким образом, чтобы ˜ такжеявлялось (,,)-сетью или (,)-последовательностью, соответственно5 .Одним из наиболее распространённых способов рандомизации для (,,)-сетей предложенОуэном А.
в [43], [44]. С одной стороны, он достаточно прост с алгоритмической точки зрения,5В случае, когда речь идёт о свойствах рандомизированных наборов ˜ , подразумевается их выполнение с вероятностью 1.27с другой – обладает некоторыми важными теоретическими свойствами, что делает его удачнымвыбором для последующих численных экспериментов.Определение 5.
Рассмотрим процедуру скрэмблинга (scrambling) для произвольной точки гиперкуба ∈ . Пусть каждая координата этой точки = (1 , . . . , ) имеет -ичное представление∞∑︀ − , где ∈ {0, 1, . . . , − 1}. На шаге алгоритма рассмотрим случайнуювида ==1перестановку 1 ...−1 чисел {0, 1, . . . , − 1}, независимую от любых ранее используемых и˜ = (˜определим ˜ = 1 ...−1 . Точка ˜ после скрэмблинга определяется как 1 , . . . , ˜ ),∞∑︀где ˜ =˜ − .=1Пусть {1 , . . . , } есть некоторая (,,)-сеть по основанию (например, отрезок последовательности Соболя при некоторых и = 2). Рандомизированная сеть {˜1 , . . . , ˜ } являетсярезультатом применения к каждой точке одной и той же процедуры скрэмблинга, описаннойопределением 5.
Для такой рандомизации Оуэном доказано несколько важных утверждений. Вопервых, скрэмблинг сохраняет параметры сети, то есть (,,)-сеть останется (,,)-сетью свероятностью 1. Во-вторых, для частного случая = 0 дисперсия оценки интеграла ограниченасверху:⎛⎞∑︁12.72 2 (˜ )⎠ 6Var ⎝. =1(1.45)В-третьих, для произвольного > 0 и = 2 (случай последовательности Соболя) справедливадругая граница дисперсии:⎛⎞∑︁12Var ⎝ (˜ )⎠ 6 2 3 . =1(1.46)Важным для рандомизированного квази-Монте-Карло является вопрос о выборе достаточного числа рандомизаций . В качестве ответа на последний вопрос приведём следующий результат Оуэна А.
из [45] для алгоритма скрэмблинга: если для функции выполнен ряд условийна смешанные частные производные порядка , то порядок убывания дисперсии рандомизи−1рованного квази-Монте-Карло равен ( ln3 ), что асимптотически лучше порядка наивного1Монте-Карло ( ). Таким образом, с точки зрения асимптотики выгоднее увеличивать коли-чество точек в рамках одной рандомизации, что в ситуации с фиксированным количествомвычислений функции ведёт к сокращению .
С другой стороны, для маленьких оценка (1.44)окажется недостоверной, и поэтому обычно для практических задач рекомендуется брать > 10(см. Лемьё К. [31]). Стоит отметить, однако, что это сугубо практическая рекомендация, и вопросо выборе не имеет окончательного ответа.1.2Квадратура QintМетод квази-Монте-Карло обладает естественной интерпретацией в терминах разложенияподынтегральной функции в ряды по кусочно-постоянным функциям. Так, многие авторы свя-28зывают остаток интегрирования с семействами функций Хаара (Соболь И.М., [14]) и Уолша(Лемьё К., [31], Дик Дж.
и Пиллихшаммер Ф., [29]), который определяется асимптотическимповедением коэффициентов такого разложения. В связи с этим возникает идея построения такой случайной квадратурной формулы, которая была бы точна для первых функций из семейств Хаара.
Мы надеемся при этом, что нам удастся провести параллели между использованием подобной формулы и квазислучайными low-discrepancy наборами: (,,)-сетями и (,)последовательностями.1.2.1Обобщённая система ХаараСистема функций Хаара, построенная Хааром А. в [46], является базисом в пространстве2ℒ [0,1]. Мы приведём определение этой системы и обобщим его на многомерный случай. Похожая идея обобщённой системы Хаара, но с другим подходом к определению, озвучена Энтахером К.
в [47].По аналогии с определениями, приведёнными Соболем И.М. в [14], введём обозначение(︂=−1 ,2 2)︂,где ∈ 1, . . . , 2 , ∈ N0 .Определение 6. Для произвольного натурального рассмотрим его разложение в виде = 2 +,где ∈ 1, . . . , 2 , ∈ N0 . Функция Хаара с номером задаётся следующим образом:1 () = 1,⎧⎪+1⎪22 , ∈ 2−1;⎪⎪⎨+1 () = −2 2 , ∈ 2;⎪⎪⎪⎪⎩0, ∈ [0,1] ∖ ¯(1.47)где ¯ – замыкание . При этом все функции непрерывны справа в нуле и непрерывны слева вединице, а во внутренних точках разрыва функции Хаара определяются как полусумма пределовслева и справа.Система Хаара (1.47) является ортонормированной в ℒ2 [0,1].
Помимо этого, Шаудер Дж. [48]показал, что система Хаара является базисом для всех пространств ℒ [0,1] для 1 6 < ∞.Другие важные свойства системы подробно описаны в книге Соболя И.М. [14], и обзорнойстатье Голубова Б.И. [49]. Введём понятие обобщённой системы Хаара, состоящей из функций,определённых не на единичном отрезке, а на множестве X.Определение 7. Рассмотрим общую постановку задачи численного интегрирования (X,F,).Пусть – произвольное натуральное число, и пусть определено некоторое разбиение X на 29непересекающихся связных подмножеств равной меры:X = X1 ∪ X2 ∪ .
. . ∪ X , ∀ (X ) =1, ∀ ̸= X ∩ X = ∅.(1.48)Мы будем называть такое разбиение (X, )-разбиением.Определение 8. Пусть, как и ранее, = 2 + , где ∈ 1, . . . , 2 , ∈ N0 . Пусть = 2 для−некоторого ∈ N0 и задано (X, 2 )-разбиение. Определим двоичные подмножества l , l+ , lследующим образом:l+ = X(−1)2− +1 ∪ . . . ∪ X2− −2−−1 ;l− = X2− −2−−1 +1 ∪ . . . ∪ X2− ;l = X(−1)2− +1 ∪ . . . ∪ X2− .Тогда обобщённая функция Хаара с номером 6 задаётся как1 () = 1,⎧⎪⎪22 , ∈ l+⎪ ;⎪⎨ () = −2 2 , ∈ l− ;⎪⎪⎪⎪⎩0, ∈ X ∖ l̄ .(1.49)[︀)︀Легко убедиться, что в одномерном случае X = [0,1] и при разбиении X1 = 0, 21 , .
. . , X =]︀[︀ [︀ −1 )︀,обобщённая система функций Хаара (1.49) совпадает с класси, . . . , X = 2 2−1 ,12 2ческой системой Хаара (1.47) за исключением точек разрыва, что не играет принципиальногозначения в контексте частной постановки задачи численного интегрирования, потому что речьидёт о множестве нулевой меры.Естественно ожидать сохранения свойства ортонормированности для обобщённой системыХаара.Лемма 1.
Обобщённая система Хаара является ортонормированной в ℒ2 (X), т.е.1) ∀∫︀2 ()() = 1,X2) ∀ ̸= ∫︀ () ()() = 0.XДоказательство. Для фиксированного номера количество таких подмножеств из имеющегося(X, 2 )-разбиения, где функция Хаара не обращается в ноль, легко определить из индексов l :оно равно 2− − (( − 1)2− + 1) + 1 = 2− . Тогда∫︁X2 ()()∫︁=l2 () = 2 2− (X1 ) = 2 2− 2− = 1.30Теперь пусть разложения для и задаются = 2 + и = 2 + . Тогда∫︁∫︁ () ()() = () ()() =Xl̄ ∩l̄В случае, когда l̄ ∩ l̄ = ∅, равенство нулю выполнено. В противном случае, = 2+2(︁)︁+−−+−−+(l+∩l)+(l∩l)−(l∩l)−(l∩l).Пусть для определённости < .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
