ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

Йсторически первым примером применения метода статистических испытаний является так называемая задача Бюффона.

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

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

где — количество всех бросаний иглы, количество

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

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

Будем считать, что значения функции заключены между нулем и единицей, т. е. при

Надо найти (рис. 1) площадь области ограниченной кривой осью и ординатами

Рис. 1.

Нужно заметить, что ограничение на функцию несущественно ввиду возможного изменения масштабов.

Пусть в квадрат случайно попадает точка, координаты которой независимы и равномерно распределены в интервале (0, 1). Какова вероятность того, что точка попадет в область под кривой? Очевидно, что вероятность этого события численно равна площади 5. Пусть взятая наугад точка будет

Эта точка заведомо попадет в квадрат, так как

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

Если это условие выполнено, то выбранная случайная точка попала в область под кривой. Далее берем много пар случайных величин и для всех этих пар проверяем, выполнено ли неравенство (0.2). Затем берем число пар, для которых выполнено неравенство (0.2), и делим на число всех пар. В силу закона больших чисел получаем величину близкую к вероятности попадания точки в область

Величина является приближенным значением искомого интеграла.

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

Обозначим через величину, равную единице, если на испытании произошло событие А, и равную нулю, если А не произошло. Таким образом, общее количество испытаний, в течение которых событие А произошло, равно

где — общее число испытаний.

Мы ограничиваемся схемой независимых испытаний. Частота появления события А равна и является величиной, распределенной почти по закону Гаусса с математическим ожиданием

и дисперсией

Поэтому с вероятностью 0,997 (при достаточно больших N) величина удовлетворяет условию

Правая часть формулы (0.3) является оценкой для ошибки метода статистических испытаний при вычислении вероятности события .

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

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

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

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

Пусть — значения величины 5, полученные при независимых испытаниях. Тогда величина

также распределена почти по закону Гаусса. Ее параметры равны соответственно

Поэтому имеет место оценка (с надежностью 0,997)

Таким образом, и в этом случае время решения связано обратной квадратичной зависимостью с достигаемой точностью

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

получаемую в процессе моделирования значений

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

Этот факт аналогичен тому, что точность физического эксперимента может быть надежно определена только по результатам этого эксперимента.

Необходимо отметить еще одну особенность метода Монте-Карло, состоящую в том, что оценка погрешности вычислений имеет вероятностный характер. При этом методе нельзя утверждать, что ошибка не превысит какого-либо значения. Можно только указать границы, за которые ошибка не выйдет с вероятностью, близкой к единице. В частности, в оценках (0.3) и (0.5) эта вероятность равнялась 0,997. При использовании электронных

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

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

Рассмотрим марковский процесс с конечным числом состояний и дискретным временем. Такой процесс представляет систему (в дальнейшем обозначаемую нами через которая может находиться в одном из конечного числа состояний: . В каждый из моментов времени, образующих дискретную упорядоченную последовательность, система находится в одном из своих состояний. Состояние, в котором находится система в момент времени, мы будем обозначать через Если в момент времени система находится в состоянии то - в следующий момент времени она с вероятностью (не зависящей от будет находиться в состоянии .

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

т. е.

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

системы до того, как она попадет в одно из особых состояний, является конечным.

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

Тогда вероятность того, что через — целое число) система не попадет в особое состояние, не превосходит величины

Отсюда следует, что среднее время «жизни» системы не превосходит величины

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

Рассмотрим случайную величину

связанную с рассматриваемым марковским процессом и являющуюся функцией от истории процесса. Полученное значение этой случайной величины мы зафиксируем.

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

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

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

Тогда (см. [8]) среднее арифметическое возникающих значений случайной величины

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

Средним значением величины мы называем здесь выражение

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

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

Ряд таких задач описан в настоящей книге.

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

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

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

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

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

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

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

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

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