Метод статистических испытаний, или метод Монте-Карло

Это численный метод решения математических задач при помощи моделирования случайных величин. Первые работы в рамках этого метода были выполнены математиками для определения числа π (смотрите опыт Бюффона). Опыт заключается в бросании иглы на бумагу с начерченными параллельными прямыми. Широкое применение метод получил в середине 20 ^ого века, когда были разработаны ЭВМ. В частности были полностью проведены имитационные эксперименты по созданию атомной бомбы. Первые работы были выполнены в 1949 году Джоном фон Нейманом и его учеником Уламом. В СССР статьи о методе были опубликованы в 1955-1956 годах Ю.Шрейдером, В.Владимировым. Сейчас метод используется во многих направлениях человеческой деятельности, там, где прямые эксперименты невозможны или опасны. Идея метода основана на использовании центральной предельной теоремы, в соответствии с которой формируется нормально распределенная случайная величина, равная сумме n случайных величин, а значит по правилу трех сигм можно записать:

, где Nm=a, b∙√N=σ. Указанное в скобках выражение можно разделить на N. В результате формируется выражение:

.

Это выражение получает получить основное соотношение для метода Монте-Карло в виде:

Это соотношение указывает на трудоемкость метода, так как при изменении точности на порядок, число опытов меняется на два порядка.

Является оценкой метода сверху.

Соотношения показывают, что среднее арифметическое N случайной величины x стремится к ее математическому ожиданию. При этом безразлично находятся ли один раз по одному значению каждой величины x₁, x₂, …, x_n, или N значений величины x, так как все случайные величины независимы и одинаково распределены. Название метода происходит от названия княжества Монако (Монте-Карло), так как одним из простейших механических приборов для получения случайных величин является рулетка. Принцип рулетки был реализован в 50 ^е годы для создания электронного устройства, где была неподвижная стрелка, а диск вращался, и при резкой его остановке стрелка указывала цифру. При помощи этой рулетки в 1955 году фирма RAND Corporation получила и опубликовала самую большую таблицу случайных чисел, содержащую миллион цифр расположенных случайным образом. Например, из непрозрачного ящика случайным образом устанавливается номер таблицы, затем номер строки, далее номер столбца, откуда нужно будет выбирать равномерно распределенные числа, то есть закон распределения имеет вид:

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

E

E₀

∆t ∆t t

Здесь E₀ – пороговый уровень шума. Если за время ∆t уровень шума больше E₀ четное число раз, то записывается 0, если нет, то 1. При параллельной работе m таких генераторов формируется за один такт m -разрядное двоичное число, или m -разрядная двоичная дробь, которая равномерно распределена в интервале от нуля до 1:

Недостатки метода: трудно запоминать случайные числа и нельзя исключить возникновение дрейфа. Наиболее распространенным методом получения случайных чисел в настоящее время является метод псевдослучайных чисел, который подразумевает вычисление случайных чисел по какой-либо формуле, прошедшей тестирование.

Здесь выделяются следующие методы:

· С помощью числа π.

· Метод середины квадратов: был предложен Нейманом. Суть метода в следующем: выбирается четырехзначное число γ₀=0,9876. Эта дробь возводится в квадрат γ₀²=0,97535376. Далее из полученной дроби выбираются четыре средние цифры: γ₁=0,5353, недостатком метода является генерация большого количества малых значений.

· Следующим методом является метод сравнений, который был предложен Лемером, который предложил функцию y={gx}, где g – очень большое число. Алгоритм метода заключается в следующем: определяется последовательность целых чисел, где m₀=1, а остальные элементы: x₁, x₂, …, x_n и так далее вычисляются по формуле m_k+1≡5¹⁷∙m_k(mod 2⁴⁰), где k=0, 1, 2 и так далее. Далее определяется псевдослучайное число γ_k=2^-40∙m_k. Число m_k+1 равно остатку от деления 5¹⁷∙m_k/2⁴⁰. В теории чисел он называется положительным вычетом по модулю 2⁴⁰. Отсюда название – метод сравнений или метод вычетов (смотрите алгебру вычетов), или конгруэнтный метод. Эта формула была реализована на ЭВМ, работавших с 40 ^а -разрядными числами.

В ЭВМ серии IBM System была реализована формула для счетчика RANDU. m_k+1=g∙m_k(mod 2³¹), γ_k=2^-31∙m_k. При g=65539 или 2¹⁶+3. При тестировании этого счетчика математики установили, что при n≥500 возникала систематическая погрешность. Была предложена и реализована другая функция g=5¹³. Равномерно распределенные случайные числа необходимы для моделирования других распределений.