2

Министерство образования РФ

Кубанский Государственный Университет

Филиал ст.Отрадная

КУРСОВАЯ РАБОТА

По предмету: «Компьютерное модлирование»

На тему: «Моделирование методом Монте-Карло»

Выполнил: студент 4-го курса специальности «Программное обеспечение вычислительной техники и автоматизированных систем»

Шабаров П.С.

Проверила:

Ильина Наталья Анатольевна

Отрадная 2008

Содержание

Введение

Глава I. Предыстория и определение метода Монте-Карло

Глава II. Расчётная часть

2.1 Простейший пример использования метода Монте-Карло

2.2.1 Вычисление числа Пи методом Монте-Карло

2.2.2 Постановка задачи для нахождения числа Пи методом Монте-Карло

2.2.3 Исходник программы для нахождения числа Пи методом Монте-Карло

2.3.1 Решение задачи аналитически и методом Монте-Карло

2.3.2 Постановка задачи

2.3.3 Исходник программы

Глава III. Генерация случайных чисел

Заключение

Список использованных источников

Введение

Методы Монте-Карло - это общее название группы методов для решения различных задач с помощью случайных последовательностей. Эти методы (как и вся теория вероятностей) выросли из попыток людей улучшить свои шансы в азартных играх. Этим объясняется и тот факт, что название этой группе методов дал город Монте-Карло - столица европейского игорного бизнеса (казино), где играют в рулетку - одно из простейших устройств для получения случайных чисел, на использовании которых основан этот метод.

ЭВМ позволяют легко получать так называемые псевдослучайные числа (при решении задач их применяют вместо случайных чисел); это привело к широкому внедрению метода во многие области науки и техники (статистическая физика, теория массового обслуживания, теория игр и др.). И.М.Соболь "Метод Монте-Карло",М.,1985

Интернет-ресурс «Метод Монте-Карло» http://apollyon1986.narod.ru/docs/TViMS/NP/lekziitv/lekziya17.htm

Глава I. Предыстория и определение метода Монте-Карло

Создателями метода статистических испытаний (метода Монте-Карло) считают американских математиков Д. Неймана и С. Улама. В 1944 году, в связи с работами по созданию атомной бомбы Нейман предложил широко использовать аппарат теории вероятностей для решения прикладных задач с помощью ЭВМ. Первая работа, где этот вопрос систематически излагался, принадлежит Метрополису и Уламу.

Первоначально метод Монте-Карло использовался главным образом для решения задач нейтронной физики, где традиционные численные методы оказались мало пригодными. Далее его влияние распространилось на широкий класс задач статистической физики, очень разных по своему содержанию. К разделам науки, где все в большей мере используется метод Монте-Карло, следует отнести задачи теории массового обслуживания, задачи теории игр и математической экономики, задачи теории передачи сообщений при наличии помех и ряд других.

Аналитические методы дают решение задачи либо в виде формулы, либо в виде разложения в ряды или интегралы по полному набору собственных функций какого-нибудь оператора.

Классические численные методы дают приближенную схему решения задачи, связанную, обычно с разбиением пространства на строго определенные клетки и заменой интегрирования суммированием и дифференцирования - конечными разностями.

Основными недостатками аналитических методов являются:

§ Недостаточная универсальность основных способов решения. Например, способ разложения в ряд по собственным функциям практически не работают для тех дифференциальных уравнений в частных производных, где переменные не разделяются, и так далее.

§ Крайне ограниченный набор геометрических условий, для которых возможно решение задачи. Даже сочетание простых, но разнотипных поверхностей делает задачу неразрешимой.

§ Невозможность расчета физического процесса, вероятностное описание которого известно, но выражение в виде уравнения крайне затруднительно.

Классические численные методы исправляют часть этих недостатков, но зато добавляют свои собственные. Они не страшатся сложной геометрии задач, однако:

§ Они чрезвычайно громоздки. Объем промежуточной информации трудно вместить даже в память современного компьютера.

§ Оценка погрешности решения представляет намного более трудную процедуру, чем сам процесс решения. Зачастую она просто невозможна.

Метод статистических испытаний свободен от всех этих недостатков.

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

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

Итак, сущность метода Монте-Карло состоит в следующем: требуется найти значение а некоторой изучаемой величины. Для этого выбирают такую случайную величину X, математическое ожидание которой равно а:

М(Х)=A.

Практически же поступают так: производят N испытаний, в результате которых получают N возможных значений X, вычисляют их среднее арифметическое и принимают его в качестве оценки (приближенного значения) A' искомого числа A.

Как правило, составляется программа для осуществления одного случайного испытания. Погрешность вычислений, как правило, пропорциональна , где D - некоторая постоянная.

Это значит, что N должно быть велико, поэтому метод существенно опирается на возможности ЭВМ. Ясно, что добиться таким путем высокой точности невозможно. Это один из недостатков метода. Во многих задачах удается значительно увеличить точность, выбрав способ расчета, которому соответствует значительно меньшее D.

Поскольку метод Монте-Карло требует проведения большого числа испытаний, его часто называют методом статистических испытаний. Теория этого метода указывает, как наиболее целесообразно выбрать случайную величину X, как найти ее возможные значения.

Отыскание возможных значений случайной величины Х (моделирование) называют «разыгрыванием случайной величины».

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

В отличие от аналитических методов, ищущих решение в виде ряда по собственным функциям, методы Монте-Карло ищут решения в виде статистических сумм. Для их применения достаточно описания вероятностного процесса и не обязательна его формулировка в виде интегрального уравнения; оценка погрешности чрезвычайно проста, их точность слабо зависит от размерности пространства.

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

Преимущество метода Монте-Карло состоит в том, что он способен “сработать” там, где отказывают другие методы.

Аналитические методы исследования позволяют существенно уменьшить погрешность метода Монте-Карло и могут поднять его до уровня получения качественных закономерностей. Синтез аналитических и статистических методов может свести D к очень малой величине, следовательно, уменьшить погрешность.

Приведем примеры задач, решаемых методом Монте-Карло:

– расчет системы массового обслуживания;

– расчет качества и надежности изделий;

– теория передачи сообщений;

– вычисление определенного интеграла;

– задачи вычислительной математики;

– задачи нейтронной физики и другие. Интернет-ресурс «Предыстория и определение метода Монте-Карло» http://armgeo.narod.ru/GIS/Learning/Monte-Carlo_2/Page01.htm

Интернет-ресурс «Метод Монте-Карло» http://www.nnspu.ru/Exponenta_Ru/educat/systemat/boziev/13.asp.htm

Глава II. Расчётная часть

2.1 Простейший пример использования метода Монте-Карло

Предположим, что нам нужно определить площадь плоской фигуры, расположенной внутри единичного квадрата, т.е. квадрата, сторона которого равна единице (рис. 1). Выберем внутри квадрата наугад N точек. Обозначим через M количество точек, попавших при этом внутрь фигуры. Тогда площадь фигуры приближенно равна отношению . Отсюда, чем больше N, тем больше точность такой оценки. Интернет-ресурс «Вундеркинд» http://inf.1september.ru/2001/leto/stend/Vynderkind.htm

Рисунок 1. Площадь фигуры приближенно равна, отношению числа точек попавших в фигуру ко всему числу точек.

2.2.1 Вычисление числа Пи методом Монте-Карло

Попробуем построить метод Монте-Карло для решения задачи о вычислении числа Пи. Для этого рассмотрим четверть круга единичного радиуса (рис. 2). Площадь круга равна , очевидно, площадь четверти круга равна:

.

Зная, что радиус круга равен 1, получим:

Рисунок 2. Нахождение числа Пи методом Монте-Карло.

Площадь же всего единичного квадрата OABC равна 1. Будем случайным образом выбирать точки внутри квадрата OABC. Координаты точек должны быть и . Теперь подсчитаем количество точек таких, что , т.е. те точки которые попадают внутрь круга.

Пусть всего было испытано N точек, и из них M попало в круг. Рассмотрим отношение количества точек, попавших в круг, к общему количеству точек (M/N). Очевидно, что чем больше случайных точек мы испытаем, тем это отношение будет ближе к отношению площадей четверти круга и квадрата. Таким образом, имеем, что, для достаточно больших N, верно равенство:

.

Из полученного равенства:

.

Итак, мы построили метод Монте-Карло для вычисления числа Пи. Опять перед нами стоит вопрос о том, какое именно количество точек N нужно испытать для того, чтобы получить Пи с предсказуемой точностью? Вопрос о точности вычислений с помощью методов Монте-Карло рассматривается в традиционных курсах теории вероятностей, и мы не будем останавливаться на нем подробно. Можно отметить лишь, что точность вычислений очень сильно зависит от качества используемого генератора псевдослучайных чисел. Другими словами, точность тем выше, чем более равномерно случайные точки распределяются по единичному квадрату. Интернет-ресурс «Метод Монте-Карло» http://u.pereslavl.ru/~gene/probset/prob13.koi8.html

И.М.Соболь "Метод Монте-Карло",М.,1985

2.2.2 Постановка задачи для нахождения числа Пи методом Монте-Карло

Для проверки формулы [1], я решил написать программу в среде программирования Турбо Паскаль. В программе нужно ввести число K - количество испытаний и число N - количество испытываемых точек. Для координат точек (X, Y) используется генератор случайных чисел. Результаты всех испытаний усредняются.

2.2.3 Исходник программы для нахождения числа Пи методом Монте-Карло

VAR

K, {количество испытаний}

N, {количество точек}

i, j: word; {для циклов}

s, {сумма всех Пи}

P: real; {среднеарифметическое значение Пи}

{функция возвращает число Пи}

FUNCTION raschet: real;

VAR

x, y: word; {координаты точек}

M: word; {число точек попавших в окружность}

BEGIN

M:=0;

for i:=1 to N do

begin

x:=random(2); {x, y - случайные числа}

y:=random(2);

if sqr(x)+sqr(y)<=1 then inc(M); {точка с координатами x, y попала в круг}

end;

raschet:=4*M/N; {из формулы [1]}

END;

BEGIN

write('Введите количество испытаний: ');

readln(K);

write('Введите количество испытываемых точек: ');

readln(N);

randomize;

s:=0;

for j:=1 to K do s:=s+raschet;

P:=s/K;

writeln('Число Пи, рассчитанное методом Монте-Карло равно:');

writeln(P:1:6);

writeln;

writeln('Точное число Пи равно:');

writeln(Pi:1:6);

END.

Итак, с помощью этой программы я проверил верность формулы [1]. Я получил число Пи равное: 3.000808, при количестве испытаний 500 раз с количеством точек 5000. Точное число Пи равно: 3.141593.

Как и говорилось выше более точный ответ можно получить при очень большом количестве проведенных опытов, при испытании большего количества точек и при использовании качественного генератора псевдослучайных чисел. "TURBO PASCAL ДЛЯ ШКОЛЬНИКОВ" издание третье дополненное, В.Б.Попов

2.3.1 Решение задачи аналитически и методом Монте-Карло

Рассмотрим задачу:

Система контроля качества продукции состоит из трех приборов. Вероятность безотказной работы каждого из них в течение времени Т равна 5/6. Приборы выходят из строя независимо друг от друга. При отказе хотя бы одного прибора вся система перестает работать. Найти вероятность того, что система откажет за время Т.

Аналитическое решение.

Событие А - выход из строя хотя бы одного из трех приборов за время Т и событие - ни один из трех приборов не выйдет из строя за время Т, противоположные. Вероятность - искомая вероятность. Отсюда:

Теперь решим задачу методом Монте-Карло.

Напомним, что при использовании данного метода возможны два подхода: либо непосредственно проводят эксперименты, либо имитируют их другими экспериментами, имеющими с исходными одинаковую вероятностную структуру. В условиях данной задачи «натуральный» эксперимент - наблюдение за работой системы в течение времени Т. Многократное повторение этого эксперимента может оказаться трудноосуществимым или просто невозможным. Заменим этот эксперимент другим.

Для определения того, выйдет или не выйдет из строя за время Т отдельный прибор, будем подбрасывать игральную кость. Если выпадет одно очко, то будем считать, что прибор вышел из строя; если два, три, четыре, пять, шесть очков, то будем считать, что прибор работал безотказно. Вероятность того, что выпадет одно очко, так же как и вероятность выхода прибора из строя, равна 1/6, а вероятность того, что выпадет любое другое число очков, как и вероятность безотказной работы прибора, равна 5/6.

Чтобы определить, откажет или нет вся система за время Т, будем подбрасывать три игральные кости. Если хотя бы на одной из трех костей выпадет одно очко, то это будет означать, что система отказала.

Повторим испытание, состоящее в подбрасывании трех игральных костей, много раз подряд и найдем отношение числа M - отказов системы к общему числу N - проведенных испытаний. Вероятность отказа будет равна: Интернет-ресурс «Метод Монте-Карло» http://apollyon1986.narod.ru/docs/TViMS/NP/lekziitv/lekziya17.htm

.

2.3.2 Постановка задачи

Для проверки формулы [3], которая основана на методе Монте-Карло, я решил написать программу в среде программирования Турбо Паскаль. Дело в том, что если бы вероятность безотказной работы приборов была не , а например , имитировать другими экспериментами, имеющими с исходными одинаковую вероятностную структуру, без использования ЭВМ было бы затруднительно.

Данная программа рассчитана на любые подобные задачи. В конце расчетов программа выдает два ответа. Первый - полученный методом Монте-Карло по формуле [3]. Второй - полученный аналитическим методом по формуле [2].

В программе нужно ввести: B - количество приборов; вероятность в виде дроби; N - количество проведенных опытов.

2.3.3 Исходник программы

VAR

B, {количество приборов}

S, D: byte; {вероятность P(A)=S/D}

N, {количество опытов}

i, j, {для циклов}

summa: word; {суммарное число отказов}

P_M, P_A: real; {полученная вероятность}

{функция возвращает количество отказов за одно испытание}

FUNCTION otkaz: word;

VAR

o:word;

R:byte;

BEGIN

o:=0;

for i:=1 to B do

begin

R:=random(D+1)+1; {случайное число >=1 и <=D}

if R<=D-S then inc(o); {выпал "отказ"}

end;

otkaz:=o;

END;

BEGIN

write('Введите количество приборов: ');

readln(B);

writeln('Введите вероятность безотказной работы (в виде дроби):');

write(' числитель - ');

readln(S);

write(' знаменатель - ');

readln(D); {т.е. P=S/D}

write('Введите количество опытов: ');

readln(N);

{расчет методом Монте-Карло}

summa:=0;

for j:=1 to N do summa:=summa+otkaz;

P_M:=summa/N;

{расчет аналитическим методом}

P_A:=S/D;

for i:=1 to B-1 do P_A:=P_A*S/D; {возведение в степень}

P_A:=1-P_A;

writeln;

writeln('* * * Ответ * * *');

writeln('Методом Монте-Карло: ', P_M:1:6);

writeln('Аналитическим методом: ', P_A:1:6);

writeln;

writeln('(С) Шабаров Павел, 2004');

END.

Итак, проверив формулу [3] с помощью своей программы со значениями: количество приборов - 3; вероятность безотказной работы ; количество опытов - 50000, я получил два ответа. Решение задачи методом Монте-Карло - 0.429420. Решение задачи аналитическим методом - 0.421296. Отсюда вывод - вероятность, полученная разными методами сходна. "TURBO PASCAL ДЛЯ ШКОЛЬНИКОВ" издание третье дополненное, В.Б.Попов

Глава III. Генерация случайных чисел

В строго детерминированном мире процессорных кодов внесение в программу элемента случайности - не такая простая задача, как может показаться на первый взгляд. В этом я убедился, получив значение числа Пи из своей программы. Наиболее часто встречающиеся приложения, в которых необходимо использование случайных чисел - это численное моделирование методом Монте-Карло и создание компьютерных игр.

Получение случайных чисел - важная стадия компьютерного эксперимента, которой не всегда уделяется должное внимание. Используемые на практике численные алгоритмы приводят к получению псевдослучайных чисел, особенностями которых являются ограниченность и воспроизводимость последовательности.

Итак, дадим определение этих чисел. Обозначим через R непрерывную случайную величину, распределенную равномерно в интервале (0, 1).

Случайными числами называют возможные значения r_j непрерывной случайной величины R, распределенной равномерно в интервале (0, 1).

В действительности пользуются не равномерно распределенной случайной величиной R, возможные значения которой имеют бесконечное число десятичных знаков, а квазиравномерной случайной величиной R', возможные значения которой имеют конечное число знаков. В результате замены R на R' разыгрываемая величина имеет не точно, а приближенно заданное распределение.

Случайная величина R' обладает свойством: вероятность попадания ее в любой интервал, принадлежащий интервалу (0; 1) равна длине этого интервала.

Получение случайных чисел - важная стадия компьютерного эксперимента, которой не всегда уделяется должное внимание. Используемые на практике численные алгоритмы приводят к получению псевдослучайных чисел, особенностями которых являются ограниченность и воспроизводимость последовательности.

Исчерпание этой последовательности при большом числе циклов Монте-Карло или размере системы снижает ее фактический размер до:

где

N - размер системы (количество частиц);

P - период последовательности псевдослучайных чисел;

k - количество случайных чисел, используемых для определения состояния одной частицы;

n - суммарное количество циклов Монте-Карло, необходимое для стабилизации (термализации) системы и расчета ее характеристик.

Например, при моделировании системы Изинга, состоящей из 2000 частиц требуется, как правило, не менее 500 циклов МК, т.е. необходимо не менее 10⁵ случайных чисел. Если используемый генератор является 16-ти разрядным и не может произвести последовательность, состоящую из более чем 2¹⁶ (65536) псевдослучайных чисел, то фактический размер системы по формуле [4] будет порядка 1000 частиц.

С играми ситуация еще более трагическая: например, колода из 52 карт может быть упорядочена 52! способами. Это примерно 8e67 или 2²²⁶. Значит для того, чтобы в процессе игры мог возникнуть любой расклад, создателю полноценной карточной игры типа «21» необходим 256 разрядный генератор случайных чисел. Если колода состоит из 36 карт, то соответствующие числа равны 4e41 и 2¹³⁸, т.е. без суперкомпьютера опять не обойдешься. В карточной игре «преферанс» количество вариантов раздач равно 32!/10! или 2⁹⁶, что тоже не мало. Несмотря на несравнимость этих чисел с реальными возможностями 32-х разрядного процессора, необходимо, конечно, использовать его возможности максимально, ведь только так можно приблизиться к разнообразию реальности. Интернет-ресурс «Метод Монте-Карло» http://apollyon1986.narod.ru/docs/TViMS/NP/lekziitv/lekziya17.htm

Интернет-ресурс «Генерация псевдослучайных чисел» http://voodoo.h1.ru/

И.М.Соболь "Численные методы Монте-Карло",М.,1973

Заключение

В отличие от аналитических методов, ищущих решение в виде ряда по собственным функциям, методы Монте-Карло ищут решения в виде статистических сумм. Для их применения достаточно описания вероятностного процесса и не обязательна его формулировка в виде интегрального уравнения; оценка погрешности чрезвычайно проста, их точность слабо зависит от размерности пространства. В этом я убедился, проведя опыты для решения двух простых задач. Результаты опытов показали свою точность, поэтому с помощью метода Монте-Карло решаются многие сложные задачи, которые очень сложно или не возможно решить другими методами.

Задачи, решаемые методом Монте-Карло: расчет системы массового обслуживания; расчет качества и надежности изделий; теория передачи сообщений; вычисление определенного интеграла; задачи вычислительной математики; задачи нейтронной физики; моделирования дискретных и непрерывных случайных величин; моделирования случайных процессов и полей; вычисления многомерных интегралов и другие.

Список использованных источников

1. И.М.Соболь «Метод Монте-Карло», М., 1985

2. Интернет-ресурс «Предыстория и определение метода Монте-Карло» http://armgeo.narod.ru/GIS/Learning/Monte-Carlo_2/Page01.htm

3. Интернет-ресурс «Метод Монте-Карло» http://u.pereslavl.ru/~gene/probset/prob13.koi8.html

4. Интернет-ресурс «Метод Монте-Карло» http://www.nnspu.ru/Exponenta_Ru/educat/systemat/boziev/13.asp.htm

5. Интернет-ресурс «Вундеркинд» http://inf.1september.ru/2001/leto/stend/Vynderkind.htm

6. «TURBO PASCAL ДЛЯ ШКОЛЬНИКОВ» издание третье дополненное, В.Б.Попов

7. Интернет-ресурс «Метод Монте-Карло» http://apollyon1986.narod.ru/docs/TViMS/NP/lekziitv/lekziya17.htm

8. Интернет-ресурс «Генерация псевдослучайных чисел» http://voodoo.h1.ru/

9. И.М.Соболь «Численные методы Монте-Карло», М., 1973