Метод Монте-Карло и его применение

Курсовая работа Зубанова М. А., студента 3 курса очного отделения физико-математического факультета

Арзамасский государственный педагогический институт имени А.П.Гайдара

Кафедра математического анализа

Арзамас-2002 г.

Введение.

Метод Монте-Карло можно определить как метод моделирования случайных величин с целью вычисления характеристик их распределений.

Возникновение идеи использования случайных явлений в области приближённых вычислений принято относить к 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 есть не что иное, как «точность оценки» математического ожидания по выборочной средней при помощи доверительных интервалов. Рассмотрим следующие три случая.

Случайная величина Х распределена нормально и её среднее квадратичное отклонение d известно.

В этом случае с надёжностью g верхняя граница ошибки

, (*)

где n число испытаний (разыгранных значений Х); t – значение аргумента функции Лапласа, при котором , s - известное среднее квадратичное отклонение Х.

Случайная величина Х распределена нормально, причём её среднее квадратическое отклонение s неизвестно.

В этом случае с надёжностью g верхняя граница ошибки

, (**)

где n – число испытаний; s – «исправленное» среднее квадратическое отклонение,  находят по таблице приложения 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)

Программа написана на языке TURBO PASCAL 7.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 01 35 86 34 67 35 48 76 80 95 90 9117

37 54 20 48 05 64 89 47 42 96 24 80 52 40 37 20 63 61 04 02

08 42 26 89 53 19 64 50 93 03 23 20 90 25 60 15 95 33 47 64

99 01 90 25 29 09 37 67 07 15 38 31 13 11 65 88 67 67 43 97

12 80 79 99 70 80 15 73 61 47 64 03 23 66 53 98 95 11 68 77

66 06 57 47 17 34 07 27 68 50 36 69 73 61 70 65 81 33 98 85

31 06 01 08 05 45 57 18 24 06 35 30 34 26 14 86 79 90 74 39

85 26 97 76 02 02 05 16 56 92 68 66 57 48 18 73 05 38 52 47

63 57 33 21 35 05 32 54 70 48 90 55 35 75 48 28 46 82 87 09

73 79 64 57 53 03 52 96 47 78 35 80 83 42 82 60 93 52 03 44

Список литературы

Гмурман В.Е. Руководство к решению задач по теории вероятностей и математической статистике: Учеб. пособие для студентов втузов. – 3-е изд., перераб. И доп. – М.: Высш. школа, 1979г.

Ермаков С. М. Методы Монте-Карло и смежные вопросы. М.: Наука, 1971г.

Севастьянов Б. А. Курс теории вероятностей и математической статистики. – М.:Наука,1982г.

Математика. Большой энциклопедический словарь / Гл. ред. Ю. В. Прохоров. – М.: Большая Российская энциклопедия,1999г.

Гмурман В. Е. Теория вероятностей и математическая статистика. Учеб. пособие для втузов. Изд. 5-е, перераб. и доп. М., «Высш. школа», 1977.