Монте-карло метод

метод статистических испытаний,- численный метод, основанный на моделировании случайных величин и построении статистич. оценок для искомых величин. Принято считать, что М.-К. м. возник в 1949 (см. [1]), когда в связи с работами по созданию атомных реакторов Дж. Нейман (J. Neumann) и С. Улам (S. Ulam) предложили использовать аппарат теории вероятностей для решения прикладных задач с помощью ЭВМ. М.-К. м. получил свое название по имени города Монте-Карло, известного своими игорными заведениями. Моделирование случайных величин с заданными распределениями. Как правило, такое моделирование осуществляется путем преобразования одного или нескольких независимых значений случайного числа [img: http://localhost:8080/file/031418-186.jpg], распределенного равномерно в интервале (0, 1). Последовательности "выборочных" значений [img: http://localhost:8080/file/031418-187.jpg] обычно получают на ЭВМ с помощью теоретико-числовых алгоритмов, среди к-рых наибольшее распространение получил т. н. метод вычетов, напр, в таком виде: [img: http://localhost:8080/file/031418-188.jpg] Здесь [img: http://localhost:8080/file/031418-189.jpg] - число разрядов мантиссы ЭВМ, а [img: http://localhost:8080/file/031418-190.jpg] Числа такого типа наз. псевдослучайными числами; они проверяются статистич. тестами и решением типовых задач (см. [2] - [6]). Длина периода для указанного варианта метода вычетов равна [img: http://localhost:8080/file/031418-191.jpg] В М.-К. м. используются также физич. генераторы и таблицы случайных чисел, а также квазислучайные числа. Существуют М.-К. м. с малым числам разыгрываемых параметров (см. [7]). Стандартный метод моделирования дискретной случайной величины [img: http://localhost:8080/file/031418-192.jpg] с распределением [img: http://localhost:8080/file/031418-193.jpg] [img: http://localhost:8080/file/031418-194.jpg] состоит в следующем: полагают [img: http://localhost:8080/file/031418-195.jpg] если для выбранного значения [img: http://localhost:8080/file/031418-196.jpg] выполняется соотношение [img: http://localhost:8080/file/031418-197.jpg] Стандартный метод моделирования непрерывной случайной величины (иногда наз. методом обратной функции) состоит в использовании легко проверяемого представления: [img: http://localhost:8080/file/031418-198.jpg], где [img: http://localhost:8080/file/031418-199.jpg] - функция распределения с заданной плотностью [img: http://localhost:8080/file/031418-200.jpg]. Иногда полезна рандомизация моделирования (иначе - метод суперпозиции) на основе выражения [img: http://localhost:8080/file/031418-201.jpg] при этом сначала выбирают номер т с распределением [img: http://localhost:8080/file/031418-202.jpg] а затем получают выборочное значение [img: http://localhost:8080/file/031418-203.jpg] из распределения с плотностью [img: http://localhost:8080/file/031418-204.jpg]. При других способах рандомизации нек-рые параметры детерминированного способа решения задачи рассматривают как случайные величины (см. [7] - [9]). Другим общим методом моделирования непрерывной случайной величины является метод исключения (метод отбора), в основе к-рого лежит утверждение: если точка [img: http://localhost:8080/file/031418-205.jpg] распределена равномерно в области [img: http://localhost:8080/file/031418-206.jpg] В методе исключения выбирают точку [img: http://localhost:8080/file/031418-207.jpg] равномерно по области [img: http://localhost:8080/file/031418-208.jpg] и полагают [img: http://localhost:8080/file/031418-209.jpg], если [img: http://localhost:8080/file/031418-210.jpg] в противном случае повторяют выбор [img: http://localhost:8080/file/031418-211.jpg] и т. д. Напр., если [img: http://localhost:8080/file/031418-212.jpg] и [img: http://localhost:8080/file/031418-213.jpg] то можно полагать [img: http://localhost:8080/file/031418-214.jpg] Среднее число операций в методе исключения пропорционально величине [img: http://localhost:8080/file/031418-215.jpg] Для многих случайных величин получены специальные представления вида [img: http://localhost:8080/file/031418-216.jpg] Напр., случайные величины [img: http://localhost:8080/file/031418-217.jpg] имеют стандартное нормальное распределение и независимы; случайная величина [img: http://localhost:8080/file/031418-218.jpg] имеет гамма-распределение с параметром п;случайная величина [img: http://localhost:8080/file/031418-219.jpg] распределена с плотностью [img: http://localhost:8080/file/031418-220.jpg] случайная величина [img: http://localhost:8080/file/031418-221.jpg] имеет бета-распределение с параметрами р, п (см. [3] - [6]). Стандартный алгоритм моделирования непрерывного случайного вектора [img: http://localhost:8080/file/031418-222.jpg] состоит в последовательном выборе значений его компонент из условных распределений соответственно представлению [img: http://localhost:8080/file/031418-223.jpg] Метод исключения переносится на многомерный случай без изменений, надо лишь в его формулировке рассматривать [img: http://localhost:8080/file/031418-224.jpg] как векторы. Многомерный нормальный вектор можно моделировать с помощью специального линейного преобразования вектора независимых стандартных нормальных случайных величин. Разработаны также специальные приемы приближенного моделирования стационарных гауссовских процессов (см., напр., [3], [6]). Если в расчете по М.-К. м. моделируются случайные величины, определяемые реальным содержанием явления, то расчет представляет собой прямое моделирование (имитацию) этого явления. Разработано моделирование на ЭВМ процессов переноса, рассеяния и размножения частиц: нейтронов, гамма-квантов, фотонов, электронов и др. (см., напр., [11] - [18]); моделирование эволюции ансамблей молекул для решения различных задач классической и квантовой статистич. физики (см., напр., [10], [18]); моделирование массового обслуживания и производственных процессов (см., напр., [2], [6], [18]); моделирование различных случайных процессов в технике, гидрологии, метеорологии, геологии, химии, биологии и т. д. (см. [18]). Алгоритмы моделирования обычно тщательно обрабатывают, напр, табулируют сложные функции, изменяют стандартные процедуры и т. д. Тем не менее часто прямое моделирование не может обеспечить требуемой точности оценок искомых величин. Разработано много способов повышения эффективности моделирования. Алгоритмы М.-К. м. для оценки многократных интегралов. Пусть необходимо оценить интеграл [img: http://localhost:8080/file/031418-225.jpg] по мере Лебега в евклидовом s-мерном пространстве [img: http://localhost:8080/file/031418-226.jpg] - плотность вероятности такая, что [img: http://localhost:8080/file/031418-227.jpg] можно записать в виде мате-матич. ожидания следующим образом: [img: http://localhost:8080/file/031418-228.jpg] где [img: http://localhost:8080/file/031418-229.jpg]. Моделируя [img: http://localhost:8080/file/031418-230.jpg] на ЭВМ, можно получить Nвыборочных значений [img: http://localhost:8080/file/031418-231.jpg]. В смысле закона больших чисел [img: http://localhost:8080/file/031418-232.jpg] Одновременно можно оценить среднеквадратичную погрешность [img: http://localhost:8080/file/031418-233.jpg], т. е. величину [img: http://localhost:8080/file/031418-234.jpg], и приближенно построить подходящий доверительный интервал для [img: http://localhost:8080/file/031418-235.jpg]. Выбором плотности f можно распорядиться для получения оценки с возможно меньшей дисперсией. Напр., если [img: http://localhost:8080/file/031418-236.jpg] то [img: http://localhost:8080/file/031418-237.jpg] и если [img: http://localhost:8080/file/031418-238.jpg] то [img: http://localhost:8080/file/031418-239.jpg]. Соответствующие алгоритмы наз. существенной выборкой (выборкой по важности). Другая общая модификация - метод выделения главной части - строится в тех случаях, когда определена функция [img: http://localhost:8080/file/031418-240.jpg] с известным значением интеграла. Иногда полезны сочетания М.-К. м. с классич. квадратурами - т. н. случайные квадратурные формулы, основная идея к-рых состоит в том, что узлы и коэффициенты какой-либо квадратурной суммы (напр., интерполяционной) выбираются случайно из распределения, обеспечивающего несмещенность получаемой оценки интеграла [3]. Частными случаями этих формул являются: т. н. метод слоистой выборки, в к-ром узлы выбираются по одному в каждой части фиксированного разбиения области интегрирования, а коэффициенты пропорциональны соответствующим объемам; так наз. метод симметричной выборки, к-рый в случае интегрирования по интервалу (0, 1) определяется выражением (см. [10]) [img: http://localhost:8080/file/031418-241.jpg] При этом порядок скорости сходимости М.-К. м. повышается и в нек-рых случаях становится максимально возможным на рассматриваемом классе задач. В общем случае область интегрирования разбивается на параллелепипеды. В каждом параллелепипеде значение интеграла вычисляется через среднее значение в случайной точке и точке, симметричной ей относительно центра параллелепипеда. Ряд модификаций М.-К. м. основан на (может быть, формальном) представлении искомой величины в виде двукратного интеграла: ' [img: http://localhost:8080/file/031418-242.jpg] где [img: http://localhost:8080/file/031418-243.jpg], а вектор [img: http://localhost:8080/file/031418-244.jpg] распределен с плотностью [img: http://localhost:8080/file/031418-245.jpg]. Известно, что [img: http://localhost:8080/file/031418-246.jpg] и [img: http://localhost:8080/file/031418-247.jpg] где [img: http://localhost:8080/file/031418-248.jpg] - условное математич. ожидание, а [img: http://localhost:8080/file/031418-249.jpg] - условная дисперсия [img: http://localhost:8080/file/031418-250.jpg] для фиксированного значения [img: http://localhost:8080/file/031418-251.jpg]. Формула (1) широко используется в М.-К. м. В частности, она показывает, что [img: http://localhost:8080/file/031418-252.jpg] т. е. аналитич. осреднение по какой-либо переменной увеличивает точность М.-К. м. Однако при этом может значительно возрасти объем вычислений. Для ЭВМ время, необходимое для достижения заданной погрешности, пропорционально величине [img: http://localhost:8080/file/031418-253.jpg], где t- среднее время получения одного значения [img: http://localhost:8080/file/031418-254.jpg]. По этому критерию оптимизируется метод расщепления, простейший вариант к-рого состоит в использовании несмещенной оценки: [img: http://localhost:8080/file/031418-255.jpg] где [img: http://localhost:8080/file/031418-256.jpg] - условно независимы и распределены как [img: http://localhost:8080/file/031418-257.jpg] при фиксированном значении [img: http://localhost:8080/file/031418-258.jpg]. С помощью (1) можно получить оптимальное значение [img: http://localhost:8080/file/031418-259.jpg] где [img: http://localhost:8080/file/031418-260.jpg] - средние времена ЭВМ, соответствующие выборкам [img: http://localhost:8080/file/031418-261.jpg] (см., напр., [4]). Если подинтегральная функция зависит от параметра, то целесообразно использовать метод зависимых испытаний, т. е. оценивать интегралы для различных значений параметра по одним и тем же случайным узлам [20]. Важным свойством М.-К. м. является сравнительно относительно слабая зависимость среднеквадратич. погрешности [img: http://localhost:8080/file/031418-262.jpg] от числа измерений, причем порядок сходимости по числу узлов [img: http://localhost:8080/file/031418-263.jpg] всегда один и тот же: [img: http://localhost:8080/file/031418-264.jpg]. Это позволяет оценивать (после предварительных преобразований задачи) интегралы очень высокой и даже бесконечной кратности. Напр., разработана методика оценки интегралов Винера [19]. Алгоритмы М.-К. м. для решений интегральных уравнений 2-го рода. Пусть необходимо оценить линейный функционал [img: http://localhost:8080/file/031418-265.jpg] причем для интегрального оператора Кс ядром [img: http://localhost:8080/file/031418-266.jpg] выполняется условие, обеспечивающее сходимость ряда Неймана: [img: http://localhost:8080/file/031418-267.jpg] Цепь Маркова [img: http://localhost:8080/file/031418-268.jpg] определяется начальной плотностью [img: http://localhost:8080/file/031418-269.jpg] и переходной плотностью [img: http://localhost:8080/file/031418-270.jpg] вероятность обрыва цепи в точке [img: http://localhost:8080/file/031418-271.jpg] равна [img: http://localhost:8080/file/031418-272.jpg] N- случайный номер последнего состояния. Далее определяется функционал от траектории цепи, математич. ожидание к-рого равно [img: http://localhost:8080/file/031418-273.jpg]. Чаще всего используется т. Н. оценка по столкновениям [img: http://localhost:8080/file/031418-274.jpg] Если [img: http://localhost:8080/file/031418-275.jpg] при [img: http://localhost:8080/file/031418-276.jpg] и [img: http://localhost:8080/file/031418-277.jpg] при [img: http://localhost:8080/file/031418-278.jpg] то при нек-ром дополнительном условии [img: http://localhost:8080/file/031418-279.jpg] (см. [3]-[5]). Возможность достижения малой дисперсии в знакопостоянном случае показывает следующее утверждение: если [img: http://localhost:8080/file/031418-280.jpg] где [img: http://localhost:8080/file/031418-281.jpg] (см. [4]). Моделируя подходящую цепь Маркова на ЭВМ, получают статистич. оценки линейных функционалов от решения интегрального уравнения 2-го рода. Это дает возможность и локальной оценки решения на основе представления: [img: http://localhost:8080/file/031418-282.jpg] В ряде случаев при решении таких задач наряду с М.-К. м. применяются теоретико-числовые методы (см. [21]). М.-К. м. оценка 1-го собственного значения интегрального оператора осуществляется итерационным методом на основе соотношения [22]: [img: http://localhost:8080/file/031418-283.jpg] Все рассмотренные результаты почти автоматически распространяются на системы линейных алгебраич. уравнений вида [img: http://localhost:8080/file/031418-284.jpg] (см. [23]). Модификации М.-К. м. в теории переноса излучения (см. [11]-[17]). Для плотности среднего числа столкновений частиц в фазовом пространстве координат [img: http://localhost:8080/file/031418-285.jpg] и скоростей [img: http://localhost:8080/file/031418-286.jpg] справедливо интегральное уравнение 2-го рода, ядро к-рого в односкоростном случае кмеет вид [img: http://localhost:8080/file/031418-287.jpg] Здесь [img: http://localhost:8080/file/031418-288.jpg] - коэффициент (сечение) рассеяния,- [img: http://localhost:8080/file/031418-289.jpg] коэффициент ослабления, [img: http://localhost:8080/file/031418-290.jpg] - индикатриса рассеяния, [img: http://localhost:8080/file/031418-291.jpg] - оптич. длина пути от [img: http://localhost:8080/file/031418-292.jpg] до [img: http://localhost:8080/file/031418-293.jpg] (см. [3], [4]). Для построения оценок с малой дисперсией используются, напр., асимптотич. решения сопряженного уравнения переноса [4]; простейший алгоритм такого типа представляет собой т. н. экспоненциальное преобразование (см. [4], [11]). Разработаны модификации локальной оценки потока частиц (см. [3], [4], [11] - [13], [17], [18]). С помощью моделирования одной цепи Маркова (напр.,. физич. процесса переноса в нек-рой среде) можно одновременно получать зависимые оценки функционалов для различных значений параметров; дифференцируя "веса" [img: http://localhost:8080/file/031418-294.jpg], иногда можно строить несмещенные оценки соответствующих производных (см. [4], [12]). Это дает возможность использовать М.-К. м. при решении нек-рых обратных задач [12]. Для решения ряда задач теории переноса эффективно используется "расщепление" траекторий и аналитич. осреднение [11]. Моделирование траекторий частиц в сложных средах иногда существенно упрощается методом максимального сечения (см. [3]-[5]). Алгоритмы М.- К. м. для решения уравнении эллиптического типа строятся на основе соответствующих интегральных соотношений. Напр., стандартная пятиточечная разностная аппроксимация для уравнения Лапласа имеет вид формулы полного математич. ожидания, соответствующей симметричному блужданию по сетке с поглощением на границе (см., напр., [2], [3]). Непрерывным аналогом этой формулы является соотношение [img: http://localhost:8080/file/031418-295.jpg] где интеграл берется по поверхности сферы, целиком лежащей в заданной области, с центром в точке Р. Формула (2) и другие аналогичные соотношения дают возможность использовать процесс изотропного "блуждания по сферам" для решения эллиптич. и параболич. уравнений (см. [24], [4]). М.-К. м. эффективен, напр., для оценки решения многомерной краевой задачи в одной точке. Моделирование марковских ветвящихся процессов позволяет строить оценки решения нек-рых нелинейных уравнений, напр, уравнения Больцмана в теории разреженных газов [3].