Соболь И.М. Численные методы Монте-Карло (1973) (1186217), страница 22
Текст из файла (страница 22)
(17) гл. !), а х — это функция распределения г'(х) случайной величины Т (при 0(х(1). Поэтому, согласно (18) гл. 1, (! — ~![5л (х) —,Чх)ог(х~ = [~ [Рх — Р1 г[Р(х)) =ф~ "о о !4з формулы (46), используя неравенство (! ) '(стр. 292) и условие (44), выводим, что если !(х)ен ее)У 2((), то ! 6 (7) ! ( — „~ ! Г ! ! 5л — й!! ! б! ( — ~ ~ ! 5 — Л'! !' г(! о о ф и иитаггллы, зависящие от плгхметех 129 Из теоремы предыдущего пункта вытекает, что для простейшего метода Моите-!(арле (47) впр ) б (~) ( = 7. ~/гонт) ЬГ.
(48) тм!гз(/.) Из оценки (49) следует, что при достаточно большом Л! с вероятностшо, приблизительно равной р, неравенство ~б())! ~~У'ха7Л! справедливо одноврел!енно для всех $!7нк!(ий Г" (х) еп ~ (р'т(й). Обратимся к иптересу!ошему иас случаю, когда вычисляется интеграл вида (40) ! 7(Х) = Г7(х,)) Д. (50) о с помощью оценки вида (4!) Е ().) =+~ )(У!,хр ! ! (51) Из предыдущего результата вытекает, что если при всех а(), .Ь производная )„(х, к)еп(т, то с веро!ппостыо, пе меньшей чем р, при всех этих Х одновременно ) йн (й) — /(Х) ) (й (Х) ф"х~фЖ, где, очевидно, (1 )иб Е (Х) = 11 К (х, к)1 !( ) 9 И.
М. Соболь Воспользуемся теоремой Мизеса — Смирнова, приведенной на стр. 34: если йГ достаточно велико, то Р(ый( (х) а!(х). Следовательно, можно выбрать любую доверительную вероятность р найти соответствующий ей корень х=хв уравнения а!(хв) =(! и утверждать, что с вероятностью, приблизительно равной (1, ьпр (б())( =йУх!!7йг. (49) тм!ко!с! ВЫЧИСЛЕНИЕ ИНТЕГРАЛОВ 1ГЛ. 3 4А. Численное днфференцированне оценка (51). Рассмотрнм слу.
чай, когда сушествует производная Д(Х) от интеграла (50), и дока. жем, что по значениям Ол(А) можно обычным способом эту произ. водную оценить: е„(А+ л) -е„(А-л) д (х) Допустим, что при а(Х(Ь сушествуют вторые производные )зх(х, Л) а 5з н ~ )ьх (х, Х) ~ < С. Тогда 1 У (Ц=) (,'(х,Цбх, э 'а оценка (41) для этого интеграла равна производной от оценки (51)1 1 Е,'„(А)--~-ч', )х'(Т,,А). з ! На основания (49) можно утверждать (мы по-прежнему считаем, что Ж достаточно велико), что с вероятностью, не меньшей чем 5, одновременно справедливы н неравенство (52), я неравенство ~ Ем ()) т~ (Х) ~ «я (ч (Х))ггх~~Ф (53) где 11 1из 5з(А)=~~[ 1А,(х А)1'ох) о Далее, в силу сделанных предположений, прн любых фиксированных значениях уз,..., ум функция (5!) дважды дифференцнруема по Х.
Из разложения е„(А+ л) = е„(А) + ле,' р) + (112) л е"„(Ал) вытекает, что е ()г+ л) — е, ()г — л), ) ! 2л ем(А)!< 2 Наконец, нз (53) и (54) саедует, что Е,„( +Л)-Е,„(А-Л) ) .И/хр 1 (Х)! ~ Ь (Х) т У + 2 Сл н это неравенство, одновременно, с (52) н (53), имеет место с вероятностью, не меньшей чем 5. В этих условиях, по-видимому, целесообразно выбирать Л порядка 1/УУ. (з( упражнения к гл. э 4.5.
О таблицах случайных чисел. Оценка (49) в какой-то степени оправдывает многократное использование таблиц случайных чисел, ибо по одним и тем же числам («по таблице») можно решать много за- у дач: вычислять интегралы от любых функций ((х), принадлежащих Иго (1.). Оценку, аналогичную (49), можно получить для гораздо более широкого класса задач, включающих вычисление интегралов от функций многих переменных.
Однако для у л; г~ хл г х всех функций )(х) из оценка погрешности тако- Рис. 45. го типа невозможна. В самом деле, каковы бы ни были точки хь ..., хм, найдется функции 1(х) (рис. 45) такая, что а) 1(хт) = 1(хт) = ° ° =1(хго) = О; ! б) )1(х)бх Š— е, где й)а)0 — жобые числа; 'о 1 в) ) 1'(х) г(х < Са. о Для такой функции, очевидно, б(1) =Ь вЂ” е. Следовательно, при любых хь .. хн ацр )5(1)(ь 5, у~не н величина эта не стремится к нулю, когда йГ- со.
Упражнения к главе 3 1. Записать формулы для расчета методом Монте-Карло интег- рала 1 = ф 1 (х, у, а) пх Ну йх (55) от прпнэвольной ограниченной функции 1(х, у, х). Область интегри- рования С определена неравенствами хо+у'Сх(2. вэ 132 (гл з ВЫЧ!!СЛЕПНЕ !!НТЕГРАЛОВ 2.
Требуется вычислить интеграл (55) от произвольной ограниченной функции !'(х, д, х) по области Сг, расположенной между Рис. 46. хз(ха У) г!(ха,ф ! ! Я+ Уг(ха! У Рис. 47. плоскостями х=х, и х=хз (рис. 45); сечение б плоскостью х хю изображено на рис. 47. случайные точки()! = (еь, ю)1, ь!) в области О будем выбирать по формулам 51= х + Т!(хю — х,), Ч! =р ($,)+у;[рю(й!) — р (з!)) 1! = хз (й!. т)!) + Т! (ха (й!. 1)!) — хз (й! т)!)!. упРлжнения к Гл. 3 Можно ли в качестве оценки для / использовать среднее арифметн. ческое м ч Х /(%)у Если нет, то написать верную оценку, содержащую значения /(() ),, /(Ом).
3. Построить оценку с конечной дисперсией для вычисления интеграла х — 5)2/(х) !(х о в случае, когда /(х) х при х-ьое и /(х) хз при х-ь'О, 4. Эапнсать формулы для расчета интеграла ОО ! [ /(х)е ~хлх, Ь > О, о с помощью значений случайной величины $, плотность которой рав. на р(х) = ае ох. Доказать, что если /(х) = Ахч,то диспеосяя будет наименьшей при ажао=»/(л+1).
6. Условно сходящийся интеграл 1 = ) х ' з1 п 2нх !(в ! можно вычислить методом Монте-Карло с помощью оценки а) В,о — — ~ ~~ Ь (у!) з!п иу! 1=1 где Ь (х) = ~~', [(2Ь + х) (2» + 1 + х)) »=1 Доказать, что М[Ь(у) з!и ну) =/, )У[Ь(у) з!п ну[ < (!/2)Ь'(О) — /!. 6. Рассмотреть симметризацни функции /(х) = аз+ ~~,' [ а» соз 2яйх+ Ь» а1п 2нйх) »=1 на интервале О(х(1 и выразить дисперсии Щ(у), ()/1~) (у) и ()/!з) (у) через коэффициенты Фурье а» и Ь».
7. Рассмотреть функцию /!з) (х) = (1/2) [/(х)л)+/(1 — х/2)) и доказать, что хотя, вообще говори, /! ) (х) Ф/!1) (х) (где /! )(х) = !3) (1) !!) (1/2) [/(х)+/(1 — х)[), но по отношению к простейшему методу Монте-Карло зги функции равносильны: М;!з) ( ) М/!П ( ) М/ (,) ()/!з) ( ) ()/!!)( у) Вычисление интегуллОВ (Гл. 3 8. Требуется вычислить интеграл (1й) ат функции ((Р) !ИЕ» (О' р) ПУсть ЯЛ(Р), ..., !Рз(Р) — оРтоиоРмьРованные фУикции со СРедними значениями, равными нул!о, т. е.
) !р (Р) (р» (Р) р (Р) !(Р = 6,» ~гр) (Р) р (Р) !(Р = О. С С Рассмотрим семейство оценок для l где 9! — независимые случайные точки с плотностью р(Р), а ест,..., а, параметры, Доказать, что дисперсия этой оценки минимальна тогда, когда ц» ) )(Р) !р»!'Р) р(Р) !(Р. с 9. Случайная величина э» подчиняется биномиальноэяу распрел — ! делению: Р р» — — 1) = С!, Р» (1 — р») ", / О, 1,..., л». Случайные величины ч!... чз независимы.
Требуется вычислить мате. магическое ожидание ограи!!ченной величины т)=г(т!, ..., чз), которое равно МЦ= ~ЧР ~) ()з,.... ),) Р (т! = )!) ... Р(т~з /,), („...Л =0 '"" з Если все л» 1О и зяк 20, то количество слагаемых в этой сумме ! 1О". Ясно, что на современных ЭВМ такая сумма вычислена быть не может.
Построить простейший метод Монте-Карло для расчета Мз) и какой. нибудь алгоритм, соответствующий этому методу. ГЛАВА 4 ВЫЧИСЛЕНИЕ ИНТЕГРАЛОВ (СЛОЖНЫЕ ОЦЕНКИ) ф 1. Методы Монте-Карло с повышенной скоростью сходилюсти 1.!. Выборка по группам. Этот хорошо известный в статистике прием (124), стр. 218) может быть с успехом использован для уменьшения дисперсии. По идее он весьма близок к методу существенной выборки: здесь также предлагается выбнрать больше точек в более «существенных» областях, однако выбор регулируется не специальной плотностью, а указанием количества точек в различных областях. Итак, пусть требуется вычислить интеграл У=~АР) р(Р) (Р. а Разобьем область интегрирования О на т частей б= 6~+...+6„ и введем обозначения ру= ) р(Р)ЙР, 1~ — — )1(Р) р(Р)г(Р.
а а. Очевидно, 'р,+..;+р.= 1, 1,+...+1.=У, В области б, рассмотрим случайную точку ЯШ с плотностью р(Р) ~р, и для оценки у, воспользуемся 1Зб Вычислгние интегралов (сложные оценки! (Гл 4 простейшим методом Монте-Карло: так как у,=м1МИ»)], то, выбрав Л( независимых реализаций 9,..., (')н. (л (и ( точки яо! можем записать оценку для ),: Р ! в, =ф~ ~()("). Складывая такие оценки для всех ун получим новую не- смещенную оценку О* = Х Р( Х 1( и!) (=! / з=! Общее количество случайных точек в формуле (2) обозначим по-прежнему через (н': У=У(+с ..+)Ч„.
(3) Заметим сразу, что оценку (2) можно считать квадратуриой суммой со случайными узлами. В самом деле, обычнаа квадратурнаи формула записывается в форме У = ~яр С„У (Р„), а 1 где точки Р„..., Рм, принадлежащие б, называются узлами, а числа Ст,..., С,ч — весами. Если квадратурная формула точна для функций 1(Р) =сола!, то Сн+ ...
+См — — 1. Оценка (2) дает нам такую же приближенную формулу У =2 Х ()у,))М') (-! з=-! причем и здесь т и И3 Х Х (~;()у) =Х )=! т=! ПРедполо>ким, что 1(Р)еейт(0; Р). Тогда точность простейшего метода Монте-Карло для расчета ! характеризуется дисперсией оценки (14) гл. 3, которая равна иВ.=Ы~Л, 2 и методы с повышеннон скОРОстью сходимости 137 где Р7 — ~~ (Р),о(Р) ЙР С Найдем теперь дисперсию оценки (2).
Очевидно, м 1 Рб.=х(р, ) ХЦ(а") 1=! в=! и так как здесь точки Я,'" при з= 1, ..., йг! независимы, то РВ.. = 5„(р,'/Л,) Р~ Уи». (4) 1=! Легко вычислить, что Р Р~ Я!11) = — ~2 (р) р (р) ар — — ' (6) ! Теорем а 1. Если разбиение тт=б!+...'+О,„и число У фиксированы, то л!инимул! выражения (4) при дополнительном условии (3) равен (2л =,ч Х р!'Ь~Ш %11!) " ~;=! (6) и реализуется при У, = Ур,)т Р~ (Я11!) /ч,' рТ~У~ Я!1!).
(7) / 1=! Доказательство. Согласно (6) величина Ьн равна 2 уй= Ы р,УРОД!т!)(Ц УИ,~й !.1=! где справа стоит (4). Остается проверить, что при яод- становке (7) в (4) получается (6). Используя неравенство Коши — Буняковского, получим "-- р21з((Ф!) у 62 ~,'у," ~ ' — ',)"," РрИ<п) ! !' ! ! 1=! 1 [зв вычисление интагиллов [сложныи оцинки> [гл. 1 В реальных задачах дисперсии Г11([',)и>), как правило, заранее неизвестны. Известны лишь вероятности рь Оказывается, этого уже достаточно, чтобы выбрать Лгь обеспечивающие уменьшение дисперсии (т. е. неравенст- ОО'„~ ЭО,).
Теорема 2. Если разбиение б=б,+...+О„фин. сировано, то при Фг= й[р, (8) величина (4) не превосходит Г>О . Доказательство. Умножив (5) на р, и просума мировав по 1 от 1 до пт, получим Х,р>П1%и') = 11(Р) р(Р) г[Р— Х (1'Ьт). 'Далее г-(вг,) -',в[чь-;[[ К1 . <Х,Я)рт)Х рт = Х (Г~Ъ) Следовательно, ~ Р>Р) Яи>) 4 ~ ~т (Р) Р (Р) йР— Р = Г>2. / 1 с Подставив (8) в (4), получим выражение )~,ПП[) ), которое в силу предыдущего неравенства не превосход>[т, '((1/>>[)Р2=1>О .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
