Компьютерра PDA N71 (06.11.2010-13.11.2010) - Компьютерра

Численное интегрирование функции методом Монте-Карло (график из "Википедии") 

Предположим, нам нужно вычислить интеграл, равный площади S под кривой, изображенной на рисунке. Для этого поместим ее в прямоугольник с известной площадью U, и будем кидать в него равномерно распределенные случайные точки. Понятно, что вероятность P попадания случайной точки в интересующую нас область равна отношению площади этой области к площади прямоугольника: P = S/U. Реализуем большое количество точек N, и подсчитаем, какое количество точек K попадет под кривую. Частота K/N попадания случайных точек под кривую приближает вероятность P, и поэтому S/U ≈ K/N, а искомый интеграл приближенно равен S ≈ KU/N.

На самом деле даже в этом простейшем одномерном случае можно строить более "хитрые" весовые оценки интеграла S, позволяющие получить требуемый уровень погрешности приближения интеграла с меньшими затратами (в первую очередь - с меньшим количеством реализуемых случайных точек).

Одним из главных недостатков метода Монте-Карло является относительно медленное убывание погрешности приближения требуемой величины с ростом числа n реализаций случайных траекторий (точек). Эта погрешность убывает со скоростью n-1/2. То есть для уменьшения погрешности в десять раз требуется взять в среднем в 100 раз больше траекторий (точек). Поэтому многие сложные прикладные задачи решаются долго - иногда сутками (даже на современных суперкомпьютерах).

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

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

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

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

Как компьютеры меняют работу астронома

Автор: Дмитрий Вибе

Опубликовано 08 ноября 2010 года

Наверняка самое сокровенное желание человека, посетившего с экскурсией астрономическую обсерваторию, состоит в том, чтобы посмотреть на звёзды в настоящий большой телескоп. И его неизменно постигает разочарование: в профессиональный телескоп смотреть нельзя. То есть, не запрещено, а вообще нельзя, не предусмотрено конструкцией. В утешение можно сказать, что и профессиональный астроном всё реже и реже имеет возможность не то что посмотреть в телескоп, но и хотя бы просто лично поучаствовать в наблюдениях.

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

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

Никакой особой премудрости в этом нет: достаточно записать в виде уравнений законы сохранения (массы, импульса, энергии...), дополнить их начальными и граничными условиями, решить эти уравнения и получить наглядное описание любого физического процесса. Конечно, разобраться с уравнениями по старинке, на старых конвертах, как делал это Эйнштейн, можно лишь в редких ситуациях, но на помощь всегда готовы придти численные методы и мощные компьютеры.

В результате возникла когорта людей, к которым вполне применимы слова Станислава Лема: "Им создавать или гасить звёзды - всё равно что семечки лузгать". В небольшой объём системного блока поместилась вся безграничная Вселенная с планетами, галактиками, астероидами, Большим Взрывом, чёрными дырами и белыми карликами. Одно нажатие клавиши Enter - и вот уже закружился на экране водоворот спиральных рукавов, побежала по межзвёздному газу ударная волна, задрожали под её натиском газопылевые облака и, потеряв устойчивость, обрушились внутрь себя под собственной тяжестью.

Сжимающийся газ разогрелся до миллионов градусов, вспыхнуло в нём термоядерное пламя - и на экране зажглась звезда, за ней другая, третья... Остатки облака закружились вокруг звезды в виде плоского диска, который (кто знает?) может стать местом рождения новой планетной системы... При этом астроном-программист всё делает своими руками: сам записывает уравнения, придумывает для них программное представление, пишет код, отлаживает его, выбирает параметры ("А не взорвать ли мне сегодня звезду с массой в пятьдесят солнечных масс?"). В общем, творит миры.

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

Проблема астрономических расчётов заключается в том, что они охватывают гигантский диапазон плотностей, температур, напряжённости магнитного поля, интенсивности излучения (от радиоволн до гамма-лучей).

Возьмём, к примеру, Солнечную систему (в конце концов, нам интересно узнать, как именно мы появились во Вселенной). Масса Солнца - 2 x 1033 граммов. Чтобы собрать такую массу из межзвёздного вещества со средней плотностью порядка 10-24 г/см3, необходимо сжать газ из объёма диаметром в полтора десятка световых лет.

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

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

Как это будет выглядеть? Может быть, появятся какие-то инструменты высокого уровня, конструкторы ("Сюда перетаскиваем звезду, сюда - планеты, задаем связь один ко многим"), может быть, на составление программ для суперкомпьютеров будут подаваться заявки, подобные нынешним заявкам на наблюдения.

В любом случае, астроном лишится ещё одной возможности сделать что-то своими руками, почувствовать себя творцом Вселенной, пусть немножко ненастоящей, немножко выдуманной, вылепленной из нескольких тысяч строк кода, но такой своей, близкой и понятной!

Кафедра Ваннаха: Егор Бычков versus Nations Unies