§ 6. Использование метода Монте-Карло для расчета
канонических средних
Метод Монте-Карло является одним из методов вычислительной математики. Специфическая черта этого метода, называемого также методом статистических испытаний, состоит в том, что в процессе вы числений используются случайные величины (случайные числа), и, следовательно, в расчеты вносятся вероятностные элементы. В любом из классических методов (например, при вычислении определенного интеграла по методу трапеций) процесс вычислений строго детермини рован; последовательность действий, с помощью которых находится искомая величина, заранее однозначно определена. Вычисление много кратного интеграла классическим методом связано с определением значений подынтегральной функции над некоторым регулярным мно жеством точек. При решении аналогичной задачи по методу МонтеКарло расчет подынтегральной функции (с последующим суммиро ванием) проводится над множеством случайных точек, равномерно распределенных в заданной области. Метод статистических испытаний используется при решении многих математических задач (вычисление интегралов, решение систем алгебраических уравнений, решение дифференциальных уравнений и др.), задач физического и прикладно го характера (в особенности, в атомной физике, статистической физи ке, в теории массового обслуживания, теории стрельбы и т. д.). Рас четы различных физических процессов по методу Монте-Карло связаны с получением последовательности случайных событий, моделирую щей рассматриваемый процесс. Датой рождения метода считают 1949 г., хотя основные его идеи зародились раньше. Широкое распро странение метод Монте-Карло получил благодаря появлению быстро действующих вычислительных машин. С помощью машин оказалось возможным производить расчеты для достаточно длинных цепей слу чайных событий, чтобы статистические методы могли дать хорошие результаты. К этому следует добавить, что расчеты по методу МонтеКарло удобно программировать; точность расчетов можно по жела нию увеличивать путем увеличения числа статистических испытаний.
Реализация метода Монте-Карло связана с получением последова тельности так называемых случайных чисел с заданным законом рас пределения. Особое значение имеют последовательности равномерно распределенных случайных величин, поскольку они часто использу ются при вычислениях и, кроме того, на основе последовательностей равномерно распределенных чисел строятся последовательности с дру гими законами распределения (нормальным, экспоненциальным и др.). Пусть £ — случайная величина, которая может принимать любые (однако с фиксированным числом знаков после запятой) значения в
|
|
|
|
|
|
|
|
|
|
|
интервале |
[0,1 J : 0 ^ S f 1 . |
Будем |
производить испытания |
над |
случайной величиной и выберем п значений |
подряд или любым |
произвольным образом, в результате чего получим |
последовательность |
£і> ^2» |
••• t |
tn |
= |
{£„}. Пусть |
(а, |
Ь) —некоторый |
промежуток на |
от |
резке |
[0,1]; цп |
(а, Ь) —число |
элементов из |
последовательности |
|
принадлежащих |
промежутку |
(а, |
Ь). |
Если |
последовательность |
£х , |
' 2 . ••• . £л равномерно распределенная, то при и > |
1 значение **" |
— |
|
п |
|
с точностью до статистической ошибки совпадает с |
величиной \ Ь — |
а], |
как бы мы ни выбирали промежуток (а, Ь). Если интервал [0, 1 ] раз делим на равные промежутки, то числа, попадающие в различные про межутки, должны встречаться в среднем в одинаковых пропорциях; при этом ни одно из чисел не должно иметь заметной тенденции следо вать за каким-либо определенным другим.
Для получения последовательности случайных чисел можно ис пользовать результаты случайных физических процессов (вращение рулетки, бросание игральной кости, вспышки в счетчике Гейгера и др.). Разработаны аналитические методы получения случайных (точ нее псевдослучайных) чисел, составлены таблицы случайных чисел.
Рассмотрим возможности использования метода статистических испытаний для расчета канонических средних. Прежде всего пока жем, как по методу Монте-Карло можно было бы рассчитать конфигу рационный интеграл. Заранее скажем, что тот путь расчета, о котором мы сейчас будем говорить, на практике не используется. Однако рас сматривая его, мы сможем лучше уяснить особенности метода МонтеКарло. Конфигурационное пространство системы будем считать дис кретным, определяя положение частицы с точностью до некоторой величины Дх = Ду = Az = (ДѴ)'/ 3 по каждой из координат. Величина ДѴ характеризует точность задания положения частицы в реальном физическом объеме (объем элементарной ячейки в пространстве коор динат X — у — z частицы). Очевидно, выбирая интервал ах по жела нию достаточно малым, можем описывать конфигурацию системы с любой желаемой степенью точности. Конфигурационное пространство системы, состоящей из N частиц, разделится на ячейки объема (Д V)N. Число конфигураций системы является конечным и равно
- ( • £ Г
(5 — число ячеек в объеме VN конфигурационного пространства). Ячейки конфигурационного пространства могут быть пронумерованы. Если изображающая точка системы находится в і-й ячейке, будем го ворить, что система находится в і-м состоянии (і = 1, ... , 5). Учиты вая сделанные допущения, можем конфигурационный интеграл за менить конфигурационной суммой следующего вида:
(XIII.71)
где Ui — энергия межмолекулярного взаимодействия для системы в і-и состоянии; суммирование проводится по всем конфигурациям системы (по всем ячейкам). Выражение (XIII.71) можем также запи-
сать в форме
( X I I I . 72)
где среднее арифметическое бзрется по всем конфигурациям системы. Каноническое среднее значение любой функции координат M (гъ ... , Гц) отвечает соотношению
5 L
i=i
Наиболее очевидной возможностью вычисления суммы (XIII.71) и (XI 11.73) с помощью метода случайных выборок является следующая. Допустим для простоты, что обьэм, в котором заключена система, представляет куб с ребром а, так что
О < xj < а; 0 < yj < а; 0 < zj < а,
где / — номер частицы. Выбзрем ЗА/ случайных числа 0 |
1. |
Образованную ими последовательность представим в следующем виде:
г(і) |
МП KD. |
С{2 ) . |
C f . С<2>; |
r(N) |
HN) |
rW) |
*l |
• ^2 |
• ^3 * |
Будем считать, что набор чисел %\п определяет |
конфигурацию си |
стемы таким образом, |
что координаты /-й частицы |
равны |
х , - С | / > я ; |
У] = Ѵ2І)а; Zj = ^ a ; (/ = 1 , 2 , . . . , N). |
Результат определяет некоторую конфигурацию системы, представляе мую точкой в конфигурационном ЗА/-мерном пространстве. Производя многократный выбор случайных чисел, получаем множество конфигу
раций системы (множество |
точек |
в конфигурационном |
А/-частичном |
пространстве). Так как случайные |
числа распределены |
равномерно, |
то и точки сравнительно |
равномерно заполнят конфигурационное |
пространство; распределение трчек тем более равномерное, чем боль
ше число испытаний. Для каждой конфигурации |
рассчитаем энергию |
межмолекулярного взаимодействия U и найдем |
значение интересую |
щей нас функции |
координат |
М. Величины |
ехр [ — U U ) /kT] и |
Aî( ; ) exp [—U{ l ) /kT] |
суммируем |
(здесь индекс / |
в скобках — номер |
выборки). Если число L генерированных конфигураций достаточно
велико, то можем приравнять приближенно:
2 к о „ ф - — |
V e k T : |
(XIII.74) |
|
/=і |
|
|
А Г |
|
Л1~ — |
. |
(XIII.75) |
По существу на примере интеграла Z K 0 H ( p мы рассмотрели стандарт
ный вариант расчета |
многократного |
интеграла по |
методу |
Монте- |
~ Карло. Рассмотренная |
схема расчета |
канонических |
средних |
(величи |
ны М) состояла в хаотическом выборе конфигураций и последующем
«взвешивании» их |
посредством умножения суммируемой величины |
Мц) на величину |
ехр [—U( j ) /kT], пропорциональную вероятности |
/-й конфигурации в системе, которая описывается каноническим рас пределением.
Хотя намеченная схема расчета канонических средних принци пиально проста, применение ее на практике нерационально в связи со следующим обстоятельством. Вклад некоторой і-й конфигурации в каноническое среднее пропорционален больцмановскому множителю ехр [—Ui/kT], а этот множитель в зависимости от конфигурации си стемы может сильно меняться. Поэтому некоторые конфигурации дают значительный вклад в канонические средние, некоторые — практи чески нулевой. При хаотическом выборе, однако, и те и другие конфи гурации появляются одинаково часто; «взвешиваем» их мы потом, формируя суммы. Нерациональность такого метода генерирования конфигураций видна на следующем примере. Предположим, что плот ность системы велика. Тогда среди хаотически выбранных конфигу раций основную долю составят такие, в которых по крайней мере две частицы «перекрываются», т. е. сближены настолько, что между ними имеется сильное отталкивание. Поскольку потенциальная энергия
такой пары — очень большая |
положительная |
величина, |
то для |
рас |
сматриваемой конфигурации |
Ut^>kT |
и ехр |
[—Ui/kT] |
~ 0. |
Так, |
для модельной системы твердых шариков равна бесконечности энер гия всех конфигураций, при которых хотя бы два шара перекрыва ются (расстояния между центрами шаров больше диаметра шара). Вклад таких конфигураций в величину Z K 0 H ( j ) равен нулю. При беспо рядочном выборе конфигурации с нулевым (или очень малым) значе нием ехр (Ui/kT) мы получали бы очень часто, и большая часть вы числительной работы была бы практически бесполезной. В связи с указанными обстоятельствами при расчете канонических средних для плотных систем метод Монте-Карло в описанной выше модификации практически не используется.
Метрополис и сотр. в 1953 г. предложили для численного расчета канонических средних использовать такой метод генерирования кон фигурации, чтобы частота появления произвольной конфигурации была
пропорциональна величине ехр (—Ui/kT):
Wj = lim |
L |
= |
— |
e |
k T |
T j r — • |
(XIII . 76) |
— i |
- |
|
L-+œ |
L |
|
|
|
|
«_ |
|
|
|
|
1=1 |
|
|
|
где L — общее число испытаний, |
L t |
— число испытаний, |
при кото |
рых наблюдалась і-я конфигурация; |
|
Lt/L |
— относительная частота |
появления і-й конфигурации |
в |
цепи, |
wt |
— вероятность |
появления |
і-й конфигурации. Если такую цепь реализовать для системы твер дых непритягивающихся шаров, то в этой цепи все конфигурации, при которых хотя бы два шарика перекрываются, исключены; все остальные конфигурации равновероятны.
Цепь конфигураций, отвечающую зависимости (XIII.76), полу чают путем задания определенных вероятностей перехода от одной конфигурации к другой. Вероятность рі} перехода от t'-й конфигура ции к /-й считают зависящей от энергии этих конфигураций, точнее,
от величины |
: р . , = р п |
. Вводят, таким образом, услов- |
kT |
|
kT |
ные вероятности перехода: вероятность данного события, состоящего в появлении конфигурации /, зависит от того, каким было предыдущее событие. Последовательность случайных событий, в которой вероят ность определенного события зависит от исхода предыдущего испыта ния, называют цепью Маркова (точнее, простой цепью Маркова; в более сложных случаях марковских цепей на исход испытания влияют результаты нескольких предшествующих испытаний). С помощью теории марковских цепей можно показать, что предельная зависимость (XIII.76) для частоты появления конфигураций с заданной энергией
будет выполняться, если вероятности перехода рц отвечают |
условиям*: |
s |
|
|
|
Epy |
= |
l ; |
(XIII . 77) |
/-1 |
|
|
|
рцв k T |
= Р л е |
k T - |
( X I I I . 78) |
В левой части ( X I 11.77) суммирование проводится по всем значениям /, включая и значение / = / (следующая конфигурация в цепи может совпасть с предыдущей). Смысл условия (XIII.77) состоит в том, что после конфигурации і с достоверностью наблюдается какая-нибудь из конфигураций (любая из 5 величин); это условие нормировки ве-
/ Uj — Ui \
роятностей р^. Зависимости ptJ I — — — I , удовлетворяющие услови
* Дополнительно ставится также условие эргодичности, согласно которому все состояния системы должны быть достижимы одно из другого, хотя бы через очень большое (но конечное) число шагов. Проблема аналогична той, которая возникала при замене средних по времени фазовыми средними (см. гл. I I I , § 3).
