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

ФГУП «Российский федеральный ядерный центр –  
Всероссийский научно-исследовательский институт  
экспериментальной физики» 
 
 
 
А. А. Воропинов 
 
 
МЕТОДЫ РЕШЕНИЯ ЗАДАЧ 
ГАЗОДИНАМИКИ  
НА НЕСТРУКТУРИРОВАННЫХ СЕТКАХ 
 
Курс лекций 
В 3 частях 
 
Часть 2  
РАЗНОСТНЫЕ СХЕМЫ 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Саров 
2016 

Введение 
2 

УДК 519.6 
ББК 22.19 
        В75 
 
Воропинов, А. А. 
В75  Методы решения задач газодинамики на неструктурирован- 
        ных сетках : курс лекций : в 3 ч. / А. А. Воропинов. – Саров: ФГУП 
        «РФЯЦ-ВНИИЭФ», 2016. 
      ISBN 978-5-9515-0207-0 
 
      Ч. 2: Разностные схемы. – 2016. – 83 с.: ил. 
       ISBN 978-5-9515-0325-1 
 
Издание рассматривает методики, предназначенные для 
решения задач механики сплошной среды на неструктурированных многоугольных и многогранных сетках. Это методики ДМК, ТИМ и МЕДУЗА, применяемые в Институте теоретической и математической физики РФЯЦ-ВНИИЭФ. 
Курс лекций предназначен для студентов старших курсов 
и аспирантов по специальности «Прикладная математика». 
 
 
УДК 519.6 
 ББК 22.19 
 
 
 
 
 
 
 
 
 
 
 
 
 
ISBN 978-5-9515-0325-1 (ч. 2)  
 
ISBN 978-5-9515-0207-0  
 
© ФГУП «РФЯЦ-ВНИИЭФ», 2016 

 

Методы решения задач газодинамики… 
3

 

ВВЕДЕНИЕ 
 
Этот курс посвящен методикам, предназначенным для решения 
задач механики сплошной среды на неструктурированных многоугольных и многогранных сетках. Это методики ТИМ [1, 2], ДМК 
и МЕДУЗА [3], разработанные в Институте теоретической и математической физики (ИТМФ) РФЯЦ-ВНИИЭФ. 
Методика включает в себя совокупность различных методов 
и алгоритмов, нацеленных на решение определенного класса задач. 
При этом каждая методика – это «живой» организм: в рамках методики создаются новые методы, улучшаются старые с целью расширить класс решаемых задач, ускорить проведение расчетов, снизить 
трудозатраты на их проведение. В результате в каждой методике 
возникает переплетение методов – особенности одного алгоритма 
учитываются в других. Из-за сильной взаимосвязи различных тем 
данный курс оказывается труден для студентов. С другой стороны, 
слишком глубоко особенности методик в курсе не рассматриваются, большая часть математических выкладок остается «за кадром», 
для самостоятельного изучения, а особое внимание уделено именно 
взаимосвязи вопросов, характерной не только для рассматриваемых методик, но и всех крупных научных программ. 
Настоящий курс лекций состоит из нескольких разделов, в которых рассматриваются вопросы возможности создания методик, 
позволяющих решать задачи двумерной и трехмерной нестационарной газовой динамики на неструктурированных сетках, сохраняя их несамопересекающимися в процессе расчета задачи. Максимальное внимание уделено вопросам, относящимся именно к неструктурированным методикам: это построение сетки, разностных 
схем, поддержание качества сетки, возможности адаптации сетки 
в процессе решения задач. 
Первая часть курса [4] описывала алгоритмы построения исходной расчетной сетки. Вторая часть курса посвящена вопросам 
построения форматов для описания неструктурированных сеток 
и разностным схемам газовой динамики. В курсе рассматриваются 

 

Введение 
4 

в основном методики для решения двумерных задач, а также основные особенности, возникающие в трехмерном случае.  
Автор выражает благодарность Бутневу О. И., Еременко А. Ю., 
Мотлохову В. Н., Панову А. И., Пронину В. А., Соколову С. С., 
Урму В. Я. за предоставленный материал, использованный при разработке данного пособия. 
 
 
 
 

Глава I 
 
ФОРМАТЫ ОПИСАНИЯ НЕСТРУКТУРИРОВАННЫХ СЕТОК 
ПРОИЗВОЛЬНОГО ВИДА 
 
Одной из ключевых особенностей использования неструктурированных сеток является необходимость хранения дополнительной 
информации о соседстве для различных элементов сетки. Это требует введения дополнительных структур данных и создания дополнительных алгоритмов, работающих с ними и получающих информацию об этом соседстве. Такие структуры данных будем называть 
форматом хранения. 
Основное требование к формату хранения информации 
о структуре сетки – его полнота, т. е. возможность получить информацию о соседстве для любого элемента сетки. При этом одновременно должны выполняться две во многом противоположные 
задачи: во-первых, данные о структуре сетки должны занимать как 
можно меньше оперативной памяти ЭВМ из расчета на одну счетную точку, а во-вторых, информацию о соседстве для элемента сетки нужно уметь получать с высокой скоростью. В реальных условиях эти задачи сложно решить одновременно, поэтому при построении формата необходимо учитывать, к каким типам данных 
будем обращаться чаще всего при проведении расчетов. Оценивать 
форматы будем по этим основным характеристикам: объем требуемой памяти и скорость получения соседства. 
При разработке формата обязательно учитывается способ 
центрирования величин. Если какие-то счетные алгоритмы используют величины, относящиеся к элементу сетки (ячейке, ребру, узлу), то этот элемент должен присутствовать в формате хранения. В дальнейшем будем рассматривать форматы данных, ориентированные на ячеечно-узловое центрирование (хотя некоторые 
форматы позволяют использовать и другое центрирование с небольшими модификациями), а также форматы, позволяющие описать сетки, состоящие из ячеек – произвольных многоугольников, 
в узлах которых может сходиться произвольное количество ребер. 

Глава I. Форматы описания неструктурированных сеток… 
6 

Речь идет, в первую очередь, о рабочих данных, хранящихся 
в оперативной памяти ЭВМ, и об использовании форматов для 
реализации счетных алгоритмов для получения соседства элементов сетки. Для долговременного хранения сетки на носителе (жесткие диски, ленты и др.) многие форматы часто могут быть существенно сокращены. 
 
1.1. Подходы к выработке формата хранения  
неструктурированной сетки 
 
При построении форматов хранения неструктурированной сетки используют различные подходы. Часто строятся форматы, содержащие минимальную информацию о сетке. Преимущество такого подхода заключается в том, что эти форматы практически не 
содержат избыточной информации и поэтому оказываются весьма 
экономичными по объему требуемой памяти. Однако при проведении расчетов использовать такие форматы бывает затруднительно, 
так как для некоторых элементов сетки может потребоваться выполнение операций глобального поиска для получения информации о соседстве. В процессе расчетов использование глобального 
поиска неприемлемо, так как приводит к возрастанию сложности 

алгоритмов получения соседства с 
(
)
O N  или 
(
)
log
O N
N до (
)
2
O N
. 

Применение таких форматов целесообразно, например, при сохранении разреза, для уменьшения объема файла-разреза.  
Один из широко распространенных методов использует соседство между элементами сетки смежных размерностей как 
в большую, так и в меньшую сторону. В трехмерном случае это 
выглядит следующим образом. Для ячейки (трехмерного объекта) 
хранятся грани (двумерные объекты), для грани хранятся ячейки 
и ребра (одномерные объекты), для ребра хранятся грани и узлы 
(объекты нулевой размерности). Условно такой подход можно назвать связанными размерностями. Его преимущество – в универсальности: формат хорошо подходит для алгоритмов, использующих различное соседство. Недостаток формата – большая избыточность и, как следствие, большой объем памяти. Форматом, близким 
к такому типу по набору информации, можно считать реберно

Методы решения задач газодинамики… 
7

ячеечно-узловой, описанный в п. 1.2.6 (хотя получен он по принципу «основного элемента»). 
Подход, который в дальнейшем будет использоваться в качестве основного, заключается в выделении «основного элемента» сетки. Для «основного элемента» информация о соседстве сохраняется 
наиболее полно, для других элементов хранится минимум информации, обычно только связь с «основным элементом». При этом 
если в качестве «основного» выбирать тот элемент сетки, по которому построено большинство алгоритмов методики, то это практически не скажется на скорости работы алгоритмов. Такой подход 
позволяет строить достаточно экономичные форматы хранения. 
Недостатком подхода является необходимость выполнения дополнительных операций поиска для получения информации о соседстве в «неосновных» элементах сетки. 
При построении формата необходимо учитывать различные 
дополнительные особенности и ограничения, которые могут встречаться в сетке. Эти особенности могут быть характерны для конкретной методики (например, методика МЕДУЗА использует треугольные сетки для описания соседства между центрами ячеек) или 
происходить из базовых положений построения методик. Например, для всех трехмерных методик используются ориентируемые 
многогранники, так как только для них (см. ч. 1, гл. III, § 1 настоящего пособия) возможно введение понятия объема. Это ограничение на ячейки позволяет ввести правило обхода (например, при перечислении узлов грани). В дальнейшем будем использовать обход 
«против часовой стрелки». 
Некоторые ограничения могут, на первый взгляд, показаться искусственными, однако зачастую они позволяют упростить и ускорить работу алгоритмов поиска соседства. Необходимо реализовать 
формат таким образом, чтобы описание особенностей и ограничений не требовало введения дополнительных признаков и дополнительных операций поиска соседства, повышающих стоимость алгоритмов. Другое ограничение, часто накладываемое на формат, связано с описанием граничных элементов сетки. Для опознавания 
граничных элементов в формате вместо соответствующей ячейки 
хранится номер граничного условия. Для определения того, что это 

Глава I. Форматы описания неструктурированных сеток… 
8 

именно граничное условие, его номер может храниться, например, 
со знаком минус.  
 
1.2. Двумерные форматы хранения 
 
Рассмотрим ряд форматов, предназначенных для описания 
неструктурированной двумерной сетки произвольного вида. На 
практике сетка произвольного вида часто близка по своей структуре и общим характеристикам к равномерной сетке одного из 
трех типов: треугольной, четырехугольной или шестиугольной. 
При этом она либо имеет один из таких видов с небольшим количеством особенностей, либо близка к одному из таких типов в усреднении на одну точку, либо является смешанной сеткой из этих 
типов. Поэтому для тестирования были использованы следующие 
типы сеток (рис. 1): 
1) треугольная сетка, во внутреннем узле которой сходятся 
6 ребер; сетка представляет интерес не только для двумерных методик, но и для работы с триангулированными поверхностными 
сетками; 
2) четырехугольная сетка, во внутреннем узле которой сходятся 4 ребра; такая сетка часто используется в качестве начальной, 
может обладать особенностями; 
3) шестиугольная сетка, во внутренних узлах которой сходятся 
по 3 ребра; граничные ячейки в этой сетке содержат по 4–5 узлов. 
 

 

Рис. 1. Фрагменты многоугольных сеток различного типа 

При выполнении оценок требуемой памяти будем считать, что 
сетка не имеет особенностей, и не будем учитывать наличие гра

Методы решения задач газодинамики… 
9

ниц. В реальных сетках количество особенностей, нарушающих 
некоторую упорядоченность, как правило, невелико, и для выполнения оценок ими можно пренебречь. Граничными точками тоже 
пренебрегаем, так как их количество также невелико для сеток, состоящих большого количества ячеек (например, для сетки из порядка миллиона ячеек количество граничных точек не превышает 
нескольких десятых процента). 
Введем следующие обозначения: N – общее количество ячеек; 
L – количество узлов; K – количество ребер; k – количество ребер, 
сходящихся во внутреннем узле (или количество ячеек, окружающих узел); i – количество узлов у ячейки (или количество соседних 
ячеек). В зависимости от типа сетки эти величины принимают следующие значения:  

• для треугольной сетки 
,
2
N
L =
 
3
,
2
K
N
=
 
6,
k =
 
3;
i =
 

• для четырехугольной сетки 
,
L
N
=
 
2 ,
K
N
=
 
4,
k =
 
4;
i =
 
• для шестиугольной сетки 
2 ,
L
N
=
 
3 ,
K
N
=
 
3,
k =
 
6.
i =
 
Оценки будем выполнять с усреднением на одну ячейку, 
т. е. требуемая память на всю сетку выражается через количество 
ячеек N.  
 
1.2.1. О хранении списковых массивов переменой длины 
 
Поскольку форматы хранения рассматриваются применительно к произвольным сеткам, состоящим из многоугольных ячеек 
с любым количеством узлов и произвольным количеством ребер 
в узле, то при организации почти всех форматов требуется организация списков, т. е. массивов переменной величины. Конечно, данные списки можно хранить напрямую, для каждого конкретного 
элемента сетки. Однако в этом случае необходимо выделение памяти для каждого элемента сетки, что является достаточно дорогой 
операцией и требует дополнительной памяти на описание каждого 
списка. В результате существенно возрастут накладные расходы.  
Решить эту проблему можно двумя способами. Первый – фиксирование определенного количества элементов сетки. Если количество заполненных элементов меньше отведенного, то можно ис