Читать «Компьютерра PDA N71 (06.11.2010-13.11.2010)» онлайн - страница 10

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

Численное интегрирование функции методом Монте-Карло (график из "Википедии")

Предположим, нам нужно вычислить интеграл, равный площади S под кривой, изображенной на рисунке. Для этого поместим ее в прямоугольник с известной площадью U, и будем кидать в него равномерно распределенные случайные точки. Понятно, что вероятность P попадания случайной точки в интересующую нас область равна отношению площади этой области к площади прямоугольника: P = S/U. Реализуем большое количество точек N, и подсчитаем, какое количество точек K попадет под кривую. Частота K/N попадания случайных точек под кривую приближает вероятность P, и поэтому S/U ≈ K/N, а искомый интеграл приближенно равен S ≈ KU/N.

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

Одним из главных недостатков метода Монте-Карло является относительно медленное убывание погрешности приближения требуемой величины с ростом числа n реализаций случайных траекторий (точек). Эта погрешность убывает со скоростью n^-1/2. То есть для уменьшения погрешности в десять раз требуется взять в среднем в 100 раз больше траекторий (точек). Поэтому многие сложные прикладные задачи решаются долго - иногда сутками (даже на современных суперкомпьютерах).

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

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

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

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

Как компьютеры меняют работу астронома

Автор: Дмитрий Вибе

Опубликовано 08 ноября 2010 года