Н.С. Бахвалов, Н.П. Жидков, Г.М. Кобельков - Численные методы (djvu) (1160088), страница 43
Текст из файла (страница 43)
Для ряда класи«в функций зта оценка пог1ивпносги на классе папки»ко плоха, что не дает никакой надежды на получение приближенного значения интеграла с требуемой точи«к:тью. Например, согласно теоремам из ! 7, не существует методов с оценкой погрешности на классе функций Ск д(А, ., А), лучшей, чем «!А)у Н' !здесь з - кратность вычисляел«ого интеграла). Предположим, что требуегся гарантирована оценку погрешности, меньшую чем 0,01АА. Тогда число узлов !«' должно удовлшв«>рмть неравенству дА1«' Н' < 0,0!АА, т.е. должно выполняться неравенство !«' > !00'. Поскольку вычисление каждого значения подыптогралыюй функции требует обычно болыпого числа арифметических операций, уже при з = 6 *гм«ое тр«бование иа число узлов оказывается практически невыполнимым. Мы оказались в положении, когда ва основе указалной выше оценки погрешив«ти пег возможности вычнсл~ггь значение интеграла с гарантированной оценкой погрешкости 0,01«)А, поскольку это потребует непомерных затрат времени ЭВМ.
Один из способов разрешении создавшегося противоречия состоит в более детальном описании клинов подьштегральных функций. Другим выходом из создавп«ейск обстановки является отказ от получения ст!югой «арантироваииой оценки погрешности и получение оценки погрешности лишь с определенной степенью достовернскти. В частности, при конструировании методов интегрирования в гл'. 3 и в 'З' 7 мы шли по пути отказа от строгой оценки погрешности: погрешность оценивалась через разность результатов вычисления приближенного значения интеграла при различных методах интегрирования.
Одним из метсщов приближенного вычисления значений игнегрюгов, при ксгором погрешность оценивается не гарантированно, а лишь с некоторой степенью достоверности, являешя мешод Монте-Карло. Пусть требуется вычислить приближенное значение интеграла 233 1 3. Метод Монте-Карло М(е ) — у(Р) гР— 1(1) гп .0(е!) = ггг(в ) — (М(е!)) = ы(!), П(Д =- 1((з) — (1() ))'. где Положим АУ) = у~ г=! Вследствие указанных свойств величин в имеем а' ун (Ви(1)) = — Яву(е ) = 1((), г=! С вероятностью 1 — Ч выполняеыя нераеенстно (неравенство Чгбмшсеа) Жну) — 1(,г)~ < Юя)(ЧМ. (1) Полагая й = 0,01, получаем: с вероятностью 99Ус выполняется неравен- сгво ~Я,У) — 1(1)) < 1бчУЪУУУ.
Еще лучшая оценка получается в предположении, чю точки Р не только попарно нщависимы, ио и независимы в совокупности. Тогда, согласно центральной предельной теореме, случайная ы.личина Фи у) — у(1))/~Г(у(у) Р' распределена асимптстически нормально с функцией распределения б(д) = — / р~ — '— ) бЕ. Для упрощения выкладок предполыаем, что д(С) — мера области С равна 1. Как правило, зто условие бывает выполнено, поскольку прн практической реализации метода Монте-Карло область интегрирования обычно преобразуется в единичный куб. Предположим, что каким-то образом удалось получить И случайных попарно независимых точек Р!,..., Рг!, равномерно распределенных в С.
Далее через М(в) будем обозначать математическое ожидание случайной величины в, а !срез С(в) — ее дисперсию. Случайные величины е =)(Р) попарно независимы и олинаково распределены, причем Глава 5. Многомерные задачи 234 Вероятность того, что случайная величина с такой функцией распределения не превосходит по модулю значение и > О, асимптосически равна о»2 Г' ( сз) ре(9) = 1 — — / ехр~ — — ) сй.
»Уку» ( 2 ) Таким образом, при больших Я с вероятностью, близкой к ре(р), вы- пслняетси неравенство (бл(У) — 1(У)( < и»/РОУ~ Пола»ни р .= 3 и 9 = 5, получаем, что неравенства )9л()) — 1(У)) < З,IР(У))Д» и !Яа(1) — У(У)! < Ь,/Р[ЙТЯ Задача 1. Показать, что Р()) = ~,-И(.;٠— Ы„У)) . (2) Поскольку ва ссновании:якова болыпих чисел с болыпай веровтностьк» вы- пслнветсл приближенное равенства то с бсльвюй вероятностью выполняется и приближенное равевопю Р(() жР1" ~(с), где Р1л»( у) = ~ , ~ (з,(д - б ( у)) . Приведем схему применении метода Монте-Карло при р(Р) = 1.
Пусть (1 — О)— уровевь иакежисош, с которым»келательно получить прибли»кеиисе значение интеграла, е — заданная точность. Опр»деллют и из равеншва выполняются соответственно с вероятностями 0,997 и 0,99999. Сформулированные выше утверждения назывюогся иногда правилами трех сигм» и «пятв сигм» соответственно. В правой части всех этих оценок стоит неизвестная величина РП" ) = 1((з) — (1(())з, которую можно оден»ггь на основании информации о вычисленных значениях )(Гу). 1 8. Метсд Моите-Карло Последовательна при я = 1,... получают случайные тачки Р„и вычисляю г величины «„(«), Яв(у], !«„(П, Р ((), пользуясь рекуррентными соопюшениял«я «„()) = «„ г(«) + «(Р„), Яв(«] = « ((]«я, й„(П =й„«(У]+ " (У(рь] — Е„(П), П„П) =й„(П«(п- Ц, а также вычисляют значение Л.=уч«КУУ . Начальные условия рекурсии: «л()) = бл(П = ((Р«], йг~) = «зг(«] =й Если оказалось, что Л < е, то вычисления прекращакнся; полагают 1(П ю Бл( П и считают, что с вероятностью 1 — З выпалняг!«я неравенство )1(У] — Бл(У«( < с.
Заметим, чта в действюельнастн неравенство ~1(Д вЂ” Ян(«')) < е выполняется с вероятностью, веск«юька меньшей чем 1 — З, хати и близкой к ней. Задача уь Проверить, что П„(у) = П("](«"). Для уменьшения погрешности метода Монте-Карло случайные узлы интегрирования берутся распределенвыии не равномерно, а с некщарай влопвютыа р(Р) и 1, / р(Р]««Р = 1. В этом случае пола«шат «с а 1(«) = У (() = — ~ У(Р«]«р(Р). л=.! Задача 3. Показать, что (г((бнЯ) = 1(Х), П(Х) = УУ'lр) — (1У))'.
Убедиться в том, что переход к такому выбору случайных величин осо- бенно целгхообрвзен в случае )(Рл(р(Р) = гапз«. Часто в руководствах по использованию метода Монте-Карло говорится слевующе:. Метод Монте-Карло явлиется универсальным методом вычислевия интегралов высокой кратности. Порядок оценки скорости сходи- масти метцла Монте-Карло «ють О(1«ь««!) н нг зависит ст размерности интеграла, в то время как порядок «арантированных оценок скорости схадвмгюти существенно ухудгпается с рея«гам размерности.
Для метода Монте-Карло при кэлгдрм и имеетси эффективная оценка пагрешносп! через величину ь«й„(у)«п, и, таким образом, вычисления прекращаются именно в тот момент, когда досппнута требуемая точность. Отнесемся осторожно к этому заавлению и рвсамотрим различные сосбражения езаь и епротивь метода Монте-Карло. 23б Глава 5. Многомерные зв,аачи В 9. Обсуждение правомерности использования недетерминированных методов решения задач Часть пользователей предубеждена против метода Монте-Карпо и отрицает правомерность его использования, поскольку ь>алость погрешности метода обеспечш>ветен лишь с иек»горо» вероятностью. Выше мы уже обрисовали картину, складыеыошуккя при вычислении интегралов большой кратности, как почти полностыо бшн>щежную н саучаг если стави>ся цель получения приближенноп> значения интеграла г гарантированно малой оценкой погрепшости. Такая обстановка и вызвала к жп>ни применение метода Монте-Карло.
Уже при пычислении однократных шпегралов п>раития малости погрешности меюда может быгь получена только прн использовании строгих теоретических оценок. Применение таких оценок требует высокой математической квалификацив исследователи, затрат еп> умственно>о труда и пе может быть перепоручена ЭВМ. Таким образом, ориентировка ла методы вычисления интегралов с >враптпрованпой оценков погреппюсти противоречит общей тенденции исполкювэлня ЭВМ.
Кроме того, при решении всякой задачи вози>ожны ошибки е постановке задачи, в программе и т.д. В силу этих и ряда других причин редко можно дат>, стопроцентную гарантия> малости погрешности результата расчета по отношению к реальной модели; иекоюрав вероятность ошибочности результатов вычислений ил>естся в лк>бол> случае. Вге >то подч> ркиваш; что лапь>й отказ от метода Моиг> Карло тол>,ко из-за ого ясроятностной природ>л является нсоправданпыь>. С другой стороны, при использовании метода Монн>-Карло нужно учитывать следую>пие отрицатальнь>е эффекты. Для применения ыетода Монте-Карло необходимо иметь в распоряжении пшюсдовательност>, о>пависиыых точек Р с заданным законом распределения. Обычно пользователь расшшвгает датчиками случайных или так называемых псевдослучайных чисел, которые выдыот последовательности случайных чисел, равномерно раслределеелых па отрезке ~0, Ц.
При помощи преобразований таких случайных величии получаемся случайные чи>ла с заданным законом распределения. Па первых ЭВМ датчиками случайных чисел были некоторые приборы, например использующие явление радиоактивного распада, которые выцввали послеповатгльности случайных величин, иногда даже удовлетворяющие требованию независимости в пнюкупности. Однако такие приборы рвботвлл ; малой скоростью, и поэтому с увеличением производительности ЭВМ эт них отказались. Вместо датчиков случайных чисел используют датчпки псевдослучайных чисел — некоюрые программы, выдыощие последо>ательности чисен, которые рекомендуется рассматривать как ш>учайные.
Использование датчиков псевдослучайных чисел явилось прогрессивным 19. Обсуждение правомерности испольэовали» методов шагом, позволившим широко применять вероятностные методы. Однако при использовании зтнх датчиков нужно всегда иыеть в виду, квкиыи свойствами обладают последовательности чисел, выдаваемые этими датчиками. Например, некоторые датчики псевдослучайных чисел вырабатывают пскледовательности чисел, которые можно рассматривать лишь как попарно независимые, а не квк независимые в совокупности.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
