Метод статистических испытаний

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

Используется для решения задач в областях физики, математики, экономи­ки, оптимизации, теории управления и др.

Случайные величины применялись для решения различных прикладных за­дач достаточно давно. Примером может служить способ определения числа Пи, который был предложен Бюффоном еще в 1777 г. Суть метода была в бросании иглы длиной L на плоскость, расчерченную параллельными прямыми, располо­женными на расстоянии г друг от друга.

Вероятность того, что отрезок пересечет прямую, связана с числом Пи:

где А - расстояние от начала иглы до ближайшей к ней прямой; 0 - угол иглы от­носительно прямых.

Значение интеграла(при условии, что r > L), поэтому, подсчитав долю отрезков, пересекающих прямые, можно приближенно определить это число. При увеличении количества попыток точность получаемого результата будет уве­личиваться.

Сначала Энрико Ферми в 1930-х годах в Италии, а затем Джон фон Нейман и Станислав Улам в 1940-х в Лос-Аламосе предположили, что можно использо­вать связь между стохастическими процессами и дифференциальными уравнения­ми «в обратную сторону». Они предложили использовать стохастический подход для аппроксимации многомерных интегралов в уравнениях переноса, возникших в связи с задачей о движении нейтрона в изотропной среде.

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

Годом рождения метода Монте-Карло считается 1949 г., когда в свет выхо­дит статья Метрополиса и Улама «Метод Монте-Карло». Название метода проис­ходит от названия города в княжестве Монако, широко известного своими много­численными казино, поскольку именно рулетка является одним из самых широко известных генераторов случайных чисел. Для демонстрации интегрирования ме­тодом Монте-Карло воспользуемся неформальным геометрическим описанием интеграла и будем понимать его как площадь под графиком этой функции. Дтя определения этой площади можно воспользоваться одним из обычных чис­ленных методов интегрирования: разбить отрезок на подотрезки, подсчитать пло­щадь под графиком функции на каждом из них и сложить. Предположим, что для функции достаточно разбиения на 25 отрезков и, следовательно, вычисления 25 значений функции. Если имеется n-мерная функция, то потребуется 25" отрез­ков и столько же вычислений значения функции.

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

Для определения площади под графиком функции можно использовать сле­дующий стохастический алгоритм (рис. 7):

1) ограничим функцию прямоугольником («-мерным параллелепипедом в случае многих измерений), площадь которого Spar можно легко вычислить;

2) «набросаем» в этот прямоугольник некоторое количество точек (N штук), координаты которых будем выбирать случайным образом;

3) определим число точек (К штук), которые попадут под график функции;

4) площадь области, ограниченной функцией и осями координат, S дается

выражением

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