Главная > Методы обработки сигналов > Численные методы
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

§ 9. Обсуждение правомерности использования недетерминированных методов решения задач

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

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

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

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

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

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

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

Пусть методом Монте-Карло вычисляется интеграл

Преположим, что в качестве узлов интегрирования мы хотим выбрать последовательность независимых равномерно распределенных точек единичного куба. Если датчик псевдослучайных чисел выдает последовательность чисел, равномерно распределенных на отрезке [0, 1], то можно попытаться в качестве узлов интегрирования взять точки .

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

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

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

Задача 1. Пусть случайные независимые величины, равномерно распределенные на отрезке [0, 1]. Пусть - дробная доля числа , т.е. , где — целая часть . Положим . Показать, что точки попарно независимы, равномерно распределены на [0, 1] и, согласно построениям предыдущего параграфа,

Задача 2. Пусть вычисляется двукратный интеграл

Показать, что при , где из задачи 1, справедливо соотношение . Вычислить

и убедиться, что, как правило, и поэтому далеко от . Задача 3. Пусть вычисляется трехкратный интеграл

При вычислить и убедиться, что, как правило, и поэтому далеко от .

Указание. Воспользоваться тем, что — — целое в пределах .

Пусть — случайные независимые в совокупности равномерно распределенные на [0, 1] случайные величины и . Положим здесь - дробная часть числа — конечная разность порядка, — число сочетаний из q по р, равное нулю при .

Пусть .

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

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

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

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

для которого .

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

<< Предыдущий параграф Следующий параграф >>
Оглавление