РусҚаз

Метод Монте-Карло

Информатика · 10 класс · Моделирование и симуляции · Урок 3 из 4

Открыть интерактивный урок ›Опыт своими руками, лекция голосом, ИИ-наставник и тест. Бесплатно.

Что это

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

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

Зачем это нужно

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

Художница анимационной студии смотрит на большой монитор, где постепенно проявляется реалистичная сцена с мягким светом из окна.

Как это работает

Если точки падают в квадрат совершенно случайно, то в любую его часть попадает доля точек, примерно равная доле её площади. Значит, посчитав, какая часть точек попала в круг, мы узнаём, какую часть квадрата он занимает, а отсюда и число пи. Каждая серия бросков даёт немного другой ответ — это случайная ошибка. Чем больше точек, тем ответ точнее, но точность растёт медленно, поэтому результат всегда записывают вместе с оценкой погрешности.

На экране компьютера квадрат постепенно заполняется тысячами цветных точек, а внутри него проступает круг.

Немного истории

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

Математик в пижаме сидит в постели в комнате сороковых годов и раскладывает на одеяле пасьянс, задумчиво глядя на карты.

Формула: оценка числа пи

Круг радиуса один вписан в квадрат со стороной два. Площадь квадрата равна четырём, а площадь круга — пи умножить на радиус в квадрате, то есть просто пи. Значит, доля точек в круге примерно равна пи делённое на четыре, и отсюда пи примерно равно четыре умножить на эм делённое на эн. Эн — сколько всего брошено точек, эм — сколько из них попало в круг, обе величины — просто числа. А попала ли точка в круг, проверяют по координатам: икс в квадрате плюс игрек в квадрате не больше единицы, то есть точка лежит не дальше радиуса от центра. Чем больше точек бросить, тем ближе оценка к трём целым четырнадцати сотым.

  • π ≈ 4 · M / Nπ — число пи, —
    M — точек внутри круга, —
    N — всего точек, —
  • x² + y² ≤ 1x — первая координата точки, —
    y — вторая координата точки, —

Формула: ошибка метода

Почему ответ уточняется так медленно? Случайные отклонения отдельных бросков частично гасят друг друга, но не до конца, и типичная ошибка оказывается обратно пропорциональна корню квадратному из числа точек. Записывают это так: дельта пропорциональна единице, делённой на корень из эн. Дельта — типичная ошибка оценки, эн — число точек в серии, обе величины безразмерные. Если увеличить число точек, ошибка уменьшится, но гораздо слабее, чем выросло число точек: например, вчетверо больше точек дают ошибку меньше всего вдвое.

  • δ ~ 1/√Nδ — типичная ошибка оценки, —
    N — число точек в серии, —

Что будем делать на практике

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

Задание в опыте

Проведите по 3 серии из 100 точек и по 3 серии из 10 000 точек, сравните разброс оценок π на графике и ответьте на вопрос под ним.
Открыть интерактивный урок ›Опыт своими руками, лекция голосом, ИИ-наставник и тест. Бесплатно.

Уроки темы: Моделирование и симуляции

  1. Что такое модель
  2. Модель роста
  3. Метод Монте-Карло
  4. Симуляция мира