авторефераты диссертаций БЕСПЛАТНАЯ  БИБЛИОТЕКА

АВТОРЕФЕРАТЫ КАНДИДАТСКИХ, ДОКТОРСКИХ ДИССЕРТАЦИЙ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ

Технология построения неструктурированных сеток и монотонная дискретизация уравнения диффузии

На правах рукописи

Данилов Александр Анатольевич

Технология построения

неструктурированных сеток

и монотонная дискретизация

уравнения диффузии

05.13.18 – Математическое моделирование,

численные методы и комплексы программ

АВТОРЕФЕРАТ

диссертации на соискание учёной степени

кандидата физико-математических наук

Москва – 2010

Работа выполнена в Учреждении Российской академии наук Институт вычислительной математики РАН.

Научный руководитель: доктор физико-математических наук, доцент, Василевский Юрий Викторович

Официальные оппоненты: доктор физико-математических наук, профессор, Агошков Валерий Иванович кандидат физико-математических наук, Гаранжа Владимир Анатольевич

Ведущая организация: Институт прикладной математики им.

М. В. Келдыша РАН

Защита состоится «24» сентября 2010 г. в 15 часов на заседании диссерта­ ционного совета Д 002.045.01 при Учреждении Российской академии наук Институт вычислительной математики РАН, расположенном по адресу:

119333, г. Москва, ул. Губкина, д. 8, ауд. 727.

С диссертацией можно ознакомиться в библиотеке Учреждения Российской академии наук Институт вычислительной математики РАН.

Автореферат разослан « » августа 2010 г.

Учёный секретарь диссертационного совета, доктор физико-математических наук Бочаров Г. А.

Общая характеристика работы

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

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

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

Научная новизна. В работе предложена технология автоматического надёжного построения тетраэдральных сеток для сложных областей на осно­ ве метода продвигаемого фронта. Проведён анализ влияния вычислительных погрешностей на алгоритмы при их реализации на ЭВМ, представлено теоре­ тическое обоснование конечности работы предложенных алгоритмов. Предло­ жена и исследована монотонная нелинейная схема на основе метода конечных объёмов для уравнения диффузии на неструктурированных сетках с много­ гранными ячейками.

Практическая значимость. Практическая значимость диссертацион­ ной работы заключается в создании и поддержке комплекса программ для автоматического построения тетраэдральных сеток и для приближённого ре­ шения задач диффузии на многогранных сетках. Программы для построения поверхностных треугольных и тетраэдральных сеток включены в библиоте­ ку программ Ani3D и находятся в свободном доступе. Решена практическая задача о стационарном распределении интерферона в лимфоузле.

На защиту выносятся следующие основные результаты:

1. Разработана технология надёжного построения неструктурированных тетраэдральных сеток, реализованы разные способы задания области, в том числе с помощью САПР.

2. Предложена и исследована новая монотонная нелинейная схема дискре­ тизации уравнения диффузии на основе метода конечных объёмов на сетках с многогранными ячейками.

3. На основе предложенных методов разработана модель стационарного распределения интерферона в лимфоузле с учётом геометрических осо­ бенностей лимфоузла.

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

М. В. Ломоносова, в Институте прикладной математики и информационных технологий, г. Павия (Италия), в Лос-Аламосской национальной лаборато­ рии, г. Лос-Аламос (США) и на следующих научных конференциях: конфе­ ренции “Тихоновские чтения” (МГУ, Москва, ноябрь 2007, октябрь 2009);



кон­ ференции “Ломоносов” (МГУ, Москва, апрель 2008, апрель 2010);

конферен­ ции “Ломоносовские чтения” (МГУ, Москва, апрель 2009, апрель 2010);

конфе­ ренция молодых учёных “Технологии высокопроизводительных вычислений и компьютерного моделирования” (СПбГУ ИТМО, С.-Петербург, апрель 2009);





конференция “Лобачевские чтения” (КГУ, Казань, ноябрь 2009);

международ­ ные конференции “NUMGRID-2006” и “NUMGRID-2008” (ВЦ РАН, Москва, июнь 2006, июнь 2008);

международная конференция “SIAM Geosciences 2009” (Лейпциг, Германия, июнь 2009);

международный научный семинар “Compu tational Mathematics and Applications” (Технологический университет Тампе­ ре, Тампере, Финляндия, сентябрь 2009).

Публикации. Основные материалы диссертации опубликованы в 6 пе­ чатных работах, из них 3 статьи в рецензируемых журналах, входящих в перечень ВАК, [1–3].

Личный вклад автора. В совместной работе [1] вклад автора заклю­ чался в разработке нелинейной схемы дискретизации уравнения диффузии в трёхмерном пространстве, в программной реализации метода и в постановке численных экспериментов.

В совместной работе [4] вклад автора заключался в разработке методов построения треугольных и тетраэдральных неструктурированных сеток.

В совместной работе [5] вклад автора заключался в разработке методов взаимодействия с САПР при построении сеток, в программной реализации алгоритмов и проведении численных экспериментов.

Структура и объём диссертации. Диссертационная работа состоит из введения, обзора методов построения сеток и комплексов программ, четы­ рёх глав, заключения и списка литературы из 73 наименований. Диссертаци­ онная работа содержит 32 рисунка и 15 таблиц. Общий объём диссертацион­ ной работы – 148 страниц.

Содержание работы Во Введении обоснована актуальность диссертационной работы, сфор­ мулирована цель и аргументирована научная новизна исследований, показана практическая значимость полученных результатов, представлены выносимые на защиту научные положения.

В обзоре методов построения сеток и комплексов программ проведён краткий анализ широко распространённых методов построения треугольных и тетраэдральных неструктурированных сеток, сделан обзор наиболее из­ вестных комплексов программ для построения неструктурированных сеток:

Triangle, TetGen, TetMesh, NETGEN и CUBIT. Автор диссертационной ра­ боты является основным разработчиком библиотек для построения неструк­ турированных треугольных и тетраэдральных сеток, входящих в свободно распространяемые пакеты библиотек Ani2D1 и Ani3D2. В обзор включено описание особенностей разработанной библиотеки и её сравнение с осталь­ ными комплексами программ. Отметим, что в пакете Ani3D предусмотрен богатый выбор способов построения поверхностных сеток [3, 4].

В первой главе предложены алгоритмы построения неструктурирован­ ных треугольных сеток для многоугольных областей.

В разделе 1.1 введены основные обозначения и понятия, используемые в первой главе.

http://sourceforge.net/projects/ani2d/ http://sourceforge.net/projects/ani3d/ В разделе 1.2 описаны основные шаги метода продвигаемого фронта, записывается формальный алгоритм (Алгоритм 1.1 ). В качестве исходных данных выступает фронт многоугольной области – дискретная граница об­ ласти с определённой ориентацией. При построении сетки алгоритм сохра­ няет заданный след на границе. Предложенный алгоритм применим как к простым многоугольникам, так и к произвольным многокомпонентным, мно­ госвязным многоугольным областям, границы которых могут не быть одно­ мерными многообразиями. На каждой итерации алгоритма около границы фронта строится подходящий треугольник, лежащий внутри расчётной об­ ласти, этот треугольник добавляется в сетку, а фронт продвигается внутрь области, ограничивая в каждый момент времени не разбитую на треуголь­ ники область. Предложенный способ построения треугольников позволяет контролировать желаемые размеры элементов в полученной сетке.

В разделе 1.3 проведено исследование устойчивости алгоритма к вы­ числительным погрешностям, возникающим при реализации алгоритма на современных ЭВМ, предлагается устойчивый алгоритм проверки пересече­ ния треугольника и отрезка на плоскости, основанный на вычислении знака определителя матрицы 2 2. Отметим, что при использовании в реализации на ЭВМ типов вещественных чисел с двойной точностью знак определителя может быть вычислен точно.

В разделе 1.4 проведён анализ Алгоритма 1.1, доказана конечность числа операций, необходимых для завершения алгоритма. В частности дока­ зано существование подходящего треугольника на каждой итерации алгорит­ ма, и получена оценка на максимальное количество построенных треугольни­ ков:

8 + 2 5, + где – количество треугольников, – площадь многоугольной области, – периметр области, – количество компонент связности и – параметр, за­ висящий от минимального расстояния между вершинами начального фронта и от функции распределения желаемых размеров треугольников в области.

В разделе 1.5 проведён анализ вычислительной сложности Алгоритма 1.1, выделены критические участки алгоритма, предложены способы ускоре­ ния работы этих участков с использованием структур данных на основе чет­ веричных деревьев поиска. В результате анализа сложности были получены оценки в среднем и в худшем случае для количества операций Алгоритма 1.1.

В упрощённом виде эти оценки записываются следующим образом: в среднем количество операций пропорционально log, и в худшем случае пропор­ ционально. Предложены две модификации Алгоритма 1.1 с улучшенны­ ми оценками количества операций в худшем случае. Первая модификация основана на результатах, полученных в разделе 1.4 при доказательстве суще­ ствования подходящего треугольника, и в худшем случае требует количество операций пропорциональное. Во второй предложенной модификации на­ кладываются дополнительные ограничения на равномерность дискретизации начального фронта: отношение минимальной и максимальной длин отрезков не должно превышать двух. В этом случае количество операций в худшем случае будет пропорционально log. Отметим, что все предложенные алгоритмы имеют среднюю сложность пропорциональную log, и на практике применяется исходный вариант Алгоритма 1.1, описанный в раз­ деле 1.2.

В разделе 1.6 рассмотрены способы улучшения качества построенной с помощью Алгоритма 1.1 сетки. Автором диссертационной работы предло­ жен метод, основанный на псевдоминимизации функционала качества сетки.

Предложенный алгоритм прост в реализации и на практике даёт хорошие результаты.

В разделе 1.7 проведены эксперименты, подтверждающие на практи­ ке среднюю оценку количества операций Алгоритма 1.1, исследовано влия­ ние способа выбора желаемого шага сетки на качество сетки и на структуру сетки. Проведена проверка работы алгоритма на сложном нерегулярном на­ чальном фронте, а также продемонстрированы возможности алгоритма для улучшения сеток, полученных для сложных областей.

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

В разделе 2.1 рассмотрены способы задания и представления в памя­ ти ЭВМ кусочно-гладких поверхностей, предложен общий способ построения дискретизации криволинейных рёбер и криволинейных граней.

В разделе 2.2 описаны возможности взаимодействия с геометрическим ядром системы автоматизации проектных работ (САПР). В работе [5] деталь­ но рассмотрен способ организации взаимодействия с промежуточной библио­ текой Common Geometry Module (CGM), предоставляющей универсальный способ доступа к данным разных САПР. В пакет Ani3D была добавлена воз­ можность подключения библиотек CGM и свободно распространяемой САПР Open CASCADE, для этого автором диссертационной работы была реализо­ вана базовая поддержка САПР Open CASCADE в библиотеке CGM.

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

В разделе 2.4 проведены эксперименты, подтверждающие на практи­ ке среднюю оценку количества операций алгоритма продвигаемого фронта на криволинейных поверхностях: количество операций в среднем пропорцио­ нально log, где – количество построенных треугольников. В каче­ стве демонстрации взаимодействия с геометрическим ядром САПР на Рис. а) б) в) Рис. 1. Модель, заданная в САПР: а) геометрическая модель, б) дискретизация криволи­ нейных рёбер, в) поверхностная квазиравномерная треугольная сетка.

приведён пример построения поверхностной сетки для модели, заданной в САПР.

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

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

Рассмотренный алгоритм не всегда строит сетку для всей области, иногда остаются лакуны – локальные несвязные части области, в которых алгоритм продвигаемого фронта не работает. На практике лакуны занимают менее 1% объёма области.

Для построения тетраэдральных сеток в лакунах в разделе 3.2 предло­ жен второй метод, основанный на тетраэдризации Делоне [6]. Доказана конеч­ ность работы второго метода. Комбинация двух методов позволяет строить сетки в трёхмерных многоугольных многосвязных многокомпонентных обла­ стях с заданным следом дискретизации на границе.

В разделе 3.3 сделан краткий обзор доступных методов улучшения ка­ чества полученной тетраэдральной сетки.

В разделе 3.4 проведено экспериментальное подтверждение оценки ко­ личества операций алгоритма продвигаемого фронта, проведено исследова­ ние распределения объёмных частей области, для которых строится сетка с помощью алгоритма продвигаемого фронта и с помощью алгоритма на основе тетраэдризации Делоне. Проведено исследование качества элементов сеток, полученных на разных этапах построения, а также изучены возможности улучшения качества с помощью доступных алгоритмов и методов. На Рис. продемонстрирован разрез тетраэдральной сетки, полученной с помощью ме­ тодов, изложенных во второй и третьей главах, на основе модели, заданной в САПР.

а) б) Рис. 2. Модель, заданная в САПР: а) геометрическая модель, б) разрез тетраэдральной сетки.

Рассмотренные методы и технология построения тетраэдральных сеток опубликованы в работе [2].

В четвёртой главе проведён обзор методов дискретизации уравнения диффузии и предложена новая монотонная нелинейная схема дискретизации на сетках с многогранными ячейками для полного анизотропного разрывного тензора диффузии. Предложенный метод, его анализ и результаты экспери­ ментов опубликованы в работе [1].

В разделе 4.1 дана постановка задачи. Пусть – трёхмерная многогран­ ная область, граница которой состоит из двух частей, =, причём множество замкнуто и непусто, =, =. Рассматривается задача диффузии для неизвестной концентрации :

div(K) = в (1) = на n · K = на, здесь K(x) = KT (x) 0 – полный анизотропный тензор диффузии, – внешние источники, и – граничные условия Дирихле и Неймана, соот­ ветственно, n – вектор внешней нормали.

В разделе 4.2 предложена новая схема дискретизации на основе мето­ да конечных объёмов с использованием нелинейного двухточечного шаблона для аппроксимации диффузионного потока на гранях расчётной сетки. Диф­ фузионный поток q на грани между двумя ячейками + и представля­ ется в виде q · n = +, + где n – нормаль к грани, направленная из + в, ± – значения дискрет­ ± ных концентраций в ±, 0 – коэффициенты, зависящие от значений концентрации в окружающих ячейках.

В разделе 4.3 приведён алгоритм решения задачи диффузии и проведён анализ монотонности предложенной схемы. Система нелинейных алгебраиче­ ских уравнений решается с помощью метода Пикара, на каждой итерации которого решается система линейных уравнений с помощью метода бисопря­ жённых градиентов (BiCGStab) с использованием предобуславливателя ILU второго порядка. Сформулирована и доказана следующая теорема.

Теорема. Пусть 0, 0, 0 и = в (1). Если начальное приближение 0 0 и линейные системы в методе Пикара решаются точ­ но, то полученное решение 0 на каждой итерации метода Пикара, 1.

В разделе 4.4 проведены эксперименты, анализирующие сохранение неотрицательности решения и выполнение дискретного принципа максиму­ ма, проведено исследование количества итераций в методе Пикара и скорости сходимости метода при различных условиях. Полученные результаты демон­ стрируют второй порядок сходимости концентрации в дискретной 2 -норме на тетраэдральных, призматических и гексаэдральных сетках, в том числе с разрывным тензором диффузии и на ячейках с неплоскими гранями. Поря­ док сходимости падает ниже второго при сильной анизотропии сетки. Дис­ кретный принцип максимума может нарушаться, но неотрицательность ре­ шения всегда сохраняется (если 0, 0, 0 и = в (1), то решение 0). Наблюдается высокая скорость сходимости метода Пикара на первых итерациях, обратная зависимость количества итераций от шага сетки и слабая зависимость от типа сетки.

В разделе 4.5 разработана модель стационарного распределения интер­ ферона в лимфоузле с учётом геометрических особенностей вторичных лим­ фоидных органов на основе уравнения диффузии-реакции. Проведена провер­ ка сходимости модели на упрощённой геометрической модели, и проведены расчёты для полной модели, состоящей из трёх подобластей, изображённой на Рис. 3.а. Отметим, что отношение характерных размеров вторичных лим­ фоидных органов и всего лимфоузла составляет величину порядка 103.

При моделировании стационарного распределения интерферона в лимфо­ узле была исследована зависимость распределения от количества источников интерферона – плазмацитоидных дендритных клеток (см. Рис. 3.б), а так­ же от скорости деградации интерферона. Важным полученным результатом является значительная неоднородность концентрации интерферона внутри лимфоузла.

а) б) Рис. 3. Стационарное распределение интерферона в лимфоузле. а) разрез построенной сетки, б) распределение интерферона (пг/л), количество плазмацитоидных дендритных клеток – 10 клеток, случайно распределённых в верхней части краевого синуса.

Основные результаты и выводы. В диссертационной работе получе­ ны следующие результаты.

Разработана технология надёжного построения треугольных и тетраэд­ ральных сеток. В работе проведён анализ влияния вычислительных погреш­ ностей при реализации алгоритмов на ЭВМ, представлено теоретическое обос­ нование конечности числа операций предложенных алгоритмов. Программы для построения треугольных, поверхностных, и тетраэдральных сеток вклю­ чены в пакет библиотек Ani3D и находятся в свободном доступе.

Разработанная технология является первым шагом на пути к созданию технологии автоматического построения конформных неструктурированных гибридных сеток с многогранными ячейками.

Для дискретизации уравнения диффузии на неструктурированных кон­ формных сетках предложена новая монотонная схема на основе метода конеч­ ных объёмов. Проведено экспериментальное исследование скорости сходимо­ сти предложенной схемы на разных типах сеток. С использованием разрабо­ танных методов и алгоритмов решена практическая задача о стационарном распределении интерферона в лимфоузле.

Список публикаций 1. Danilov A., Vassilevski Y. A monotone nonlinear finite volume method for diffusion equations on conformal polyhedral meshes // Russ. J. Numer. Anal.

Math. Modelling. 2009. V. 24, № 3. P. 207–227.

2. Danilov A. Unstructured tetrahedral mesh generation technology // Ж. Выч.

Мат. и Мат. Физ. 2010. Т. 50, № 1. С. 146–163.

3. Данилов А. А. Способы построения трёхмерных поверхностных триангу­ ляций и тетраэдральных сеток // Научно-технический вестник СПбГУ ИТМО. 2010. Т. 65, № 1. С. 87–92.

4. Василевский Ю. В., Вершинин А. В., Данилов А. А., Плёнкин А. В.

Технология построения тетраэдральных сеток для областей, заданных в САПР // Матричные методы и технологии решения больших задач / Под ред. Е. Тыртышникова. М.: ИВМ РАН, 2005. С. 21–32.

5. Василевский Ю. В., Данилов А. А. Взаимодействие с САПР для постро­ ения расчётных сеток в сложных областях // Труды Математического центра им. Н.И. Лобачевского. 2009. Т. 39. С. 5–12.

6. Данилов А. А. Построение тетраэдральных сеток для областей с заданны­ ми поверхностными триангуляциями // Численные методы, параллельные вычисления и информационные технологии. М.: МГУ, 2008. С. 119–130.



 

Похожие работы:





 
2013 www.netess.ru - «Бесплатная библиотека авторефератов кандидатских и докторских диссертаций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.