8. Методы Монте-Карло

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

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

где область определена неравенствами

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

Очевидный статистический процесс для замены этих вычислений состоит в том, что берется некоторое число случайно выбранных точек в -мерном кубе с равной вероятностью из любого места и среди этих точек подсчитывается доля тех, которые удовлетворяют данным неравенствам. Очевидно, что для получения точности порядка одного процента достаточно взять число точек, намного меньшее (порядка 104), чем общее число вершин решетки: Это ясно в случае, когда нам a priori известно, что объем рассматриваемой области не очень мал по сравнению с объемом содержащего ее куба.

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

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

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

Для оценки ошибок в процессах размножения и диффузии нужен аналог теоремы Лапласа — Ляпунова.

Счетные машины весьма хорошо приспособлены к экспериментам такого рода над качественным поведением решений

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

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

где - неизвестные функции координат х, у, z и времени скажем, данные константы; и данные функции, для простоты линейные относительно их и и содержащие также независимые переменные Требуется выяснить асимптотический вид их и (для больших значений Эту задачу можно рассматривать как обобщение диффузионной модели уравнения Шредингера. Она соответствует системе из двух частиц, в которой потенциальная функция, зависящая от заменена функцией от распределения частиц.

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

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

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

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

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

представляющих соответственно числа +1 и —1. Это соответствие, очевидно, сохраняет сложение и умножение. Любая система, описанная матрицей порядка из действительных чисел, может быть интерпретирована вероятностно с помощью матрицы порядка из неотрицательных чисел. Выбор будет осуществляться из двух видов частиц («черных» и «красных») с правилами преобразований, заданными вышеприведенными матрицами. Однако в этом случае снова необходима частая перепись результатов, так как окончательные результаты зависят от разности между числом черных и красных частиц в каждой точке. Можно реализовать стохастические модели для матриц с комплексными элементами с помощью 4 видов частиц или более общие алгебры над действительными числами с помощью соответствующего числа видов частиц. Подобным образом можно изучать уравнение Дирака (см. Эверетт, Улам [5]).