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

Размещено на http://www.allbest.ru/

Контрольная работа

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



Содержание

Введение

1. Общие сведения про метод Монте-Карло

1.1 Общая схема метода

1.2 Рождение метода Монте-Карло

1.3 Интегрирование методом Монте-Карло

2. Моделировании метода Монте-Карло

2.1 Геометрический алгоритм Монте-Карло интегрирования



Введение

Предложена методическая разработка темы с целью продемонстрировать насколько описываемый метод является мощным и универсальным инструментом для решения различных задач во многих областях знаний. Тема моделирования обычно изучается в школе на примере адекватного представления процессов (например, движения) по выбранным приближенным уравнениям. Статистическое моделирование, наоборот, не предполагает изначально знание математических связей и позволяет получить их на основе многократного наблюдения (компьютерной генерации) возможных событий в представленной модели.

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

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



1 Раздел. Общие сведения про метод Монте-Карло

1.1 Общая схема метода

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

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

Закон больших чисел «разыгрываемых» историй утверждает, что среднее арифметическое полученных в каждом розыгрыше значений исследуемой величины имеет предельное искомое значение (в нашей задаче оно равно 1/2).

Это вероятностная сходимость, т.е. чем больше историй, тем достоверней можно утверждать, что наш результат близок к истинному. Для задач с элементами неопределенности - а в реальном мире все задачи такие - это даже естественно. Погрешность определения предельного значения пропорциональна 1/vN. Таким образом, для увеличения точности результата на один порядок, требуется разыграть в 100 раз больше историй. «Разумно» число историй первоначально задавать порядка 10000.

Следовательно, требуется получать много случайных чисел так, чтобы переход от одного числа к другому определялся простыми правилами, но чтобы сами числа “производили впечатление случайности” (их называют поэтому псевдослучайными числами). Например, для выбора последовательности случайных цифр можно взять дробную часть числа пи (р = 3.14159265358979323846264338327950288 4197169399375105820974944592307816406286208998628034825342117… Представляет интерес обратное утверждение: возможно ли, что для любой конечной, наперед заданной последовательности цифр есть ее вложение в бесконечном представлении числа р). Данный способ, однако, мало приемлем для программирования. Как правило, при решении задач методом Монте-Карло используются процедуры, которые с помощью рекуррентных формул генерируют случайные числа, равномерно распределенные на промежутке [0, 1]. В Pascal для этого используется стандартная функция RANDOM. Для отладки программы бывает важно уметь воспроизвести псевдослучайные числа, а для генерации другой последовательности случайных чисел используется процедура RANDOMIZE.

Очень полезным для понимания данного метода является моделирование игровых вероятностных ситуаций (бросание монеты или кубика, блуждания). Именно «игровая» или связанная с чем-то знакомым (известным, «бытовым») формулировка задачи помогает лучше усвоить метод, осмыслить понятие вероятности.

Пример 1. (Районная олимпиада ).

Три игрока (с номерами 1, 2 и 3), имеющие изначально X, Y и Z жетонов соответственно, играют в следующую игру. В каждом раунде каждый игрок ставит на кон один жетон. Затем бросают кубик, на котором цифры 4, 5, 6 заменены на 1, 2 и 3. При выпадении числа i игрок с номером i забирает с кона все три жетона. Игра заканчивается, когда кто-нибудь из игроков проигрывает все жетоны. Введем функцию f(X, Y, Z), как среднюю длительность игры (среднее количество раундов) при заданных начальных капиталах X, Y, Z. Например, f(2, 2, 2) = 2. Ваша задача состоит в том, чтобы определить эту функцию. Для этого необходимо смоделировать игру на компьютере, накопить экспериментальные результаты, проанализировать их, а затем выдвигать гипотезы о виде функции f, проверять их для разных входных значений, и, отбросив неподходящие, найти решение.

Моделирование игры не вызывает трудности (программа приведена ниже). Также очевидно, что вид функции симметричен относительно порядка задания входных параметров f(X, Y, Z) = f(Y, X, Z) и т.д. Сложность задачи заключается в нахождении вида функции f(X, Y, Z) = X · Y · Z / (X + Y + Z - 2), так как результаты моделирования определяются не точно.

var

i, n, Rounds: LongInt;

x, y, z, j: Integer;

a: array[0..2] of Integer;

begin

Write('x, y, z натуральные: '); ReadLn(x, y, z);

Write('Число историй (игр): '); ReadLn(n);

Rounds:=0; {число раундов в одной игре}

Randomize;

for i:=1 to n do {разыгрываем n историй развития начальной ситуации}

begin

a[0]:=x; a[1]:=y; a[2]:=z;

while a[0]*a[1]*a[2]<>0 do {моделируем игру, пока у всех игроков есть жетоны}

begin

Inc(Rounds);

for j:=0 to 2 do Dec(a[j]); {все игроки ставят по одному жетону}

Inc(a[Random(3)], 3); {а победитель берет все три жетона}

end;

end;

WriteLn('f(x,y,z) = ', Rounds/n:0:3); {среднее количество раундов}

end.

Данная задача достаточно хорошо характеризует метод Монте-Карло, а именно:

Идею метода

- ожидаемый результат игры может быть оценен усреднением результатов большого числа игр (это число так и называется - математическим ожиданием или средним значением).

То есть результат приближенно равен числу

,

где x_i - результат игры i, а N- число всех проведенных игр (испытаний)

Достоинство метода

- незнание a priori (до опыта) функциональных зависимостей исследуемой задачи в целом, выявление этих зависимостей a posteriori (после опыта).

Недостатки метода

- неопределенное время расчета (варианты примера 1 при больших числах X, Y, Z);

- приближенное вычисление результата.

Последний недостаток компенсируется тем, что с использованием данного метода вместе со значением может одновременно определяться и его погрешность по формулам:



При больших N формулу можно упростить:

где

В пределах [ - , + ] с достоверностью 68.27% находится искомая величина, а в пределах ± 2 или ± 3 достоверность уже 95.45% и 99.73% соответственно. Поэтому метод по праву называют порой прецизионным или точным в смысле, что известна точность рассчитываемых величин, и это может служить точкой отсчета для проверки программ, использующих другие приближенные методы.

Иногда, чтобы избежать потери значащих цифр при суммировании, среднее значение определяется в программе после каждого испытания по формуле:

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

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

Задача 1. «Лучшее пари для простаков». (Районная олимпиада 1997).

Игрок A выбирает комбинацию из цифр 0 и 1 длиной 3 знака (например, 001). Игрок B выбирает свою комбинацию (отличную от игрока A). Подбрасывается монета и записываются результаты бросания (например, 101101..., где 0 обозначает «орел», а 1 -- «решка»). Игра прекращается в тот момент, когда в последовательности цифр на конце возникает комбинация, выбранная A или B (побеждает A или B соответственно). Игра повторяется.

а) Оценить шансы на выигрыш каждого из игроков R(A,B) (т.е. отношение числа выигрышей игрока B к числу выигрышей игрока A).

б) Для выбранной игроком A комбинации определить такую комбинацию для игрока B, которая ему дает больше шансов на выигрыш.

Ниже представлена таблица значений R(A,B) для всевозможных выбранных игроками A и B исходных комбинаций при «неограниченном продолжении» игры (выделены наиболее выигрышные ситуации для игрока B).

Пари является беспроигрышным (!) для игрока B. Парадокс заключается в том, что какую бы комбинацию цифр не выбрал игрок A, его соперник B может выбрать другую комбинацию, которая ему дает больше шансов на выигрыш.

Таблица R(A,B)



Указание. При решении задачи полученные результаты по пункту a) не будут совпадать с данными из таблицы, так как число опытов ограничено, тем не менее, позволяют дать качественный ответ по пункту б)

Метод Монте-Карло используется для определения вероятности наступления какого-либо события.

Задача 2.

Пусть дана ось с отмеченными на ней целочисленными точками. Предположим, что Чиполлино спрятался в точке 0, в точке N находится пропасть, и сыщик Моркоу находится в точке k (0 < k < N). Сыщик ищет Чиполлино случайным образом, блуждая по соседним целочисленным точкам. Если он попадет в точку 0, то найдет Чиполлино, а если попадет в точку N, то свалится в пропасть. С какой вероятностью сыщик найдет Чиполлино?

Под вероятностью какого-либо события (P) мы будем понимать предельное значение частоты события, а именно, отношения числа успешных (приведших к появлению данного события) испытаний (N_у) к общему числу проведенных испытаний (N), то есть P » N_у / N. Чем больше мы проведем испытаний, тем точнее (в идеале) мы определяем численное значение вероятности. Очевидно, что вероятность P удовлетворяет условию: 0 Ј P Ј 1.

Указание. Смоделируйте многократный поиск сыщика из точки k, доля удачных попыток от общего их числа дает приближенную оценку искомой вероятности. На основании этой оценки сформулируйте простую формулу для нахождения вероятности события (обозначим ее P₀(k)), указанного в задаче.

Данную задачу можно решить точно, используя рекуррентную формулу:

P₀(k) = P₀(k-1)/2 + P₀(k+1)/2 при очевидных условиях, что P₀(0) = 1 и P₀(N)=0, однако использовать рекурсию в такой форме неприемлемо, так как глубина рекурсии неограниченна, что ведет к переполнению стека и краху программы.

Упражнение 1.

Выведите рекуррентную зависимость P₀(k+1) от P₀(k), начиная с k = 0 и, используя известное значение P₀(N), обратным ходом получите общее выражение для P₀(k).

Задача 3.

Пусть имеется “однорукий бандит” - игровой автомат с ручкой, которой его запускают для игры. Считаем (для упрощения), что игра будет типа “в орлянку”, и игрок имеет начальный капитал в одну монету. Игра ведется до тех пор, пока игрок не обанкротится или выиграет Nмонет. Промоделировать игру для N=10, определить вероятность (шансы) игрока “сорвать указанный куш” и объяснить, почему автомат назвали “бандитом”.

Задача о разорении игрока аналогична задачи блуждания по отрезку [0, N] с той лишь разницей, что требуется определить вероятность P_N(k) достичь точки N, находясь в точке k=1. Образно говоря, эти модели “связаны одной цепью”. Последовательность испытаний, в которой каждое следующее испытание зависит только от исхода предыдущего, называется цепью Маркова. Многие реальные явления (например, броуновское движение частиц, обслуживание телефонных линий) описываются данными вероятностными моделями /2/.

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

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

Пример 2. (Областная олимпиада 2001).

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

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

Переформулируем условие задачи. Опишем квадрат около одной из окружностей (например, меньшего радиуса). Будем случайным образом кидать точки в этот квадрат. При достаточно большом их количестве ($n$) они равномерно распределятся по площади квадрата. Часть из них (m) попадет в область пересечения трех окружностей. Можно ожидать, что отношение m/$n$ имеет конечный предел, равный отношению искомой площади к площади описанного квадрата (см. Упражнение 2).

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

label

NotInCircle;

var

i, n, m: LongInt;

j: Integer;

x, y, r, rr: array[1..3] of Real;

xp, yp, xmin, ymin, d: Real;

begin

for j:=1 to 3 do {вводим координаты центра и радиус трех окружностей}

begin

Write(j, '-я окружность (x y r): ');

ReadLn(x[j], y[j], r[j]);

rr[j]:=Sqr(r[j]); {вычислим квадраты радиусов - они будут часто использоваться}

end;

Write('Количество историй: '); ReadLn(n);

xmin:=x[1]- r[1]; {опишем квадрат около первой окружности}

ymin:=y[1]- r[1];

d:=r[1]*2;

m:=0;

Randomize;

for i:=1 to n do {в цикле по числу историй}

begin

xp:=Random*d+xmin; {бросаем случайным образом}

yp:=Random*d+ymin; {точки в выбранный квадрат}

for j:=1 to 3 do {проверяем, попадает ли точка в каждый круг}

if Sqr(xp-x[j])+Sqr(yp-y[j]) > rr[j] then goto NotInCircle;

Inc(m); {считаем количество точек, попавших сразу во все три круга}

NotInCircle:

end;

WriteLn('S = ', Sqr(d)*m/n:0:3); {результат, тем точнее, чем больше историй}

end.

Задача 4. Два цилиндра одинакового радиуса R=1 пересекаются под прямым углом. Найти объем V их общей части.

Указание. В журнале “Квант” (№2, 1988 г.) приводится геометрический формализм решения задачи: V = 16R³/3.

Задача 5. Оценить чего больше: несократимых или сократимых дробей.

Фривольное условие задачи предполагает строгую формулировку: какова вероятность того, что наудачу взятая дробь несократима?

Ответ достаточно сложен и равен 6/р² = 0.6079... (Н.Я. Виленкин. В таинственном мире бесконечных рядов. Квант №10, 1989)

Сформулируем условие иначе. Рассмотрим несократимые дроби вида a/b, где 1Ј a, b Ј.N. Количество их f(N). Нужно найти предел f(N) / N²для больших чисел N. Выберем случайные натуральные числа (не превосходящие фиксированного достаточно большого числа N) для числителя и знаменателя дроби. Повторяем «эксперимент» $n$ раз, подсчитывая количество (m) несократимых дробей, используя алгоритм Эвклида для нахождения наибольшего общего делителя числителя и знаменателя. Отношение m/$n$ дает оценку доли несократимых дробей.

Строго говоря, мы должны доказать, что характер соотношения не изменится при увеличении числа N. Мы же будем это предполагать во всех задачах, так как математические критерии, гарантирующие сходимость решения, известны в редких случаях. Сходимость можно проверять для различного числа испытаний (например, увеличивая в 10 раз). Важно, чтобы число историй по закону было “большим”.

Упражнение 2.

Свойство равномерного распределения случайных чисел на отрезке [0,1] означает, что вероятность попасть очередному числу, сгенерированному ДСЧ, в любой выбранный отрезок из [0,1] равна длине этого отрезка (проверьте моделированием).

Поэтому смоделировать событие (обозначим его C), реализующееся с вероятностью P можно так: на единичном отрезке выбирается отрезок длины P, и если случайная точка попала в заданный отрезок, то считаем, что событие C произошло. Если есть несколько независимых событий, то им следует сопоставить непересекающиеся отрезки с длинами, соответствующими вероятностям событий.

Равномерность распределения точек по отрезку справедлива для большого числа сгенерированных случайных точек. Так, если мы разобьем единичный отрезок на k равных частей, то необходимо сгенерировать более 10·k случайных чисел, чтобы они распределились в каждой части примерно одинаково. Для k случайных точек получим совершенно иную картину распределения.

Пример 3.

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

Указание. Пронумеруем клетки шахматной доски от 0 до 63. Случайное попадание зерна на какую-либо клетку моделируем случайным выбором клетки с помощью датчика случайных чисел RANDOM(64).

const

Iterations = 10000;

var

Board: array[0..63] of LongInt;

Count: array[0..63] of LongInt;

i, j: LongInt;

begin

Randomize;

FillChar(Count, SizeOf(Count), 0);

for i:=1 to Iterations do

begin

FillChar(Board, SizeOf(Board), 0);

for j:=0 to 63 do Inc(Board[Random(64)]);

for j:=0 to 63 do Inc(Count[Board[j]]);

end;

for j:=0 to 10 do

WriteLn(j:2, ' ', Count[j]/Iterations:8:5);

end.

В результате моделирования оказывается, что вероятнее всего: 23 клетки останутся пустыми, на 24 клетках будет по одному зерну, на 12 клетках - по два, на 4 клетках - по три, на одной клетке - четыре.

Генератор случайных чисел можно использовать для построения различных геометрических объектов.

Приведем алгоритм построения простейшего лабиринта. Лабиринты служат основой многочисленных игровых программ и олимпиадных задач.

На плоскости чертится прямоугольник, задающий границы лабиринта. Внутри прямоугольника выбирается точка (координаты которой задаются случайным образом), не лежащая на ранее построенных границах. От точки в случайном направлении (вправо, влево, вверх, вниз) рисуется линия границы до пересечения с какой-либо другой линией. Чтобы проходы в лабиринте были одинаковой ширины, координаты точки задаются с заранее выбранным шагом (например, на целочисленной сетке). Построение лабиринта прекращается по нажатию клавиши <ESC> или когда выбраны все допустимые точки. Такой алгоритм построения не дает циклических путей в лабиринте и, следовательно, в нем всегда можно найти выход. На рис. 1 приведен вариант сгенерированного лабиринта.

Пример 4.

Построим лабиринт, используя приведенный выше алгоритм.

uses

Graph, Crt;

const

Step = 20; {шаг - размер клетки в пикселах}

Width = 30; {ширина лабиринта в клетках}

Height = 20; {высота лабиринта в клетках}

dx: array[0..3] of Integer = (1, 0, -1, 0); {смещения по горизонтали}

dy: array[0..3] of Integer = (0, -1, 0, 1); {и вертикали для четырех направлений}

Рис. 1



var

Driver, Mode: Integer;

x, y, n: Integer;

Wall: Boolean;

begin

Driver:=Vga; Mode:=VgaHi;

InitGraph(Driver, Mode, '');

{очертим границы лабиринта}

Rectangle(0, 0, Width*Step, Height*Step);

Randomize;

repeat

x:=Random(Width)*Step; {выбираем случайную точку}

y:=Random(Height)*Step;

if GetPixel(x, y)<>0 then Continue; {если она лежит на стене, пробуем заново}

MoveTo(x, y);

n:=Random(4); {выбираем случайное направление}

repeat {рисуется линия от текущей точки}

Inc(x, dx[n]*Step); {с заданным шагом и направлением}

Inc(y, dy[n]*Step);

Wall:=(GetPixel(x, y)<>0); {до ближайшей стенки}

LineTo(x, y);

until Wall;

until KeyPressed;

ReadKey;

CloseGraph;

end.



1.2 Рождение метода Монте-Карло

Сначала Энрико Ферми в 1930-х годах в Италии, а затем Джон фон Нейман и Станислав Улам в 1940-х в Лос-Аламосе предположили, что можно использовать связь между стохастическими процессами и дифференциальными уравнениями «в обратную сторону». Они предложили использовать стохастический подход дляаппроксимации многомерных интегралов в уравнениях переноса, возникших в связи с задачей о движении нейтрона в изотропной среде.

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

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

Годом рождения метода Монте-Карло считается 1949 год, когда в свет выходит статья Метрополиса и Улама «Метод Монте-Карло». Название метода происходит от названия коммуны в княжестве Монако, широко известного своими многочисленными казино, поскольку именно рулетка является одним из самых широко известныхгенераторов случайных чисел. Станислав Улам пишет в своей автобиографии «Приключения математика», что название было предложено Николасом Метрополисом в честь его дяди, который был азартным игроком.

Дальнейшее развитие и современность

В 1950-х годах метод использовался для расчётов при разработке водородной бомбы.

Основные заслуги в развитии метода в это время принадлежат сотрудникам лабораторий ВВС США и корпорации RAND. Одними из первых Метод Монте-Карло для расчёта ливней частиц применили советские физики А. А. Варфоломеев и И. А. Светлолобов.

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

Иногда можно, пожертвовав точностью, найти алгоритм, сложность которого растёт медленнее, но есть большое количество задач, для которого этого нельзя сделать (например, задача определения объёма выпуклого тела вn-мерном евклидовом пространстве) и метод Монте-Карло является единственной возможностью для получения достаточно точного ответа за приемлемое время.

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



1.3 Интегрирование методом Монте-Карло

Рисунок 2. Численное интегрирование функции детерминистическим методом

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

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



2. Моделировании метода Монте-Карло

Обычный алгоритм Монте-Карло интегрирования

Предположим, требуется вычислить определённый интеграл

Рассмотрим случайную величину , равномерно распределённую на отрезке интегрирования . Тогда также будет случайной величиной, причём еёматематическое ожидание выражается как

где -- плотность распределения случайной величины , равная на участке .

Таким образом, искомый интеграл выражается как

.

Но математическое ожидание случайной величины можно легко оценить, смоделировав эту случайную величину и посчитав выборочное среднее.



Итак, бросаем точек, равномерно распределённых на , для каждой точки вычисляем . Затем вычисляем выборочное среднее:

.

В итоге получаем оценку интеграла:

Точность оценки зависит только от количества точек .

Этот метод имеет и геометрическую интерпретацию. Он очень похож на описанный выше детерминистический метод, с той разницей, что вместо равномерного разделения области интегрирования на маленькие интервалы и суммирования площадей получившихся «столбиков» мы забрасываем область интегрирования случайными точками, на каждой из которых строим такой же «столбик», определяя его ширину как

, и суммируем их площади.



2.1 Геометрический алгоритм Монте-Карло интегрирования

Рисунок 3. Численное интегрирование функции методом Монте-Карло

Для определения площади под графиком функции можно использовать следующий стохастический алгоритм:

· ограничим функцию прямоугольником (n-мерным параллелепипедом в случае многих измерений), площадь которого можно легко вычислить; любая сторона прямоугольника содержит хотя бы 1 точку графика функции, но не пересекает его;

· «набросаем» в этот прямоугольник (параллелепипед) некоторое количество точек ( штук), координаты которых будем выбирать случайным образом;

· определим число точек ( штук), которые попадут под график функции;

· площадь области, ограниченной функцией и осями координат, даётся выражением

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

Использование выборки по значимости.

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

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

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

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

Как выполняется моделирование по методу Монте-Карло

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

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

Нормальное распределение (или « гауссова кривая »). Чтобы описать отклонение от среднего, пользователь определяет среднее или ожидаемое значение и стандартное отклонение. Значения, расположенные посредине, рядом со средним, характеризуются наиболее высокой вероятностью. Нормальное распределение симметрично и описывает множество обычных явлений -- например, рост людей. К примерам переменных, которые описываются нормальными распределениями, относятся темпы инфляции и цены на энергоносители.

Логнормальное распределение. Значения имеют положительную асимметрию и в отличие от нормального распределения несимметричны. Такое распределение используется для отражения величин, которые не опускаются ниже нуля, но могут принимать неограниченные положительные значения. Примеры переменных, описываемых логнормальными распределениями, включают стоимость недвижимого имущества, цены на акции и нефтяные запасы.

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

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

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

Дискретное распределение. Пользователь определяет конкретные значения из числа возможных, а также вероятность получения каждого из них. Примером может служить результат судебного процесса: 20% вероятность положительного решения, 30% вероятность отрицательного решения, 40% вероятность соглашения сторон и 10% вероятность аннулирования судебного процесса.

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

Моделирование по методу Монте-Карло имеет ряд преимуществ по сравнению с детерминистским анализом, или анализом « по точечным оценкам»:

· Вероятностные результаты. Результаты демонстрируют не только возможные события, но и вероятность их наступления.

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

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

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

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

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

Размещено на Allbest.ru

...