Глава I. МЕТОД СТАТИСТИЧЕСКИХ ИСПЫТАНИЙ (МОНТЕ КАРЛО)

1. Сущность метода

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

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

Сущность метода статистических испытаний поясним на примерах.

В качестве первого примера рассмотрим вычисление площади некоторой фигуры произвольной формы. Остановимся сначала на частном случае решения этой задачи. Пусть требуется вычислить площадь фигуры (см. рис. 1), ограниченной отрезками ОА и на осях прямоугольных координат ОХ и ОУ, кривой и ординатой (искомая площадь на рис. 1 заштрихована), причем будем считать выполненным условие для всех

Рис. 1.

Пользуясь обычными численными методами для приближенного вычисления искомой площади, поступают следующим образом. Разбивают отрезок (0,1) на оси ОХ на равных частей длиной Искомую площадь 5 представляют в виде суммы площадей элементарных фигур, как показано на рис. 2. Площадь каждой

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

Рис. 2.

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

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

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

Рис. 3.

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

Предположим, что количество точек под кривой равно над кривой равно (точки, попадающие точно на кривую, будем считать находящимися под кривой).

Если следовать геометрическим соображениям, ясно, что вероятность Р попадания точки в часть квадрата, находящуюся под кривой равна отношению площади этой части квадрата к площади всего квадрата. Частота попадания точки в часть квадрата под кривой при достаточно большом близка к вероятности Р (см. [5]). Отсюда следует, что в качестве приближенного значения искомой площади можно взять частоту т. е.

Для решения рассмотренного примера на ЭВМ нет необходимости в воспроизведении всех указанных выше действий. Сущность метода статистических испытаний для данного случая состоит в моделировании эксперимента при помощи случайных чисел.

Процедура решения выглядит следующим образом:

1. Выбирается случайное число из отрезка [0; 1] с равномерным законом распределения (из таблиц случайных чисел или вырабатывается самой машиной с помощью датчика случайных чисел); это случайное число принимается в качестве координаты случайной точки на оси

2. Вычисляется значение рассматриваемой функции в точке

3. Вырабатывается следующее случайное число принимаемое в качестве координаты точки на оси О У; таким образом и определяют случайную точку на плоскости внутри единичного квадрата.

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

5. Значение функции сравнивается со случайным числом Если неравенство (см. рис. 3)

выполнено, что соответствует попаданию случайной точки в часть квадрата под кривой то результату сравнения присваивается специальный признак если не выполнено

6. Полученные значения признака (о прибавляются к содержимому счетчика количества точек под кривой

7. Управление передается снова первой операции, что соответствует переходу к новой случайной точке После проведения N таких экспериментов определяется приближенное значение площади под кривой:

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

Точность решения задачи методом статистических испытаний растет с увеличением количества испытаний N и при достаточно больших N становится приемлемой с практической точки зрения. (Этот вопрос будет более обстоятельно выяснен ниже, в § 5.)

Целесообразно обратить внимание на ряд возможных обобщений.

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

Тогда квадрат АВЕД будет единичным, а искомая площадь

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

Величина 5 может быть определена методом статистических испытаний.

Рис. 4.

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

причем выбирается уже не из отрезка [0,1], а из преобразованного (сдвинутого) единичного отрезка.

Если это неравенство выполнено, случайная точка находится внутри контура фигуры и тогда

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

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

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

где максимальное значение в отрезке [а, Ь] равно Используя замену переменных

и изменение масштаба по оси у, получим

где

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