Дискретизация сложных двумерных и трехмерных областей для решения задач математического моделирования

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

АВТОРЕФЕРАТ

диссертация на соискание ученой степени кандидата физико-математических наук

Дискретизация сложных двумерных и трехмерных областей для решения задач математического моделирования

Специальность 05.13.18 - "Математическое моделирование, численные методы и комплексы программ"

Щеглов И.А.

Москва - 2010

Работа выполнена на кафедре "Прикладная математика" Московского государственного технического университета имени Н.Э. Баумана

Научный руководитель: доктор физико-математических наук, профессор Галанин Михаил Павлович

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

доктор физико-математических наук, профессор Мухин Сергей Иванович

Ведущая организация: ФГУП «Центральный институт авиационного моторостроения имени П.И. Баранова»

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

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

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

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

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

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

1. Анализ существующих методов дискретизации и возможностей их использования для дискретизации сложных областей.

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

3. Решение ряда задач математического моделирования в сложных областях с помощью разработанного программного комплекса.

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

Достоверность и обоснованность полученных результатов обеспечена строгостью используемого математического аппарата и подтверждена успешным применением на практике.

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

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

· Разработанные автором алгоритмы двумерной и трехмерной дискретизации сложных областей и оптимизации сеток.

· Разработанный программный комплекс Gridder.

· Решенные с помощью комплекса Gridder задачи математического моделирования.

Апробация работы. Результаты работы докладывались на следующих семинарах и конференциях: II научно-методическая конференция аспирантов и молодых исследователей «Актуальные проблемы фундаментальных наук», МГТУ им. Н.Э. Баумана, (Москва, 2008); VI Республиканская научная конференция молодых учёных и студентов «Современные проблемы математики и вычислительной техники», (Брест, Беларусь, 2009); VII International Seminar on Mathematical Models and Modeling in Laser-Plasma Processes (Москва, 2010); семинар отдела №11 ИПМ им. М.В. Келдыша РАН "Вычислительные методы и математическое моделирование", (Москва, 2010).

Публикации. Основные научные результаты диссертации опубликованы в девяти печатных работах, в том числе в двух статьях в изданиях из Перечня ведущих научных журналов и изданий ВАК РФ [4, 5], в составе энциклопедического издания [7], в четырех препринтах [1, 2, 3, 6] и в двух тезисах докладов [8, 9].

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

Структура и объем работы. Диссертация состоит из введения, трех глав, заключения и списка литературы. Работа представлена на 163 страницах и содержит 101 иллюстрацию. Список литературы содержит 99 наименований.

Содержание работы

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

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

В первом разделе поставлена проблема оценки качества сеток. Всего таких оценок предложено достаточно много; некоторые варианты приведены в таблицах 1 и 2.

Таблица 1. Некоторые критерии оценки качества треугольных элементов

Таблица 2. Некоторые критерии оценки качества тетраэдрических элементов

Однако использовать эти оценки явным образом достаточно неудобно, поскольку требуется знать пределы изменения оценки и оптимальное значение. Для решения этой проблемы предложено ввести понятие аппроксимационной характеристики (АХ) элемента: эта величина получается при отображении значения используемой оценки на отрезок [0, 1] так, что чем ближе она к 1, тем ближе качество элемента к идеальному. В работе были использованы оценки: "отношение длины наибольшего ребра к радиусу вписанной окружности" для треугольников и "отношение объема тетраэдра к наибольшему из произведений длин тройки ребер, выходящих из одной вершины" для тетраэдра. Эти оценки являются одними из наиболее достоверных, а кроме того, явным образом входят в некоторые оценки ошибки аппроксимации для метода конечных элементов, откуда и пошло название "аппроксимационная характеристика".

Во втором разделе приведена авторская классификация методов дискретизации, представленная в форме диаграммы на рис. 1.

Рис. 1. Классификация методов дискретизации

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

Четвертый раздел посвящен итерационным методам. В первом его подразделе рассмотрены методы граничной коррекции. Описана проблема построения первичной сетки на примере алгоритма QuadTree. Приведен разработанный автором алгоритм коррекции первичной сетки для трехмерного случая. Указаны достоинства (высокая, в сравнении с другими итерационными методами, скорость работы; возможность применения для дискретизации сложных областей) и недостатки (низкая надежность, ограниченная возможность применения) данного класса методов. Во втором подразделе обсуждаются методы на основе критерия Делоне. Указана принципиальная отличительная особенность методов - сначала в области размещаются узлы, а затем между узлами устанавливаются связи с помощью критерия Делоне либо иного схожего критерия. Описана методика преобразования произвольной двумерной сетки к триангуляции Делоне. Приведен пример одного из вариантов алгоритма построения триангуляции Делоне на заданном наборе точек. Описана методика построения триангуляции Делоне с ограничениями в двумерном и трехмерном случаях. Обозначены проблемы, затрудняющие применение методов на основе критерия Делоне в трехмерном случае. В третьем подразделе описаны методы исчерпывания, их общая идея и некоторые варианты реализации. Указана их ключевая особенность - в качестве входных данных требуется триангуляция границы, что может быть как достоинством (при построении согласованной триангуляции), так и недостатком (в остальных случаях).

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

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

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

Блок-схема 1. Общий алгоритм дискретизации сложной трехмерной области

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

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

Блок-схема 2. Алгоритм двумерной триангуляции "от угла"

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

дискретизация треугольный двумерный gridder

Блок-схема 3. Алгоритм трехмерной дискретизации "от ребра"

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

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

Рис. 2. Этапы построения сетки в сложной двумерной области
с помощью ПК Gridder

Комплекс Gridder предназначен для симплициальной дискретизации сложных плоских и пространственных областей. Геометрия областей описывается системой ориентированных контуров из ломаных линий на заданном наборе опорных точек, т.е. в двумерном случае входными данными являются один или несколько многоугольников (они могут быть невыпуклыми и содержать отверстия также в форме многоугольников), а в трехмерном - один или несколько многогранников, которые также могут быть невыпуклыми и содержать полости. Предусмотрена возможность импорта геометрии из некоторых стандартных форматов. У пользователя есть возможность устанавливать коэффициенты сгущения сетки, шаг триангуляции, уровень оптимизации и присваивать подобластям, фрагментам границы и отдельным точкам уникальные идентификаторы, позволяющие легко задавать граничные условия в решателе. Комплекс позволяет строить сетки как в консольном режиме, так и с помощью визуального интерфейса (в этом случае пользователю доступны дополнительные инструменты, такие как визуализация сетки и оценка ее качества). Также разработаны и версии в форме динамических библиотек. С помощью комплекса Gridder можно строить сетки, содержащие до 2 млн. элементов. На рис. 3 и 4 приведены примеры сеток, построенных в комплексе.

Рис. 3. Примеры двумерных сеток

Рис. 4. Примеры трехмерных сеток

Во втором разделе приведены примеры задач математического моделирования, решенных с помощью комплекса Gridder: задача для уравнения Лапласа, задача теории линейной упругости в композиционном материале, задача об МГД-насосе и задача о движении пластинчатого лайнера в магнитном компрессоре. Так как диссертационная работа посвящена вопросам построения сеток, а также в виду ограниченного объема автореферата, мы приведем здесь лишь краткие постановки задач, а полученные результаты ограничим иллюстративной выборкой.

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

Здесь U (потенциал) - функции от x и y в двумерном и от x, y и z - в трехмерном случае; - константы, - граница области. На рис. 5 показаны сетка и решение для одного из двумерных вариантов задачи, а на рис. 6 - для одного из трехмерных.

Рис. 5. Сетка и полученное на ней решение двумерной задачи для уравнения Лапласа. В точечном контакте 1 задано условие U=1, в контакте 2 - U=5

Рис. 6. Срез сетки и полученное на ней решение трехмерной задачи для уравнения Лапласа. На нижней грани задано условие U=10, а одном из углов верхней грани - U=1

МГД-насос - это устройство для перекачки жидкого метала с помощью бегущего магнитного поля. На рис. 7,а представлена принципиальная схема этого устройства. Область моделирования в этой задаче состоит из большого количества подобластей сильно разнящихся размеров, что требует использования сеток со сгущением. Задача обладает осевой симметрией, поэтому решается в пространственно-двумерном приближении. Математическая модель представлена уравнениями Максвелла в МГД-приближении (1), уравнениями Навье-Стокса (2) и уравнением теплового баланса (3).

(1)

Здесь E и H - напряженности электрического (в системе координат, где вещество покоится) и магнитного полей соответственно, - магнитная индукция, - магнитная проницаемость, j - вектор плотности тока, t - время, v - скорость движения вещества (в данном случае жидкого металла; скорость остальных частиц в области равна нулю).

(2)

Здесь с - плотность вещества, p - гидродинамическое давление, з = с н - коэффициент динамической вязкости, н - коэффициент кинематической вязкости, v - вектор скорости, - сила Лоренца.

. (3)

Здесь T - температура среды, c_v - удельная теплоемкость вещества, к - теплопроводность, - мощность выделения энергии, включающая в себя джоулеву теплоту и источник теплоты за счет вязкости.

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

На рис. 7,б и 7,в приведены построенная сетка и полученное решение в один из моментов времени (показаны тангенциальная компонента напряженности электрического поля и моментальные линии тока для r- и z-компонент напряженности магнитного поля).

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

а) б) в)

Рис. 7. Схема области (а), построенная сетка (б) и решение на ней (в) для задачи об МГД-насосе

Рис. 8. Принципиальная схема магнитного компрессора

Электродинамическая часть математической модели представлена уравнениями Максвелла в МГД-приближении (1), дополненными уравнениями для внешних электрических цепей:

Здесь L, R, C - индуктивность, сопротивление и емкость в цепи соответственно, I и U - сила тока в цепи и напряжение на обкладках конденсатора, - плотность поверхностных магнитных токов.

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

В модели термоупругого тела лайнер описывается уравнениями:

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

Рис. 9. Схема области в начальный момент времени (слева) и построенная в области сетка в один из последующих моментов времени (справа). Отдельно показаны увеличенные фрагменты сетки

Соответствующее уравнение энергии записано в виде уравнения теплопроводности:

где - удельная массовая теплоемкость при постоянной деформации, - коэффициент теплопроводности, - мощность тепловыделения.

На рис. 9 показана схема области решения и построенная для нее сетка в один из моментов времени. На рис. 10 приведено распределение напряженности электрического поля в этот же момент времени для модели термоупругого лайнера.

Рис. 10. Напряженность электрического поля для модели термоупругого лайнера в один из моментов времени. Справа показан увеличенный фрагмент графика вблизи края лайнера

На примере данной задачи также можно продемонстрировать, сколь велико может быть влияние качества сетки на качество решения. На рис. 11 приведены решения одной и той же задачи (показаны положение и форма лайнера в варианте модели жидкого тела в различные моменты времени). Решение на графике слева получено на качественных сетках, созданных с помощью ПК Gridder, а решение на графике справа - на низкокачественных сетках, содержащих большое количество вытянутых треугольников. Хотя качественно решения похожи, между ними имеются значительные количественные различия.

Рис. 11. Положение и форма лайнера в варианте модели жидкого тела в различные моменты времени. Решение на графике слева получено на сетках, построенных в ПК Gridder, а решение на графике справа - на низкокачественных сетках, использовавшихся ранее

Основные выводы

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

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

3. С помощью разработанного программного комплекса решен ряд задач математического моделирования: модельная задача для уравнения Лапласа, задача об МГД-насосе, модельная задача линейной упругости в ячейке композиционного материала, задача о движении пластинчатого лайнера в магнитном компрессоре.

Основные результаты диссертации опубликованы в работах

1. Галанин М.П., Щеглов И.А. Разработка и реализация алгоритмов трехмерной триангуляции сложных пространственных областей: прямые методы. М., 2006. 32 с. (Препринт ИПМ им. М.В. Келдыша РАН, № 10).

2. Галанин М.П., Щеглов И.А. Разработка и реализация алгоритмов трехмерной триангуляции сложных пространственных областей: итерационные методы. М., 2006. 32 с. (Препринт ИПМ им. М.В. Келдыша РАН, № 9).

3. Применение метода конечных суперэлементов для расчета напряженно-деформированного состояния композиционных материалов / И.А. Щеглов [и др.] 2006. 32 c. (Препринт ИПМ им. М.В. Келдыша РАН, № 36).

4. Применение метода конечных суперэлементов для расчета характеристик дисперсно-армированных композиционных материалов / И.А. Щеглов [и др.] // Вестник МГТУ им. Н.Э. Баумана. Естественные науки. 2007. №3. С. 54-68.

5. Щеглов И.А. Использование вспомогательного массива узлов при дискретизации сложной трехмерной области методом исчерпывания // Вестник МГТУ им. Н.Э. Баумана. Естественные науки. 2008. № 2. С. 270-283.

6. Щеглов И.А. Программа для триангуляции сложных двумерных областей Gridder2D. М., 2008. 32 с. (Препринт ИПМ им. М.В. Келдыша РАН, №60).

7. Двумерная и трехмерная триангуляция / М.П. Галанин, И.А. Щеглов
// Энциклопедия низкотемпературной плазмы. М.: Янус-К, 2008. Т. VII, Ч. 1. С. 319-342.

8. Щеглов И.А. Разработка программного комплекса для дискретизации сложных пространственных областей // Актуальные проблемы фундаментальных наук: Сборник трудов. М., 2008. С. 78-81.

9. Щеглов И.А. Методы дискретизации сложных пространственных областей // Современные проблемы математики и вычислительной техники: Материалы VI Республиканской научной конференции молодых ученых и студентов. Брест, 2009. Ч. 1. С. 113-115.

Размещено на Allbest.ru