Математическая энциклопедия - монте-карло метод

метод статистических испытаний,численный метод, основанный на моделировании случайных величин и построении статистич. оценок для искомых величин. Принято считать, что М.-К. м. возник в 1949 (см. [1]), когда в связи с работами по созданию атомных реакторов Дж. Нейман (J. Neumann) и С. Улам (S. Ulam) предложили использовать аппарат теории вероятностей для решения прикладных задач с помощью ЭВМ. М.-К. м. получил свое название по имени города Монте-Карло, известного своими игорными заведениями.

Моделирование случайных величин с заданными распределениями. Как правило, такое моделирование осуществляется путем преобразования одного или нескольких независимых значений случайного числа , распределенного равномерно в интервале (0, 1). Последовательности "выборочных" значений обычно получают на ЭВМ с помощью теоретико-числовых алгоритмов, среди к-рых наибольшее распространение получил т. н. метод вычетов, напр, в таком виде:

Здесь число разрядов мантиссы ЭВМ, а

Числа такого типа наз. псевдослучайными числами; они проверяются статистич. тестами и решением типовых задач (см. [2] [6]). Длина периода для указанного варианта метода вычетов равна В М.-К. м. используются также физич. генераторы и таблицы случайных чисел, а также квазислучайные числа. Существуют М.-К. м. с малым числам разыгрываемых параметров (см. [7]).

Стандартный метод моделирования дискретной случайной величины с распределением состоит в следующем: полагают если для выбранного значения выполняется соотношение

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

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

Другим общим методом моделирования непрерывной случайной величины является метод исключения (метод отбора), в основе к-рого лежит утверждение: если точка распределена равномерно в области В методе исключения выбирают точку равномерно по области и полагают , если в противном случае повторяют выбор и т. д. Напр., если и то можно полагать Среднее число операций в методе исключения пропорционально величине

Для многих случайных величин получены специальные представления вида Напр., случайные величины

имеют стандартное нормальное распределение и независимы; случайная величина имеет гамма-распределение с параметром п;случайная величина распределена с плотностью случайная величина имеет бета-распределение с параметрами р, п (см. [3] [6]).

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

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

Если в расчете по М.-К. м. моделируются случайные величины, определяемые реальным содержанием явления, то расчет представляет собой прямое моделирование (имитацию) этого явления. Разработано моделирование на ЭВМ процессов переноса, рассеяния и размножения частиц: нейтронов, гамма-квантов, фотонов, электронов и др. (см., напр., [11] [18]); моделирование эволюции ансамблей молекул для решения различных задач классической и квантовой статистич. физики (см., напр., [10], [18]); моделирование массового обслуживания и производственных процессов (см., напр., [2], [6], [18]); моделирование различных случайных процессов в технике, гидрологии, метеорологии, геологии, химии, биологии и т. д. (см. [18]). Алгоритмы моделирования обычно тщательно обрабатывают, напр, табулируют сложные функции, изменяют стандартные процедуры и т. д. Тем не менее часто прямое моделирование не может обеспечить требуемой точности оценок искомых величин. Разработано много способов повышения эффективности моделирования.

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

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

Одновременно можно оценить среднеквадратичную погрешность , т. е. величину , и приближенно построить подходящий доверительный интервал для . Выбором плотности f можно распорядиться для получения оценки с возможно меньшей дисперсией. Напр., если то и если то . Соответствующие алгоритмы наз. существенной выборкой (выборкой по важности). Другая общая модификация метод выделения главной части строится в тех случаях, когда определена функция с известным значением интеграла. Иногда полезны сочетания М.-К. м. с классич. квадратурами т. н. случайные квадратурные формулы, основная идея к-рых состоит в том, что узлы и коэффициенты какой-либо квадратурной суммы (напр., интерполяционной) выбираются случайно из распределения, обеспечивающего несмещенность получаемой оценки интеграла [3]. Частными случаями этих формул являются: т. н. метод слоистой выборки, в к-ром узлы выбираются по одному в каждой части фиксированного разбиения области интегрирования, а коэффициенты пропорциональны соответствующим объемам; так наз. метод симметричной выборки, к-рый в случае интегрирования по интервалу (0, 1) определяется выражением (см. [10])

При этом порядок скорости сходимости М.-К. м. повышается и в нек-рых случаях становится максимально возможным на рассматриваемом классе задач.

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

Ряд модификаций М.-К. м. основан на (может быть, формальном) представлении искомой величины в виде двукратного интеграла: '

где , а вектор распределен с плотностью . Известно, что и

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

где условно независимы и распределены как при фиксированном значении . С помощью (1) можно получить оптимальное значение

где средние времена ЭВМ, соответствующие выборкам (см., напр., [4]).

Если подинтегральная функция зависит от параметра, то целесообразно использовать метод зависимых испытаний, т. е. оценивать интегралы для различных значений параметра по одним и тем же случайным узлам [20]. Важным свойством М.-К. м. является сравнительно относительно слабая зависимость среднеквадратич. погрешности от числа измерений, причем порядок сходимости по числу узлов всегда один и тот же: . Это позволяет оценивать (после предварительных преобразований задачи) интегралы очень высокой и даже бесконечной кратности. Напр., разработана методика оценки интегралов Винера [19].