Реферат: Метод Монте-Карло и его применение
Арзамасский государственныйпедагогический институт
имени А.П.Гайдара
Кафедра математического анализа
Зубанов М. А., студент3 курса очного отделения
физико-математического
факультета
КУРСОВАЯ РАБОТАМетод Монте-Карло и его применениеНаучный руководитель:
канд. тех. наук, доцент
Потехин В.А.
Арзамас-2002 г.
Содержание
Введение……………………………………………………………..3
Глава 1. Некоторые сведения теории вероятностей ………….5
§1. Математическое ожидание, дисперсия……………………..5
§2. Точность оценки, доверительная вероятность.Доверительный
интервал……………………………………………………….6
§3. Нормальное распределение…………………………………..6
Глава 2. Метод Монте-Карло……………………………………...8
§1. Общая схема метода Монте-Карло……………………….….8
§2.Оценка погрешности метода Монте-Карло…………………8
Глава 3. Вычисление интегралов методом Монте-Карло…….12
§1. Алгоритмы метода Монте-Карло для решения
интегральных уравнений второго рода………………….…12
§2. Способ усреднения подынтегральной функции………….…13
§3. Способ существенной выборки, использующий
«вспомогательную плотность распределения»…………… .16
§4. Способ, основанныйна истолковании интеграла как
площади……………………………………………………. ..19
§5. Способ «выделения главной части»……………………… ...21
§6. Программа вычисления определенного интеграла методом
Монте-Карло…………………………………………………..23
§7. Вычисление кратных интегралов методом Монте-Карло.…25
Заключение…………………………………………………………..28
Приложение………………………………………………………....29
Литература…………………………………………………………...30
Введение.
Метод Монте-Карло можноопределить как метод моделирования случайных величин с целью вычисленияхарактеристик их распределений.
Возникновение идеи использования случайных явлений в области приближённыхвычислений принято относить к 1878 году, когда появилась работа Холла об определениичисла p с помощью случайных бросанийиглы на разграфлённую параллельными линиями бумагу. Существо дела заключается втом, чтобы экспериментально воспроизвести событие, вероятность котороговыражается через число p, и приближённооценить эту вероятность. Отечественные работы по методу Монте-Карло появилисьв 1955-1956 годах. С того времени накопилась обширная библиография по методуМонте-Карло. Даже беглый просмотр названий работ позволяет сделать вывод оприменимости метода Монте-Карло для решения прикладных задач из большого числаобластей науки и техники.
Первоначально метод Монте-Карло использовался главным образом для решениязадач нейтронной физики, где традиционные численные методы оказались малопригодными. Далее его влияние распространилось на широкий класс задачстатистической физики, очень разных по своему содержанию.
Метод Монте-Карло оказал и продолжает оказывать существенное влияние наразвитие методов вычислительной математики (например, развитие методовчисленного интегрирования) и при решении многих задач успешно сочетается сдругими вычислительными методами и дополняет их. Его применение оправдано впервую очередь в тех задачах, которые допускают теоретико-вероятностное описание.Это объясняется как естественностью получения ответа с некоторой заданнойвероятностью в задачах с вероятностным содержанием, так и существеннымупрощением процедуры решения.
Глава 1.Некоторые сведения теории вероятностей
§1. Математическоеожидание, дисперсия.
Дискретной называют случайную величину, которая принимает отдельные,изолированные возможные значения с определёнными вероятностями. Число возможныхзначений дискретной случайной величины может быть конечным или бесконечным.
Математическим ожиданием дискретной случайной величины называют суммупроизведений всех её возможных значений на их вероятность.
/>,
где Х –случайная величина, /> - значения,вероятности которых соответственно равны />.
Математическоеожидание приближённо равно (тем точнее, чем больше число испытаний) среднемуарифметическому наблюдаемых значений случайной величины.
Дисперсией (рассеянием) случайной величины называют математическоеожидание квадрата отклонения случайной величины от её математического ожидания:/>.
Средним квадратичным отклонением случайной величины Х называют квадратныйкорень из дисперсии: />.
§2. Точность оценки, доверительная вероятность. Доверительныйинтервал.
Точечной называют оценку, которая определяется одним числом.
Интервальной называют оценку, которая определяется двумя числами –концами интервала. Интервальные оценки позволяют установить точность инадёжность оценок.
Пусть, найденная по данным выборки, статистическая характеристика /> служит оценкойнеизвестного параметра />. Ясно, что /> тем точнее определяетпараметр />, чем меньше абсолютнаявеличина разности />. Другими словами,если d>0 и />, то, чем меньше d, тем оценка точнее. Положительное число d характеризует точность оценки.
Надёжностью (доверительной вероятностью) оценки /> по /> называют вероятность g, с которой осуществляется неравенство />.
Доверительным называют интервал />,который покрывает неизвестный параметр с заданной надёжностью g.
§3. Нормальное распределение.
Нормальным называют распределение вероятностей непрерывной
случайнойвеличины, которое описывается дифференциальной функцией
/>.
а — математическое ожидание, s — среднее квадратичное отклонение нормального распределения.
Глава 2. Метод Монте-Карло
/>
§1.Общая схема метода Монте-Карло.
Сущность метода Монте-Карло состоит в следующем: требуется найти значениеа некоторой изучаемой величины. Для этого выбирают такую случайную величину Х,математическое ожидание которой равно а: М(Х)=а.
Практически же поступают так: производят nиспытаний, в результате которых получают n возможныхзначений Х; вычисляют их среднее арифметическое /> ипринимают x в качестве оценки (приближённого значения) a* искомого числа a:
/>.
Посколькуметод Монте-Карло требует проведения большого числа испытаний, его частоназывают методом статистических испытаний. Теория этого метода указывает, какнаиболее целесообразно выбрать случайную величину Х, как найти её возможныезначения. В частности, разрабатываются способы уменьшения дисперсиииспользуемых случайных величин, в результате чего уменьшается ошибка,допускаемая при замене искомого математического ожидания а его оценкой а*.
§2.Оценка погрешности метода Монте-Карло.
Пусть для получения оценки a*математического ожидания а случайной величины Х было произведено n независимых испытаний (разыграно nвозможных значений Х) и по ним была найдена выборочная средняя />, которая принята вкачестве искомой оценки: />. Ясно,что если повторить опыт, то будут получены другие возможные значения Х,следовательно, другая средняя, а значит, и другая оценка a*.Уже отсюда следует, что получить точную оценку математического ожиданияневозможно. Естественно возникает вопрос о величине допускаемой ошибки. Ограничимсяотысканием лишь верхней границы dдопускаемой ошибки с заданной вероятностью (надёжностью) g: />.
Интересующая нас верхняя грань ошибки dесть не что иное, как «точность оценки» математического ожидания по выборочнойсредней при помощи доверительных интервалов. Рассмотрим следующие три случая.
1. Случайнаявеличина Х распределена нормально и её среднее
квадратичное отклонение d известно.
В этомслучае с надёжностью g верхняя границаошибки
/>, (*)
где n число испытаний (разыгранных значений Х); t– значение аргумента функции Лапласа, при котором />,s — известное среднее квадратичноеотклонение Х.
2. Случайнаявеличина Х распределена нормально, причём её среднее квадратическое отклонение s неизвестно.
В этомслучае с надёжностью g верхняя границаошибки
/>, (**)
где n – число испытаний; s –«исправленное» среднее квадратическое отклонение, /> находят по таблице приложения 3.
3. Случайнаявеличина Х распределена по закону, отличному от нормального.
В этомслучае при достаточно большом числе испытаний (n>30)с надёжностью, приближённо равной g,верхняя граница ошибки может быть вычислена по формуле (*), если среднееквадратическое отклонение s случайнойвеличины Х известно; если же sнеизвестно, то можно подставить в формулу (*) его оценку s– «исправленное» среднее квадратическое отклонение либо воспользоватьсяформулой (**). Заметим, что чем больше n, тем меньшеразличие между результатами, которые дают обе формулы. Это объясняется тем, чтопри /> распределение Стьюдентастремится к нормальному.
Из изложенного следует, что метод Монте-Карло тесно связан с задачамитеории вероятностей, математической статистики и вычислительной математики. Всвязи с задачей моделирования случайных величин (в особенности равномернораспределённых) существенную роль играют также методы теории чисел.
Среди других вычислительных методов, метод Монте-Карло выделяется своейпростотой и общностью. Медленная сходимость является существенным недостаткомметода, однако, могут быть указаны его модификации, которые обеспечиваютвысокий порядок сходимости при определённых предположениях. Правда, вычислительнаяпроцедура при этом усложняется и приближается по своей сложности к другимпроцедурам вычислительной математики. Сходимость метода Монте-Карло являетсясходимостью по вероятности. Это обстоятельство вряд ли следует относить к числуего недостатков, ибо вероятностные методы в достаточной мере оправдывают себя впрактических приложениях. Что же касается задач, имеющих вероятностноеописание, то сходимостью по вероятности является даже в какой-то мереестественной при их исследовании.
Глава 3. Вычисление интегралов методом Монте-Карло.
§1. Алгоритмы метода Монте-Карло длярешения интегральных уравнений второго рода.
Пусть необходимо вычислить линейный функционал />, где />, причём для интегральногооператора K с ядром /> выполняется условие,обеспечивающее сходимость ряда Неймана: />.Цепь Маркова /> определяется начальнойплотностью /> и переходной плотностью />; вероятность обрыва цепи вточке /> равна />. N– случайный номер последнего состояния. Далее определяется функционал оттраектории цепи, математическое ожидание которого равно />. Чаще всего используетсятак называемая оценка по столкновениям />, где />, />. Если /> при />, и /> при />, то при некоторомдополнительном условии />.Важность достижения малой дисперсии в знакопостоянном случае показываетследующее утверждение: если /> и />, где />, то />, а />. Моделируя подходящую цепьМаркова на ЭВМ, получают статистическую оценку линейных функционалов от решенияинтегрального уравнения второго рода. Это даёт возможность и локальной оценкирешения на основе представления: />, где />. Методом Монте-Карлооценка первого собственного значения интегрального оператора осуществляетсяинтерациональным методом на основе соотношения />.Все рассмотренные результаты почти автоматически распространяются на системылинейных алгебраических уравнений вида />.Решение дифференциальных уравнений осуществляется методом Монте-Карло на базесоответствующих интегральных соотношений.
§2.Способ усреднения подынтегральной функции.
В качестве оценки определённого интеграла /> принимают
/>,
где n – число испытаний; /> -возможные значения случайной величины X, распределённойравномерно в интервале интегрирования />,их разыгрывают по формуле />, где /> - случайное число.
Дисперсия усредняемой функции /> равна
/>,
где />, />. Если точное значениедисперсии вычислить трудно или невозможно, то находят выборочную дисперсию(при n>30) />, или исправленнуюдисперсию (при n<30) />, где />.
Эти формулы для вычисления дисперсии применяют и при других способахинтегрирования, когда усредняемая функция не совпадает с подынтегральнойфункцией.
В качестве оценки интеграла />, гдеобласть интегрирования D принадлежит единичномуквадрату />, />, принимают
/>, (*)
где S – площадь области интегрирования; N– число случайных точек />,принадлежащих области интегрирования.
Если вычислить площадь S трудно, то в качестве еёоценки можно принять />; в этом случаеформула (*) имеет вид
/> ,
где n – число испытаний.
В качестве оценки интеграла />, гдеобласть интегрирования V принадлежит единичному кубу />, />, />, принимают />, где V– объём области интегрирования, N – число случайныхточек />, принадлежащих областиинтегрирования.
Если вычислить объём трудно, то в качестве его оценки можно принять />, в этом случае формула(**) имеет вид />, где n – число испытаний.
Задача: найти оценку />определённогоинтеграла />.
Решение. Используем формулу />. Поусловию, a=1, b=3, />. Примем для простоты числоиспытаний n=10.Тогда оценка />, где возможные значения /> разыгрывается по формуле />.
Результаты десяти испытаний приведены в таблице 1.
Случайные числа /> взяты из таблицыприложения.
Таблица 1.
Номер i/>
/>
/>
1
2
3
4
5
6
7
8
9
10
0,100
0,973
0,253
0,376
0,520
0,135
0,863
0,467
0,354
0,876
1,200
2,946
1,506
1,752
2,040
1,270
2,726
1,934
1,708
2,752
2,200
3,946
2,506
2,752
3,040
2,270
3,726
2,934
2,708
3,752
Из таблицы 1 находим />. Искомая оценка
/>
§3. Способ существенной выборки, использующий«вспомогательную плотность распределения».
В качестве оценки интеграла /> принимают/>, где n– число испытаний; f(x) –плотность распределения «вспомогательной» случайной величины X,причём />; /> - возможные значения X, которые разыгрывают по формуле />.
Функцию f(x) желательновыбирать так, чтобы отношение /> приразличных значениях x изменялось незначительно. Вчастности, если />, то получимоценку />.
Задача. Найти оценку /> интеграла/>.
Решение. Так как />, то в качествеплотности распределения «вспомогательной» случайной величины Xпримем функцию />. Из условия /> найдём />. Итак, />.
Запишем искомый интеграл так:
/>.
Таким образом, интеграл I представлен в видематематического ожидания функции />. Вкачестве искомой оценки примем выборочную среднюю (для простоты ограничимсядесятью испытаниями):
/>,
где /> - возможные значения X, которые надо разыграть по известной плотности />. По правилу (для того,чтобы разыграть возможное значение /> непрерывнойслучайной величины X, зная её плотность вероятности f(x), надо выбрать случайное число /> и решить относительно /> уравнение
/>, или уравнение />,
где a – наименьшее конечно возможное значение X),имеем />. Отсюда находим явнуюформулу для разыгрывания возможных значений X:
/>.
В таблице 2 приведены результаты 10 испытаний.
Сложивчисла последней строки таблицы 2, получим />. Искомая оценка равна />.
Таблица 2.
Номер i/>
/>
/>
/>
/>
1
2
3
4
5
6
7
8
9
10
0,100
0,973
0,253
0,376
0,520
0,135
0,863
0,467
0,354
0,876
0,140
0,980
0,326
0,459
0,600
0,185
0,894
0,550
0,436
0,905
1,150
2,664
1,385
1,582
1,822
1,203
2,445
1,733
1,546
2,472
1,140
1,980
1,326
1,459
1,600
1,185
1,894
1,550
1,436
1,905
1,009
1,345
1,044
1,084
1,139
1,015
1,291
1,118
1,077
1,298
§4.Способ, основанный на истолковании интеграла как площади.
Пусть подынтегральная функция неотрицательна и ограничена: />, а двумерная случайнаявеличина /> распределена равномерно впрямоугольнике D с основанием /> и высотой />. Тогда двумерная плотностьвероятности /> для точек,принадлежащих D; /> внеD.
В качестве оценки интеграла /> принимают/>, где n– общее число случайных точек />,принадлежащих D; /> -число случайных точек, которые расположены под кривой />.
Задача. Найти оценку /> интеграла/>.
Решение. Используем формулу />.
В интервале (0,2) подынтегральная функция /> неотрицательнаи ограничена, причём />; следовательно,можно принять c=4.
Введём в рассмотрение двумерную случайную величину (X,Y), распределённую равномерно в прямоугольнике D с основанием /> ивысотой с=4, плотность вероятности которой />.
Разыгрываем n=10 случайных точек />, принадлежащихпрямоугольнику D. Учитывая, что составляющая X в интервале (0,2) распределена равномерно с плотностью /> и составляющая Y в интервале (0,4) распределена равномерно с плотностью />, разыграем координатыслучайной точки />, принадлежащейпрямоугольнику D, по паре независимых случайных чисел />: />, />.Отсюда />, />.
Номер i/>
/>
/>
/>
/>
/>
/>
1
2
3
4
5
6
7
8
9
10
0,100
0,253
0,520
0,863
0,354
0,809
0,911
0,542
0,056
0,474
0,200
0,506
1,040
1,726
0,708
1,618
1,822
1,084
0,112
0,948
0,040
0,256
1,082
2,979
0,501
2,618
3,320
1,175
0,013
0,899
3,960
3,744
2,918
1,021
3,499
1,382
0,680
2,825
3,987
3,101
0,973
0,376
,135
0,467
0,876
0,590
0,737
0,048
0,489
0,296
3,892
1,504
0,540
1,868
3,504
2,360
2,948
0,192
1,956
1,184
1
1
1
1
1
1
Если окажется, что />, тоточка /> лежит под кривой /> и в «счётчик />» надо добавить единицу.
Результаты десяти испытаний приведены в таблице 3.
Из таблицы3 находим />. Искомая оценка интеграла
/>
§5.Способ «выделения главной части».
В качестве оценки интеграла /> принимают
/>,
где /> - возможные значенияслучайной величины X, распределённой равномерно винтервале интегрирования />,которые разыгрывают по формуле />;функция />, причём интеграл /> можно вычислить обычнымиметодами.
Задача. Найти оценку /> интеграла/>.
Решение. Так как /> />, то примем />. Тогда, полагая числоиспытаний n=10, имеем оценку
/>.
Выполнивэлементарные преобразования, получим
/>.
Учитывая, что a=0, b=1,возможные значения /> разыграем поформуле />. Результаты вычисленийприведены в таблице 4.
Номер i/>
/>
/>
/>
/>
1
2
3
4
5
6
7
8
9
10
0,100
0,973
0,253
0,376
0,520
0,135
0,863
0,467
0,354
0,876
0,010
0,947
0,064
0,141
0,270
0,018
0,745
0,218
0,125
0,767
1,010
1,947
1,064
1,141
1,270
1,018
1,745
1,218
1,125
1,767
1,005
1,395
1,032
1,068
1,127
1,009
1,321
1,104
1,061
1,329
2,000
1,843
2,000
1,995
1,984
2,000
1,897
1,990
1,997
1,891
Сложив числа последнего столбца таблицы 4, найдём сумму 19,597, подставивкоторую в соотношение />,получим искомую оценку интеграла
/>.
Заметим, что точное значение I=1,147.
§6. Программа вычисленияопределенного интеграла методом Монте-Карло.
Вычислить определенныйинтеграл />по методу “Монте-Карло” по формуле
/>,
где n – число испытаний ;g(x) – плотность распределения“вспомогательной” случайной величины X, причем />, в программе g(x) = 1/(b-a)
Программа написана на языке TURBOPASCAL7.0
Program pmk;
Uses crt;
Var k,p,s,g,x,Integral:real;
n,i,a,b: integer;
BEGIN
writeln(‘Введите промежуток интегрирования (a;b):’);
readln(a);
readln(b);
writeln(‘Введите количество случайных значений(числоиспытаний):’);
readln(n);
k:=b-a; {Переменной“k”присвоим значение длины промежуткаинтегрирования}
writeln(‘k=’,k);
for i:= 1 to n do begin {проведем n испытаний}
g:=random; {g –переменная вещественного типа, случайная величина из промежутка [0;1]}
x:= a + g*(b-a); {По этойформуле получается произвольная величина из [a; b] }
s:=s + (1+x); {s:=s +(x*x)} {Вообще можно подставить любую функцию}
delay(1000); {задержка, чтобы произвольные значения неповторялись}
end; {конец испытаний}
writeln(‘s=’,s); {Сумма функции для n произвольных значений}
Integral:=(1/n)*k*s ;
writeln(‘Интеграл=’,Integral);
readln;
END.
Требуется ввестипромежуток интегрирования и количество испытаний, интегрируемая функция ужезадана в программе (но ее можно поменять).
/>; />.
Функция k N=10 N=100 N=500 N=1000 f(x)=1+x 2 5.737 5.9702 6.02 5.99 f(x)=x*x 3 9.6775 8.528 8.7463 8.937§7. Вычисление кратных интегралов методом Монте-Карло.
Пусть функция />непрерывнав ограниченной замкнутой области S итребуется вычислить m-кратный интеграл
/>/>. (1)
Геометрически число I представляет собой (m+1)-мерный объём прямогоцилиндроида в пространстве />,построенного на основании S и ограниченного сверху данной поверхностью />, где />.
Преобразуем интеграл (1) так, чтобы новая область интегрирования целикомсодержалась внутри единичного m-мерного куба. Пусть область S расположена вm-мерном параллелепипеде
/>. (2)
Сделаем замену переменных />. (3)
Тогда, очевидно, m-мерныйпараллелепипед (2) преобразуется в m-мерный единичный куб /> /> (4)
и, следовательно, новая область интегрирования σ, которая находитсяпо обычным правилам, будет целиком расположена внутри этого куба.
Вычисляя якобиан преобразования, будем иметь:
/>. Таким образом, />/>, (5)
где />.Введя обозначения /> и />, запишем интеграл (5)короче в следующем виде: />/>. (5/)
Укажем способ вычисленияинтеграла (5/) методом случайных испытаний.
Выбираем m равномернораспределённых на отрезке [0, 1] последовательностей случайных чисел:
/>
Точки />можно рассматривать какслучайные. Выбрав достаточно большое N число точек />, проверяем, какие из нихпринадлежат области σ (первая категория) и какие не принадлежат ей(вторая категория). Пусть
1. /> при i=1, 2, …, n (6)
2. /> при i=n+1, n+2,…,N (6/)
(для удобства мы здесь изменяем нумерацию точек).
Заметим, что относительнограницы Г области σ следует заранее договориться, причисляются лиграничные точки или часть их к области σ, или не причисляются к ней. Вобщем случае при гладкой границе Г это не имеет существенного значения; вотдельных случаях нужно решать вопрос с учётом конкретной обстановки.
Взяв достаточно большое число n точек />, приближённо можно положить:/>; отсюда искомый интегралвыражается формулой />, где под σпонимается m-мерный объём области интегрированияσ. Если вычисление объёма σ затруднительно, то можно принять: />, отсюда />. В частном случае, когдаσ есть единичный куб, проверка становится излишней, то есть n=N и мы имеем просто />.
Заключение.
Метод Монте-Карло используется очень часто, порой некритично инеэффективным образом. Он имеет некоторые очевидные преимущества:
а) Он не требует никакихпредложений о регулярности, за исключением квадратичной интегрируемости. Этоможет быть полезным, так как часто очень сложная функция, чьи свойстварегулярности трудно установить.
б) Он приводит к выполнимойпроцедуре даже в многомерном случае, когда численное интегрированиенеприменимо, например, при числе измерений, большим 10.
в) Его легко применять прималых ограничениях или без предварительного анализа задачи.
Он обладает, однако, некоторыминедостатками, а именно:
а) Границы ошибки неопределены точно, но включают некую случайность. Это, однако, болеепсихологическая, чем реальная, трудность.
б) Статическая погрешностьубывает медленно.
в) Необходимость иметьслучайные числа.
Приложение.
Равномернораспределённые случайные числа
10 09 73 25 33 76 52 0135 86 34 67 35 48 76 80 95 90 9117
37 54 20 48 05 64 89 4742 96 24 80 52 40 37 20 63 61 04 02
08 42 26 89 53 19 64 5093 03 23 20 90 25 60 15 95 33 47 64
99 01 90 25 29 09 37 6707 15 38 31 13 11 65 88 67 67 43 97
12 80 79 99 70 80 15 7361 47 64 03 23 66 53 98 95 11 68 77
66 06 57 47 17 34 07 2768 50 36 69 73 61 70 65 81 33 98 85
31 06 01 08 05 45 57 1824 06 35 30 34 26 14 86 79 90 74 39
85 26 97 76 02 02 05 1656 92 68 66 57 48 18 73 05 38 52 47
63 57 33 21 35 05 32 5470 48 90 55 35 75 48 28 46 82 87 09
73 79 64 57 53 03 52 9647 78 35 80 83 42 82 60 93 52 03 44
Литература.
1. Гмурман В.Е. Руководство к решению задач по теории вероятностей иматематической статистике: Учеб. пособие для студентов втузов. – 3-е изд.,перераб. И доп. – М.: Высш. школа, 1979г.
2. Ермаков С. М. Методы Монте-Карло и смежные вопросы. М.: Наука, 1971г.
3. Севастьянов Б. А. Курс теории вероятностей и математической статистики.– М.: Наука,1982г.
4. Математика. Большой энциклопедический словарь / Гл. ред. Ю. В. Прохоров.– М.: Большая Российская энциклопедия,1999г.
5. Гмурман В. Е. Теория вероятностей и математическая статистика. Учеб.пособие для втузов. Изд. 5-е, перераб. и доп. М., «Высш. школа», 1977.