Диссертация (1150625), страница 12
Текст из файла (страница 12)
Во-первых, для каждогофиксированного (траектории, обозначенные „Qint_0“, „Qint_1“ и так далее) порядокубыва(︁)︁ния стандартного отклонения ровно такой же, как для наивного Монте-Карло, 11/2 . Этосвойство вполне естественно и было отмечено нами в предыдущей главе. Во-вторых, переборвсевозможных параметров влияет только на константу (не на порядок убывания), причём чембольше , тем эта константа меньше. Этому вопросу мы также уделяли внимание: такое свойствовыполнено в соответствии с теоремой 10. Кроме того, для = 0 (траектория „Qint_0“) имеем в622-62-7Оценка стандартного отклонения2-8МетодMCQint_0Qint_1Qint_2Qint_3Qint_4Qint_5Qint_6Qint_7Qint_8Qint_9Qint_10Qint_11Best Qint2-92-102-112-122-132-142-152-162-172-182-192829210211212213214Количество вычислений подынтегральной функции215216Рисунок 2.2: Произведение кубических полиномов, = 1, без внешних повторовточности ту же самую оценку, что и для наивного Монте-Карло (траектория „MC“), что такжепредсказывалось ранее.
В-третьих, и что наиболее важно, для фиксированного (траектория„Best Qint“) скоростьубыванияоценки стандартного отклонения совпадает с теоретическим(︁)︁1предсказанием, 3/2 . Улучшенный порядок сходимости (по сравнению как с Монте-Карло,(︁)︁(︀ 1 )︀ 11/2 , так и с квази-Монте-Карло, 1−) хорошо виден на иллюстрации 2.3.Многомерный случай ( = 15) представлен иллюстрациями 2.4 и 2.5.С ростом размерности преимущество от использования Qint падает, но остаётся существенным.
Несмотря на то, что траектория „Best Qint“ не перекрывает траекторию квази-Монте-Карло,она тем не менее сокращает разрыв между наивным Монте-Карло и квази-Монте-Карло примерно вдвое, причём равномерно по количеству вычислений функции.2.5.2Плотность нормального распределенияСледующая предлагаемая тестовая функция является адаптацией функции „Gaussian“ изсборника „TESTPACK“ Генца А.
[63]. Она определяется как2 () =∏︁1=1( ; , ),(2.37)632-6Оценка стандартного отклонения2-72-8МетодMCQint_0Qint_1Qint_2Qint_3Qint_4Qint_5Qint_6Qint_7Qint_8Qint_9Best QintRQMC2-92-102-112-122-132-142-152-162-172-182829210211212213214Количество вычислений подынтегральной функции215216Рисунок 2.3: Произведение кубических полиномов, = 1, 16 внешних повторовгде ( ; , ) есть плотность нормального распределения с параметрами и :(−)21(; , ) = √ − 22 . 2(2.38)В нашем случае мы фиксируем параметры = 0.5 (функция симметрична относительно середины∫︁отрезка [0,1]), = 1, а константа подбирается таким образом, чтобы значение интеграла2 = 2 () было равно единице.
Её можно вычислить как (1; , ) − (0; , ) ≈ 0.383,∫︁где (; , ) =(; , ) – функция нормального распределения с теми же параметрами.−∞Продемонстрируем работу алгоритма для низких размерностей (случаи = 2, 3, 4 представлены иллюстрациями 2.6, 2.7 и 2.8, соответственно). Отметим одну интересную деталь. Траектории оценок стандартного отклонения монотонны по параметру , что наблюдалось нами и ранееи предсказано теоретически. Однако в тех случаях, когда кратно размерности , более явновыражена разница между траекториями, определяемыми параметрами − 1 и .
Так, например,для размерности = 3 разница между траекториями „Qint_6“ и „Qint_7“ примерно такая же,как для пары „Qint_7“ и „Qint_8“, но примерно в два раза меньше, чем для „Qint_8“ и „Qint_9“.64Оценка стандартного отклонения2-3МетодMCQint_0Qint_1Qint_2Qint_3Qint_4Qint_5Qint_6Qint_7Qint_8Qint_9Qint_10Qint_11Qint_12Qint_13Qint_14Best Qint2-42-52-62-72-82829210211212213214Количество вычислений подынтегральной функции215216Рисунок 2.4: Произведение кубических полиномов, = 15, без внешних повторовТо же самое справедливо и для других наборов параметров и других размерностей, поэтомутраектории разделяются на характерные группы по траекторий в каждой.Обратимся к случаю высокой размерности: иллюстрации 2.9 и 2.10 соответствуют = 20без внешних повторов и с внешними повторами, соответственно.
Известно, что для высокихразмерностей и гладких функций, таких как 2 , квази-Монте-Карло демонстрирует очень хорошие результаты по сравнению с наивным Монте-Карло. Именно такую ситуацию мы можемнаблюдать на иллюстрации 2.10.В этом свете неудивительно то, что улучшение метода Qint по сравнению с Монте-Карлоне выглядит значительным. Отметим ещё и следующее обстоятельство: гладкие функции, какправило, плохо приближаются рядами Хаара. Это означает, что остаток ряда Хаара убываетнедостаточно быстро, чтобы улучшить порядок сходимости Qint на сколь угодно значимую величину, которая была бы видна в экспериментальных условиях.
Впрочем, это не отменяет тогофакта, что константа сходимости всё равно улучшена (траектория „Best Qint“ расположена существенно ниже траектории Монте-Карло).2.5.3Функция „Морокофф-Кафлиш №1“Тестовая функция 3 является классической для численных экспериментов в области квазиМонте-Карло. Она взята из работы Морокоффа У. и Кафлиша Р. [64] и определяется как652-3Оценка стандартного отклонения2-4МетодMCQint_0Qint_1Qint_2Qint_3Qint_4Qint_5Qint_6Qint_7Qint_8Qint_9Qint_10Best QintRQMC2-52-62-72-82-92829210211212213214Количество вычислений подынтегральной функции215216Рисунок 2.5: Произведение кубических полиномов, = 15, 16 внешних повторов(︂)︂ 11 ∏︁3 () = 1 +( ) .
=1(2.39)Функция уже нормирована таким образом, чтобы значение интеграла было равно единице:3 = 1.В размерности = 1 (иллюстрация 2.11) результат вычислений очень похож на случай рассматриваемой(︁ ранее)︁ функции 1 . В частности, порядок сходимости стандартного отклоненияблизок к 13/2 , присутствует ярко выраженная монотонность по .Для случая = 2 (иллюстрация 2.12) сходимость Qint такая же, как и у квази-Монте-Карло,и присутствует группировка траекторий по парам. В этом смысле результат для 3 объединяет всебе характерные особенности Qint, наблюдаемые ранее для 1 и 2 .В высоких размерностях, таких как = 30 (иллюстрации 2.13, 2.14), разница в сходимостидля траекторий „Best Qint“ и наивного Монте-Карло экспериментально обнаруживается только вконстанте.
Она наверняка присутствует и в порядке сходимости, но подтвердить это в масштабахпроводимых вычислений не представляется возможным.662-82-9МетодMCQint_0Qint_1Qint_2Qint_3Qint_4Qint_5Qint_6Qint_7Qint_8Qint_9Qint_10Qint_11Qint_12Qint_13Qint_14Best QintОценка стандартного отклонения2-102-112-122-132-142-152-162-172-182829210211212213214Количество вычислений подынтегральной функции215216Рисунок 2.6: Плотность нормального распределения, = 2, без внешних повторов2.5.4Кусочно-линейная функцияПоследней тестовой функцией рассмотрим кусочно-линейную функцию 4 :4 () =∏︁ℎ ( ),(2.40)=1гдеℎ () = 2 ·⎧⎪⎪0,⎪⎪⎨10+⎪⎪⎪⎪⎩1, 6 0.5 − , − 5 , ∈ (0.5 − , 0.5 + ],(2.41) > 0.5 + ,а для каждого = 1, . . . , определены постоянные =.2+10Они подобраны таким образом,чтобы значение интеграла было равно его размерности: 4 = . Функции ℎ () устроены так,что при малых они близки к одномерной первой функции Хаара 1 (), а при больших – клинейной функции () = .Для малых размерностей ( = 3, иллюстрация 2.15, и = 5, иллюстрация 2.16) мы обнаруживаем некий новый эффект, происходящий при = .
Скачки в константе сходимости мыотмечали и ранее (например, для плотности нормального распределения), но здесь подобное явление имеет резко выраженный характер. За счёт такого сильного скачка траектория „Best Qint“претерпевает в определённый момент ускоренную сходимость, и, хотя эта сходимость выдержи-672-8Оценка стандартного отклонения2-9МетодMCQint_0Qint_1Qint_2Qint_3Qint_4Qint_5Qint_6Qint_7Qint_8Qint_9Qint_10Qint_11Qint_12Qint_13Qint_14Best Qint2-102-112-122-132-142-152829210211212213214Количество вычислений подынтегральной функции215216Рисунок 2.7: Плотность нормального распределения, = 3, без внешних повтороввается лишь на коротком промежутке, она приближается к сходимости квази-Монте-Карло, а вразмерностях = 3 и менее и превосходит последнюю.Описанное свойство, по-видимому, специфично для выбранного метода разбиения гиперкуба.В самом деле, при использовании правила бинарного рассечения в момент = разбиение наподмножества X1 , .
. . , X впервые задействует все имеющиеся размерности2 .Подобная картина сохраняется и для достаточно высоких размерностей. Так, результаты для = 10 представлены иллюстрациями 2.17 и 2.18. Описываемый эффект скачка хорошо наблюдается для траектории „Qint_10“, но он уже не так явно выражен. Это происходит отчасти потому,что сказывается увеличение размерности, как мы уже отмечали для предыдущих примеров; отчасти потому, что функции ℎ () при растущем всё хуже приближаются функциями Хаара.2.5.5Выводы о практическом применении QintПодведём итоги численных экспериментов и сформулируем некоторое общие выводы о предложенном методе и его конкретной реализации.– В ходе вычислений проверены и подтверждены все предсказанные теоретические свойства,а именно:2Напомним, что при = 1 рассечение проводится только по первой координате, при = 2 – по второй, и такдалее, то есть все размерностей исчерпываются при = .682-8МетодMCQint_0Qint_1Qint_2Qint_3Qint_4Qint_5Qint_6Qint_7Qint_8Qint_9Qint_10Qint_11Qint_12Qint_13Qint_14Best QintОценка стандартного отклонения2-92-102-112-122-132-142829210211212213214Количество вычислений подынтегральной функции215216Рисунок 2.8: Плотность нормального распределения, = 4, без внешних повторов– Дисперсия Qint не превосходит дисперсии наивного Монте-Карло, совпадая с ней вслучае = 0.– По количеству повторов (при фиксированном ) скорость убывания дисперсии рав(︀ )︀на 1 , то есть имеет такой же порядок, как и метод Монте-Карло.
Константа сходимости монотонно убывает по .– По количеству разбиений (при фиксированном ) скорость убывания дисперсиизависит от скорости сходимости ряда Фурье-Хаара, но эта скорость всегда быстрее,чем у Монте-Карло.– Для низких размерностей ( 6 3) скорость сходимости достигает (︁1 3/2)︁, что быстрее посравнению со стандартным квази-Монте-Карло. Преимущество по сравнению с наивнымМонте-Карло явно выражено.– Для высоких размерностей ( > 10) определить улучшение порядка затруднительно, нов некоторых случаях скорость сходимости близка к квази-Монте-Карло. Преимуществопо сравнению с наивным Монте-Карло не такое существенное, но присутствует во всехрассматриваемых случаях.– Правило бинарного рассечения хорошо подходит в качестве универсального способа разбиения гиперкуба.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
