Автор: Илья Лейрих
Тяжело не согласиться, что двадцатый век был богат на открытия. На прошедшие сто лет пришлись заря и рассвет авиации, первые полеты в космос, на кухнях появились микроволновые печи, а в карманах мобильные телефоны. И продолжать можно бесконечно. Все это – результат работы ученых и техников, теоретических разработок и сложных расчетов. И если в наши дни в теории не так часто происходят прорывы, то уж сложность расчетов растет экспоненциально.
К помощи компьютеров прибегают во многих физических задачах. Например, основополагающие уравнения гидродинамики, уравнения Навье-Стокса, связывающие основные переменные среды давление и скорость частиц в точке с их производными, давно известны. Но , даже зная начальное состояние жидкости , аналитически предсказать его развитие в общем случае сейчас невозможно. Более того, до сих пор не доказано, что такое аналитическое решение существует. Математический институт Клэя назначил премию в 1млн . долларов США за доказательство или опровержение последнего для трехмерного случая.
Но если мы, скажем, хотим рассчитать сопротивления среды для тысячи разных форм крыла, и при этом не проводить тысячу экспериментов в аэродинамической трубе , то нам эти решения получать необходимо. Причем они должны быть точными. Тут на помощь приходит компьютерное моделирование. И газодинамика не единственный пример: термодинамика, механика волн, теория напряжений, – в общем , во всех разделах механики сплошн ых сред, необходимо компьютерное моделирование. Проблемами решения дифференциальных уравнений при помощи компьютера занимается вычислительная математика. Надо заметить, что целью статьи является скорее не рассказ о вычислительной математике (уж очень она большая), а показ ценности всестороннего подхода к решаемой задаче, нестандартного взгляда на устоявшиеся вещи.
При моделировании некоего процесса на компьютере значение физических параметров (температура, давление, напряженность) рассчитывается не в каждой точке моделируемого объекта, а в конечном, пусть и очень большом, до тысяч миллионов, наборе узлов. Данные узлы , соединенные между собой ребрами , образуют сеть.
Распределить подобную сеть по объему моделируемого объекта – важная задача вычислительной математики. Важна она потому, что от этого сильно зависит качество решения. При удачном выборе системы узлов можно получить результаты , совпадающие до тысячных долей с реальным экспериментом. В противном случае моделирование даст нечто, абсолютно несвязанное с реальностью.
Возникает вопрос о построении оптимальных сеток. Что такое оптимальные сетки? – Вопрос сложный. Четкого определения не существует. И это не удивительно вычислительная математика – относительно молодая наука. Критерии могут меняться от задачи к задаче. Например в трехмерном случае оптимальная сетка может представляет собой разбиение области на подобласти простой формы, близкие к правильным тетраэдрам.
Классический подход к построению сеток состоит из двух этапов. Во-первых, создание двух независимых сетей: регулярной внутри области (те же правильные тетраэдры) и некой сети на поверхности. Во-вторых, сращивание их каким-либо образом. Программы, основанные на таком принципе, очень громоздкие. Код трудно разобрать и модифицировать. Да и результат раскладки часто оставляет желать лучшего.
Рис.1 Создание сетки в результате раскладки графа-заготовки
Недавно был предложен новый подход, взятый из теории раскладки графов. Принцип работы его можно объяснить на физической аналогии. Сначала создаем заготовку сетки – граф с достаточным количеством вершин и хорошей структурой ребер. Сожмем ее до размера, малого по сравнению с телом , которое мы хотим покрыть данной сеткой и поместим заготовку внутрь. Представим , что в узлы сетки помещены заряды одного знака, а ребра заменим пружинами. И предоставим систему самой себе. Вершины будут расталкиваться, постепенно занимая весь объем, как губка впитывающая воду. Когда система придет в равновесие , мы получим искомую сетку узлов.
Данный алгоритм прозрачен для понимания, и легко модифицируется, например мы можем использовать силы с произвольными потенциалами, задавать отталкивание от стенок объекта, а также пересматривать реберную структуру во время раскладки через определенные промежутки времени. А главное, он прост в реализации и дает хорошие результаты. Написанные программы неоспоримо подтвердили это.
Методы раскладки графов являются перспективными в вычислительной математике. И впереди еще много работы и открытий.
Литература:
[1] Persson P .- O . Strang G . A simple mesh generator in Matlab . SIAM Rev. 46-2004.
[2] В.В.Воеводин. Вычислительная математика и структура алгоритмов.-М.: Изд-во МГУ, 2006.-112 с. ISBN 5-211-05310-9
[2] Иванов В.Д., Косарев В.И., Лобанов А.И., Петров И.Б., Пирогов В.Б., Рябенький В.С., Старожилова Т.К., Тормасов А.Г., Утюжников С.В., Холодов А.С. Лабораторный практикум “Основы вычислительной математики” – М: МЗ Пресс – 2003
[3] Типовые задачи курса Вычислительной математики с решениями и теоретическими пояснениями // Экспонента, 2009.