автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Метод построения трехмерных оптимальных сеток

003062695

— — ■ " (,ии(

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

УШАКОВА Ольга Васильевна

МЕТОД ПОСТРОЕНИЯ ТРЕХМЕРНЫХ ОПТИМАЛЬНЫХ СЕТОК

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

АВТОРЕФЕРАТ

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

Екатеринбург-2007

003062695

Работа выполнена в Институте математики и механики Уральского отделения Российской академии наук

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

профессор Владимир Дмитриевич

Лисейкин,

доктор физико-математических наук Геннадий Павлович Прокопов, доктор физико-математических наук Александр Агасиевич Чарахчьян Ведущая организация Федеральное государственное унитарное

предприятие "Российский Федеральный Ядерный Центр — Всероссийский научно-исследовательский институт технической физики" имени академика Е И Забабахина

Защита состоится " 29 " мая 2007 г в 10 ч 00 мин на заседании Диссертационного совета ДООЗ 046 01 при Институте вычислительных технологий Сибирского отделения РАН по адресу 630090 г Новосибирск, пр Ак Лаврентьева, 6

С диссертацией можно ознакомиться в специализированном читальном зале вычислительной математики и информатики ГПНТБ СО РАН

Автореферат разослан апреля 2007 г

Ученый секретарь /)Л Б Чубаров

диссертационного совета

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

профессор

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы Большое число физических явлений и процессов описывается обыкновенными дифференциальными уравнениями или дифференциальными уравнениями в частных производных И только для небольшой части дифференциальных уравнений обоих типов удается найти точное решение В большинстве случаев при исследовании физических явлений и процессов средствами математического моделирования дифференциальные уравнения решаются численно Общепринятая стратегия численного решения дифференциальных уравнений состоит в замене непрерывной среды области, в которой происходит физический процесс или явление, дискретным набором точек, называемым сеткой, а дифференциальных уравнений или их систем — соответствующими данной сетке системами алгебраических уравнений От того, как выбрана сетка, зависит и процесс решения задачи, и его результат О важности этапа выбора и построения расчетной сетки в численном решении задачи говорится в монографии К И Бабенко1 В монографии подчеркнуто, что в вопросах вычислительной технологии и математического моделирования методы конструирования сеток и нумерации узлов могут быть центральными и по значимости превосходить методы оценок погрешностей

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

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

:К И Бабенко Основы численного анализа Москва Наука 1986

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

Целью работы является

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

— создание эффективных и надежных средств численного анализа трехмерных сеток, предназначенных для автоматического анализа трехмерных сеток, подсчета их геометрических и качественных характеристик в процессе осуществления математического моделирования задач,

— применение метода и созданных средств численного анализа в практических расчетах сеток для математического моделирования пространственных задач многокомпонентной гидродинамики

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

Новизна работы. В диссертации в рамках подхода [4,5,14] предло-

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

Практическая значимость результатов диссертации состоит в следующих аспектах

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

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

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

3) Метод построения и предложенные средства численного анализа сеток реализованы в универсальном комплексе программ, который был передан в заинтересованную организацию Универсальный автоматизированный комплекс программ позволяет осуществлять расчеты, диагностику и анализ качества трехмерных сеток

Апробация работы. Результаты диссертации докладывались на следующих конференциях IV, V, VI, VIII, IX Всероссийских совещаниях "Проблемы построения сеток для решения задач математической физики", 1992, 1994, 1996, 2000, 2002 г, Всероссийских конференциях "Теоретические основы и конструирование численных алгоритмов решения задач математической физики" памяти К И Бабенко, 1994 и 2006 г, Международной конференции "Современные проблемы прикладной и вычислительной математики (АМСА)", г Новосибирск, 1995 г, 10 Зимней школе по механике сплошных сред, 1995 г, Всероссийских школах-семинарах "Современные проблемы математического моделирования", 1995 и 2003 г, V международной конференции по методам построения сеток "5th International conference on Numerical Grid Generation m Computational Field Simulation", США, Старквилл, 1996 г, Международной конференции в честь академика С К Годунова, 1999 г, Международной конференции "ENUMATH-2001, European Conference on Numerical Mathematics and Advanced Applications", Италия, Искья,

2001 г, Российско-финском совещании "Russian-Finish workshop on grid-generation", Финляндия, Ювяскуля, 28 августа 2002 г, Международных конференциях ' Забабахинские научные чтения", Снежинск, 2001, 2003, 2005 г, Международной конференции ' OFEA'2001 Optimization of finite-element approximations, splines and wavelets", 2001 г, Международном семинаре "Супервычисления и математическое моделирование",

2002 г, семинаре "Построение расчетных сеток теория и приложения" 2002 г, Всероссийских конференциях памяти А Ф Сидорова "Актуальные проблемы прикладной математики и механики", 2003 и 2006 г, Всероссийской конференции "Численная геометрия, построение расчетных сеток и высокопроизводительные вычисления" 2006 г, на семинарах в

ИПМ РАН им М В Келдыша, 2006 г, ИММ УрО РАН, ИВТ СО РАН, 2007 г

Кроме того, результаты диссертации использовались в совместных с иностранными учеными исследованиях (грант Национального научного фонда США, National Science Foundation для совместных с В К Som, Engineering Research Center, Mississippi State University, исследованиях по разработке методов построения адаптивных сеток, 1996 г), докладывались в курсах лекций по методам построения сеток, в том числе и по представляемому методу, в различных университетах (The 12th Jyvaskyla International Summer School, Jyvaskyla University, Finland, 2002 г, Hongkong Baptist University, 2003 г)

Публикации. Основные результаты опубликованы в 3 монографиях (5 работ, международные издательства Novascience Publishers, CRC PRESS, издательство Физ мат лит), 8 журнальных статьях, в 2 сборниках статей ИММ УрО РАН, 1 препринте ИММ УрО РАН и 25 полнотекстовых публикациях докладов на зарубежных и всероссийских конференциях, в том числе в трудах Всероссийских и Международных конференций по методам построения сеток издательства ISGG (International Society of Grid Generation, Международное сообщество по построению сеток)

Структура и объем работы. Диссертация состоит из введения, 3 глав, заключения и перечня цитируемой литературы Диссертация содержит 256 страниц, в общей сложности 88 рисунков и 5 таблиц Список цитируемой литературы содержит 132 наименования

Личный вклад автора. В совместных работах [4-6,14,34,42] автору принадлежат различные способы задания краевых условий и численные процедуры для расчета сеток, обоснование целесообразности замены численного решения уравнений Эйлера-Остроградского алгоритмом прямой геометрической минимизации функционала качества сетки, обзор различных вариационных функционалов, тесты для построения сеток, анализ состояния исследований по развитию методов построения сеток В работах [3, 11,16,18-20] автором получены общая постановка задачи, анализ особенностей и описание расчетов сеток в областях вращения, численные алгоритмы и программная реализация оптимизации сеток, классификация шестигранных линейчатых ячеек В работах [7,22,25-27] автору принадлежат технологии глобальной перестройки трехмерных сеток

СОДЕРЖАНИЕ РАБОТЫ

Введение содержит краткий обзор по развитию методов построения сеток

Методы конструирования сеток стали интенсивно развиваться с конца 50-х годов (см [14, 42], Soviet Journal of Numerical Analysis and Mathematical Modelling, 1989) Было выполнено несколько циклов исследований как российских авторов — С К Годунова, Г П Прокопо-ва, Н Н Яненко, А Ф Сидорова, В Д Лисейкина, В П Шанеева, Ю П Мещерякова, Н Т Данаева, А А Самарского, Н И Мажу-кина, Н А Дарьина, Л М Дегтярева, С А Иваненко, А А Чарах-чьяна, А М Сорокина, Б Н Азаренка и др , так и иностранных — А М Wmslow, А В White, J F Thompson , Z U A Warsi, С W Mastm, H A Dwyer, В К Soni, P R Eiseman, P Knupp, и др (список, разумеется, далеко не полный), в которых обсуждаются как общие вопросы построения сеток как части математического моделирования, так и более конкретные подходы и методы

Развитие методов построения сеток привело к тому, что алгоритмы и программы для расчета сеток в сложных областях, а также программные средства для описания геометрий областей стали общепризнанным инструментом математического моделирования Главным образом за рубежом созданы, активно используются и нашли свое применение во многих отраслях промышленности двумерные и трехмерные программы построения сеток, была создана "индустрия" и рынок программных продуктов для построения сеток, созданы международные стандарты описания геометрий областей и задания сеток2 Сформировались различные направления развития методов построения сеток3 Несмотря на достигнутый прогресс, запросы математического моделирования требуют дальнейшего развития и усовершенствования методов построения сеток

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

Перечисляются основные итоги развития вариационного подхода к построению оптимальных сеток в областях геометрически сложной формы [4,5,14], в рамках которого был разработан метод Этот подход

^Handbook of Grid Generation/ J F Thompson, В K Som, N P Wcathenll CRC Press 1999

3V D Liseikm Grid Generation Methods Springer 1999

был предложен А Ф Сидоровым в конце пятидесятых Была предложена концепция построения криволинейных сеток в областях сложной формы, основанная на минимизации функционалов, отвечающих за близость сеток к определенным видам качеств равномерности, ортогональности и адаптации к решениям дифференциальных задач В рамках этой концепции были созданы и разработаны одномерные и двумерные программы построения сеток Двумерные оптимальные сетки использовались для решения различных задач математической физики, в частности, для моделирования вихревых течений газа в каналах сложных геометрий [4,5,34] Применение оптимальных гладких блочно-структурированных криволинейных сеток явилось весьма существенным фактором при решении указанных задач Хорошие аппроксимаци-онные качества используемых сеток стали основой достигнутых результатов

Данная диссертация представляет собой новый естественный этап развития подхода [4,5,14]

По мере разработки трехмерного метода были получены новые результаты, сформировавшие основы численного анализа трехмерных сеток [8,12] (ЖВМ и МФ, 2001 и Proceedings of the Steklov Institute of Mathematics, 2004) с изложения которых начинается описание метода в главе 1 диссертации В главе 2 описываются алгоритмы построения трехмерных оптимальных сеток В главе 3 метод применен к практическим расчетам сеток В заключении описываются возможные перспективы развития метода

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

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

Для структурированных сеток координаты узлов сетки организуются в определенную структуру, например, в двумерном случае — в матрицу, в трехмерном случае — в трехмерный массив Для структурированных сеток число соседних узлов сохраняется для каждого внутреннего узла сетки, форма ячеек является одной и той же (см [12])

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

Построение структурированной сетки в области б, в общем случае имеющей сложную геометрическую форму, осуществляется с помощью непрерывного отображения х вспомогательной области Р более простой формы на область С Техника построения структурированных сеток с помощью отображений, основные определения и понятия введены в разделе 1.1, с которого начинается глава 1 В данном случае трехмерная сетка узлов х,1г2,3 = х(гх, %2, гз) в области геометрически сложной формы С строится с помощью отображения х Р —> О

трехмерной равномерной и ортогональной сетки —Ч, I = 1,2,3, г; = 0,1, , 1[ в прямоугольном параллелепипеде Р (Значения 7; задают число узлов по каждому из координатных направлений ) При таком способе построения сеток область б представляется в виде криволинейного шестигранника Под конфигурацией области понимается не только форма области, но и способ ее представления в виде криволинейного шестигранника Отличительной особенностью такого подхода является то, что граница области состоит из координатных линий и поверхностей сетки В рассматриваемых уравнениях в частных производных осуществляется преобразование координат, и все вычисления, таким образом, могут проводится на равномерной и прямоугольной сетке в прямоугольном параллелепипеде

Несмотря на то, что методы построения сеток стали интенсивно развиваться более сорока лет назад, а сетка, как понятие, появилась в вычислительной практике еще раньше, полный перечень требований к ней еще не сформирован и до сих пор пополняется Тому, какие требования предъявляются к сеткам, посвящен раздел 1.2 Часть требований определяется конкретным численным алгоритмом, предназначенным для решения физической задачи на построенной сетке, а некоторые из требований, как в случае с адаптацией, — свойствами решения физической задачи

Среди общих требований к сеткам условие невырожденности — самое важное На вырожденных сетках физическое явление не может

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

Среди других общих требований, влияющих на точность решения задачи (имеется в виду случай структурированных сеток), обычно рассматриваются требования гладкости сеточных линий, близости сетки к равномерной (Р) и ортогональной (О), и адаптации к решению физической задачи (А) Перечисленные общие требования к сеткам называют требованиями оптимальности [4,5,14] Большое число требований к сеткам (часто противоречивых) усложняло выделение основных требований и их формализацию Поэтому, несмотря на важность, не во всех исследованиях по построению сеток формулируется проблема невырожденности Обсуждение этого вопроса часто опускается также, как и получение надежных условий и способов оценки этого свойства Как правило, невырожденность сетки (ячейки) понимается как взаимная однозначность отображения, используемого для построения сетки (ячейки) Однако, в процессе математического моделирования часто о невырожденности сетки судят лишь визуально — проверкой отсутствия самопересекающихся ячеек, расположения ячеек без наложений и зазоров, отсутствия ячеек с разной ориентацией ребер (граней) и т д Такой способ оценки невырожденности сетки может быть затруднительным, особенно, в трехмерном случае Довольно часто при просмотре трехмерной сетки по семействам криволинейных поверхностей с помощью различных графических пакетов визуализации сетки на поверхностях могут быть несамопересекающимися (или невырожденными), но как трехмерная сетка (задаваемая с помощью трехмерного отображения) совокупный трехмерный массив узлов может быть вырожденным Поэтому для оценки невырожденности сетки часто используют условия положительности объемов ячеек либо якобиана отображения, вычисленного, например, в узлах сетки Вместе с тем хорошо известно (см , например, в литературе по построению сеток4, именно в этих источниках вопросы невырожденности специально обсуждаются), что положительность якобиана не гарантирует взаимную однозначность отображения глобально — она гарантирует взаимную однозначность отображения локально Подробное обсуждение вопроса о необходимости получения условий, проверка

4Knupp Р М and Steinberg S Fundamentals of Grid Generation CRC Press, Boca Raton, FL 1994

которых позволила бы сделать вывод о невырожденности сетки (ячейки), содержится в книге С А Иваненко5 По инициативе С А Иваненко с целью получения эффективных критериев Н А Бобылевым с соавторами были предприняты исследования, давшие основу и теоретическое обоснование многих алгоритмов построения сеток К тому времени локальные условия, гарантирующие невырожденность для большинства типов ячеек, были получены для двумерного случая Полученные общие теоремы6 давали возможность использовать эти условия при разработке алгоритмов расчета сеток и проверки невырожденности сеток, в том числе и заданных дискретным набором узлов

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

Раздел 1 4 посвящен вопросу о невырожденности трехмерных структурированных сеток, составленных из линейчатых шестигранных ячеек Такие ячейки являются образами единичного куба при трилинейном отображении х = хооо(1 - 6)(1 - 60(1 ~ 6) + xooi(l - 6)(1 ~ 6)6

+ хто(1 - 6)6(1 - 60 + хоп(1 - 6)66 + х1006(1 - 6)(1 - 6) + xioi6(l - 6)6 + хПо66(1 - 6) + хшббб, 0 < 6 < 1, Z = 1,2,3

и наиболее употребительны в трехмерном случае (см, например, монографию Дж Киллина7) Для простоты рассматриваем ячейку, имеющую вершинами узлы сетки x,j,j,3 = (xi{ii,i2,iz),x2{ii^2,iz),x3{iii2i3)), гг,г2,г3 = 0,1 В методе построения оптимальных сеток используются как раз такого вида ячейки Поэтому для разработки метода потребовалось найти условия невырожденности для таких сеток Как оказалось, условий, гарантирующих невырожденность структурированных сеток, составленных из шестигранных линейчатых ячеек, до 2000 г (публикация [33]) получено не было, несмотря на то, что многие авторы (G Strang, G Fix 8,

5Иваненко С А Адаптивно-гармонические сетки / М ВЦ РАН 1997

6Бобылев Н А , Иваненко С А , Казунин ABO кусочно-гладких гомеоморфных отображениях ограниченных областей и их приложениях к теории сеток // Журн выч матем и матем физики 2003 43, Х> 6 С 808-817

Управляемый термоядерный синтез / Под ред Дж Киллина М Мир 1980

8Strang G and Fix G An Analysis of the Fmite Element Method / New York Prentice-Hall, New York, 1973

Р М Knupp С А Иваненко и другие) предпринимали попытку найти такие условия Условия, обеспечивающие невырожденность шестигранных ячеек, впервые были опубликованы в [33], а их подробный вывод - в [8,13] (ЖВМ и МФ 2001, SIAM J Sci Comp, 2001) Затем на основе [8,13] были предложены критерии [31], а позже — условия [12] (Proceedings of the Steklov Institute of Mathematics, 2004) для других видов сеток Основная сложность в нахождении условий невырожденности для шестигранных линейчатых ячеек состояла в поиске простой и удобной формулы для якобиана трилинейного отображения единичного куба, а также в исследовании его на положительность Если вычислять непосредственно якобиан этого отображения (зависящего от трех пространственных переменных) как смешанное произведение векторов, каждый из которых содержит 18 слагаемых (полиномы от двух переменных), то результирующий многочлен содержал бы 183 3' или 34992 алгебраических члена Естественно изучать якобиан в такой конструкции представлялось достаточно сложным В [8,13,33] был предложен специальный способ записи векторов, компонентов смешанного произведения, который позволил получить первоначально якобиан в виде многочлена шестой степени от трех переменных Были получены необходимые условия, а также достаточные условия положительности якобиана (не совпадающие с необходимыми) в виде алгебраических неравенств Далее степень полинома удалось понизить до четвертой

Здесь индексы к,1,т образуют перестановку цикла (123), те, к,1,тп принимают значения 1,2,3, 2,3,1, 3,1,2, соответственно (последнее обозначается как (kirn) = (123) ) В формуле используются также обозначения Еч =ii + (—1)" (1 — £i), I = 1,2,3, ц = 0,1 (Е„ = 1 — iu

9Knupp Р М On the mvertibihty of isoparametric тар// Comput Methods Appl Mech Engrg 78 1990 P 313-329

1

!ъ'2,гз=0

(lim)=.(124)

если ц — 0, с,, = если ц = 1),

«W3 = = <w = (-1),1+Î2+Î3, (1)

= ¿„„„[p, q. v]!l!2.3 = = q, u]ll!2l3 =

Нижние индексы при скобках относятся к каждому элементу внутри скобок Векторы р, q, г направлены вдоль ребер, векторы u, v, w играют роль "диагоналей" граней ячейки р,,,2,3 = х,-,2,3 - хг„2,3, qîlJ2,3 =

x,-,,,- - xîtt2î3,wtlî2l3 = x,-,-t3 - xI]l2!3, 6 = 1, 1=0 Обозначение VZ3 используется для объемов тетраэдров с вершиной xîlî2t3 и ребрами, соответствующими верхним индексам

К сожалению, не удалось найти условий невырожденности, являющихся одновременно необходимыми и достаточными, но были проведены исследования, показывающие, что найденные условия охватывают достаточно широкий класс шестигранных ячеек [8] (ЖВМ и МФ, 2001) Для тестирования на невырожденность не вошедших в этот класс ячеек был предложен специальный численный алгоритм проверки якобиана на положительность [12,31] (Proceedings of the Steklov Institute of Mathematics, 2004) Отличительной особенностью условий невырожденности [8,12,13,21,28,29,31-33] является то, что все виды условий были получены в виде систем алгебраических неравенств для объемов определенных видов тетраэдров с плоскими гранями, в то время, как у самой ячейки грани могли быть не плоскими (линейчатыми поверхностями второго порядка) Это оказалось удобным для разработки численных алгоритмов расчета сеток Примерно в тоже время, когда были получены условия невырожденности [33] для шестигранных ячеек, были получены условия невырожденности для призматических и пирамидальных ячеек10 с линейчатыми гранями, и позднее — численный алгоритм для проверки невырожденности шестигранных линейчатых ячеек11 Отличительной чертой указанных исследований является то, что в отображениях, используемых для построения данных ячеек, выделяется линейная и нелинейная части отображений Авторы данных работ

10Knabner Р , Summ G The lnvertibihty of the isoparametric mapping for pyramidal and prismatic finite elements // Numerical mathematics 88 2001 P 661-681

nKnabner P , Korotov S , Summ G Conditions for the mvertibility of the isoparametric mapping for hexahedral finite elements // Finite elements in analysis and design 2003

рассматривают общее отображение как композицию двух отображений и изучают их свойства по отдельности Однако, форма представления полученных условий была отличной от [33] Поэтому, для получения условий невырожденности, аналогичных [33], в виде систем неравенств на объемы специальных тетраэдров техника [33] была использована и для пирамид, и призм Получены критерии невырожденности в новой форме [12] (Proceedmgs of the Steklov Institute of Mathematics, 2004), аналогичной для шестигранных ячеек Эти критерии приведены в разделах 1.6 и 1.7 Критерии для тетраэдров очевидны Они приведены в разделе 1 5

Далее техника [8] была применена и для других видов криволинейных ячеек12, а, именно, для ячеек, построенных с помощью отображений, задаваемых полиномами Бернштейна-Безье Такие ячейки также могут быть использованы при построении трехмерных сеток Полиномы Бсрнштейна-Безье позволяют конструировать отображения, являющиеся обобщением трилинейного отображения, таким образом, шестигранные линейчатые ячейки это только один из частных видов ячеек, определяемых с помощью данных полиномов Техника [8] позволяет найти условия невырожденности существенно более общие ( [12], Proceedmgs of the Steklov Institute of Mathematics, 2004), чем найденные S A Vavasis для таких отображений Условия для рассматриваемого вида криволинейных ячеек были получены в разделе 1.8, а, именно, были получены условия невырожденности для криволинейных ячеек, построенных с помощью обобщения трилинейного отображения

При изучении шестигранных линейчатых ячеек была получена новая формула для объема ячейки [8] (ЖВМ, 2001) Ранее формула для вычисления объема ячеек была анонсирована в уже упомянутой монографии Дж Киллина затем новый способ вычисления объема был получен А С Шведовым13 Экономичный способ и формула для вычисления объема были получены J К Dukowicz14 Формула [8] отлична, но может быть приведена к виду последней, и в той же степени экономична Новая формула [8] позволила выявить связь шестигранной ячейки, имеющей сложную конфигурацию и форму криволинейных

12 Vavasis S A A Bcrnstcm-Bczicr Sufficicnt Condition for Invertibility of Polynomial Mappmg Functions November 3, 2001 http //www es cornell edu/home/vavasis

13Шведов A С Формулы для объема ячеек // Матем заметки 19S6 Т 39 В 4 С 597—605

"Dukowicz J К Efficient Volume Computation for Three-Dimeosional Hexahcdral Cells // Journal of Computationa! Physics 74(2) 1988 P 493-496

граней, с двумя двенадцатигранниками с теми же, что и у шестигранной ячейки вершинами, но плоскими треугольными гранями Согласно этой формуле объем линейчатой ячейки вычисляется как полусумма объемов данных двух двенадцатигранников либо как полусумма объемов 10 тетраэдров восьми тетраэдров при вершинах шестигранной ячейки и построенных на ребрах, выходящих из вершин, и двух тетраэдров с ребрами — диагоналями граней

Здесь £*г1!2гз определены в (1) и соответствуют тетраэдрам при вершинах, Km = (^¡[u, v, -wjiu = 6I = 0,1 соответствуют диагональным тетраэдрам

В последствии на основе этой формулы Б Н Азаренком15 был предложен подход к консервативной переинтерполяции газодинамических величин на шестигранных сетках, позволяющий заменять шестигранную ячейку данными двумя двенадцатигранниками Данная замена позволила существенно упростить процесс переинтерполяции (см для сравнения аналогичную процедуру, авторы J К Dukowicz, N Т Padial16) В указанной работе линии пересечения линейчатых поверхностей ячеек находятся решением дифференциальных уравнений, которые могут иметь особенности в областях, где грани ячеек старой и новой сеток пересекаются и почти параллельны, в местах соприкосновения граней и тд В работе Б Н Азаренка замена ячейки с линейчатыми гранями двумя двенадцатигранниками приводит к задаче построения фигуры пересечения двух двенадцатигранников, что существенно проще, чем решение дифференциальных уравнений Фигура пересечения двенадцатигранников суть многогранник с плоскими гранями — симплекс Применение техники [8] привело к получению аналогичных формул для объема призм и пирамид, имеющих линейчатые грани [2] Отличительной особенностью полученных формул снова является то, что объем ячеек, имеющих не плоские грани, вычисляется через объемы многогранников с плоскими гранями Перечисленные формулы для объемов ячеек и их вывод приведены в разделе 1.9

1оАзаренок Б H Алгоритм консервативной интерполяции на гексаэдральных сетках // М ВЦ РАН 2006 58 с

16Dukowicz J К , Padial N Т REMAP3D A conservative three-dimensional remapping code, Los Alamos report, 1991

l( E Vtz* + Vm+Vi

4»li'2>«3=0

111

•uvw

В процессе осуществления расчетов сеток по созданным алгоритмам и программам на основе полученных условий невырожденности ячеек была создана классификация шестигранных ячеек и получены критерии для такой классификации Эта классификация и критерии приведены в разделе 1.10 Для некоторых конфигураций областей в процессе математического моделирования пришлось столкнуться с ситуациями, когда на границе расчетных областей возникали шестигранные ячейки, вырождающиеся в линейчатые призмы с треугольным основанием Кроме того, при переинтерполяции на трехмерных сетках, составленных из шестигранных ячеек, Б Н Азаренком был обнаружен специальный класс невырожденных шестигранных ячеек сложной формы, а их диагностика была осуществлена диссертантом с помощью созданной классификации Эти ячейки были названы выкрученными шестигранными ячейками [17,18], так как они похожи по форме на параллелепипед, подвергшийся выкручиванию Наличие выкрученных шестигранных ячеек в сетках оказалось недопустимым в алгоритмах консервативной иереин-теполяции газодинамических величин Наличие таких экзотических по форме ячеек мол-сет быть нежелательным и в других численных алгоритмах При построении сеток в объемах вращения [7,12](ЖВМ, 2003, Proceedings of the Steklov Institute of Mathematics, 2004, подробно об этом будет написано в главе 3) возникли случаи диагностики вырождения шестигранных ячеек в линейчатые многогранники с меньшим числом граней — призмы и пирамиды Возникновение таких вырожденных шестигранных ячеек возможно также в вырожденных криволинейных системах координат, например, цилиндрической и сферической, очень часто используемых для построения трехмерных сеток при математическом моделировании пространственных задач газовой динамики Такие ячейки могут возникать также в трехмерных сетках, полученных вращением двумерных сеток вокруг оси Призмы появляются на оси вращения при вращении четырехугольных ячеек, а пирамиды и тетраэдры — при вращении треугольных ячеек Тетраэдры появляются при вращении треугольных ячеек, лежащих на оси вращения В последнем случае исходная двумерная сетка также является вырожденной Для указанных случаев приведены численные критерии для диагностики ячеек В некоторых случаях в вариационных алгоритмах расчета сеток начальная сетка может содержать и другие виды вырожденных шестигранных ячеек, например, вырождающиеся в многогранники, которые могут быть представлены в виде объединения двух призм с треугольным

основанием Аналогом таких ячеек в двумерном случае являются вырожденные ячейки — невыпуклые четырехугольники Выделен также случай, когда шестигранная ячейка вырождается в самопересекающийся многогранник Наличие такого рода вырожденных ячеек в сетках является недопустимым В разделе 1 10 обсуждается возможность возникновения вырожденных ячеек в форме других видов многогранников на границах трехмерных областей и различные стратегии в разработке как алгоритмов построения сеток (замена шестигранных ячеек двенадцатигранниками), так и численных алгоритмов решения физических задач на рассматриваемых сетках В разделе 1.11 приводится описание и сравнение различных условий, заменяющих условия невырожденности для шестигранных ячеек [8,12] на практике построения сеток Среди всех рассмотренных условий выделены наиболее удачные

Если определяющим для компоновки материала в главу 1 было требование невырожденности сетки, то в главе 2 к требованию невырожденности добавляются требования оптимальности сеток Предлагаемый метод построения сеток создан в рамках концепции построения оптимальных сеток, подробно описанной в [9,14] (Soviet Journal of Numerical Analysis and Mathematical Modelling, 1989, Математическое Моделирование, 1997), а также в [4,5] В качестве критериев оптимальности выбраны требования близости криволинейной сетки к равномерной, ортогональной и адаптации к заданной функции или решению уравнений в частных производных

Главная особенность подхода связана со специальным способом формализации критерия близости сеток к равномерным, приводящему к нелинейному вариационному функционалу, в который входят как первые, так и вторые частные производные функций, реализующих отображение Этот непрерывный функционал появляется естественным образом после рассмотрения дискретного функционала, минимизирующего меру относительной погрешности неравномерной сетки по сравнению с равномерной Такая формализация приводит к системе уравнений Эйлера-Остроградского (Э-О) четвертого порядка, гиперболической в широком смысле Это позволило рассмотреть новые более широкие типы краевых условий, а также разработать эффективные алгоритмы и программы построения сеток для весьма сложных областей Экономичные и эффективные процедуры расчета сеток связаны с применением итерационных процессов, использующих как специальную нестационарную модификацию уравнений Э-0 (см [5]), так и прямые геомет-

рические способы минимизации дискретных функционалов (см [9,40], ВАНТ, 1994 и Математическое Моделирование, 1997) В описываемом методе при построении сеток рассматриваются только два критерия оптимальности А Ф Сидорова (близости сеток к равномерным и ортогональным), критерий адаптации сетки не учитывается, те рассматривается метод построения геометрически оптимальных сеток Минимизируемый функционал имеет вид

— дискретные функционалы равномерности и ортогональности Весовой коэффициент Aq > 0 регулирует степень близости сетки к равномерной и ортогональной Здесь r,±u,fc = — =

|h,±i| Аналогично определяются ги±1,ь ггj,k±u hj±i, hjt±i Величины Vy 1'-Pjk' P — 1,2,3,4 определяют соответственно углы между векторами hiJrbhj+,, h,±i, h^i, hJ±b hfc±1

В разделе 2.1 дан краткий обзор вариационных функционалов, используемых для построения структурированных сеток Приведен вывод дискретных функционалов, формализующих критерии оптимальности, дан анализ их свойств в одномерном и многомерном случаях ( [14], Soviet Journal of Numerical Analysis and Mathematical Modelling, 1989)

В разделе 2.2 описываются вариационные задачи построения оптимальных сеток непрерывные конструкции функционалов оптимальности, общий вид минимизирумого функционала, система уравнений Э-0 и краевые условия ( [5,9,14] Soviet Journal of Numerical Analysis and

D = Dp+A0D0,

где

i }k К

|2

Mathematical Modelling, 1989, Математическое моделирование, 1997) В трехмерном случае общий минимизируемый функционал, непрерывные функционалы равномерности и ортогональности имеют вид

Сг = дккди - 9ы,

Система уравнений Эйлера-Остроградского для общего минимизируемого функционала имеет вид

где Ьг(х 1, ,хп) - нелинейные формы, содержащие частные производные функций Хк не выше третьего порядка Ранее (1981 г) А Ф Сидоровым было показано, что система уравнений (3) является гиперболической в широком смысле, а линии или плоскости £г=сол^ являются характеристическими, кроме того, если в вариационной конструкции (2) оставить лишь функционал, отвечающий за близость сеток к ортогональным, то прямой анализ системы уравнений Эйлера-Остроградского показывает, что эта система второго порядка смешанного эллиптико-гиперболического типа, так что краевая задача для расчета сетки может быть некорректно поставленной Таким образом, введение слагаемого с 1р играет важную регуляризующую роль Второй порядок производных в подинтегралыюм выражении минимизуруемого функционала позволяет рассматривать различные типы краевых условий фиксированные узлы, свободные узлы, ортогональность линий сетки к границам

/ = /р + AqIq,

7Р = ///Е (Jrln^)

(2)

р

,Хп) = 0, ? = 1, ,Т1,П = 3, (3)

Раздел 2.3 посвящен описанию эффективных алгоритмов, позволяющих строить трехмерные оптимальные гладкие сетки в односвяз-ных областях Прежде, чем был разработан метод построения трехмерных оптимальных сеток, был создан аналогичный двумерный метод17, а позднее экономичный двумерный алгоритм и программа для построения двумерных оптимальных сеток ЛАДА (см [9,40], ВАНТ, 1994 и Математическое Моделирование, 1997, [34-37], а также ее параллельный вариант [38,39]) Трехмерные алгоритмы и программа созданы на основе этого двумерного алгоритма и программы ЛАДА Метод [9,40] представляет собой алгоритм прямой геометрической минимизации двумерного дискретного функционала оптимальности В трехмерном случае удалось разработать аналогичный численный алгоритм и сохранить основные особенности двумерного алгоритма экономичность, надежность, и "барьерность" — свойство, обеспечивающее возможность строить невырожденные сетки В данном подходе конструкция минимизируемого функционала обладает "барьером" против вырожденных ячеек, так как целевая функция (подинтегральное выражение минимизируемого функционала в непрерывном случае) содержит якобиан от искомого преобразования или его дискретный аналог в качестве знаменателя, поэтому минимизируемый функционал будет обращаться в бесконечность, если якобиан или его дискретный аналог в узле сетки (в трехмерном случае объем тетраэдра, построенный на ребрах ячейки, выходящих из данного узла) будет обращаться в нуль Такие конструкции для построения сеток относят к барьерным методам18, обладающим "барьером" против вырожденных элементов Раздел 2 3 содержит общую характеристику вариационного алгоритма как итерационного, перечисляются требования на начальную сетку, описывается итерационная процедура для оптимизации внутренних узлов сетки Далее описывается специальный порядок вычислений узлов для обеспечения соответствия симметрий сетки симметриям трехмерной области и способ вычисления дискретного функционала в том числе и для случаев, когда начальная сетка содержит вырожденные ячейки Отметим, что сама конструкция функционала ввиду наличия свойства барьерности предусмотрена для расчетов с начальных невырожденных сеток, однако на практике для многих конфигураций областей могут возникать ячейки, вырождающи-

17Ушакова О В Метод построения оптимальных адаптирующихся сеток Диссертация на соискание ученой степени кандидата физико-математических наук Свердловск 1990 145 с

18Иваненко С А , Чарахчьян А А Криволинейные сетки из выпуклых четырехугольников // Журнал вычислительной математики и матем физики Т28, N4 1988 С 503-514

еся в другие виды многогранников (см раздел 1 10) Для таких случаев функционал модифицирован и предусмотрен специальный способ его вычисления В этом же разделе описываются шесть различных алгоритмов, отличающихся способами расчета узлов, главным образом, на границе областей В [7] (ЖВМ, 2003), [3,16,27] были предложены следующие алгоритмы для построения сеток

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

2) алгоритм со свободными узлами на границе области, когда положение узлов на границе находится из условия минимума функционала,

3) алгоритм с координатными линиями ортогональными граням области,

4) алгоритм с координатными линиями ортогональными ребрам и граням области,

5) алгоритм, осуществляющий перестройку только в тех узлах, в которых указывает пользователь,

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

Движение узлов в алгоритмах осуществляется по линейчатым поверхностям граней начальной сетки Все перечисленные алгоритмы были применены в расчетах сеток

Глава 3 начинается с описания применения метода построения трехмерных оптимальных сеток для глобальной перестройки сеток ( [7], ЖВМ, 2003 и [23-26]) с целью улучшения их качества в процессе математического моделирования задач (раздел 3.1) Сначала в разделе подробно описывается, что понимается под глобальной перестройкой сетки и при решении каких физических задач может возникнуть необходимость такой перестройки, затем приводятся примеры перестройки невырожденных и вырожденных сеток

В следующем разделе 3.2 описываются примеры расчетов сеток для областей вращения ( [7], ЖВМ, 2003 и [2,3,11,15-20,22,27]) Описывается постановка задачи о расчете сеток в областях вращения, где по-

ясняется, что понимается под областью вращения и какие случаи областей вращения рассматриваются. Выделяются в рассмотрение несколько областей вращения (тело, оболочка, и срез или срезанная оболочка), возникающие при численном моделировании задач многокомпонентной гидродинамики, и предлагаются примерь! конфигураций для данных областей вращения. Одной из главных особенностей расчетов сеток в областях вращения является то, что к рассматриваемых конфигурациях областей, как правило, две и более граней лежат в одной плоскости, т.е. представление области в виде криволинейного шестигранника имеет весьма экзотический характер и сам шестигранник имеет особенности, отсюда возникновение особенностей (шестигранных ячеек, вырождающихся в призмы) в сетках ( |12], Proceedings of the Steklov Institute of Mathematics, 2C04, а также [2,3,11,15-17,17,20]). Частично наличие особенностей конфигураций областей явилось причиной разработки различных алгоритмов расчета сеток на границах областей. Описываются примеры расчетов сеток для конфигураций различных типов, а также для различных способов расстановки узлов на границе области

Рис. 1. Начальная (слева) и оптимальная сетки (алгоритм 1).

Если качество Начальной сетки на границе области является удовлетворительным, в процессе минимизации функционалов узлы на границе или ее части, например, па плоских гранях, фиксируются (алгоритм 1, Рис. 1), Если Начальная сстка не удовлетворяет пользователя (см. Рис. 2), то узлы в процессе минимизации считаются свободным:-! (алго-

ритм 2). При расчете сеток но алгоритму 2 качество ячеек вдоль ребер на плоских гранях может быть неудовлетворительным также из-за не гладкой стыковки координатных линий вдоль данных ребер (Рис. 3,6).

Для получения сеток с гладкой стыковкой на ребрах, находящихся в одной плоскости, расчеты могут проводится по алгоритмам 4 и 6. Расчеты по алгоритму 4 проводились при условии ортогональности координатных линий ребрам, лежащим в одной плоскости. Расчеты координат остальных узлов проводились из условия минимума функционала. Сетка. полученная по алгоритму 4, представлена на рисунках 4,7. Сетка с гладкой стыковкой на ребрах (алгоритм 6), представлена па рисунках 5.7. Построенные сетки тестируются сначала по качеству ячеек.

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

Рис. 2. Начальная сетка (разные ракурсы).

Рис. 4. Оптимальная сетка, условие ортогональности линий ребрам (алгоритм 4).

Рис. 5, Оптимальная сетка, условие гладкой стыковки па ребрах (алгоритм 6),

Рис. 6. Фрагменты начальной (слева) и оптимальной (алгоритм 2) сетки вдоль ребер на плоских гранях.

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

27

Рис. 7. Фрагменты сетки вдоль ребер на плоских гранях (алгоритмы 4 (слева) и 6).

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

Для применения предложенного метода в численном моделировании физических задач все разработанные алгоритмы были реализованы в универсальном автоматизированном комплексе программ (генераторе сеток), предназначенном для решения широкого круга задач математической физики. Комплекс налисаи на языке FORTRAN, предусматривает динамическую загрузку массивов и может быть использован в различных вычислительных средах и системах, (в том числе и параллельных для расчетов сеток в последовательном режиме либо для создания параллельных программ для расчета блочных сеток). Краткое описание комплекса программ приводится в разделе 3.3.

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

1вКошм1иа Т.Н. (Бронина Т.Н.). Сидоров А.Ф. Об одном геометрическом способе построения трехмерных разностных сеток // Сб, Численные I' аналитические методы реи:ення задач механики сплошной среды. С]Ифдловск. 1981. С. 91-100,

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ

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

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

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

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

Монографии и отдельные главы в них

1 Advances m Grid Generation / ed by Ushakova OV Novascience Publishers 2005 430 p

2 Ushakova О V Nondegeneracy Conditions for Different Types of Grids / Advances in Grid Generation ed by Ushakova О V Novascience Publishers 2005 P 281-326

3 Bronma T N , Ushakova О V Application of Optimal Grid Generation Algorithms to the Volumes of Revolution / Advances m Grid Generation ed by Ushakova О V Novascience Publishers 2005 P 327-368

4 Сидоров А Ф , Ушакова О В , Хайрулина О Б Вариационные методы построения оптимальных сеток / Сидоров А Ф Избранные труды Математика Механика М Физмат лит 2001 С 512-538

5 Khairullma О В , Sidorov A F , Ushakova О V 36 Variational methods of construction of optimal grids / Handbook of Grid Generation Ed

by Thompson J F , Soni В К , Weatherill N P Boca Raton etc CRC Press, 1999 P 36-1-36-25

6 Sidorov A F , Khairullina О В , Ushakova О V Tests for two-dimensional grid generation Suggestions / Handbook of Grid Generation Ed by Thompson J F , Soni В К , Weatherill N P Boca Raton etc CRC Press, 1999 P B-22-B-26

Статьи в рецензируемых журналах, рекомендованных ВАК

7 Броиина Т Н , Гасилова И А , Ушакова О В Алгоритмы построения трехмерных структурированных сеток // Журнал вычисл матем и матем физики Т 43 №6 2003 С 875-883

8 Ушакова О В Условия невырожденности трехмерных ячеек Формула для объема ячеек // Ж вычисл матем и матем физ 2001 Т 41 №6 С 881-894

9 Ушакова О В Алгоритм построения двумерных оптимальных адаптивных сеток // Математической моделирование, Т 9, №2 1997 С 88-91

10 Ушакова О В ЛАДА — экономичный алгоритм и программа построения двумерных криволинейных оптимальных адаптивных сеток в односвязных областях геометрически сложной формы // Вопр атомной науки и техн Сер Матем моделирование физ процессов 3 1994 С 47-56

Статьи в рецензируемых журналах

11 BronmaT N and Ushakova О V Three-dimensional Grid Generation Algorithms for the Volumes of Revolution // AIP Conference Proceedings August 3, 2006 Vol 849 P 492-498

12 Ushakova О V On Nondegeneracy of Three-Dimensional Grids // Proceedings of the Steklov Institute of Mathematics Suppl 1 2004 P S78-S100

13 Ushakova О V Conditions of nondegeneracy of three-dimensional cells A formula of a volume of cells // SIAM J Sci Comput Vol 23 , № 4 P 1273-1289

14 Serezhnikova T I , Sidorov A F and Ushakova О V On One Method of Construction of Optimal Curvilinear Grids and Its Applications // Soviet Journal of Numerical Analysis and Mathematical Modelling 4,(2) 1989 P 137-155

Прочие публикации

15 Ушакова О В О развитии метода построения трехмерных структурированных сеток // Актуальные проблемы прикладной математики и механики Тезисы докладов III Всероссийской конференции, посвященной памяти академика А Ф Сидорова (4-7 сентября 2006 г), Екатеринбург УрО РАН, 2006 С 101

16 Бронина Т Н , Ушакова О В Расчеты трехмерных структурированных сеток в конфигурациях с особенностями // Труды Всероссийской конференции ВЦ РАН им А А Дородницина Москва, 4-7 июля 2006 г С 190-199

17 Ушакова О В Классификация шестигранных ячеек // Численная геометрия, построение расчетных сеток и высокопроизводительные вычисления Труды Всероссийской конференции ВЦ РАН им А А Дородницина Москва, 4-7 июля 2006 г (ред Ю Г Евтушенко, М К Керимов, В А Гаранжа) С 180-189

18 Bronma Т N , Ushakova О V Generation of Optimal Grids for the Volume of Revolution / Proceedings of the 9th International Conference on Optimal Grid Generation m Computational Field Simulations The Fairmont San Jose in San Jose, California on June 12-15 ed by Papadopolous P, Som В , Hauser J , Eiseman P, and Thompson J Birmingham, Alabama International Society of Grid Generation 2005 P 3-12

19 Бронина T H , Ушакова О В Алгоритмы построения трехмерных сеток в областях вращения // ТЕЗИСЫ Международной конференции "VII Забабахинские научные чтения " Снежинск, РФЯЦ-ВНИИТФ 2005 С 218

20 Бронина Т Н , Ушакова О В Метод построения трехмерных структурированных сеток в областях вращения //II Всероссийская конференция, посвященная памяти академика А Ф Сидорова Актуальные проблемы прикладной математики и механики Россия,

Абрау-Дюрсо, 8-11 сентября 2004, г Екатеринбург, УрО РАН 2004 С 29-30

21 Ушакова О В Условия невырожденности для различных типов сеток //II Всероссийская конференция, посвященная памяти академика А Ф Сидорова Актуальные проблемы прикладной математики и механики Россия, Абрау-Дюрсо, 8-11 сентября 2004 г Екатеринбург, УрО РАН 2004 С 101-103

22 Бронина Т Н , Гасилова И А , Ушакова О В Алгоритмы построения регулярных трехмерных сеток // Международная конференция ''Забабахинские научные чтения" Сентябрь 8-12, 2003 Сне-жинск, РФЯЦ-ВНИИТФ 2003 Тезисы докладов С 229-230

23 Ушакова О В Вариационный подход построения оптимальных сеток итоги, современное состояние и перспективы развития // Тезисы докладов Всероссийской конференции "Актуальные проблемы математики и механики", посвященной 70-летию со дня рождения академика А Ф Сидорова Екатеринбург УрО РАН 2003 С 78-79

24 Ушакова О В Алгоритмы глобальной перестройки сетки // Тезисы докладов IX Всероссийского совещания по проблемам построения сеток для решения задач математической физики Екатеринбург, УрО РАН 2002 С 55-57

25 Бронина Т Н , Гасилова И А , Ушакова О В Алгоритмы построения трехмерных структурированных сеток // Построение расчетных сеток теория и приложения Труды семинара 24-28 июня 2002 г ВЦ РАН, Москва С 327-338

26 Бронина Т Н , Гасилова И А , Ушакова О В Технологии построения трехмерных структурированных сеток // Международный семинар ' Супервычнсления и математическое моделирование" Тезисы докладов Саров 2002 С 29-30

27 Вгошпа Т N , Gasilova IА, Ushakova О V Application of the Sidorov's approach to generation of three-dimensional structured grids // Proceedings of 8th International Conference on Numerical Grid Generation m Computational Field Simulations Waikiki Beach Marriott Resort, Honolulu, Hawaii, USA, June 2-6, 2002 P 445-454

28 Ushakova О V Criteria for the Inveribility of the Trihnear Map for Hexahedral Cells A Forraular of a Volume of Cells // Enumath 2001 European Conference on Numerical Mathematics and Advanced Applications Abstracts Universita di Napoli 2001

29 Ушакова О В Критерии невырожденности трехмерных ячеек Формула для объема ячеек // Международная конференция "Забаба-хинские научные чтения", 24-28 сентября 2001 г Тезисы, Снежинск, РФЯЦ-ВНИИТФ 2005 С 204-205

30 Ushakova О V Nondegeneracy criteria for 3-D grid cells Formulas for a cell volume // Optimization of finite-element approximations, splines and wavelets (OFEA'2001) Abstracts of International conference (June 25-29, 2001 St -Petersburg, Russia) St -Peterburg State University 2001 P 105-107

31 Ushakova О V Nondegeneracy criteria for 3-D grid cells Formulas for a cell volume / Grid Generation New trends and applications m real-world simulations Proceedings of the mimsymposium m the International conference "Optimization of finite-element approximations, splines and wavelets' June 25-29, 2001 St -Petersburg, Russia edited by S A Ivanenko, V A Garanzha P 115-128

32 Ушакова О В Условия невырожденности трехмерных ячеек Формула для объема ячеек // VIII Всеросийское совещание по проблемам построения сеток для решения задач математической физики, посвященное памяти Анатолия Федоровича Сидорова Тезисы докладов Пущино 2000 ПНЦ РАН С 22-23

33 Ushakova О V Conditions of Nondegeneracy of Three-dimensional Cells A formula of a Volume of Cells / Numerical Grid Generation m Computational Field Simulations, Proceedings of the 7th International Conference, September 25-28, 2000, Whistler, British Columbia Edited by В К Som J Haeuser, J F Thompson P Eiseman P 659-668

34 Сидоров А Ф Ушакова О В , Хайрулина ОБ / Вариационные методы построения оптимальных сеток Екатеринбург Ин-т Матем и Мех УрО РАН 1997 50 С

35 Ushakova O V Algorithm of Two-Dimensional Adaptive Grid Generation / Numerical Grid Generation in Computationa Field

Simulations Proc of the 5 th International Conference, held at Missippi State University, April 1- Apr 5 1996, P 37-47

36 Ushakova О V An efficient algorithm and program of generation of two-dimensional curvilinear optimal adaptive grids // Advanced Mathematics Computations and Applications Proceedings of the International Conference, AMCA-95, Novosibirsk, Russia, 20-24 June, 1995, NCC Publisher, Novosibirsk 1995 P 542-551

37 Ushakova О V Efficient Algorithm and Program of Generation of Two-dimensional Curvilinear Optimal Adaptive Grids // International Conference '"Advanced Mathematics Computations and Applications" (AMCA-95, Novosibirsk, June 20-24, 1995) Abstracts Kos-Z NCC Publisher, Novosibirsk 1995 P 330-331

38 Ушакова О В Параллельный алгоритм и программа построения оптимальных адаптивных сеток // Сб науч труд ИММ "Алгоритмы и программные средства параллельных вычислений" Екатеринбург УрО РАН, 1995 С 182-192

39 Ушакова О В Параллельный алгоритм и программа построения оптимальных адаптивных сеток //10 Зимняя школа по механике сплошных сред (Пермь) Тезисы докладов Екатеринбург УрО РАН, 1995 С 244-245

40 Ушакова О В ЛАДА — экономичный алгоритм и программа построения двумерных криволинейных оптимальных адаптивных сеток в односвязных областях геометрически сложной формы // X всероссийская конференция "Теоретические основы и конструирование численных алгоритмов решения задач математической физики" 1994

41 Ушакова О В Итерационная процедура расчета двумерных оптимальных адаптирующихся сеток // Приближенные методы исследования нелинейных задач механики сплошной среды Сборник научных трудов Свердловск, 1992 С 58-65

42 Сидоров А Ф , Ушакова О В О работах в СССР по разработке методов и программ расчета сеток // Вычислительные технологии Т I, №2, Ч 2 Новосибирск, 1992 С 289-294

Подписано в печать Плоская печать

Ризография НИЧ ГОУ ВПО УГТУ-УПИ 620002, г Екатеринбург, ул Мира 19

Формат 60 х 84 1/16 Бумага писчая

Тираж 100 Заказ № 40

Введение

ГЛАВА 1. Основы численного анализа трехмерных сеток

1.1 Конструирование сеток с помощью отображений.

1.2 Основные требования, предъявляемые к сеткам.

1.3 Требование невырожденности сеток.3G

1.4 Невырожденность шестигранных ячеек.

1.4.1 Построение шестигранных линейчатых ячеек с помощью трилинейного отображения.

1.4.2 Якобиан трилинейного отображения.

1.4.3 Условия положительности якобиана трилинейного отображения.

1.4.4 Специальный алгоритм для тестирования якобиана на положительность.G

1.4.5 Критерии невырожденности па практике построения структурированных сеток.

1.4.6 О допустимости вырожденных шестигранных ячеек.

1.5 Невырожденность тетраэдральных ячеек.

1.6 Невырожденность пирамидальных ячеек.

1.6.1 Построение пирамидальных ячеек с помощью отображения.

1.6.2 Критерии положительности якобиана отображения.

1.7 Невырожденность призматических ячеек.

1.7.1 Построение призматических ячеек с помощью отображения.

1.7.2 Критерии положительности якобиана отображения в виде неравенств на объемы тетраэдров.

1.8 Невырожденность других видов криволинейных трехмерных ячеек

1.8.1 Построение криволинейных ячеек с помощью полипомов

Бериштейиа-Безье.

1.8.2 Условия положительности якобиана для обобщения трилинейного отображения.

1.8.3 Выводы по условиям невырожденности.

1.9 Формулы для вычисления объемов различных видов трехмерных ячеек .;.

1.9.1 Объем шестигранных линейчатых ячеек.

1.9.2 Сравнение различных формул объема шестигранной ячейки.

1.9.3 Объем пирамидальных линейчатых ячеек.

1.9.4 Объем призматических линейчатых ячеек.

1.10 Классификация шестигранных ячеек.

1.10.1 Вырожденные шестигранные ячейки.

1.10.2 Невырожденные "выкрученные" шестигранные ячейки.

1.10.3 Невырожденные "невыкручснные" шестигранные ячейки.

1.10.4 Алгоритм тестирования трехмерных сеток.

Большое число физических явлений и процессов описывается обыкновенными дифференциальными уравнениями или дифференциальными уравнениями в частных производных. И только для небольшой части дифференциальных уравнений обоих типов удается найти точное решение. В большинстве случаев при исследовании физических явлений и процессов средствами математического моделирования дифференциальные уравнения решаются численно. Общепринятая стратегия численного решения дифференциальных уравнений состоит в замене непрерывной среды области, в которой происходит физический процесс или явление, дискретным набором точек, называемым сеткой, а дифференциальных уравнений или их систем — соответствующими данной сетке системами алгебраических уравнений. От того, как выбрана сетка зависит и процесс решения задачи, и его результат. О важности этапа выбора и построения расчетной сетки в численном решении задачи говорится в монографии К. И. Бабенко Основы численного анализа (Наука, Москва, 1986) [8]. В монографии подчеркнуто, что в вопросах вычислительной технологии и математического моделирования методы конструирования сеток и нумерации узлов могут быть центральными и по значимости превосходить методы оценок погрешностей.

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

Методы конструирования сеток стали интенсивно развиваться с конца 50-х годов (см. [50,112], Soviet Journal of Numerical Analysis and Mathematical

Modelling, 1989 и Вычислительные технологии, 1992). Было выполнено несколько циклов исследований как российских авторов — С. К. Годунова, Г. П. Прокопова, Н. Н. Яненко, А. Ф. Сидорова, В. Д. Лисейкииа, В. П. Ша-псева, Ю. П. Мещерякова, Н. Т. Данаева, А. А. Самарского, Н. И. Мажу-кина, Н. А. Дарьина, JI. М. Дегтярева, С. А. Иваненко, А. А. Чарахчьяпа, А. М. Сорокина, Б. Н. Азареика и др., так и иностранных — А. М. Winslovv,

A. В. White, J. F. Thompson., Z. U. A. Warsi, C. W. Mastin, H. A. Dwycr,

B. K. Soni, P. R. Eiseman, P. Knupp, и др. (список, разумеется, далеко не полный), в которых обсуждаются как общие вопросы построения сеток, так и и более конкретные подходы и методы.

Интерес к проблемам построения сеток особенно усилился в связи с переходом к многомерным расчетам. Конец восьмидесятых годов характеризуется (см., например, [107] Лисейкин, 1999) созданием трехмерных генераторов сеток — универсальных компьютерных программ, используемых для построения сеток при моделировании различных типов физических задач.

Развитие методов построения сеток привело к тому, что алгоритмы и программы для расчета сеток в сложных областях, а также программные средства для описания геометрий областей стали общепризнанным инструментом математического моделирования и используются для численного решения широкого круга задач математической физики. Главным образом за рубежом созданы, активно используются и нашли свое применение во многих отраслях промышленности двумерные и трехмерные программы построения сеток, была создана "индустрия" и рынок программных продуктов для построения сеток, созданы международные стандарты описания геометрий областей и задания сеток ( [121] Thompson, Soni, Weatherill, 1999).

Сформировались различные направления развития методов построения сеток. Существует большое разнообразие подходов. Классифицируя их по средствам конструирования сеток, среди них можно выделить следующие главные направления: алгебраические методы, методы построении сеток с помощью дифференциальных уравнений, вариационные методы. Самые рас-проетраппые методы построения сеток — это алгебраические методы. В этих методах координаты узлов сеток вычисляются по явным алгебраическим формулам и с использованием известных преобразований. К этим методам относят методы интерполяции, конструирование сеток с помощью сплайнов и др. Это самые быстрые методы. Для многих типов областей они генерируют невырожденные и хорошего качества сетки. Именно большинство известных трехмерных генераторов сеток используют данные методы. Эти методы удобны для построения блочпо-структурированиых сеток. Главный недостаток алгебраических методов это то, что для многих областей геометрически сложной формы они не гарантируют построение сеток хорошего качества и невырожденных. Построение сеток с помощью дифференциальных уравнений осуществляется путем решения различных типов дифференциальных уравнений — эллиптических, параболических, гиперболических. Подробно это направление описано в отечественной литературе в [22] (Годунов, Забродин, Прокопов и др.), в зарубежной — в [118] (Thompson, Warsi, Mastine), новые тенденции — в [37,108] (Лисейкин). В этом направлении существует большое разнообразие различных подходов. В вариационных методах построение сеток осуществляется путем минимизации некоторых мер качества сеток или иных величин. Они являются наиболее гибкими в построении сеток, удовлетворяющим различным требованиям, в управлении формой ячеек, в построении адаптивных сеток и др. [2,22,25,27,28,33-36,42,80,121] (Годунов, Забродин, Прокопов, Thompson, Soni, Weatherill, Иваненко, Лисейкин, Азаренок и др.). Между различными направлениями существуют тесная взаимосвязь. Часто характеризуя метод, можно выделить в нем использование элементов различных направлений.

Публикуются обзоры по методам построения, сборники статей и трудов конференций, монографин. Среди последних можно выделить как монографии, рассматривающие вопросы численного моделирования, где вопросы построения сеток формируют самостоятельную и неотъемлемую часть, например, Численное решение многомерных задач газовой динамики под редакцией С. К. Годунова, А. В. Забродина, М. Я. Иванова, А. Н. Крайко, Г. П. Про-копова (М.:Наука, 1976) [22], так и монографии, посвященные отдельно теме построения сеток, например Numerical Grid Generation: Foundation and Applications, J. F. Thompson, Z. U. A. Warsi, C. W. Mastine (North Holland, 1985) [118], Fundamentals of Grid Generation, P. M. Knupp и S. Steinberg (Springer, 1994) [106], Адаптивно-гармонические сетки, С. А. Иваненко (M.: ВЦ РАН. 1997) [25], Grid Generation Methods (Springer, 1999), A Computational Differential Geometry Approach to Grid Generation (Springer, 2003), V.D.Liseikin [107,108], Методы адаптивных сеток в задачах газовой динамики, А. Н. Гильманов (М.: Наука. ФИЗМАТЛИТ, 2000) [20], Selected Chapters on Grid Generation and Applications, S. A. Ivanenko (CC RAS, Moscow, 2004) [95], и др. Более полный список монографий и сборников можно найти в Интернете на сайте: http://www-users.informatik.rwth-aachen.de/ roberts/literature.html). Там же можно найти список ученых, занятых исследованиями по рассматриваемой тематике по странам, перечень заявленных программных продуктов, сравнение некоторых из них, информацию об объявленных конференциях и многое другое.

По-мимо выделенных книг можно отдельно указать также книгу Handbook of Grid Generation под редакцией J. F. Thompson, В. К. Soni, и N. P. Weatlierill (CRC Press, 1999) [99], собравшую в себя описание современных технологий и представившую много различных школ по построению сеток.

Из Российских подходов [50] в данной книге были представлены два подхода: вариационный подход к построению гармонических сеток С. А. Иваненко и вариационный подход к построению оптимальных сеток А. Ф. Сидорова, О. Б. Хайруллиной и О. В. Ушаковой. Дальнейшее развитие этих подходов было описано, в частности, в недавно вышедшей книге Advances of grid generation, (Novoscience publishers, 2005, ed. О. V. Ushakova) [75].

Вариационный подход к построению оптимальных сеток в областях геометрически сложной формы развивается в течении уже более сорока лет [52,99,112]. Он был предложен А. Ф. Сидоровым в конце пятидесятых. Тогда же была создана первая программа автоматического выбора расчетной сетки и предложена методика МОПС (массовые оптимальные сетки) для построения оптимальных одномерных сеток [4G] близких к равномерным с заданными значениями граничных интервалов. Описание алгоритма было опубликовано в 1966 г. Методика МОПС использовалась при решении задач энерговыделепия в Российских федеральных ядерных центрах в г. Саро-ве и г. Снежниске [38]. Она обеспечивает автоматический расчет сетки при задании ориентировочного числа интервалов в областях и допустимого перепада масс на их границах. Позднее была предложена концепция построения криволинейных сеток в областях сложной формы, основанная па минимизации функционалов, отвечающих за близость сеток к определенным видам качеств: равномерности, ортогональности и адаптации к решениям дифференциальных задач [48,49] (Численные методы механики сплошной среды, 1981 — Сидоров, Шабашова, 1985 — Сидоров, Ушакова). В рамках этой концепции были созданы и разработаны программы построения сеток. В частности, программа МОПС-2 (многомерные оптимальные сетки) и ее версии для параллельного расчета геометрически оптимальных структурированных и блочно-структурированных сеток в двумерных односвязиых и многосвязных областях геометрически сложной формы со сложной топологией ( [97,113] Хайруллипа, Хайруллип, Артемова), программы для построения одномерных и двумерных оптимальных адаптивных сеток, в том числе и параллельные ( [49,57,58,125] Ушакова). Были разработаны алгоритмы и программы для построения невырожденных начальных сеток, используемых в качестве начальных приближений для итерационных процедур расчета сеток, на основе R-функций — для двумерных областей звездного типа ( [18] Гасилова), и на основе геометрического подхода — для трехмерпых областей ( [31] Сидоров, Бронина). Двумерные оптимальные сетки использовались О. Б. Хайруллипой для решения различных задач математической физики, в частности, для моделирования вихревых течений газа в каналах сложных геометрий [7,65-67, 98]. Применение оптимальных гладких блочно-структурированных криволинейных сеток явилось весьма существенным фактором при решении задачи [7,65-67,98]. Хорошие аппрокси-мациоиные качества используемых сеток [24, 72, 91] стали основой достигнутых результатов. Работы [7, 65-67,97,98] были только частью большого цикла исследований по разработке эффективных методов моделирования газодинамических и акустических процессов в камерах сгорания твердотопливных ракетных двигателей, за которые А. Ф. Сидорову, О. Б. Хайруллипой, О. В. Коковихиной и большой группе других ученых была присуждена государственная премия Российской Федерации в области науки и техники. Были найдены точные решения для специальных вариационных задач расчета сеток в двумерном случае А. Ф. Сидоровым [47], в трехмерном — J1. И. Ру-бииой [45]. Эти решения могут быть использованы в качестве тестов для алгоритмов и программ расчета сеток. К. В. Емельяновым проведены теоретические исследования по применению оптимальных сеток к численному решению задач с пограпслоями [24,91]. В трехмерном случае подход описан в [52,99,112,113]. Его основной чертой является специальный способ формализации критерия близости сетки к равномерной, обеспечивающий вместе с критерием ортогональности гладкость сеток, реализацию различных краевых условий для построения сеток и возможность создания эффективных вычислительных процедур для расчета сеток на основе дискретных и вариационных формулировок. Итерационные алгоритмы расчета трехмерных сеток могут быть разработаны на тех же идеях, что и в двумерном случае. И хотя эффективных автоматизированных комплексов программ в трехмерном случае [52,99,112,113] создано не было, первый опыт в этом направлении получен в [70] (Шабашова, 1986). Это пе полный перечень разработок, выполненных в рамках подхода [52,99,112].

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

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

Создание и развитие данного метода построения сеток было определено потребностями математического моделирования задач многокомпонентной гидродинамики. Динамика многокомпонентных сред очень важная область прикладных исследований во многих научных областях, таких как физика высоких плотностей и энергий (термоядерный синтез, взрывные процессы), астрофизика (зарождение и эволюция звезд, сверх новые звезды), физика атмосферы и гидросферы Земли. Физические задачи, возникающие в данных областях, характеризуются гидродинамической неустойчивостью, возникновением вихревых и потоковых течений, а также сильными деформациями границ областей, в которых происходят физические процессы. Математическое моделирование гидродинамических течений в таких средах и потеря начальной топологической структуры представляет собой очень сложную проблему. Разностные методы с использованием лагранжевых переменных и структурированных сеток просты в реализации для таких задач и позволяют описывать как границы, так и детали течения. Но и они становятся непригодными при сильных деформациях границ. В данном случае возникают сильно искривленные сетки, близкие к вырожденным, сильно различающиеся по размерам и форме ячеек, что ведет к потере аппроксимации и точности. В этом случае расчеты часто становятся невозможными. Для продолжения расчетов должна применяться глобальная перестройка сетки с целью улучшения ее качества и консервативная переиптерполяция газодинамических полей. Многие процессы в таких задачах происходят в областях вращения, а также в объемах, полученных деформациями данных областей. Таким образом, создание и разработка метода построения трехмерных оптимальных сеток крайне важны и актуальны для математического моделирования многокомпонентных сред.

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

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

Данная диссертация представляет собой новый естественный этап развития подхода [52,99,112]. В диссертации для трехмерного случая разработан метод построения оптимальных ссток и описан соответствующий автоматизированный комплекс программ. (В [55], Ушакова, 1990 подход [112] был реализован в одномерном и двумерном случае.)

По мере разработки трехмерного метода были получены новые результаты, сформировавшие основы численного анализа трехмерных сеток [61,129] (ЖВМ и МФ, Ушакова, 2001 и Proceedings of the Steklov Institute of Mathematics, 2004), с изложения которых начинается описание метода в главе 1 диссертации. Сама диссертация состоит из введения, трех глав и заключения. В главе 2 описываются алгоритмы построения трехмерных оптимальных сеток. В главе 3 метод применен к практическим расчетам сеток. В заключении описываются возможные перспективы развития метода.

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

Другое возможное направление применения метода это расчеты многоблочных сеток со сложной топологией. В развитии этого паправлеиня сложным является вопрос о разбиении трехмерной области на блоки. Для автоматического построения начальных сеток удобно рассмотрение блоков звездного типа либо областей вращения, так как алгоритмы расчета начальных сеток для таких областей предложены (см. [13,18] Бронина, Гаеилова, Ушакова). Однако процесс разбиения на блоки пока практически не автоматизирован, за исключением областей вращения (см. [77] Artyomova, Khairullin, and Khairullina).

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

Изложенные в диссертации алгоритмы допускают несколько способов распараллеливания. Это прежде всего

- распараллеливание по блокам при расчете блочно-структурнрованных сеток [G8] (Хайруллип, Хайруллииа);

- распараллеливание явных итерационных процессов по группам соседних ячеек [58] (Ушакова).

1. Азарепок Б.Н. Алгоритм консервативной интерполяции на гексаэдраль-ных сетках // М. ВЦ РАН. 200G. 58 с.

2. Азарепок Б.Н. Об одном вариационном методе построения пространственных сеток // М. ВЦ РАН. 200G. 51 с.

3. Азаренок Б.Н., Бронина Т.Н., Ушакова О.В. / Итоговый Отчет о НИР "Разработка алгоритмов и программ построения регулярных трехмерных сеток и интерполяции газодинамических иоле" Ип-т Математики и Механики УрО РАН, Екатеринбург, 2001 г.

4. Азаренок Б.Н., Бронина Т.Н., Ушакова О.В. / Итоговый Отчет о НИР. "Расширение возможностей алгоритмов и программ построения регулярных трехмерных сеток и интерполяции газодинамических полей", Ип-т Математики и Механики УрО РАН, Екатеринбург, 2003 г.

5. Ахмадеев В.Ф., Сидоров А.Ф., Спиридонов Ф.Ф., Хайруллина О.Б. О трех методах численного моделирования дозвуковых течений в осесим-метричных каналах сложной формы // Моделирование в механике. Новосибирск, 1990. Т. 4 (21), Ж 5. С. 15-25.

6. Бабенко К.И. Основы численного анализа. М.: Наука, 198G. 744 с.

7. Бобылев Н.А., Иваненко С.А., Исмаилов И.Г. Несколько замечаний о гомеоморфных отображениях // Мат. заметки GO, 4, 199G, С. 593-59G.

8. Бобылев H.A., Иваненко C.A., Казунин A.B. О кусочно-гладких гомеоморфных отображениях ограниченных областей и их приложениях к теории сеток // Жури. выч. матем. и матем. физики. 2003. Т. 43, №. G. С. 808-817.

9. Белинский П.П., Годунов С.К., Иванов Ю.Б., Япепко И.К. Применение одного класса квазиконформных отображений для построения разностных сеток в областях с криволинейными границами // Жури, вычисл. математики и мат. физики. 1975. Т. 15, №6. С. 1499-1511.

10. Бронипа Т.Н., Гасилова И.А., Ушакова О.В. Алгоритмы для построения трехмерных структурированных сеток // Журнал выч. матем. физики. 2003. Т. 43, №. 6. С. 875-883.

11. Брошша Т.Н., Гасилова И.А., Ушакова О.В. Алгоритмы построения регулярных трехмерных сеток // Международная конференция "Заба-бахинскне научные чтения". Сентябрь 8-12, 2003. Сиежииск, РФЯЦ-ВНИИТФ. 2003, Тезисы докладов. С. 229-230

12. Т.Н.Брошша, О.В.Ушакова. Расчеты трехмерных структурированных сеток в конфигурациях с особенностями // Труды Всероссийской конференции. ВЦ РАН им. А.А.Дородпицина. Москва, 4-7 июля 2006 г., С. 190-199.

13. Гасилова И.А. Алгоритм автоматического построения начального приближения криволинейной сетки для областей звездного типа // ВАНТ, Сер. Мат. моделир. физ. процессов. 1994. Вып. 3. С. 33-40.

14. Гильмаиов А.Н. Методы адаптивных сеток в задачах газовой динамики. М.: Наука. ФИЗМАТЛИТ, 2000. 248 с.

15. Годунов С.К., Прокопов Г.П. О расчетах конформных отображений и построения разностных сеток // Журн. вычисл. математики и мат. физики. 1967. Т. 7, №5. С. 1031-1059.

16. Годунов С.К., Забродин А.В., Иванов М.Я., Крайко А.Н., Прокопов Г.П. Численное решение многомерных задач газовой динамики. М.:Наука, 1976. 400 с.

17. Годунов С.К. Об идеях, используемых прн построении разностных сеток // Журнал выч. матем. физики., Т.43, №6, 2003. С. 787-789.

18. Емельянов К.В. Применение оптимальных разностных сеток к решению задач с сингулярным возмущением // Жури, вычисл. математики и мат. физики. 1994. Т. 34, №6. С. 936-943.

19. Иваненко С.А. Адаптивно-гармонические сетки / М.: ВЦ РАН. 1997.

20. Иваненко С.А., Чарахчьян А.А. Криволинейные сетки из выпуклых четырехугольников. // Журнал вычислительной математики и матем. физики. Т.28, №.4. 1988. С. 503-514.

21. Иваненко С.А. Управление формой ячеек в процессе построения сеток. // Журнал выч. матем. физики., 2000. Т.40, №11. С. 830-814.

22. Иваненко С.А. Вариационные методы построения адаптивных сеток // Журнал выч. матем. физики. Т.43, №6. 2003. С. 830-814.29. -Управляемый термоядерный синтез / Под ред. Дж. Киллина. М.:Мир. 1980.

23. Корн Г., Кори Т. Справочник по математике. М.: Наука. 1984. 831 С.

24. Кошкина Т.Н. (Бронипа Т.Н.), Сидоров А.Ф. Об одном геометрическом способе построения трехмерных разностных сеток // Сб.Численпые и аналитические методы решения задач механики сплошной среды, Свердловск, 1981 г. С. 91-100.

25. Курант Р. Уравнения с частными производными. М.: Мир. 1962. 830 с.

26. Лисейкин В.Д. О построении регулярных сеток па н-мерных поверхностях // Журп. вычисл. математики и мат. физики. 1991. Т. 31, №11. С. 41-57.

27. Лисейкин В.Д. Обзор методов построения структурных адаптивных сеток // Журн. вычисл. математики и мат. физики. 1996. Т. 36, №1. С. 341.

28. Лисейкин В.Д. О геометрических анализе свойств разностных сеток // ДАН 2002. Т.65, №2. С. 190-193.

29. Лисейкин В.Д. О геометрических методах в теории разностных сеток // Журн. вычисл. математики и мат. физики. 2003. Т.43, №7. С. 1035-1048.

30. Лисейкин В.Д. Об универсальном эллиптическом методе построения адаптивных распостных сеток // Журп. вычисл. математики и мат. физики. 2004. Т.44, №12. С. 2179-2205.

31. Потугина И.В. Освоение и развитие методики программ расчета одномерных задач энерговыделения во ВНИИЭФ (1954-1986). // ВАНТ. Сер.: Математическое моделирование физических процессов. 1998, Вып. 2, С. 50-59.

32. Прокопов Г.П. Некоторые общие проблемы в конструировании алгоритмов построения сеток // М., Препринт ИПМ им. М.В.Келдыша РАН. №98. 1987.

33. Прокопов Г.П. Об организации сравнения алгоритмов и программ построения регулярных двумерных разностных сеток // Вопросы атомной науки и техники. Сер. Мат. моделир. физ. процессов. 1989. Вып. 3. С. 98-108.

34. Прокопов Г.П. Универсальные вариационные функционалы для построения двумерных сеток // М., Препринт ИПМ им. М.В.Келдыша РАН. 2001. №1. 36 стр.

35. Прокопов Г.П. Вариационные методы расчета двумерных сеток при решении нестационарных задач // Препринт ИПМ РАН им. М. В. Келдыша. 4. 2003. 32 стр.

36. Прокопов Г.П. Реализация вариационного подхода к расчету двумерных сеток в нестационарных задачах // Препринт ИПМ РАН им. М. В. Келдыша. №116. 2005. 36 стр.

37. Прокопов Г.П. Выбор параметров при вариационном подходе к расчету регулярных сеток // Препринт ИПМ РАН им. М. В. Келдыша. №14. 2006. 32 стр.

38. Рубина Л.И. Примеры точного решения задачи построения трехмерных оптимальных сеток // ВАНТ. Сер. Мат. моделир. физ. процессов. 1995. Вып. 4. С. 37-41.

39. Сидоров А.Ф. Об одном алгоритме расчета оптимальных разностных сеток // Тр. матем. ин-та им. В.А.Стеклова АН СССР. 1966. Т. 74. С. 147-151.

40. Сидоров А.Ф. Примеры точного построения геометрически оптимальных двумерных сеток //ВАНТ. Сер. Мат. моделир. физ. процессов. 1994. Вып. 4. С. 18-22.

41. Сидоров А.Ф., Шабашова Т.И. Об одном методе расчета оптимальных разностных сеток для многомерных областей // Численные методы механики сплошной среды. 1981. Т. 12, №5. С. 106-123.

42. Сидоров А.Ф., Ушакова О.В. Об одном алгоритме расчета оптимальных разностных сеток и его приложениях // Численные методы механики сплошной среды. 1985. Т. 16, №5. С. 101-115.

43. Сидоров А.Ф., Ушакова О.В. О работах в СССР по разработке методов и программ расчета сеток // Вычислительные технологии. T.I, №2, 4.2. Труды школы-семинара по комплексам программ мат. физики. Новосибирск, 1992 г. С. 289-294.

44. Сидоров А.Ф., Ушакова О.В., ХайрулинаО.Б. / Вариационные методы построения оптимальных сеток. Екатеринбург. Ин-т Матем. и Мех. УрО РАН. 1997. 50 С.

45. Сидоров А. Ф., Ушакова О.В., ХайрулинаО.Б. Вариационные методы построения оптимальных сеток. / Сидоров А.Ф. Избранные труды: Математика. Механика. М. Физ.мат.лит. 2001. С. 512-538.

46. Ушакова О.В. Об одной итерационной схеме решения уравнения с малым параметром па адаптирующейся сетке // Аналитические и численные методы исследования задач механики сплошной среды. Свердловск, 1987. Т. 8, N 4, С. 157-163.

47. Ушакова О.В. Теорема существования и единственности решения краевой задачи построения одномерных оптимальных адаптирующихся сеток // Моделир. в механике. Новосибирск, 1989. Т. 3, №2. С. 134-141.

48. Ушакова О.В. Метод построения оптимальных адаптирующихся сеток. Диссертация на соискание ученой степени кандидата физико-математических паук. Свердловск, 1990. 145 с.

49. Ушакова О.В. Итерационная процедура расчета двумерных оптимальных адаптивных сеток // Приближенные методы исследования нелинейных задач механики сплошной среды. Свердловск, 1992. С. 58-65.

50. Ушакова О.В. ЛАДА экономичный алгоритм и программа построения двумерных криволинейных оптимальных адаптивных сеток в одно-связных областях геометрически сложной формы. // ВАНТ. Сер. Мат. моделир. физ. процессов. 1994. Вып. 3. С. 47-56.

51. Ушакова О.В. Параллельный алгоритм и программа построения оптимальных адаптивных ссток // Сб. науч. труд. ИММ "Алгоритмы и программные средства параллельных вычислений". Екатеринбург: УрО РАН, 1995. С. 182-192.

52. Ушакова О.В. Параллельный алгоритм и программа построения оптимальных адаптивных сеток //10 Зимняя школа по механике сплошных сред (Пермь). Тезисы докладов. Екатеринбург: УрО РАН, 1995. С. 244— 245.

53. Ушакова О.В. Алгоритм построения двумерных оптимальных адаптивных сеток // Математической моделирование, Т. 9, №2. 1997. С. 88-91.

54. Ушакова О.В. Условия невырожденности трехмерных ячеек. Формула для объема ячеек // Журнал вычислительной математики и матем. физики. Т.41, №. 6. 2001. С. 881-894.

55. Фихтенгольц Г.М. Основы математического анализа. Т.2. Москва: Наука, 1968. 4.63 С.

56. Хайруллина О.Б. Расчет стационарных дозвуковых вихревых потоков идеального газа в осесимметрпчных каналах сложных геометрий // Вопросы атомной науки и техники. Сер. Мат. моделир. физ. процессов. 1990. Вып. 3. С. 32-39.

57. Хайруллина О.Б. К расчету вихревых течений газа в каналах сложных конфигураций // Прикл. механика и техн. физика. 1996. Т. 37, №2. С. 103-108.

58. Хайруллин А.Ф., Хайруллина О.Б. Построение оптимальных сеток в многосвязиых областях сложных топологий на многопроцессорных машинах // Вопросы атомной науки и техники. Сер. Математическое моделирование физических процессов. 2002. Вып.З. С. 33-39.

59. Шабашова Т.Н. Об одном экономичном способе построения оптимальных разностных сеток // Численные методы механики сплошной среды. 1983. Т. 14, №5. С. 139-157.

60. Шабашова Т.И. О построении оптимальных криволинейных координатных сеток в трехмерных областях // Численные методы механики сплошной среды. Новосибирск, 198G. Т. 17, №1. С. 144-155.

61. Шведов А.С. Формулы для объема ячеек. // Матем. заметки. 1986. Т.39. В.4. С. 597-605.

62. Широковская О.С. Замечание к статье А.Ф.Сидорова "Об одном алгоритме расчета оптимальных разностных сеток" // Журп. вычисл. математики и мат. физики. 1969. Т. 9, №2. С. 468-469.

63. Шокин Ю.И., Лисейкин В.Д., Лебедев А.С., Дапаев Н.Т., Китаева И.А. Методы римаповой геометрии в задачах построения разностных сеток. Новосибирск: Наука, 2005. 256 с.

64. Яненко Н.Н., Данаев Н.Т., Лисейкин В.Д. О вариационном методе построения сеток // Численные методы механики сплошной среды. Новосибирск, 1977. Т. 8, №4. С. 157-163.

65. Advanaces in Grid Generation / ed. by Ushakova O.V. Novascince Publishers. New-York. 2005. 430 p.

66. Artyomova N.A., Khairullin A.F., and Khairullina O.B. Generation of Curvilinear Grids in Multiply Connected Domains of Complex Topology /- Advances in Grid Generation, ed by Ushakova O.V. Novascience Publishers. 2005. pp. 191-216

67. Azarenok B,N. Conservative Remapping on Hexahedral Meshes /Advanaces in Grid Generation, ed. by O.V.Ushakova. Novascince Publishers. New-York. 2005. pp. 387-429.

68. Azarenok B.N. A variational hexahedral grid generator with control metric // J. Comput. Phys. 2006. V. 218. №2. P. 720-747.

69. Brackbill J.U., Saltzman J.C. Adaptive zoning for singular problems in two dimensions // J. Сотр. Phys. 1982. V. 46, № 3. P. 342-368.

70. Deitachmayer G.S., Droegemeier K.K. Application of continuous dynamic grid adaptation techniques to meteorological model-ling / Part I: Basic Formulation and Accuracy Monthly Weather Rev. 1992. V. 120, N 8, P. 1675-1706.

71. Dukowicz J. K. Efficient Volume Computation for Three-Dimensional Hexahedral Cells // Journal of Computational Physics. 74, №2. 1988. pp. 493-496.

72. Dukowicz J.K., Padial N.T. REMAP3D: A conservative three-dimensional remapping code, Los Alamos report, 1991.

73. Edelsbruimer H. Algorithms in combinatorial geometry / Springer-Vcrlag, New York. 1987.

74. Emcl'yanov K.V. On optimal grids and their application to the solution of problems with a singular perturbation // Rus. J. Numer. Anal. Math. Modcll. 1995. V. 10, №4. P. 299-310.

75. Farin G. Curves and Surfaces for Computer Aided Geometric Design, A Practical Guide. Fouth Edition. / Academic Press. 1997.

76. Grandy J. Conservative remapping and regions overlays by intersecting arbitrary polyhedra // J. Сотр. Phys. 148(1999). pp. 433-46G.

77. Ivanenko S. A. Harmonic mappings // in Handbook of Grid Generation, Thompson J. F., Soni В. K., and Wcathcrill N. P, eds., CRC Press, Boca Raton, FL, 1999. pp. 8-1-8-43.

78. Ivanenko S. A. Selected Chapters on Grid Generation and Applications. CC RAS, Moscow, 2004.

79. Kennon S.R., Dulikravich G.S. Generation of computational grids using optimization // AIAA J. 1986. V. 24, №7. P. 1009-1073.

80. Khairullina O.B. Method of Constructing Block Regular Optimal Grids in Two-dimensional Multiply-connected Domains of Complex Geometries // Russian Journal of Numerical Analysis and Mathematical Modelling. 11, (4). 1996. pp. 343-358.

81. Khairullina O.B. Modelling subsonic vortex gas flows in channels of complex geometries // Russian Journal of Numerical Analysis and Mathematical Modelling. 13, (3). 1998. pp. 191-219.

82. Khairullina O.B., Sidorov A.F. and Ushakova O.V. Variational methods of construction of optimal grids / Handbook of Grid Generation, Thompson J. F., Soni В. K., and Wcathcrill N. P., eds., CRC Press, Boca Raton, FL, 1999, pp. 36-1-36-25.

83. Killccn J., Controlled Fusion, Academic Press, New York, San Francisco, London, 1976.

84. Knupp P. M. and Steinberg S. Fundamentals of Grid Generation / CRC Press, Boca Raton, FL, 1994.

85. Knabner P., Summ G. The invertibility of the isoparametric mapping for pyramidal and prismatic finite elements // Numerical mathematics. 88. 2001. pp. 661-681.

86. Knabner P., Korotov S., Summ G. Conditions for the invertibility of the isoparametric mapping for hexahedral finite elements // Finite elements in analysis and design. 2003.

87. Kreis R.I., Thames F.C., Hassan H.A. Application of a variational method for generating adaptive grids // AIAA J. 1986. V. 24, №3. P. 404-410.

88. Knupp P.M. On the invertibility of isoparametric map // Comput. Methods Appl. Mech. Engrg. 78 (1990). pp. 313-329.

89. Knupp P.M. and Steinberg S. Fundamentals of Grid Generation. Springer, 1994.

90. Liseikin V.D. Grid Generation Methods. Springer, 1999.

91. Liseikin V.D. A Computational Differential Geometry Approach to Grid Generation. Springer. 2003.

92. Mastin C.W.,Thompsom J.F. Transformation of Three-Dimensional Regions onto Rectangular Regions by Elliptic Systems // Numerische

93. Mathematik. Vol.29. Fasc. 4. 1978. pp. 397-409.

94. Megiddo N. Linear-time algorithms for linear programming in Л3 and related problems // SIAM J. Computing. 12. 1983. pp. 759-776.

95. Nakahashi К., Deiwcrt G.S. Three-dimensional adaptive grid method // AIAA J. 1986. №6. P. 948-954.

96. Serezhnikova T.I., Sidorov A.F. and Ushakova O.V. On One Method of Construction of Optimal Curvilinear Grids and Its Applications // Soviet Journal of Numerical Analysis and Mathematical Modelling. 4, (2). 1989. pp. 137-155.

97. Sidorov A.F., Khairullina O.B., Ushakova O.V. Tests for two-dimensional grid generation. Suggestions / Handbook of Grid Generation Ed. by Thompson J.F., Soni B.K., Weatherill N.P. Boca Raton etc.: CRC Press, 1999. P. B-22-B-26.

98. Shangyou Z. Subtetrahedral test for the positive Jacobian of hexahcdral elements, http://www.matli.udel.edu/ szhang/research/p/subtettest.pdf.

99. Shritharan S.S. Mathematical Aspects of Harmonic Grid Generation / Mathematical Aspects of Numerical Grid Genertaion. ed. by Jose E. Castillo. SIAM. Philadelphia, Pensylvania. 1991. p.157.

100. Strang G. and Fix G. An Analysis of the Finite Element Method / New York: Prentice-Hall, New York, 1973.

101. Thompson J.F., Warsi Z.U.A., Mastine C. W. Numerical grid generation: Foundation and applications. N.Y.: North-Holland, 1985. 483 p.

102. Thomson J.F. A Survey of dynamically-adaptive grids in the numerical solution of partial differential cquationas // Appl. Numcr. Math. 1985. №1. P. 3-27.

103. Thomson J.F., Mastin C.W. Order of difference expressions in curvilinear coordinate systems // J. Fluids. Engineering. 1985. Vol 107. Pp. 241-250.

104. Thompson J.F., Soni B.K., and Weatherill N.P. / Handbook of Grid Generation. CRC Press. Boca Raton. FL. 1999.

105. Yu T.Y., Soni В. K. NURBS in Structured Grid Generation / in Handbook of Grid Generation. CRC Press. Boca Raton. FL. 1999. pp. 30-1-30-26.

106. Ushakova O.V. Algorithm of two-dimensional optimal grid generation // Numerical Grid Generation in Computational Field Simulation. Soni В. K. and Thompson J. F., eds., Mississippi State University, Mississippi State, MS, 1996. pp. 37-46.

107. Ushakova O.V. Conditions of nondegeneracy of three-dimensional cells. A formula of a volume of cells // SIAM J. Sci. Сотр. 23, 4. 2001, pp. 12731289.

108. Ushakova O.V. On Nondegeneracy of Three-Dimensional Grids. Proceedings of the Steklov Institute of Mathematics, Suppl. 1, 2004, pp. S78-S100.

109. Ushakova O.V. Nondegeneracy Conditions for Different Types of Grids / Advanaces in Grid Generation, ed. by O.V.Ushakova. Novascincc Publishers. New-York. 2005. pp. 281-322.

110. Vavasis S.A. A Bernstein-Bezier Sufficient Condition for Invertibility of Polynomial Mapping Functions. November 3, 2001. Iittp: / / www.cs.cornell.edu/home/vavasis.

111. Winslow A.M. Numerical solution of quasilinear Poisson equation in nonuniform triangle mesh // J. Сотр. Phys. 196G. V. 1, N 2, P. 149-172.