§1. Вычисление интегралов: считаем площадь жребием

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

Задача: площадь под кривой

Начнём с классики — посчитать интеграл

Если не вникал в интегралы — не парься, суть простая: это площадь под кривой $y = \varphi(x)$ на отрезке $[0,1]$. Надо её измерить, а аналитической формулы под рукой нет.

Честный способ: метод прямоугольников

Самый прямой подход — метод прямоугольников. Режем отрезок $[0,1]$ на $n$ равных кусков, в середине каждого берём значение функции и усредняем:

Разбираем по кирпичикам:

• $x_i = \tfrac{i-1/2}{n}$ — середины кусочков равномерной сетки (узлы стоят по струнке, через равные промежутки).
• $\varphi(x_i)$ — высота кривой в каждом узле.
• $\tfrac1n \sum$ — усредняем все высоты. Среднее высот, умноженное на ширину (а она тут равна 1), и есть приближение площади.

Для гладких функций этот способ точный: погрешность падает как $1/n^2$ (взял вдвое больше узлов — ошибка упала вчетверо). Казалось бы, зачем ещё что-то выдумывать?

Способ Монте-Карло: узлы наугад

А теперь фокус. Метод Монте-Карло отличается только одним: вместо ровной сетки узлы берут случайными. Кидаем $n$ псевдослучайных точек $\eta_1, \dots, \eta_n$, равномерных на $[0,1]$, и так же усредняем:

И — магия — это среднее тоже сходится к интегралу: $\hat I_n \to I$ при $n \to \infty$. Почему? Разберём по кирпичикам, тут красивая логика:

• Возьмём одну случайную точку $\eta$ (равномерную на $[0,1]$) и посчитаем матожидание $\varphi(\eta)$. По определению матожидания это

То есть среднее ожидаемое значение функции в случайной точке — это ровно наш интеграл.

• А теперь вспомни закон больших чисел (гл. 1): среднее арифметическое многих независимых величин сходится к их матожиданию. Значит $\hat I_n = \tfrac1n\sum\varphi(\eta_i) \to \mathbf{M}\,\varphi(\eta) = I$.

Вот и всё. Накидал случайных точек, усреднил высоты — получил площадь. По-дворовому: не хочешь честно размечать сетку — швыряй дротики наугад и считай средний улов, в итоге выйдет то же самое.

Покрути сам. Выбери функцию (например, 4·√(1−x²) → π — так можно посчитать число $\pi$ жребием!) и накидывай точки. Оценка пляшет, но с ростом $n$ садится на точное значение:

Теперь то же самое кодом — оценим $\pi$ бросанием точек. Жми Run и меняй n:

Зачем это надо, если прямоугольники точнее

Честный вопрос: раз метод прямоугольников даёт точность $1/n^2$, а Монте-Карло — хуже (точность порядка $1/\sqrt{n}$, это мы выведем в §2), то зачем вообще кидать жребий?

Для одномерного интеграла — незачем, прямоугольники рулят. Но вся сила Монте-Карло вылезает в многомерии: когда интеграл не по отрезку, а по кубу в десятках измерений, аккуратная сетка становится неподъёмной (узлов — астрономическое число), а жребию всё равно — кидай точки да усредняй. Об этом — в §3. А пока запомни главное: среднее по случайным точкам сходится к интегралу.

Проверь себя