Стохастический процесс - метод Монте-Карло

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

Кокшетауский университет им. Абая Мырзахметова

Стохастический процесс - метод Монте-Карло

Эсмагамбет М.Г. - к.ф.м.н.

Зинченко В.А. - магистрант

Аннотация

монте карло стохастический вычислительный

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

Annotation

History and principles of one of the methods of stochastic process which known as the Monte Carlo are considered in this article.

Аннотация

Берілген ма?алада Монте Карло ?дісі ретінде танымал стохастикалы? ?рдісті? ?дісі мен ?станымы, тарихы ?арастырылады

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

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

Методы проведения расчётов и экспериментов на основе случайных процессов, как формы стохастического моделирования, применялись ещё на заре развития теории вероятностей (напр. Задача Буффона и в работах по оценке малых выборок Уильяма Госсета), но наиболее развились в предкомпьютерную эру. Отличительной чертой методов моделирования Монте-Карло является то, что сначала идёт поиск вероятностного аналога (см. алгоритм имитации отжига). До этого методы моделирования шли в противоположном направлении: моделирование использовалось для того, чтобы проверить результат полученной ранее детерминированной проблемы. И хотя подобные подходы существовали до этого, они не были общими и популярными до тех пор, пока не появился метод Монте-Карло.

Возможно, наиболее известное из ранних применений подобных методов, принадлежит Энрико Ферми, который в 1930 году использовал стохастические методы для расчёта свойств только что открытого нейтрона. Методы Монте-Карло широко использовались в ходе работы над манхэттенским проектом, несмотря на то, что возможности вычислительных машин были сильно ограничены. По этой причине только с появлением компьютеров, методы Монте-Карло начали широко распространяться. В 1950-х их использует Лос-Аламосская национальная лаборатория для создания водородной бомбы. Широкое распространение методы получили в таких областях, как Физика, Физическая химия и Исследование операций [6].

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

2. Рождение метода Монте-Карло в Лос-Аламосе

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

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

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

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

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

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

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

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

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

,

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

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

.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература

1. Neumann J., "NBS Appl. Math, scries", 1951 № 12, p. 36-38;

2. Бусленко Н. П. [и др.], Метод статистических испытаний (метод Монте-Карло), М., 1962;

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

4. Бахвалов Н. С, в сб.: Численные методы решения дифференциальных и интегральных уравнений и квадратурные формулы, М., 1964, с. 5-63

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

6. Полляк Ю. Г., Вероятностное моделирование на электронных вычислительных машинах, М., 1971

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