Перестроение неструктурированных четырехугольных и смешанных сеток

ВЕСТНИК УДМУРТСКОГО УНИВЕРСИТЕТА

МАТЕМАТИКА. МЕХАНИКА. КОМПЬЮТЕРНЫЕ НАУКИ

МАТЕМАТИКА



2013. Вып.4

УДК 519.63


© А. С. Караваев, С. П. Копысов


            ПЕРЕСТРОЕНИЕ НЕСТРУКТУРИРОВАННЫХ ЧЕТЫРЕХУГОЛЬНЫХ И СМЕШАННЫХ СЕТОК ¹


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

Ключевые слова: неструктурированные сетки, смешанные сетки, перестроение сеток, шаблоны перестроений, геометрически адаптивные сетки.


            Введение


   Перестроение сетки используется для уточнения границы (геометрически адаптивные сетки) или искомого решения на определенной подобласти, в некоторых случаях их можно рассматривать как один из способов построения новой расчетной сетки. Необходимыми условиями такой операции являются конформность сетки (согласованность узлов в соседних ячейках) и сохранение выпуклости ячеек после перестроения. Важным условием является также постоянство максимальных и минимальных величин углов в ячейках при перестроении.
   Как правило, в методе конечных элементов для задач на плоскости используется деление области на треугольные и четырехугольные ячейки. При этом расчетные сетки содержат ячейки одного типа, однако применение смешанных сеток, состоящих из ячеек обоих типов, находит всё большее применение. Последние могут возникать в результате работы непрямых методов построения четырехугольных сеток, а также путем перестроения начальной сетки, содержащей ячейки только одного вида. Соответственно, алгоритмы перестроения сеток можно разделить на две группы. К первой относятся методы, генерирующие полностью треугольную или четырехугольную сетку, они являются основными и наиболее часто используются в расчетах. Вторая группа — это алгоритмы, в результате работы которых получается сетка, состоящая из треугольных и четырехугольных ячеек. Такие способы перестроения применяются в приложениях, где использование смешанных сеток является допустимым; как правило с помощью таких перестроений улучшают качество ячеек исходной сетки.
   Для методов перестроения треугольных сеток [1-3] существует два основных варианта или шаблона перестроения: бисекция — деление на два треугольника (по «большой» стороне или «новому» узлу) и регулярное перестроение — на четыре треугольника. В отношении четырехугольных сеток известно несколько схем перестроения, удовлетворяющих отмеченным выше требованиям. Однако, данные методы ориентированы на структурированные сетки, когда узлы и ячейки сетки строго упорядочены, размер и форма четырехугольников близки к идеальным показателям. Среди способов перестроения неструктурированной четырехугольной сетки основными можно считать перестроения на четыре и девять ячеек, предложенные Р. Шнейдером [4]. Используя идеи Шнейдера, сходную методику перестроения по шаблонам предложил Р. Гаримелла [5]. Также можно отметить работу М. Эбейды, Д. Оуэнса и др. [6] по модифицированию перестроения на четыре ячейки Шнейдера для случая неструктурированных сеток. Способы перестроения смешанных сеток на данный момент практически не изучены.

   Работа выполнена при финансовой поддержке РФФИ (гранты 13-01-00101, 12-07-31114).

Перестроение неструктурированных четырехугольных и смешанных сеток 63

МАТЕМАТИКА                                                       2013. Вып.4

   Далее будут рассмотрены основные алгоритмы и предлагаемые модификации для перестроения неструктурированных четырехугольных и смешанных сеток. Работа имеет следующую структуру: сначала вводятся некоторые определения и понятия, относящиеся к сеткам; в § 3 рассматриваются методы перестроения неструктурированных четырехугольных сеток и предлагается модифицированная версия алгоритма перестроения Гаримелла; § 4 посвящен перестроению смешанных сеток, описывается разработанный алгоритм перестроения неструктурированной смешанной сетки; в § 5 рассматриваются шаблоны для перестроения четырехугольных ячеек с ограничениями и приводятся практические результаты работы.



            § 1. Перестроение неструктурированных сеток


   Методы перестроения неструктурированных сеток можно разделить на следующие группы: уменьшение шага сетки и увеличение шага сетки (огрубления). В данной работе методы увеличения шага сетки не рассматриваются. Уменьшение шага сетки достигается путем деления ячеек, а также движением узлов сетки к границе области.
   Обозначим через T неструктурированную сетку, которая состоит из множества ее узлов N = UNi ni, множества ребер E = UEn ei и множества ячеек M = UMi mi. Максимальный и минимальный углы ячеек сетки определим через Oₘₐₓ, Oₘiₙ соответственно.
  Определение 1. Ячейка m называется неконформной, если существует ребро e G m, e = [n₁,n₂], И существует узел n, лежащий на данном ребре, такой, что n = n1, n = n₂.

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

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

  Определение 3. Уровнем деления ячейки (ребра) s назовем число итераций деления данной ячейки (ребра) в процессе перестроения сетки.

   Каждая уточняемая ячейка будет иметь уровень деления s > 0. На рисунке 1 приведены примеры перестроения четырехугольной сетки. В обоих случаях нижней ячейке был присвоен уровень деления s = 2, в результате она была разбита на 27 новых четырехугольников. Верхняя ячейка имела уровень деления, равный нулю, но была перестроена для обеспечения конформности сетки. Отметим, что как для первого, так и для второго случая в качестве ячеек согласующего перестроения были использованы только соседние четырехугольники, то есть область согласующего перестроения не зависела от уровня деления уточняемой ячейки.
   Одной из характеристик алгоритмов по перестроению сетки является независимость максимального и минимального углов сетки от уровней деления ее ячеек (см. рис. 1).

  Определение 4. Перестроение является устойчивым, если минимальный угол O^in пере-s
е" е2’„ > ©•, s ^ №.