ВВЕДЕНИЕ

0.1. Методы Монте-Карло.

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

В то же время в определении подчеркивается что:

а) речь идет о численных методах (и конкурировать они могут с классическими численными методами, а не с аналитическими методами решения задач);

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

Название «Монте-Карло» произошло от города Монте-Карло (княжество Монако), известного своим казино, ибо одним из простейших приборов для генерирования случайных чисел служит рулетка.

Официальной датой рождения методов Монте-Карло считают 1949 год, когда появилась статья под заглавием «Метод Монте-Карло» [159]. Возникновение метода связывают обычно с именами Дж. Неймана, С. Улама, Н. Метрополиса, а также Г. Кана и Э. Ферми; все они в 40-х годах работали в Лос-Аламосе (США). Необходимо сразу же подчеркнуть, что теоретические основы

методов Монте-Карло были известны значительно раньше. Более того, фактически такие методы не раз использовались для расчетов в математической статистике. Однако до появления электронных вычислительных машин (ЭВМ) методы Монте-Карло не могли стать универсальными численными методами, ибо моделирование случайных величин вручную — весьма трудоемкий процесс.

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

0.2. Общий курс методов Монте-Карло.

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

Пример. Требуется оценить объем некоторой ограниченной пространственной фигуры

Выберем параллелепипед П, содержащий G, объем которого известен (рис. 1). Выберем N случайных точек, равномерно распределенных в П, и обозначим через N количество точек, попавших в G. Если N велико, то, очевидно, откуда получаем оценку

В этом примере случайная величина равна если случайная точка попадает в G, и равна нулю, если точка попадает в . Нетрудно проверить, что математическое ожидание а среднее арифметическое

Рис. 1.

Легко видеть, что существует бесконечно много случайных величин таких, что Поэтому теория методов Монте-Карло должна дать ответы на два вопроса:

1) как выбрать удобную величину для расчета той или иной задачи?

2) как находить значения произвольной случайной величины

Изучение этих вопросов и должно составить основное содержание практического курса методов Монте-Карло.

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

Среди методов Монте-Карло можно выделить методы, в которых полностью воспроизводится модель рассчитываемого процесса. Такие методы иногда называют «физическими», хотя автору представляется более удачным другое название этих методов — имитационные. Имитация естественных процессов широко используется в самых различных областях науки, техники, экономики. Однако приемы имитаций в каждой области свои, и подробно излагать их более целесообразно в специальных руководствах, а не в общем курсе методов Монте-Карло.

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

Слово «численные» включено в заглавие книги, чтобы подчеркнуть, что здесь рассматриваются главным образом не имитационные методы.