Н.С. Бахвалов, Н.П. Жидков, Г.М. Кобельков - Численные методы (djvu) (1160088), страница 44
Текст из файла (страница 44)
В этом случае будет неправомерно пользоваться оценками погрешности, основанными на центральной предельной теорема. Пусть методоы Манто Карло вычисляется интеграл г' г' ГЯ = / / )(зс хв) с(хс йл„ о о Прелшсожим, что в качестве узлов интегрирования мы хотим выбрать последовательность независимых равномерно распределенных точек единичного куба. Если датчик псевдослучайных чисел выдает последовапшьность бс,...
чисел, равномеряо распределенных иа отршке [О, Ц, то можно попытатьск в качестве узнав интегрирования взять зонги (бс,..., с,), (зсес .: (зс),...- Дсся законности применения неравенства Чебышева нужно выполнение прелположення о независимости распределения любых точек Пм т.е.
ншависиьсости распределения соеокушнх тей Ы(1-с)вес* 4г.) К(*- с)'с»" 6..). При увеличении з зто ушювие нвклэ,вывает все более жесткие требования иа датчики псевдослучайных чисел. Известно много реальных приме(юэ неудачного применения метода Монте-Карло в случае болыпих в. вызнаиных следующей причиной.
При использонысии метода в оценке погрешности делались допущения о знх или иных статистических снойствах псендослучайных чисел, в то время кшс зти предположении на самоы деле ве выполнялись. В результате делался вывод о малости знюсения погрешности, который на самом деле не был справедлив. Такиы образом, опасность применения лютада Монте-Карло заклсочается по большей чести не в вероятностном характере оценки погрешности, а в том, что вероятностная оПенка погрешности производятся зачастую в предположении о свойствах датчиков случайных чисел, кссгорые на самом деле не имеют места.
Зцдача 1. Пусть бс, бз — случайные независимые величины, равномерно распределенные на отрезке [О, Ц. Пусть (р) — дробная доля числа р, т.е. (у) = р — [у), где [р) — целая часть р. Положим б„= ((с + (и — 1)((з — бз)). Показать, что точки б попарно независимы, равномерно распределены на [О, Ц и, согласно построениям предыдущего параграфа, гс 1 1()) =-у) )(я)Из=В,()) = — )')((1). Пива 5. Миан|мерные задачи 233 Зада |а 2. Пусть вычисляется двукратный интеграл г' г' 1(2) = / / 1 (И1, я2) з1|1т2. е е Показать, что при Р„=- (бхв |,бз„), где бь ич задачи 1, справедпиво соотношение лх(ьл(2')) = 1(2).
Вычислить ,1-„О(В (Л) = 4(Л и убелиться, что, как правило, н(Х) ~ 0 и поэтому Ял(Д далеко от 1(2'). Задача 3. Пусть вычисляется трехкратный интеграл 21г' 1 1(() = / / 1(х1, кз, хз)|йс1|1хз|Ьз. При Р = (бзл 2, (2 . 1, бз„) вычислить М(Яь(1)] =- 1(1) и убеяитьсл, что, как правило, 1(() ф 1(Я) и псе|о||у 8л(() далеко от 1(1). Указонне.
Воспользовагьса тем, что (бз„, — 2бз„1+бзв. 2) —.Целое в пРе- делах ( — 1, 1). Пусть ф..., 2~', й = 1,..., 1 — случайные нелависимые в совокупности равномерно распределенные на (О, 1) случайные величины и Рь| = (б11,..., бе), й = 1,..., 1. Положим (Г = (бг+С1, 1Ьб1'+ ° +Сс '1211 здесь (р) = у — (р] — дробная часть числа р, Ьеб/1. = бсш — С|бе-1---. + ( — 1)2Ссебз — конечная разность д-го порядка, Сч — число сочетаний нз д по р, равное нулю при р ) 4.
Пусть Р„= (б~,..., б;). Задача 4. Проверить, что Ре Зада|а 5. Показат|ь что точки Р|,..., Рл равномерно распределены в единичном кубе и |побые 1 из ннх независимы в совокупносчш К числу достоинств мстцца Монте-Карло относят нжависимость порядка оценки от размераооги вычисляемого интеграла. Однако рассуждая только о порцпке сходимости метода, можно не заметить следуюшую немаловажную деталь. Мы получали оценки погрешности приближенного значения интеграла вида )3 (У)- (У))< .,УП(У)У . 230 з 10. Ускорение сюлнмосш метола Моим-Карло Типичным для практики является требование малости югносипльной погрешности приближенною значения интегпалга, что в данном случае означает требование малости величины з/Р(/)/(]1(/)(х/Ф].
Статистика реально предьявляемых к вычислению интегралов показыгнст, что величина, гР(/)/]1(/)] имеет тенденцию к резколгу росту с ростом размерности интегралов. В кж~естве иллюстрации приведем интеграл г' г' 1(/.)= / " / . ~(-32(' "..'])д* -"д'в, в е для которого,,/Р(/„]/(1(/,]( > 10ет — 1. Следовапльно, практическая трудоемкость метода Монте-Карло существ~иле возрастапг с ростом размерности интегралов (при одинаковой относитжльной погрешности).
При действительном вычислении многократных интегралов ыстодом Монте-Карло перед непосредственным применением метода за|астую с целью уменьшения величины ь/Р(/)/]1(/)~ проводится довольно кропотливое исследование свойств подьштвгральной функции, преобразование интегралов с помощью замен переменных н других приемов, требующие достаточно высокой квалификации исследоватюгя. 3 10. Ъ'скореиие сходимости метода Монте-Карло Рассмотрнм некоторые приемы повышения практической эффективности метода Мовте-Карло. 1.
Функция /(Р) представляется в виде /(Р) = Р(Р] -~- д(Р), где функция Р(Р) интегрирупггл явно и содержит в себе вгз резко меняющиеся компоненты /(Р), а д(Р) плавно меняющаяся функция с неболыпой дисперсией Р(д). Игюгда область интегрирования разбивается па малые подобласти и в каждой чжти в качестве Р(Р) берут некоторый интерполяционный полипом с узлами в этой подобласти.
2. Подходящий подбор плотности распределения узлов р(Р) (см. залачу 3 в З 8) также приводит к уменьшению дисперсии. Мы рассматривали случай, когда все узлы Р имеют одинаковую функцию распределени» р(Р). В ряде случаев окаюаваепм целесообразным выбирать узлы интегрирования твким образом, чтобы каждый имел своею функцию распределения р (Р). 3. Следугощий прием является частным случаем приемов 1 и 2. Исходный интеграл представляется в виде суммы интегралов 1(/) /(Р] бР ), й(/),Ю) /(Р] дР зс г=г тс, Глава 5.
Многомерные задачи число узлов интегрировании дл предстаюляетс» в виде дл = длл-~" .+Фю и каждый интеграл ул() ) вычисляетгя по методу Монте-Карло с лллл узлами интегрирования. Обратимся к случаю вычисления интвграла от функции, лшобрвженной на рис. 5.10.1. При непосред- 1,5 отвеинам вычислении исходною интеграла в случае р(Р) = 1 имеем П()') = 1/4. Если Сл = (О, 1/2), бз = [1лл2, Ц, 'ю при лвлбых л"ллл, л"лз Ф 0 оба интеграла Щ), а следова. тельно, н исходный интеграл будут вычислены точно. Конечно, случай, когда исходную область интегрирования удаегс» разбить на части, где глцлынюгральная функция постоянна, очень редкий.
Однако, если все-таки удается разбить ее па части, где функция меняется мало, то можно получить существенное увеличение точности при том же объеме вычислений. 0,5 Рис. 5.10.1 Разбиение области ннтагрировання на части с целью уменьшения дисперсии метода Моиза-Карло шщюко вспальзуегся, в частшнтн, прн обработке есгественво-научной инфорллапин. Пусть требуется аиредезкгь водасадержанне снега в бассейне некоторой реки. Прн непосредственном применении метода Монте-Карло выбиралось бы с равномерной плотваетью распредевения несколько тачек, где пронзвалилась бы измерение количества вадасодлржания на единице поверхвости. Учасгки поверхности г. однородными природными условиями (высота нвд уровнем моря, уровень абла.лвости, звлеснепнасть, ориентация склонов юр, оллвки, юспспствующее направление ветра) хараклерлшулотся примерно одинаковым водлксдержавием.
Поэтому удввтсв дсбилъся сушесгммнаго повышения тачлкнчи, разбивая бзссейв на части с однарадвымв условиям» и применяя метал Монте-Карло для вычисления интегралов по зтим чшчяль В случае гладкой подынтегральной функции разбиение области интегрирования на части приводит к увеличению порядка скорости сходимости. Пусть вычислпегся интеграл гл г! 1(() = / / ~(хл хв) Ихл дх, а а Положим л"лс = и' и разобьем исходную область интегрирования на равные кубы Пв, я, . (пл — 1)/и < хл < ллл/и,..., (п„— 1л)лл < х, < лл,/и.
В шлждом кубе выберем случайную точку Ра, а,. Считаем, что ее плотность распределения — постоянная, равная и', и случайные точки в любых двух кубах вьлбираюгся нсзлависиьло. Положим 8л(у) = „—, ~ У(Р.л..., .). 1 110. Ускорение оюднмостн метсла Монте-Карла 241 Звднча 1. Доказать, что |З(3а (У)) < .0(Ян(У)) = тз(У)У)т. Провезем оценку дисперсии в предположении, что функция У(Р) удою|отворяет условию Лнгвпица с пост|инной А по каждой нз переменных. Спранедливо равенство П(Ун(У)) = ~ П ~ †,У(рю,,оь)) = ~ — ~(у(рю „ )) („) /1 и,...,а.=| Имеем равонстно М(У(рю....ю)) =и о..., . = и'у(р)АР.
у Ото На основании теоремы о среднем имы'.м п|н „=- у (р|ч Р,,...,„„б П|ч е„понто||у М(У(р,, лн))=У(Рн ои). В то же время у'[з| .|- Ьн..., тч -~- Ь,) — у(зо,..., х|) = = (У(х| й й|м..., х, й Л ) — Дх, + А|н..., з:„| -р бг„, |, х )) -|- + (у(х| + гам ...,т, | + зз, .и з:„) — у(х| + б|м ...,х, е + СГ -з |с — | х )) ~ '' + (у(х| 1 Ьс хз ° .. х ) у(:с| .. .'с )). Отсюда гледует, что длн функций рассматриваемого класса (У(в| + б|м..., ху ~- 1 ) — У(хп..., х)~ < А()Ь|(+ .-~-)А|)).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
