Диссертация (1150625), страница 14
Текст из файла (страница 14)
Если количество подмножеств разбиения значительно превышает количество точек рандомизированной квазислучайной последовательности, то что можно утверждать о погрешностиоценки? В численных экспериментах второй главы общее количество точек подбиралось такимобразом, чтобы такая ситуация не имела место, но вопрос актуален в случае, когда допустимоеколичество вычислений подынтегральной функции меньше необходимого для равномерного покрытия.Выберем произвольное натуральное основание > 2 и разделим -тое ребро единичногогиперкуба на равных частей, где – натуральные числа. Через каждую точку такогоразделения проведём рассечение гиперкуба с помощью гиперплоскостей размерности − 1,параллельных координатным гиперплоскостям, не содержащим данную точку1 .
Мы получим∏︀рассечение гиперкуба на = гиперпараллепипедов равного объёма, то есть ( , )=1разбиение.Точки, в которых пересекается − 1 взаимно перпендикулярных гиперплоскостей (включаяграни гиперкуба ) образуют сетку, представимую для всех координат = 1, . . . , в виде =∑︁=1,(3.1)где = 0, . . . , − 1 для всех допустимых . Иными словами, есть -ичная дробь вида = (0.1 2 . . . ) .(3.2)Вектор ⃗ можно рассматривать как (векторный) номер той ячейки ( , )-разбиения, длякоторой он указывает на вершину, имеющую все координаты минимальными из имеющихся дляэтого гиперпараллелепипеда.
Так, например, на рисунке 3.1 представлен случай = 3, 1 = 1,2 = 3. Отмеченные ячейки соответствуют векторным номерам (0,0), (1,22) и (2,10).Пусть теперь ( ) суть не обязательно независимые равномерно распределённые на (0,1)случайные величины. Тогда, очевидно, точка Ξ(⃗) с координатами (⃗) = +( )(3.3)будет равномерно распределена в ячейке сетки с номером ⃗.Для приближения интеграла естественно использовать оценку вида (1.9), которая в этомслучае может быть записана в виде∑︁1 ∑︁ = ( ), =1=11(3.4)Аналогичная процедура применялась для определения правила бинарного рассечения, проиллюстрированногорисунком 2.1.7712/31/3001/32/31Рисунок 3.1: Пример неравномерного разбиения двоичного гиперкубагде обозначает общее количество узлов, входящих в такую оценку.Для того, чтобы обеспечить несмещённость такой оценки и выполнение условия неубывания дисперсии для всех функций из ℒ2 ( ), обычно пользуются таким алгоритмом расслоения,который гарантирует некоторое пропорциональное размещение точек в каждой ячейке.
Это вносит дополнительную алгоритмическую сложность: необходимо обеспечивать запоминание ужеимеющегося распределения после генерации каждой последующей точки.При сравнительно небольших значениях можно использовать различные способы перечисления векторных номеров сетки. Случай = 2 довольно подробно изучен нами в предыдущихглавах. Показано, как последовательность Соболя может быть эффективно использована для выполнения необходимого условия распределения. Напомним, что правило бинарного рассеченияв методе Qint подобрано таким образом, чтобы это условие пропорциональности выполнялосьавтоматически для точек Соболя в силу определения (,)-последовательности 4.Рассмотрим случай „мелкой“ сетки ≫ при достаточной больших и .
Интерес представляет поведение последовательности оценок вида (3.4) с ростом в зависимости от алгоритма выбора номеров ⃗ ячеек сетки. Легко наблюдать, что если выбор номера ⃗ осуществляется78случайным и равновероятным образом из совокупности номеров, то точка Ξ(⃗) будет равномерно распределена в , что приводит к простейшему методу Монте-Карло.В общем же случае, если определён алгоритм выбора номеров ⃗, то для математическогоожидания оценки справедливо равенство∫︁∑︁1 ∑︁E( ) = =1=1 (),(3.5)Δ⃗( )где ∆⃗ обозначает ячейку с номером ⃗.
Если дополнительно все = 1, то имеем = и∫︁1 ∑︁E( ) = (),(3.6)⃗ Δ⃗где суммирование ведётся по всевозможным номерам ⃗.При ̸= величина является, вообще говоря, смещённой оценкой интеграла, однако малое смещение оценки может быть обеспечено при значениях , близких к . Строгий результат˜ оценки может быть получен для модификации ∑︁˜ = 1 (⃗ ),(3.7)⃗где ⃗ ∈ ∆⃗ , а вся -точечная совокупность {⃗ }⃗ представляет собой рандомизированнуюlow-discrepancy последовательность.Рассмотрим вспомогательную функцию ˜(), определяемую как˜() =∫︁ ()(3.8)Δ⃗при ∈ ∆⃗ . ˜() есть ступенчатая функция, аппроксимирующая (), которая будет близка кней при достаточно больших .
При этом величина ошибки аппроксимации зависит от классарассматриваемых функций.Справедливо следующее утверждение.Утверждение 1. Пусть функция ˜ является функцией ограниченной вариации. При ≫ имеет место равенство⃒⃒⃒⃒)︂(︂ ∫︁⃒⃒ln ( )⃒ ˜⃒.⃒E( ) − ()⃒ = ⃒⃒⃒⃒79Доказательство. Из неравенства Коксмы-Хлавки (теорема 3) для функции ˜ непосредственноследует, что⃒⃒⃒⃒(︂ )︂∫︁⃒⃒ 1 ∑︁ln ( )⃒⃒˜˜. ( ) − ()⃒ = ⃒⃒⃒⃒⃒ =1∫︁Но˜() =∫︁1 ∑︁ ˜ (), а E( ) = ( ), что и доказывает утверждение. =1В этих же предположениях для оценки интеграла методом RQMC возможны два варианта.1) Рассмотрим один -точечный квазислучайный набор 1 , .
. . , . Проведём для него независимых рандомизаций и построим оценок интеграла∑︀(1)1 , . . . , → 1 , . . . , → =... ( );=1...()1 , . . . , → (−1) +1 , . . . , → ∑︀= ( ).=(−1) +12) Рассмотрим последовательных точек квазислучайной последовательности, и для каждого отрезка длины проведём рандомизацию, независимую с остальными. Получим оценок→ 1, . . . , 1 , .
. . , ...∑︀(1)→ = ( );=1...∑︀()(−1) +1 , . . . , → (−1) +1 , . . . , → = ( ).=(−1) +1Теперь рассмотрим комбинированные оценки для обоих случаев, полученные усреднением:1 ∑︁ ()1 ∑︁ () , = .= =1 =1 (1)()Предположим, что выполнены условия утверждения 1. В этом случае для оценок , . . . , ,составляющих , будет выполнено(1)E( )= ... =()E( )∫︁=ln ( ) () + (︂)︂.Из этого в силу независимости рандомизаций следует, что для общей оценки справедливо(︂ )︂∫︁1 ∑︁ln ( )()E() =E( ) = () + .
=1(3.9)80С другой стороны, для случая, когда мы берём последовательных точек, мы вправе ожидать,что∫︁E() =ln ( ) () + (︂)︂,(3.10)что лучше с точки зрения асимптотики. Эта разница может быть существенной при относительно малых размерностях и достаточно больших значениях .В пользу второго подхода свидетельствует ещё одно обстоятельство. Говоря нестрогим языком, использование большего количества точек квазислучайной последовательности являетсяболее оправданным в силу того, что к оценкам и применима центральная предельная теорема в предположении выполнения условия Линдеберга.
В этом свете для следует ожидатьболее точного результата относительно математического ожидания предельного распределения,потому что мы задействуем более длинный кусок квазислучайной последовательности.По вышеозначенным причинам во всех уже изложенных и последующих численных экспериментах рандомизация проводится именного по второй схеме. Отметим при этом, что предыдущие утверждения формально не зависят от способа рандомизации, поэтому они остаются всиле и для процедуры скрэмблинга, и для нового алгоритма рандомизации квазислучайных последовательностей, о котором речь пойдёт далее.3.2Алгоритм гибридной битовой рандомизацииТрадиционный способ применения расслоенной выборки в контексте численного интегрирования подразумевает разбиение области интегрирования на некоторое количество частей игенерацию случайных точек при наличии определённых ограничений на их попадание в выбранные подобласти (более строгое описание метода приведено в подразделе 1.1.3).
Так, в простейшем случае мы имеем уже рассмотренную ранее ситуацию: X1 , . . . , X является ( , )разбиением. Для генерации -точечной расслоенной выборки необходимо обеспечить принадлежность ∈ X ; обычно полагают, что имеет равномерное распределение в соответствующем множестве: ∼ (X ). Как уже отмечалось ранее, такая процедура в этом частном случае(который, тем не менее, является самым распространённым именно по причине своей простоты)не может вести к увеличению дисперсии.Однако уже в таком простейшем варианте появляются некоторые сложности.1) При интегрировании на практике подсчёт обычно ведётся до тех пор, пока не будет достигнута наперёд заданная точность, поэтому общее количество вычислений функции .формально никак не связано с .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
