Алгоритмы: Метод Монте-Карло

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

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

Метод имеет две основных особенности. Первая — простая структура вычислительного алгоритма. Вторая — ошибка вычислений, как правило, пропорциональна $\sqrt{D\zeta/N}$ , где $D\zeta$ — некоторая постоянная, а $N$ — число испытаний.

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

Однако одну и ту же задачу можно решать различными вариантами метода Монте-Карло, которым отвечают различные значения $D\zeta$ . Во многих задачах удается значительно увеличить точность, выбрав способ расчета, которому соответствует значительно меньшее значение $D\zeta$ .

Общая схема

Допустим, что нам требуется вычислить какую-то неизвестную величину m. Попытаемся придумать такую случайную величину $\xi$ , чтобы $M\xi =m$ . Пусть при этом $D\xi ={{b}^{2}}$ .

Рассмотрим $N$ независимых случайных величин ${{\xi }^{1}},{{\xi }^{2}},\ldots,{{\xi }^{N}}$ (реализаций), распределения которых совпадают с распределением $\xi$ . Если $N$ достаточно велико, то согласно центральной предельной теореме распределение суммы

${{\rho }_{N}}=\sum\limits_{i}{{{\xi }_{i}}}$

будет приблизительно нормальным с параметрами $M\rho_N=Nm$ , $D\rho_N=Nb^2$ .

На основе Центральной предельной теоремы (или если хотите предельной теоремы Муавра-Лапласа) не трудно получить соотношение:

$P\left( \left| \frac{{{\rho }_{N}}}{N}-m \right|\le k\frac{b}{\sqrt{N}} \right)=P\left( \left| \frac{1}{N}\sum\limits_{i}{{{\xi }_{i}}}-m \right|\le k\frac{b}{\sqrt{N}} \right)\to 2\Phi (k)-1,$

где $\Phi(x)$ — функция распределения стандартного нормального распределения.

Это — чрезвычайно важное для метода Монте-Карло соотношение. Оно дает и метод расчета $m$ , и оценку погрешности.

В самом деле, найдем $N$ значений случайной величины $\xi$ . Из указанного соотношения видно, что среднее арифметическое этих значений будет приближенно равно $m$ . С вероятностью близкой к $(2\Phi (k)-1)$ ошибка такого приближения не превосходит величины $kb/\sqrt{N}$ . Очевидно, эта ошибка стремится к нулю с ростом $N$ .

В зависимости от целей последнее соотношение используется по разному:

Если взять k=3, то получим так называемое «правило $3\sigma$ »:

$P\left( \left| \frac{{{\rho }_{N}}}{N}-m \right|\le 3\frac{b}{\sqrt{N}} \right)\approx 0.9973.$
Если требуется конкретный уровень надежности вычислений $\alpha$ ,

$P\left( \left| \frac{{{\rho }_{N}}}{N}-m \right|\le \left( {{\Phi }^{-1}}\left( (1+\alpha )/2 \right) \right)\frac{b}{\sqrt{N}} \right)\approx \alpha$

Точность вычислений

Как видно из приведенных выше соотношений, точность вычислений зависит от параметра $N$ и величины $b$ – среднеквадратичного отклонения случайной величины $\xi$ .

В этом пункте хотелось бы указать важность именно второго параметра $b$ . Лучше всего это показать на примере. Рассмотрим вычисление определенного интеграла.

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

Итак, требуется вычислить определенный интеграл:

$I=\int\limits_{a}^{b}{g(x)dx}$

Выберем произвольную случайную величину $\xi$ с плотностью распределения ${{p}_{\xi }}(x)$ , определенной на интервале $(a,b)$ . И рассмотрим случайную величину $\zeta =g(\xi )/{{p}_{\xi }}(\xi )$ .

Математическое ожидание последней случайной величины равно:

$M\zeta =\int\limits_{a}^{b}{[g(x)/{{p}_{\xi }}(x)]{{p}_{\xi }}(x)dx=I}$

Таким образом, получаем:

$P\left( \left| \frac{1}{N}\sum\limits_{i}{{{\zeta }_{i}}}-I \right|\le 3\sqrt{\frac{D\zeta }{N}} \right)\approx 0.9973.$

Последнее соотношение означает, что если выбрать $N$ значений ${{\xi }^{1}},{{\xi }^{2}},\ldots,{{\xi }^{N}}$ , то при достаточно большом $N$ :

$\frac{1}{N}\sum\limits_{i}{\frac{g({{\xi }_{i}})}{{{p}_{\xi }}({{\xi }_{i}})}\approx I}$

Таким образом, для вычисления интеграла, можно использовать практически любую случайную величину $\xi$ . Но дисперсия $D\zeta$ , а вместе с ней и оценка точности, зависит от того какую случайную величину $\xi$ взять для проведения расчетов.

Можно показать, что $D\zeta$ будет иметь минимальное значение, когда ${{p}_{\xi }}(x)$ пропорционально |g(x)|. Выбрать такое значение ${{p}_{\xi }}(x)$ в общем случае очень сложно (сложность эквивалентна сложности решаемой задачи), но руководствоваться этим соображением стоит, т.е. выбирать распределение вероятностей по форме схожее с модулем интегрируемой функции.

Вычисление числа Пи

С помощью метода Монте-Карло можно вычислить число Пи.

Вписав круг в квадрат (диаметр круга равен стороне квадрата), можно выразить отношение площади круга к площади квадрата следующим образом:

Если мы сможем вычислить это отношение, значит, мы сможем получить значение числа Пи.

Заполним квадрат точками со случайными координатами. Рассчитаем отношение количества точек, попавших в круг, к общему количеству точек. Умножим результат на 4, чтобы получить значение числа Пи.

Чем больше количество точек, тем ближе полученное значение к истинному значению числа Пи.

Этот простой пример демонстрирует метод Монте-Карло в действии.

Поиск по этому блогу

Computer Science