§ 8. Метод Монте-Карло

При построении квадратурных формул вместе с формулой, как правило, получалась оценка ее погрешности на некотором классе функций. Например, для одномерной формулы трапеций была получена оценка погрешности вида на классе функций со второй производной, ограниченной по модулю постоянной здесь -число узлов интегрирования. Такого рода оценки погрешности называют гарантированными оценками погрешности на классе функций. На основании этой оценки можно гарантировать, что погрешность приближенного значения интеграла не превосходит определенной величины для всех подынтегральных функций из рассматриваемого класса. Оценивая погрешность метода как оценку на классе функций, при оценке погрешности конкретного интеграла мы ориентируемся на величину, получающуюся в случае интегрирования «худшей» функции рассматриваемого класса. Для ряда классов функций эта оценка погрешности на классе настолько плоха, что не дает никакой надежды на получение приближенного значения интеграла с требуемой точностью. Например, согласно теоремам из § 7, не существует методов с оценкой погрешности на классе функций , лучшей, чем (здесь s — кратность вычисляемого интеграла).

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

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

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

Пусть требуется вычислить приближенное значение интеграла

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

и

где

Положим

Вследствие указанных свойств величин имеем

С вероятностью выполняется неравенство (неравенство Чебышева)

Полагая получаем: с вероятностью 99% выполняется неравенство

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

распределена асимптотически нормально с функцией распределения

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

Таким образом, при больших N с вероятностью, близкой к , выполняется неравенство

Полагая и получаем, что неравенства

выполняются соответственно с вероятностями 0,997 и 0,99999. Сформулированные выше утверждения называются иногда правилами «трех сигм» и «пяти сигм» соответственно.

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

Задача 1. Показать, что

Поскольку на основании закона больших чисел с большой вероятностью выполняется приближенное равенство

то с большой вероятностью выполняется и приближенное равенство

где

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

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

а также вычисляют значение

Начальные условия рекурсии:

Если оказалось, что , то вычисления прекращаются; полагают и считают, что с вероятностью выполняется неравенство .

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

Задача 2. Проверить, что .

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

Задача 3. Показать, что

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

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

Отнесемся осторожно к этому заявлению и рассмотрим различные соображения «за» и «против» метода Монте-Карло.