Метод монте карло в физических процессах пример. Метод монте карло

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

Метод Монте-Карло

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

Задача 1. Найти значение интеграла:

На рис. 1.1 представлен график функции f (x ). Вычислить значение интеграла этой функции - значит, найти площадь под этим графиком.

Рис. 1.1

Ограничиваем кривую сверху, справа и слева. Случайным образом распределяем точки в прямоугольнике поиска. Обозначим через N 1 количество точек, принятых для испытаний (то есть попавших в прямоугольник, эти точки изображены на рис. 1.1 красным и синим цветом), и через N 2 - количество точек под кривой, то есть попавших в закрашенную площадь под функцией (эти точки изображены на рис. 1.1 красным цветом). Тогда естественно предположить, что количество точек, попавших под кривую по отношению к общему числу точек пропорционально площади под кривой (величине интеграла) по отношению к площади испытуемого прямоугольника. Математически это можно выразить так:

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

Фрагмент алгоритма метода Монте-Карло в виде блок-схемы выглядит так, как показано на рис. 1.2

Рис. 1.2

Значения r 1 и r 2 на рис. 1.2 являются равномерно распределенными случайными числами из интервалов (x 1 ; x 2) и (c 1 ; c 2) соответственно.

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

Схема использования метода Монте-Карло при исследовании систем со случайными параметрами

Построив модель системы со случайными параметрами, на ее вход подают входные сигналы от генератора случайных чисел (ГСЧ), как показано на рис. 1.3 ГСЧ устроен так, что он выдает равномерно распределенные случайные числа r рр из интервала . Так как одни события могут быть более вероятными, другие - менее вероятными, то равномерно распределенные случайные числа от генератора подают на преобразователь закона случайных чисел (ПЗСЧ), который преобразует их в заданный пользователем закон распределения вероятности, например, в нормальный или экспоненциальный закон. Эти преобразованные случайные числа x подают на вход модели. Модель отрабатывает входной сигнал x по некоторому закону y = ц (x ) и получает выходной сигнал y , который также является случайным.

статистическое моделирование случайная величина

Рис. 1.3

В блоке накопления статистики (БНСтат) установлены фильтры и счетчики. Фильтр (некоторое логическое условие) определяет по значению y , реализовалось ли в конкретном опыте некоторое событие (выполнилось условие, f = 1) или нет (условие не выполнилось, f = 0). Если событие реализовалось, то счетчик события увеличивается на единицу. Если событие не реализовалось, то значение счетчика не меняется. Если требуется следить за несколькими разными типами событий, то для статистического моделирования понадобится несколько фильтров и счетчиков N i . Всегда ведется счетчик количества экспериментов - N .

Далее отношение N i к N , рассчитываемое в блоке вычисления статистических характеристик (БВСХ) по методу Монте-Карло, дает оценку вероятности p i появления события i , то есть указывает на частоту его выпадения в серии из N опытов. Это позволяет сделать выводы о статистических свойствах моделируемого объекта.

Например, событие A совершилось в результате проведенных 200 экспериментов 50 раз. Это означает, согласно методу Монте-Карло, что вероятность совершения события равна: p A = 50/200 = 0.25. Вероятность того, что событие не совершится, равна, соответственно, 1 - 0.25 = 0.75.

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

При большом количестве опытов N частота появления события, полученная экспериментальным путем, стремится к значению теоретической вероятности появления события.

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

Заметим, что оценивание ведут по худшей из частот. Это обеспечивает достоверный результат сразу по всем снимаемым характеристикам модели.

Пример 1. Решим простую задачу. Какова вероятность выпадения монеты орлом кверху при падении ее с высоты случайным образом?

Начнем подбрасывать монетку и фиксировать результаты каждого броска (см. табл. 1.1).

Таблица 1.1.

Результаты испытаний бросания монеты

Будем подсчитывать частость выпадения орла как отношение количества случаев выпадения орла к общему числу наблюдений. Посмотрите в табл. 1.1 случаи для N = 1, N = 2, N = 3 - сначала значения частости нельзя назвать достоверными. Попробуем построить график зависимости P о от N - и посмотрим, как меняется частость выпадения орла в зависимости от количества проведенных опытов. Разумеется, при различных экспериментах будут получаться разные таблицы и, следовательно, разные графики. На рис. 1.4 показан один из вариантов.

Рис. 1.4

Сделаем некоторые выводы.

• 1. Видно, что при малых значениях N , например, N = 1, N = 2, N = 3 ответу вообще доверять нельзя. Например, P о = 0 при N = 1, то есть вероятность выпадения орла при одном броске равна нулю! Хотя всем хорошо известно, что это не так. То есть пока мы получили очень грубый ответ. Однако, посмотрите на график: в процессе накопления информации ответ медленно, но верно приближается к правильному (он выделен пунктирной линией). К счастью, в данном конкретном случае правильный ответ нам известен: в идеале, вероятность выпадения орла равна 0.5 (в других, более сложных задачах, ответ нам, конечно, будет неизвестен). Допустим, что ответ нам надо знать с точностью е = 0.1. Проведем две параллельные линии, отстоящие от правильного ответа 0.5 на расстояние 0.1 (см. рис. 1.4). Ширина образовавшегося коридора будет равна 0.2. Как только кривая P о (N ) войдет в этот коридор так, что уже никогда его не покинет, можно остановиться и посмотреть, для какого значения N это произошло. Это и есть экспериментально вычисленное критическое значение необходимого количества опытов N кр э для определения ответа с точностью е = 0.1; е -окрестность в наших рассуждениях играет роль своеобразной трубки точности. Заметьте, что ответы P о (91), P о (92) и так далее уже не меняют сильно своих значений (см. рис. 1.4); по крайней мере, у них не изменяется первая цифра после запятой, которой мы обязаны доверять по условиям задачи.
• 2. Причиной такого поведения кривой является действие центральной предельной теоремы . Пока здесь мы сформулируем ее в самом простом варианте "Сумма случайных величин есть величина неслучайная". Мы использовали среднюю величину P о, которая несет в себе информацию о сумме опытов, и поэтому постепенно эта величина становится все более достоверной.
• 3. Если проделать еще раз этот опыт сначала, то, конечно, его результатом будет другой вид случайной кривой. И ответ будет другим, хотя примерно таким же. Проведем целую серию таких экспериментов (см. рис. 1.5). Такая серия называется ансамблем реализаций. Какому же ответу в итоге следует верить? Ведь они, хоть и являются близкими, все же разнятся. На практике поступают по-разному. Первый вариант - вычислить среднее значение ответов за несколько реализаций (см. табл. 1.2).

Рис. 1.5

Мы поставили несколько экспериментов и определяли каждый раз, сколько необходимо было сделать опытов, то есть N кр э. Было проделано 10 экспериментов, результаты которых были сведены в табл. 1.2 По результатам 10-ти экспериментов было вычислено среднее значение N кр э.

Таблица 1.2.

Экспериментальные данные необходимого количества бросков монеты для достижения точности е

Таким образом, проведя 10 реализаций разной длины, мы определили, что достаточно в среднем было сделать 1 реализацию длиной в 94 броска монеты.

Еще один важный факт. Внимательно рассмотрите график на рис.21.5 На нем нарисовано 100 реализаций - 100 красных линий. Отметьте на нем абсциссу N = 94 вертикальной чертой. Есть какой-то процент красных линий, которые не успели пересечь е -окрестность, то есть (P эксп - е ? P теор? P эксп + е ), и войти в коридор точности до момента N = 94. Обратите внимание, таких линий 5. Это значит, что 95 из 100, то есть 95%, линий достоверно вошли в обозначенный интервал.

Таким образом, проведя 100 реализаций, мы добились примерно 95% -ного доверия к полученной экспериментально величине вероятности выпадения орла, определив ее с точностью 0.1.

Для сравнения полученного результата вычислим теоретическое значение N кр т теоретически. Однако для этого придется ввести понятие доверительной вероятности Q F , которая показывает, насколько мы готовы верить ответу.

Например, при Q F = 0.95 мы готовы верить ответу в 95% случаев из 100. Имеет вид: N кр т = k (Q F ) · p · (1 - p ) /е 2 , где k (Q F ) - коэффициент Лапласа, p - вероятность выпадения орла, е - точность (доверительный интервал). В табл. 1.3 показаны значения теоретической величины количества необходимых опытов при разных Q F (для точности е = 0.1 и вероятности p = 0.5).

Таблица 1.3.

Теоретический расчет необходимого количества бросков монеты для достижения точности е = 0.1 при вычислении вероятности выпадения орла

Как видите, полученная нами оценка длины реализации, равная 94 опытам очень близка к теоретической, равной 96. Некоторое несовпадение объясняется тем, что, видимо, 10 реализаций недостаточно для точного вычисления N кр э. Если вы решите, что вам нужен результат, которому следует доверять больше, то измените значение доверительной вероятности. Например, теория говорит нам, что если опытов будет 167, то всего 1-2 линии из ансамбля не войдут в предложенную трубку точности. Но имейте в виду, количество экспериментов с ростом точности и достоверности растет очень быстро.

Второй вариант, используемый на практике - провести одну реализацию и увеличить полученное для нее N кр э в 2 раза . Это считают хорошей гарантией точности ответа (см. рис. 1.6).

Рис. 1.6. Иллюстрация экспериментального определения N кр э по правилу "умножь на два"

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

Рис. 1.7

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

Таблица 1.4.

Теоретическая зависимость количества экспериментов, необходимых для обеспечения заданной точности при Q F = 0.95

Построим по табл. 1.4 график зависимости N кр т (е ) (см. рис. 1.8).

Рис. 1.8 Зависимость числа экспериментов, требуемых для достижения заданной точности е при фиксированном Q F = 0.95

Итак, рассмотренные графики подтверждают приведенную выше оценку:

Заметим, что оценок точности может быть несколько.

Пример 2. Нахождение площади фигуры методом Монте-Карло. Определите методом Монте-Карло площадь пятиугольника с координатами углов (0, 0), (0,10), (5, 20), (10,10), (7, 0).

Нарисуем в двухмерных координатах заданный пятиугольник, вписав его в прямоугольник, чья площадь, как нетрудно догадаться, составляет (10 - 0) · (20 - 0) = 200 (см. рис. 1.9).

Рис. 1.9

Используем таблицу случайных чисел для генерации пар чисел R , G , равномерно распределенных в интервале от 0 до 1. Число R X (0 ? X ? 10), следовательно, X = 10 · R . Число G будет имитировать координату Y (0 ? Y ? 20), следовательно, Y = 20 · G . Сгенерируем по 10 чисел R и G и отобразим 10 точек (X ; Y ) на рис. 1.9 и в табл. 1.5

Таблица 1.5.

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

Статистическая гипотеза заключается в том, что количество точек, попавших в контур фигуры, пропорционально площади фигуры: 6: 10 = S : 200. То есть, по формуле метода Монте-Карло, получаем, что площадь S пятиугольника равна: 200 · 6/10 = 120.

Проследим, как менялась величина S от опыта к опыту (см. табл. 1.6).

Таблица 1.6.

Оценка точности ответа

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

Рис. 1.10 Иллюстрация процесса сходимости определяемого экспериментально ответа к теоретическому результату

Лекция 2. Генераторы случайных чисел

В основе метода Монте-Карло (см. Лекцию 1. Статистическое моделирование) лежит генерация случайных чисел, которые должны быть равномерно распределены в интервале (0;1).

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

Математическое ожидание m r и дисперсия D r такой последовательности, состоящей из n случайных чисел r i , должны быть следующими (если это действительно равномерно распределенные случайные числа в интервале от 0 до 1):

Если пользователю потребуется, чтобы случайное число x находилось в интервале (a ; b ), отличном от (0;

• 1), нужно воспользоваться формулой x = a + (b - a ) · r , где r - случайное число из интервала (0;
• 1). Законность данного преобразования демонстрируется на рис. 2.1

Рис. 2.1

1) в интервал (a; b)

Теперь x - случайное число, равномерно распределенное в диапазоне от a до b .

За эталон генератора случайных чисел (ГСЧ) принят такой генератор, который порождает последовательность случайных чисел с равномерным законом распределения в интервале (0;

• 1). За одно обращение данный генератор возвращает одно случайное число. Если наблюдать такой ГСЧ достаточно длительное время, то окажется, что, например, в каждый из десяти интервалов (0; 0.1), (0.1; 0.2), (0.2; 0.3), …, (0.9;
• 1) попадет практически одинаковое количество случайных чисел - то есть они будут распределены равномерно по всему интервалу (0;
• 1). Если изобразить на графике k = 10 интервалов и частоты N i попаданий в них, то получится экспериментальная кривая плотности распределения случайных чисел (см. рис. 2.2).

Рис. 2.2

Заметим, что в идеале кривая плотности распределения случайных чисел выглядела бы так, как показано на рис. 2.3. То есть в идеальном случае в каждый интервал попадает одинаковое число точек: N i = N /k , где N - общее число точек, k - количество интервалов, i = 1, …, k .

Рис. 2.3

Следует помнить, что генерация произвольного случайного числа состоит из двух этапов:

• · генерация нормализованного случайного числа (то есть равномерно распределенного от 0 до 1);
• · преобразование нормализованных случайных чисел r i в случайные числа x i , которые распределены по необходимому пользователю (произвольному) закону распределения или в необходимом интервале.

Генераторы случайных чисел по способу получения чисел делятся на:

• · физические;
• · табличные;
• · алгоритмические.

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

Суть метода состоит в следующем. Для вычисления площади некоторой фигуры, проведем эксперимент: поместим данную фигуру в квадрат и будем наугад бросать точки в этот квадрат. Естественно предполагать, что чем больше площадь фигуры, тем чаще в нее будут попадать точки. Таким образом, можно сделать допущение: при большом числе точек, наугад выбранных внутри квадрата, доля точек, содержащихся в данной фигуре, приближенно равна отношению площади этой фигуры и площади квадрата.

Такой метод приближенного нахождения площадей фигур и носит название метода Монте-Карло.

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

Постановка задачи: для вычисления числа π методом Монте-Карло рассмотрим круг радиуса 1 с центром в точке (1, 1). Круг вписан в квадрат, сторона которого, а=2. Тогда площадь квадрата S квадрата = a 2 = 2 2 = 4.

Решение.

Выбираем внутри квадрата N случайных точек. Выбрать точку означает задать ее координаты – числа x и y.

Обозначим N круга – число точек попавших при этом внутрь круга.

Точка принадлежит квадрату, если 0≤x≤2 и 0≤y≤2.

Если (x-1) 2 +(y-1) 2 ≤ 1, то точка попадает в круг, иначе она находится вне круга. Геометрически очевидно, что

Отсюда

То есть для круга единичного радиуса:

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

Данная формула дает оценку числа π. Чем больше N, тем больше точность этой оценки. Следует заметить, что данный метод вычисления площади будет справедлив только тогда, когда случайные точки будут не просто случайными, а еще и равномерно разбросанными по всему квадрату.

Для моделирования равномерно распределенных случайных чисел в интервале от 0 до 1 в языке программирования Turbo Pascal используется датчик случайных чисел – функция RANDOM, которая выдает последовательность случайных величин, равномерно распределенных от 0 до 1.

Таким образом, суть компьютерного эксперимента заключается в обращении к функции RANDOM для получения N раз координат х и у точки. При этом определяется, попала ли точка с координатами (х ,у ) в круг единичного радиуса. В случае попадания значение величины N круга увеличивается на 1.

Программа:

Program monte_karlo;

var i, n, n1: LongInt; x, y, pi: real; begin Randomize;

WriteLn("Введите количество точек n=");

Readln(n); for i:=1 to n do begin x:=2*Random; y:=2*Random; if sqr(x-1)+sqr(y-1)<=1 then n1:=n1+1; end; pi:=4*n1/n; WriteLn("pi=", pi:15:11); end.

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

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

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

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

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

Общая характеристика метода Монте-Карло

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

Допустим, необходимо вычислить математическое ожидание случайной величины X, подчиняющейся некоторому закону распределения F(x). Для этого в машине реализуют датчик случайных чисел, имеющий данное распределение F(x), и по формуле, которую легко запрограммировать, определяют оценку математического ожидания:

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

Рассмотрим ещё один пример. Производится десять независимых выстрелов по мишени. Вероятность попадания при одном выстреле задана и равна p. Требуется определить вероятность того, что число попаданий будет чётным, т.е. 0, 2, 4, 6, 8, 10. Вероятность того, что число попаданий будет 2k, равна:

откуда искомая вероятность

Если эта формула известна, то можно осуществить физический эксперимент, произведя несколько партий выстрелов (по десять в каждой) по реальной мишени. Но проще выполнить математический эксперимент на вычислительной машине следующим образом. Датчик случайных чисел выдаст в цифровом виде значение случайной величины?, подчиняющейся равномерному закону распределения в интервале . Вероятность неравенства?

Для пояснения целесообразно обратиться к рис. 1, на котором весь набор случайных чисел представляется в виде точек отрезка . Вероятность попадания случайной величины?, имеющей равномерное распределение в интервале , в интервал (где) равна длине этого отрезка, т.е. p. Поэтому на каждом такте моделирования полученное число? сравнивают с заданной вероятностью p. Если?

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

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

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

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

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

Эта идея используется в задачах дискретной оптимизации, которые возникают при управлении. Часто эти задачи сводятся к перебору большого числа вариантов, исчисляемого комбинаторными числами вида N=. Так, задача распределения n видов ресурсов между отраслями для n>3 не может быть точно решена на существующих цифровых вычислительных машинах (ЦВМ) и ЦВМ ближайшего будущего из-за большого объёма перебора вариантов. Однако таких задач возникает очень много в кибернетике, например синтез конечных автоматов. Если искусственно ввести вероятностную модель-аналог, то задача существенно упростится, правда, решение будет приближённым, но его можно получить с помощью современных вычислительных машин за приемлемое время счёта.

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

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

Если y является функцией x, т.е. y=F(x), то и поэтому. Таким образом, для получения последовательности случайных чисел, имеющих заданную функцию распределения F(x), необходимо каждое число y с выхода датчика случайных чисел, который формирует числа с равномерным законом распределения в интервале , подать на нелинейное устройство (аналоговое или цифровое), в котором реализуется функция, обратная F(x), т.е.

Полученная таким способом случайная величина X будет иметь функцию распределения F(x). Рассмотренная выше процедура может быть использована для графического способа получения случайных чисел, имеющих заданный закон распределения. Для этого на миллиметровой бумаге строится функция F(x) и вводится в рассмотрение другая случайная величина Y, которая связана со случайной величиной X соотношением (2) (рис. 2).

Так как любая функция распределения монотонно неубывающая, то

Отсюда следует, что величина Y имеет равномерный закон распределения в интервале , т. к. её функция распределения равна самой величине

Плотность распределения вероятности для Y

Для получения значения X берётся число из таблиц случайных чисел, имеющих равномерное распределение, которое откладывается на оси ординат (рис. 2), и на оси абсцисс считывается соответствующее число X. Повторив неоднократно эту процедуру, получим набор случайных чисел, имеющих закон распределения F(x). Таким образом, основная проблема заключается в получении равномерно распределённых в интервале случайных чисел. Один из методов, который используется при физическом способе получения случайных чисел для ЭВМ, состоит в формировании дискретной случайной величины, которая может принимать только два значения: 0 или 1 с вероятностями

Можно доказать, что случайная величина? * , заключённая в интервале , имеет равномерный закон распределения

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

Вероятность каждого значения (3) равна 2 -k . Эти значения можно получить следующим образом

Случайная величина имеет математическое ожидание

Учитывая, что

и выражение для конечной суммы геометрической прогрессии

получаем:

Аналогично можно определить дисперсию величины:

или, используя формулу (4), получаем:

Согласно формуле (5) оценка величины?* получается смещённой при конечном k. Это смещение особенно сказывается при малом k. Поэтому вместо вводят оценку

Очевидно, что случайная величина? в соответствии с соотношением (3) может принимать значения

I=0,1,2,…, 2 k -1

с вероятностью p=1/2 k .

Математическое ожидание и дисперсию величины? можно получить из соотношений (5) и (6), если учесть (7). Действительно,

Отсюда получаем выражение для среднеквадратичного значения в виде

Напомним, что для равномерно распределённой в интервале величины x имеем

Из формулы (8) следует, что при среднеквадратичное отклонение? квазиравномерной совокупности стремится к. Ниже приведены значения отношения среднеквадратичных значений двух величин? и? в зависимости от числа разрядов, причём величина? имеет равномерное распределение в интервале (табл. 1).

Таблица 1

Из табл. 1 видно, что при k>10 различие в дисперсиях несущественно.

На основании вышеизложенного задача получения совокупности квазиравномерных чисел сводится к получению последовательности независимых случайных величин z i (i=1,2,…, k), каждая из которых принимает значение 0 или 1 с вероятностью 1/2. Различают два способа получения совокупности этих величин: физический способ генерирования и алгоритмическое получение так называемых псевдослучайных чисел. В первом случае требуется специальная электронная приставка к цифровой вычислительной машине, во втором случае загружаются блоки машины.

При физическом генерировании чаще всего используются радиоактивные источники или шумящие электронные устройства. В первом случае радиоактивные частицы, излучаемые источником, поступают на счётчик частиц. Если показание счётчика чётное, то z i =1, если нечётное, то z i =0. Определим вероятность того, что z i =1. Число частиц k, которое испускается за время?t, подчиняются закону Пуассона:

Вероятность чётного числа частиц

Таким образом, при больших??t вероятность P{Z i =1} близка к 1/2.

Второй способ получения случайных чисел z i более удобен и связан с собственными шумами электронных ламп. При усилении этих шумов получается напряжение u(t), которое является случайным процессом. Если брать его значения, достаточно отстоящие друг от друга, так чтобы они были некоррелированы, то величины u(t i) образуют последовательность независимых случайных величин. Обычно выбирают уровень отсечки a и полагают

причём уровень a следует выбрать так, чтобы

Также применяется более сложная логика образования чисел z i . В первом варианте используют два соседних значения u(t i) и u(t i+1), и величина Z i строится по такому правилу:

Если пара u(t i) - a и u(t i+1) - a одного знака, то берётся следующая пара. Требуется определить вероятность при заданной логике. Будем считать, что P {u(t i)>a}=W и постоянная для всех t i . Тогда вероятность события равна по формуле событий A 1 H v . Здесь H v - это вероятность того, что v раз появилась пара одинакового знака

u(t i) - a; u(t i+1) - a. (9)

Поэтому вероятность события A 1 H v

P{A 1 H v }=W (1-W) v .

Это - вероятность того, что после v пар вида (9) появилось событие A 1 . Оно может появиться сразу с вероятностью W (1-W), оно может появиться и после одной пары вида (9) с вероятностью

W (1-W)

и т.д. В результате

Отсюда следует, что если W=const, то логика обеспечивает хорошую последовательность случайных чисел. Второй способ формирования чисел zi состоит в следующем:

W=P {u(t i)>a}=1/2+?.

P{Z i =1}=2W (1-W)=1/2-2? 2 .

Чем меньше?, тем ближе вероятность P{Z i =1} к величине 1/2.

Для получения случайных чисел алгоритмическим путём с помощью специальных программ на вычислительной машине разработано большое количество методов. Так как на ЦВМ невозможно получить идеальную последовательность случайных чисел хотя бы потому, что на ней можно набрать конечное множество чисел, такие последовательности называются псевдослучайными. На самом деле повторяемость или периодичность в последовательности псевдослучайных чисел наступает значительно раньше и обусловливается спецификой алгоритма получения случайных чисел. Точные аналитические методы определения периодичности, как правило, отсутствуют, и величина периода последовательности псевдослучайных чисел определяется экспериментально на ЦВМ. Большинство алгоритмов получается эвристически и уточняется в процессе экспериментальной проверки. Рассмотрение начнём с так называемого метода усечений. Пусть задана произвольная случайная величина u, изменяющаяся в интервале , т.е. . Образуем из неё другую случайную величину

u n =u , (10)

где u используется для определения операции получения остатка от деления числа u на 2 -n . Можно доказать, что величины u n в пределе при имеют равномерное распределение в интервале .

По существу с помощью формулы (10) осуществляется усечение исходного числа со стороны старших разрядов. При оставлении далёких младших разрядов естественно исключается закономерность в числах и они более приближаются к случайным. Рассмотрим это на примере.

Пример 1. Пусть u = 0,10011101… = 1?1/2 + 0?1/2 2 + 0?1/2 3 + 1?1/2 4 + 1?1/2 5 + 1?1/2 6 + 0?1/2 7 + 1?1/2 8 + …

Выберем для простоты n=4. Тогда {u mod 2 -4 } = 0,1101…

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

При проверке качества псевдослучайных чисел прежде всего интересуются длиной отрезка апериодичности и длиной периода (рис. 3). Под длиной отрезка апериодичности L понимается совокупность последовательно полученных случайных чисел? 1 , …, ? L таких, что? i ? j при, но? L+1 равно одному из? k ().

Под длиной периода последовательности псевдослучайных чисел понимается T=L-i+1. Начиная с некоторого номера i числа будут периодически повторяться с этим периодом (рис. 3).

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

Точность метода Монте-Карло

Метод Монте-Карло применяется там, где не требуется высокой точности. Например, если определяют вероятность поражения мишени при стрельбе, то разница между p 1 =0,8 и p 2 =0,805 несущественна. Обычно считается, что метод Монте-Карло позволяет получить точность примерно 0,01-0,05 максимального значения определяемой величины.

Получим некоторые рабочие формулы. Определим по методу Монте-Карло вероятность пребывания системы в некотором состоянии. Эта вероятность оценивается отношением

где M - число пребываний системы в этом состоянии в результате N моделирований. Учитывая выражение для дисперсии величины M/N

и неравенство Чебышёва

Величина

есть ни что иное, как ошибка моделирования по методу Монте-Карло. С помощью формулы (11) можно написать следующую формулу для величины (12):

где p 0 - вероятность невыполнения этой оценки. С помощью частоты M/N может быть получена оценка математического ожидания m x некоторой случайной величины X. Ошибка этой оценки

находится с помощью соотношения

Отсюда видно, что ошибка моделирования находится в квадратичной зависимости от числа реализаций, т.е.

Пример 2. Допустим, что определяется математическое ожидание ошибки x поражения мишени. Процесс стрельбы и поражения моделируется на ЦВМ по методу Монте-Карло. Требуется точность моделирования? = 0,1 м с вероятностью p = 1-p 0 = 0,9 при заданной дисперсии? x = 1 м. Необходимо определить количество моделирований N. По формуле (13) получаем:

При таком количестве реализаций обеспечивается?=0,1 м с вероятностью p=0,9.

Введение

Метод Монте-Карло – это численный метод решения математических задач при помощи моделирования случайных величин.

Датой рождение метода Монте-Карло принято считать 1949 г., когда появилась статья под названием «Метод Монте-Карло» (Н. Метрополис, С. Улам). Создателями этого метода считают американских математиков Дж. Неймана и С. Улама. В нашей стране первые статьи были опубликованы в 1955–56 гг. (В.В. Чавчанидзе, Ю.А. Шрейдер, В.С. Владимиров)

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

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

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

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

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

1. Теоретическая часть

1.1 Сущность метода Монте-Карло и моделирование случайных величин

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

Предположим, что эта фигура расположена внутри единичного квадрата.

Выберем внутри квадрата

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

Непрерывная случайная величина

Множество значений

1) плотность

2) интеграл от плотности

Математическим ожиданием непрерывной случайной величины называется число

Дисперсией непрерывной случайной величины называется число:

Нормальной случайной величиной называется случайная величина

Любые вероятности вида

Согласно (1.1)

В интеграле сделаем замену переменной

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

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

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

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

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

2.2.2 Листинг программы для нахождения числа Пи методом Монте-Карло 10

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

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

Заключение 20

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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

М(Х)= A .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

задачи нейтронной физики и другие.

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

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

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

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

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

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

.

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

X

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

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

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

.

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

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

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

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

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

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

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

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

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

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

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

FUNCTION raschet: real;

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

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

for i:=1 to N do

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

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

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

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

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

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

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

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

writeln(Pi:1:6);

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

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

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

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

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

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

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

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

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

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

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

Повторим испытание, состоящее в подбрасывании трех игральных костей, много раз подряд и найдем отношение числа M – отказов системы к общему числу N – проведенных испытаний. Вероятность отказа будет равна:

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

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

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

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

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

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

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

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

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

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

FUNCTION otkaz: word;

for i:=1 to B do

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

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

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

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

write(" числитель – ");

write(" знаменатель – ");

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

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

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

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

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

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

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

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

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

Итак, проверив формулу с помощью своей программы со значениями: количество приборов – 3; вероятность безотказной работы ; количество опытов – 50000, я получил два ответа. Решение задачи методом Монте-Карло – 0.429420 . Решение задачи аналитическим методом – 0.421296 . Отсюда вывод – вероятность, полученная разными методами сходна.

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

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

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

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

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

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

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

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

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

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

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

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

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

С играми ситуация еще более трагическая: например, колода из 52 карт может быть упорядочена 52! способами. Это примерно 8e67 или 2 226 . Значит для того, чтобы в процессе игры мог возникнуть любой расклад, создателю полноценной карточной игры типа «21» необходим 256 разрядный генератор случайных чисел. Если колода состоит из 36 карт, то соответствующие числа равны 4e41 и 2 138 , т.е. без суперкомпьютера опять не обойдешься. В карточной игре «преферанс» количество вариантов раздач равно 32!/10! или 2 96 , что тоже не мало. Несмотря на несравнимость этих чисел с реальными возможностями 32-х разрядного процессора, необходимо, конечно, использовать его возможности максимально, ведь только так можно приблизиться к разнообразию реальности.

Заключение

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

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

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

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

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

/~gene/probset/prob13.koi8.html

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

Интернет-ресурс «Вундеркинд» /2001/leto/stend/Vynderkind.htm

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