Лекционные материалы (стр. 2 )

Метод статистических испытаний – метод вычислительной и прикладной математики, основанный на моделировании случайных величин и построении статистических оценок для искомых величин; то же, что Монте-Карло методы. Принято считать, что метод статистических испытаний возник в 1944 году, когда в связи с работами по созданию атомных реакторов американские учёные Дж. фон Нейман и С. Улам начали широко применять аппарат теории вероятностей для решения прикладных задач с помощью ЭВМ. Первоначально метод использовался главным образом для решения сложных задач теории переноса излучения и нейтронной физики, где традиционные численные методы оказались мало пригодными. Затем его влияние распространилось на больший класс задач статистической физики, очень разных по своему содержанию. Метод применяется для решения задач теории игр, теории массового обслуживания и математической экономики, задач теории передачи сообщений при наличии помех и т. д. [14]

Итак, таинственное название «Методы Монте-Карло». Откуда оно взялось и что стоит за этим звучным наименованием? Попробуем разобраться, для чего обратимся к истории.

Некоторые эксперименты по использованию метода статистических испытаний проводились достаточно давно. Так, еще французский естествоиспытатель Бюффон выполнял эксперименты по вычислению числа p путем подбрасывания иглы и вычисления частоты пересечения иглы одной из параллельных прямых. В 1930 году Э. Ферми использовал то, что сейчас носит название методов Монте-Карло, в исследовании нейтронных потоков. Позже, он разработал «Fermiac», механическое устройство, которое использовалось в вычислениях в задачах ядерной физики. Настоящее распространение идей, связанных с подобными методами, стало реальностью с началом эры вычислительной техники, которая позволила проводить компьютерные эксперименты, в том числе и по получению случайных чисел.

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

Происхождение названия методов связано с одноименным городом в княжестве Монако, в котором расположены одни из самых известных казино в мире. Дело в том, что случайные числа и их генерация составляют «сердце» методов Монте-Карло. Рулетка казино – один из наиболее простых приборов для генерации случайных чисел[1]. Именно это и явилось наводящим соображением для названия. Как писал Стэнли Улам в автобиографии «Приключения математика», метод был назван в честь его дяди, который был заядлым игроком, по совету Метрополиса.

Датой рождения методов Монте-Карло принято считать 1949 год, когда появилась статья Улама и Метрополиса «Метод Монте-Карло» [8]. Как это часто бывало в истории науки, основным побуждающим фактором в развитии статистического моделирования стали военные исследования по заказу Министерства обороны США. Далее эти исследования не стали носить секретного характера, и результаты были успешно внедрены в разных областях, благодаря общности схемы метода и отсутствию привязки к конкретному объекту или предметной области.

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

Методы Монте-Карло. Анализ общей схемы, достоинства и недостатки

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

Принципиальная математическая основа использования методов Монте-Карло – Усиленный закон больших чисел в форме .

Теорема Колмогорова.

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

Итак, первое несомненное достоинство методов Монте-Карло – простая схема вычислительного алгоритма.

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

Следующая важная составляющая – моделирование случайных величин с заданными распределениями. Как правило, такое моделирование осуществляется путём преобразования одного или нескольких независимых значений случайного числа a, распределённого равномерно в интервале (0,1). Последовательности «выборочных» значений a обычно получают на ЭВМ с помощью теоретико-числовых алгоритмов, среди которых наибольшее распространение получил «метод вычетов». Такие числа называются «псевдослучайными», они проверяются статистическими тестами и решением типовых задач [14]. Итак, существенную роль играет качество используемых генераторов случайных чисел. Написание корректных генераторов – сложная задача, успешно решаемая в рамках разных научных и инженерных математических библиотек, например, в одной из лучших из них - Intel® Math Kernel Library (Intel® MKL), которой мы будем неоднократно пользоваться в рамках нашего курса.

Продолжая разговор о точности вычислений, посмотрим на этот вопрос немного с другой стороны. Как известно, ошибка вычислений по методу Монте-Карло обычно пропорциональна , где d – некоторая константа, а N – количество испытаний. Из формулы очевидно, что для повышения точности в 10 раз необходимо увеличить количество испытаний в 100 раз [22], а это значит, что метод Монте-Карло требует больших вычислительных ресурсов.

Примеры применения методов Монте-Карло

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

Задача вычисления площади фигуры на плоскости

Пусть дана некоторая плоская фигура F, для которой требуется найти площадь.

Введем следующие предположения:

1.  Для определенности предположим, что эта фигура целиком расположена внутри единичного квадрата.

2.  С учетом предположения 1 периметр фигуры может быть устроен совершенно произвольно.

3.  Фигура может не быть связной, т. е. может состоять из нескольких областей.

4.  Фигура может быть задана аналитически или графически.

Рис. 1.1 Площадь фигуры на плоскости. Метод Монте-Карло

Сгенерируем в квадрате N случайных точек (рис. 1.1). Пусть N* – количество точек, попавших внутрь рассматриваемой фигуры.

Тогда при достаточно больших значениях N площадь фигуры F может быть оценена как

(1.3)

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

Задача оценивания числа p

История числа p –
изящное маленькое зеркало
истории человечества.

Петр Бекманн

Из школьного прошлого всем известно, что число p есть отношения длины окружности к ее диаметру. С древних времен внимание человечества было приковано к вычислению этого замечательного числа. Первоначально, заметив, что искомое отношение постоянно и не зависит от окружности, люди пытались представить его рациональной дробью. Такие попытки предпринимались в Древнем Египте, Индии, Древней Греции. Постепенно ученые осознали бесплодность попыток найти рациональную дробь, представляющую число p, и дело сдвинулось с мертвой точки. Так Архимед, в III в до н. э. создал некоторый алгоритм приближенного вычисления p и определил, что p = 3.1419... [4]. Далее более точные решения были найдены в Древнем Китае, в Самарканде. В Европе результатами в данной области отметились Виет, Джонсон, Эйлер, ван Цейлен, Лежандр (доказал иррациональность числа), Лейбниц, Малчин.