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

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

Введение

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

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

Сущность метода Монте-Карло

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

Практически же поступают так: производят n испытаний, в результате которых получают n возможных значений X; вычисляют их среднее арифметическое

и принимают х в качестве оценки (приближенного значения) а* искомого числа а:

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

Случайные величины использовались для решения различных прикладных задач достаточно давно. Примером может служить способ определения числа Пи, который был предложен Бюффоном еще в 1777 году. Суть метода была в бросании иглы длиной L на плоскость, расчерченную параллельными прямыми, расположенными на расстоянии r друг от друга (см. Рис. 1).

Рисунок 1. Метод Бюффона

Вероятность (как видно из дальнейшего контекста, речь идёт не о вероятности, а о математическом ожидании количества пересечений за один опыт; вероятностью это становится лишь при условии, что r > L) того, что отрезок пересечет прямую, связана с числом Пи:

где

A -- расстояние от начала иглы до ближайшей к ней прямой;

? -- угол иглы относительно прямых.

Этот интеграл просто взять: (при условии, что r > L), поэтому подсчитав долю отрезков, пересекающих прямые, можно приближенно определить это число. При увеличении количества попыток точность получаемого результата будет увеличиваться.

В 1864 году капитан Фокс, выздоравливая после ранения, чтобы как-то занять себя, реализовал эксперимент по бросанию иглы. Результаты представлены в следующей таблице:

Комментарии:

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

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

Создание математического аппарата стохастических методов началось в конце XIX века. В 1899 году лорд Релей показал, что одномерное случайное блуждание на бесконечной решётке может давать приближенное решение параболического дифференциального уравнения. Андрей Колмогоров в 1931 году дал большой толчок развитию стохастических подходов к решению различных математических задач, поскольку он сумел доказать, что цепи Маркова связаны с некоторыми интегро-дифференциальными уравнениями. В 1933 году Иван Петровский показал, что случайное блуждание, образующее Марковскую цепь, асимптотически связано с решением эллиптического дифференциального уравнения в частных производных. После этих открытий стало понятно, что стохастические процессы можно описывать дифференциальными уравнениями и, соответственно, исследовать при помощи хорошо на тот момент разработанных математических методов решения этих уравнений.

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

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

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

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

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

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

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

Пусть для получения оценки а* математического ожидания а случайной величины X было произведено n независимых испытаний (разыграно n возможных значений X) и по ним была найдена выборочная средняя <х>, которая принята в качестве искомой оценки: а* = <х>. Ясно, что если повторить опыт, то будут получены другие возможные значения X, следовательно, другая средняя, а значит, и другая оценка а*. Уже отсюда следует, что получить точную оценку математического ожидания невозможно. Естественно, возникает вопрос о величине допускаемой ошибки. Ограничимся отысканием лишь верхней границы б допускаемой ошибки с заданной вероятностью (надежностью) у:

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

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

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

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

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

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

где n -- число испытаний; s -- «исправленное» среднее квадратическое отклонение, находят по таблице.

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

В этом случае при достаточно большом числе испытаний (n>30) с надежностью, приближенно равной у, верхняя граница ошибки может быть вычислена по формуле (*),

если среднее квадратическое отклонение о случайной величины X известно; если же а неизвестно, то можно подставить в формулу (*) его оценку s -- «исправленное»

среднее квадратическое отклонение либо воспользоваться формулой (**). Заметим, что чем больше п, тем меньше различие между результатами, которые дают обе формулы.

Это объясняется тем, что при n --»¦ оо распределение Стьюдента стремится к нормальному.

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

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

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

Для определения площади под графиком функции можно использовать следующий стохастический алгоритм:ограничим функцию прямоугольником (n-мерным параллелепипедом в случае многих измерений), площадь которого Spar можно легко вычислить;«набросаем» в этот прямоугольник (параллелепипед) некоторое количество точек (N штук), координаты которых будем выбирать случайным образом; определим число точек (K штук), которые попадут под график функции; площадь области, ограниченной функцией и осями координат, S даётся выражением

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

Рисунок 3

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

Традиционно метод Монте-Карло применялся для определения различных физических параметров систем, находящихся в состоянии термодинамического равновесия. Предположим имеется набор W(S) возможных состояний физической системы S. Для определения среднего значения некоторой величины A необходимо рассчитать

где суммирование производится по всем состояниям S из W(S), P(S) -- вероятность состояния S.

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

Примеры прямого моделирования методом Монте-Карло:

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

- Прямое Монте-Карло моделирование разреженных газов.

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

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

В качестве примера будет приведено решение задачи № 724 из Руководства к решению задач по теории вероятностей и математической статистике, Гмурмана.

Задача

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

А, В (они соединены параллельно) и отказывает при одновременном отказе обоих элементов. Второй блок содержит один элемент С и отказывает при отказе этого элемента,

а) Найти методом Монте-Карло оценку Р* надежности (вероятности безотказной работы) системы, зная вероятности безотказной работы элементов: Р(А) = 0,8, Р (В) = 0,85, Р(С) = 0,6;

б) найти абсолютную погрешность |Р -- Р*|, где Р -- надежность системы, вычисленная аналитически. Произвести 50 испытаний.

Решение

а) Выберем из таблицы приложения 9 три случайных числа: 0,10, 0,09 и 0,73; по правилу (если случайное число меньше вероятности события, то событие наступило; если случайное число больше или равно вероятности события, то событие не наступило) разыграем события А, В, С, состоящие в безотказной работе соответственно элементов А, В, С. Результаты испытания будем записывать в расчетную таблицу. Поскольку Р(А)=0,8 и 0,10 < 0,8, то событие А наступило, т. е. элемент А в этом испытании работает безотказно. Так как Р (В) =50,85 и 0,09 < 0,85, то событие В наступило, т. е. элемент В работает безотказно. Таким образом, оба элемента первого блока работают; следовательно, работает и сам первый блок. В соответствующих клетках таблицы ставим знак плюс.

Так как Р(С) = 0,6 и 0,73 > 0,6, то событие С не наступило, т. е. элемент С получает отказ; другими словами, второй блок, а значит и вся система, получают отказ. В соответствующих клетках таблицы ставим знак минус. Аналогично разыгрываются и остальные испытания. В таблице приведены результаты четырех испытаний. Произведя 50 испытаний, получим, что в 28 из них система работала безотказно. В качестве оценки искомой надежности Р приймем относительную частоту Р* = 28/50 =0,56.

б) Найдем надежность системы Р аналитически. Вероятности безотказной работы первого и второго блоков соответственно равны:

Вероятность безотказной работы системы

Искомая абсолютная погрешность \Р -- Р* | =0,582--0,56 = 0,022.

Выводы

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

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

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

алгоритм монте карло интегрирование

1. Гмурман В.Е. Теория вероятностей и математическая статистика: Учеб. Пособие для вузов 2003г.

2. Гмурман В.Е. Руководство к решению задач по теории вероятностей и математической статистике 2004г

3. Вентцель Е.С. Овчаров Л.А. Теория случайных процессов и ее инженерные приложения. Пособие для ВТУЗов 2003г.

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