2.4. Сравнение трудоемкости алгоритмов Монте-Карло.

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

И тогда оценка окажется практически более эффективной, чем .

Обычно говорят, что «построен метод Монте-Карло» для расчета интеграла тогда, когда определена оценка вида (1), приближающая

при этом обычно предполагается, что Условимся говорить, что «построен алгоритм Апонте-Карло», соответствующий данному методу, если указаны также формулы для моделирования используемых в этом методе случайных величин. Например, оценка (14) и формула определяют метод Монте-Карло; чтобы получить алгоритм Монте-Карло, надо указать еще формулы для расчета точки Q по стандартным случайным числам. Как мы видели в гл. 2, это можно делать различными способами, так что один и тот же метод Монте-Карло может быть реализован в виде различных алгоритмов.

Рассмотрим два алгоритма Монте-Карло (безразлично соответствуют ли они разным методам или одному) для вычисления интеграла . Пусть в одном алгоритме осредняются значения случайной величины , а во втором , так что соответствующие оценки интеграла равны

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

Для того чтобы вероятная ошибка для первого из сравниваемых алгоритмов равнялась количество осредняемых значений , согласно (5), должно равняться

Время счета при этом окажется равным

Для второго алгоритма время счета, необходимое для достижения той же вероятной ошибки , равно

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

Так как трудоемкость используется обычно для сравнения алгоритмов, то вычислять ее можно в любых единицах, в частности, t можно выражать в секундах, а можно — в количествах элементарных операций. Конечно, надо предполагать, что сравниваемые алгоритмы реализуются с помощью одних и тех же вычислительных средств. Кстати, не исключена возможность того, что при переходе к другим средствам вычисления менее тру доемкий алгоритм станет более трудоемким.

Пример. Вычислить интеграл

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

Дисперсия осредняемой случайной величины равна

Так как то можно воспользоваться также геометрическим методом:

где если в противном случае. Дисперсию

осредняемой величины вычислить по формуле (20):

Таким образом, в полном согласии с

Оценим количество операций, затрачиваемых на расчет одного значения или Для расчета надо найти одно случайное число — три операции — и вычислить . На ЭВМ вычисление осуществляется путем логарифмирования с помощью стандартных программ Общее количество используемых в таком расчете элементарных операций

Для расчета надо найти два случайных числа — шесть операций — и вместо неравенства проверить равносильное неравенство . Общее количество элементарных операций в таком расчете

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

Однако тот же простейший мегод можно реализовать с помощью другого алгоритма (см. п. 4.1 гл. 2).

тогда так что трудоемкость этого алгоритма оказывается заметно меньшей.