Метод Монте Карло. Некоторые сведения из теории вероятности и матстатистики, статистической физики и термодинамики. Цепи Маркова. Реализа

 

 

Лекция. Метод Монте Карло. Некоторые сведения из теории вероятности и матстатистики, статистической физики и термодинамики. Цепи Маркова. Реализация метода МК. Алгоритм Метрополиса.

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

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

Метод Монте-Карло - метод статистических испытаний, численный метод решения математических задач при помощи моделирования случайных процессов и событий. Термин «Метод Монте-Карло» возник в 1949, хотя некоторые расчёты путём моделирования случайных событий осуществлялись статистиками и ранее. (Название «Метод Монте-Карло» происходит от города Монте-Карло, известного своим игорным домом.) Широкое распространение метод Монте-Карло получил только после появления быстродействующих вычислительных машин. Программы для расчётов по методу Монте-Карло на ЭВМ сравнительно просты и, как правило, позволяют обходиться без большой оперативной памяти.

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

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

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

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

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

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

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

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

 

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

 

 

 

 

 

p=2l/ap  при a< l

 

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

, где A — расстояние от начала иглы до ближайшей к ней прямой; θ - угол иглы относительно прямых. Этот интеграл просто взять: p=2l/ap при a< l, поэтому, подсчитав долю отрезков, пересекающих прямые, можно приближенно определить это число. При увеличении количества попыток точность получаемого результата будет увеличиваться.

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

 

	Число бросаний	Число пересечений	Длина иглы	Расстояние между прямыми	Вращение	Значение p
1 поп.	500	236	3	4	отсутствует	3.1780
2 поп.	530	253	3	4	присутствует	3.1423
3 поп.	590	939	5	2	присутствует	3.1416

 

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

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

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

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

Определение  S  под графиком функции с помощью стохастического алгоритма:

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

 

Тогда , S - площадь под графиком функции.

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

Компьютерный эксперимент в статистической физике и термодинамике

Основная задача статистической теории - вычисление средних значений различных величин, характеризующих поведение системы в состоянии равновесия. Путь к вычислению средних значений параметров физической системы был развит Больцманом и Гиббсом. Идея: наблюдаемое свойство вычисляется как среднее по множеству различных состояний системы, которые возникают с определенной вероятностью. Это - усреднение по статистическому ансамблю.

Вероятность (или частота) возникновения состояния физической системы пропорционально статистическому весу, т.е. определяется потенциальной энергией U данной конфигурации.

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

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

Есть набор W(S) возможных состояний физической системы S. Для определения среднего значения  некоторой величины A необходимо рассчитать

Суммирование проводится по всем состояниям S из набора W(S) возможных состояний, P(S) - вероятность состояния S.

Общая процедура Метод МК: Как осуществляются переходы между состояниями системы?

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

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

1. Пусть есть некоторая вероятность wi события A и вероятность ui события B. Тогда                            wi > ui т.е. событие А более вероятно, чем событие В, а если, wi= ui, то эти события равновероятны. Если wi = 1, то событие А достоверно, если wi = 0, то событие А невозможно.
2. Если Аi - случайные величины, то случайная величина полностью задается функцией вероятности W(Аi). Для непрерывной случайной величины можно ввести понятие плотности вероятности - т.е. вероятность того, что величина А лежит в интервале А, А + dA определяется выражением  dW(А) = W(А) dA.
3. Условие нормировки: сумма всех событий - достоверное событие: SW(Аi) = 1, или для непрерывной величины А: òW(А)dA = 1, где интегрирование ведется по всем возможным А.
4. Для независимых непрерывных величин можно записать, что их вероятность равна произведению вероятности каждого из событий w(х,у) = w(х)w(у). Системы называются независимыми, если между ними нет физических взаимодействий.
5. Среднее значение физических величин. Статистическое среднее, или математическое ожидание:                      - для дискретной величины                      или                                - для непрерывной величины.

6. Дисперсия случайной величины:                               или
7. Закон больших чисел. Многие физические величины можно выражать как арифметические средине случайных величин:

 

 

Это возможно на основе закона больших чисел, в котором утверждается, что                                        отклонение от средних при достаточно больших N® ¥ становится сколь угодно малым.