Методы самоорганизации и оптимизации для построения трехмерных расчетных сеток тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

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

Кудрявцева Людмила Николаевна А

V

МЕТОДЫ

САМООРГАНИЗАЦИИ И ОПТИМИЗАЦИИ ДЛЯ ПОСТРОЕНИЯ ТРЕХМЕРНЫХ РАСЧЕТНЫХ

СЕТОК

01.01.07 — вычислительная математика

АВТОРЕФЕРАТ диссертации па соискание ученой степени кандидата физико - математических наук

6 НОЯ 2014

Москва — 2014

005554206

005554206

Работа выполнена на кафедре интеллектуальных систем Московского физико-технического института (государственного университета).

Научный руководитель:

Официальные оппоненты:

Ведущая организация:

Гаранжа Владимир Анатольевич,

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

Жуков Виктор Тимофеевич,

доктор физико-математических наук, старший научный сотрудник, Институт прикладной математики им. М.В. Келдыша РАН,

отдел прикладных задач механики сплошных сред, заведующий отделом

Лисейкин Владимир Дмитриевич,

доктор физико-математических наук, профессор, Институт вычислительных технологий Сибирского отделения РАН, лаборатория вычислительных технологий, ведущий научный сотрудник

Институт вычислительной математики РАН

Защита состоится "_ //» 2014

/0

лэ

часов на

заседании диссертационного совета Д 212.156.05 на базе Московского физико-технического института (государственного университета) по адресу: 141700, Московская обл., г. Долгопрудный, Институтский переулок, д.9, ауд. 903 КИМ.

С диссертацией можно ознакомиться в библиотеке Московского физико-технического института (государственного университета) и на сайте университета http://www.mipt.ru.

Автореферат разослан « Р 2014 г.

Ученый секретарь /¿г ,т. „

__.___Федько Ольга Сергеевна

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

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

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

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

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

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

1 Frey J. L., George P. L. Mesh generation: Applications to finite elements. - Paris: Herm'es, 2000. - 817 p.

2 Du Q., Wang, D. Tetrahedral mesh generation and optimization based on centroidal Voronoi tessellations' // Internat. J. Numer. Meth. in Engrg. - 2003. - V. 56, N. 9. - P. 1355-1373.

3Danczyk J., Surech K. Finite element analysis over tangled simplicial meshes: Theory and implementation. // Finite Elements in Analysis and Design - 2013. - V. 70-71. -P.57-67.

области и построением поверхностной сетки.

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

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

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

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

Наличие алгоритма распутывания позволило впервые реализовать

4Гаранмса В.А. Барьерный метод построения квазиизометрических сеток // Ж. вычисл. матем. и матем. физ. - 2000. - Т.40, № 11. - С. 1685-1705.

5Persson Р.-О., Strang G. A Simple Mesh Generator in MATLAB // SIAM Rev. -2004. - V. 46, N 2. - P. 329-345.

6Ohtake Y., Belyaev A., Pasko A. Dynamic mesh optimization for polygonized implicit surfaces with sharp features // The Visual Computer. - 2003. - V. 19, N. 2. - P. 115-126.

7Иваненко С. А. Адаптивно-гармонические сетки. - M.: ВЦ РАН, 1997. - 181 с.

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

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

Все основные результаты диссертации являются новыми.

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

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

Апробация работы. Результаты работы докладывались на Международной научной конференции "Science of the future", Санкт-Петербург, 17-20 сентября 2014 г.; на XXXVIII Академических чтениях по космонавтике "Королевские чтения", Москва, 28-31 января 2014 г.; на Международной конференции "The Joint MASCOT12-12th Meeting on Applied Scientific Computing and Tools and ISGG12-12th International Conference on Numerical Grid Generation", Лас-Пальмас-де-Гран-Канария, Испания, 22-26 октября, 2012 г.; на II Международной конференции "Optimization and applications" (OPTIMA-2011), Пет-ровац, Черногория, 25 сентября - 2 октября, 2011 г., на 51-ой, 54-ой, 55-ой и 56-ой конференции МФТИ, Москва-Долгопрудный, 2008, 2011, 2012, 2013; на XI Международной конференции "Забабахинские на-

учные чтения" (ЗНЧ-2012), Снежинск, 16-20 апреля 2012 г.; на XIV Международной Байкальской школе-семинаре "Методы оптимизации и их приложения Северобайкальск, 2-8 июля 2008 г.; на Международной конференции "Numerical geometry, grid generation and scientific computing"(NUMGRID2008, NUMGRID2010, NUMGRID2012), Москва; на семинаре ВЦ РАН (рук. Ю.Г. Евтушенко), Москва, 2014 г.; на семинаре Лаборатория математического моделирования нелинейных процессов в газовых средах "Fiowmodellium Laboratory" (рук. C.B. Утюжников), Москва, 2014 г.

Публикации. Основные результаты диссертации опубликованы в 11 работах, включая 2 статьи в российских и международных рецензируемых журналах, рекомендованных ВАК [1], [2].

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

Структура и объем диссертации. Диссертация состоит из введения, семи глав, заключения и списка литературы. Она изложена на 102 страницах текста, набранного в редакционного-издательской системе Latex2e, содержит 48 рисунков и 1 таблицу. Библиография содержит 98 наименований.

Содержание диссертации

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

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

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

Рассмотрим ограниченную область iîcK3 с кусочно-гладкой границей. Пусть задана некоторая функция и(х) : R3 —>■ R такая, что во внутренних точках области выполнено и(х) < 0, а в дополнении области справедливо и(х) > 0. Предполагается, что функция и(х) непрерывна по Липшицу, представима в виде разности выпуклых функций, является кусочно-гладкой, и ее производные вдоль некоторого невырожден-

ного векторного поля, транверсального к сХ1, существуют и не равны нулю в некотором конечном слое около Oil. При решении прикладных задач для построения неявных функций разработан ряд подходов, так функция расстояния со знаком или более общая неявная функция может быть приближенно вычислена для поверхностной триангуляции, для облака точек, для набора плоских сечений, для вокселыюй решетки, а также для САПР модели тела, которая одновременно задается В-сплайнами и тесселяцией. Если входные данные неполны и противоречивы, то хорошо себя показали методы реконструкции, основанные на радиальных базисных функциях, в частности, мультиквадрики, хотя с теоретической точки зрения они сравнительно плохо изучены. Булевы операции над областями позволяют собирать области из простых примитивов и комбинировать различные типы представлений в единой неявной функции.

Пусть Ui(x) и 11,2(ж) - неявные функции, задающие области fii и 0,2 ■ Результат булевых операций - это Г2з, которая задается функцией u:s(x) следующим образом следующим образом:

Пз = iii U => из(х) = mm(ui(x), U2(x)) f23 = f2infi2 => из(х) = ma.x(ui(x),ii2(x)) П3 = f2i \ Пг => из(а;) = max(ui(a;), —U2(x))

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

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

В 2004г. в работе Перссона и Стренга5 был предложен простой эвристический алгоритм самоорганизации для построения сеток в неявных

9Shen С., O'Brien J.F., Shewchuk J.R. Interpolating and approximating implicit surfaces from polygon soup. // Proc. of ACM SIGGEAPH 2004. - New York: ACM Press, 2004. - P. 896-904.

10 Boissonat J.-D., Cohen-Steiner D., Mourrain B. et al. Meshing of surfaces // Effective Comput. Geometry for Curves and Surfaces. - Berlin, Heidelberg, New York: Springer, 2007. - P. 181-230.

11Labelle F., Shewchuk J.R. Isosurface stuffing: fast tetrahedral meshes with good dihedral angles //ACM Trans. Graphics: Special Issue on the Proc. of ACM SIGGRAPH 2007. - New York: ACM Press, 2007. - V. 26, N 3. - P. 57:1-57:10.

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

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

• Вершины сетки - это материальные точки, на которые действуют нелинейные упругие расталкивающие силы;

• для множества точек строится сетка Делоне, тетраэдры вне расчетной области удаляются;

• точки, оказавшиеся вне области, проецируются обратно на ее границу;

• на граничные грани действует специальная "обостряющая сила" 6, которая разворачивает нормаль к грани вдоль градиента неявной функции;

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

• в процессе самоорганизации происходит реконструкция неявной области и "проявление" острых ребер на ее границе;

• после реконструкции границы используется вариационный алгоритм оптимизации для удаления почти плоских тетраэдров.

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

Рис. 1. Этапы работы алгоритма самоорганизации.

Рис. 2. Пример восстановления границы области алгоритмом самоорганизации с обострением и сравнение с алгоритмом марширующих

кубов.

На рис. 2 показаны тела с восстановленной сложной структурой острых ребер. Для сравнения на рис. 2 в центре показан результат работы

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

Рис. 3. Пример построения сетки по разнородным данным.

На рис. 3 слева показано, как расчетная область "собирается" из разнородных предметов: "беседка" задается набором плоских контуров и булевыми операциями, "слон" задается поверхностной триангуляцией, а "мяч" - аналитически. В центре показана реконструкция поверхности и поверхностная сетка, а справа - трехмерная сетка.

Рис. 4. Этапы построения сетки: начальное приближение и конечный

результат.

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

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

12 Lorensen W.E., Cline Н.Е. Marching cubes: a high resolution 3D surface construction algorithm // Proc. of ACM SIGGRAPH '1987. - New York: ACM Press, 1987. - V. 21, N 4. - P. 163-170.

ток. Вариационные методы являются надежным и эффективным средством для построения расчетных сеток высокого качества 13, 14, 15, 16

Рассмотрим вариационный принцип теории упругости в лагран-жевых координатах. Пусть - это лагранжевы координаты,

a xi,x2,%3 - эйлеровы координаты материальной точки. Предположим, что отображение х(£) задает стационарную деформацию упругого тела. Матрица Якоби отображения обозначается через С, где dj = dxi/d^j.

Упругая деформация х(^) является минимизирующим отображением для функционала запасенной энергии. Для того, чтобы выписать функционал для отображения между двумя многообразиями, предположим, что (?£(£) и Gx (х) - метрические тензоры, задающие посредством линейных элементов метрики в лагранжевых и эйлеровых координатах в областях и 0.х, соответственно. Тогда функционал можно записать в виде4

F(x)= [ wifiWiQVsxH-^detHdZ, (1)

Jn(

где

,y(C) = (1-e)ii++ <letc, (2)

это упругий потенциал, w(£) ^ 1 - весовая функция, 1 > в > 0, а НТН = G^detff > О, QTQ = Gx, det Q > О

- некоторые факторизации метрических тензоров. Если существуют квазиизометрические параметризации ту(£) и у(х) многообразий М^ и Мх, то II и Q могут быть выбраны как матрицы Якоби этих параметризаций. Функционал (1) зависит только от главных инвариантов матрицы Vja.

13 Brackbill J.U., Saltzman J.S. Adaptive zoning for singular problems in two dimensions //J. Comput. Phys. - 1982. - V. 46, N. 3. - P. 342-368.

14 Liseikin V.D. Grid generation methods. - Berlin, Heidelberg, New York: Springer, 1999.

15Charakhch'yan A.A., Ivanenko S.A. A variational form of the Winslow grid generator. 11 J. Comput. Phys. - 1997. - V. 136, N. 2. - P. 385-398.

16Jacquotte O-P. A mechanical model for a new mesh generation method in computational fluid dynamics. // Сотр. Meth. Appl. Mech. Eng. - 1988. - V. 66, N. 3.

- P. 323-338.

Рассмотрим поверхность 5' в М3, заданную параметрически как , £2). Поскольку векторная средняя кривизна поверхности совпадает с бельтрамианом ее координатного представления Авх = уН, то дискретный аналог оператора Лапласа-Бельтрами Дв может быть использован для вычисления дискретной средней кривизны. Для дискретизации оператора Лапласа-Бельтрами в работе используется вариант метода конечных объемов, обеспечивающий локально второй порядок при вычислении "потоков" через ребра на сильно неравномерных сетках при слабом уклонении от ортогональности, а также сохраняющий устойчивость на невыпуклых четырехугольных ячейках на плоскости. Для того, чтобы адаптировать поверхностную сетку к кривизне поверхности, используется функционал (1), в котором й = 2, а метрический тензор Сх(х) задается как

Сх(х) = (1+с\Н{х)\)1

где Н(х) - векторная средняя кривизна поверхности, с - постоянный вес. При этом предполагается, что переменные х, - это декартовы переменные на касательной плоскости к 5 в некоторой точке р, так что локально можно полагать, что в точке р метрический тензор поверхности - это единичная матрица, и рассматривается функционал только в малой окрестности точки р. В других переменных выражение для тензора С?х оказывается более сложным.

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

- (1 - х(сЫС) +

где

С) = С + ^г1 + С2) (3)

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

Хе^С) =ае!;С + е, (4)

17Гаранмса В.А., Капорин И.Е. Регуляризация барьерного вариационного метода построения расчетных сеток // Ж. вычисл. матем. и матем. физ. - 1999. - Т. 39, №

9. - С. 1489-1503.

где параметр продолжения е выбирается из условия с^ С + е > 0 во всех точках области.

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

где ж/,(£) - непрерывное кусочно-гладкое отображение. Если ячейки К). - симплексы, то отображение на каждом таком элементе мож-

но положить аффинным, а матрицу Якоби - постоянной. Так что при

где -р/' обозначает дискретный функционал. Когда локальное отображение не является аффинным, необходимо использовать квадратурные правила. Для класса непрерывных кусочно-полиномиальных отображений, используя свойство поливыпуклости \¥0, в 18, [2] были предложены геометрические квадратуры, гарантирующие, что

Заметим, что вне допустимого множества функционалу F^XhiQ) приписывается значение +оо.

В главе 4 изложены алгоритмы оптимизации и распутывания ссток. Дискретный функционал можно записать как функцию Fe(Z) = Fs(z\,..., zrlv), аргумент Z £ R3xrív которой составлен из nv трехмерных векторов Zk ■ Каждый такой вектор - это искомые координаты вершины трехмерной сетки, которые в совокупности однозначно определяют отображение хн{С)-

Градиент R.e е R3хфункции Fe{z\,..., znv) составлен из трехмерных векторов г% = '-Щ-. Матрица Гессе Не функции Fe составлена

18Branets L.V., Garanzha V.A. Distortion measure for trilinear mapping. Application to 3-D grid generation. // Num. Linear Algebra Appl. - 2002. - V. 9, N. 6-7. - P. 511 -526.

w(£) = 1

Fs(xh(0) = £ We(Vxh(É))|tffc vol(Kk) = FEh(xh(0)

k

F0(xh(0) < F0fc(:r/,(0)

Q2 тр

из 3 x 3 блоков Hfj = dz.g^T , причем матрица Hfj помещается па место

пересечения г-й блочной строки и j-го блочного столбца.

Для неявных областей граничные условия входят в схему минимизации, поскольку вершина сетки zk должна двигаться по поверхности и(х) = 0. Предположим, что вектор Vu(zk) определен. В противном случае для вычисления градиента можно использовать касательный конус в граничной точке. Так что мы предполагаем, что в каждой граничной вершине определены два линейно независимых вектора Ii, /2, задающих касательную плоскость к 9П, т.е. lf^7u(xk) — 0. Условия стационарности в точке zk можно записать так

lfgfk=0, г =1,2 (5)

u{zk) = 0 (6)

Пусть (5Zk обозначает смещение в точке zk. Линеаризуя уравнение (6), получаем 5zJVu(zk)+u(zk) = 0. Таким образом, если u(zk) = 0, то смещение Szk лежит в касательной плоскости Szk = ßih+ßih ■ Обозначим через V оператор, который проектирует граничную точку на dQ вдоль линий, приближающих градиентные кривые функции и(х) и оставляет внутреннюю точку неизменной. Пусть Lk = I — V u{zk)V u{zk)T £ Ж3х3 в случае, когда zk - это граничная вершина, и Lk = I для внутренних точек.

Z-ая итерация предобусловленного метода проекции градиента, объединенного с продолжением по параметру е для штрафного метода (3), записывается следующим образом

e{Zl) = (6g + 0.004♦ (min^mintdetC^))))2)C = QVixP~1 (7)

nv

Z LfHijLjSSj + LjrtiZ1) = 0 (8)

3 = 1

4+1 = V(z'k + riLközk), к = 1,..., nv. (9)

Параметр ti находится посредством приближенного решения одномерной задачи минимизации

г, = arg min Fe(V(Zl + rSZ)) ■" (10)

методом деления пополам. Формула (7) означает, что минимимум детерминанта матрицы С вычисляется по всем квадратурным узлам всех

ячеек сетки Zl . Параметр ¿о - это некоторое малая положительная постоянная. При использовании поправочной функции Хе(') Для барьерного метода из (4), формулы пересчета для е необходимо модифицировать:

£l+1 = £1 - a(sl — | min(det С, 0)|)), 0 < а < 1 (11)

Эта формула гарантирует, что el+1 < е1 и ei+1 удовлетворяет det C(Z)+e > 0 с Z = Z1, что дает допустимое начальное приближение для итерации / + 1. Здесь предполагается, что е° = || min(det С, 0)|.

Матрицу линейной системы обычно дополняют до полного ранга так, чтобы не модифицировать значащие компоненты решения. Для того, чтобы получить итерационный метод Иваненко-Чарахчьяна 18, нужно положить Hij = 0 для i ф j. Для того, чтобы получить неявный метод из работы4, нужно выбросить внедиагональные элементы в матрицах Lj Пг] Lj. В результате линейная система (8) распадется на 3 независимых линейных системы по отношению к векторам 5Zrn, определенных перестановкой (SZm)i = (ÖZi)m. Если е > 0, то надо отбрасывать также все члены, которые зависят от вторых производных функции Хе(') из (3). В4 было показано, что матрицы полученных линейных систем положительно определены, так что для приближенного решения можно использовать метод сопряженных градиентов. Расчетные формулы метода оптимизации для допустимых сеток можно получить если везде положить е = 0.

Для метода распутывания справедлива следующая теорема Теорема 1. Пусть допустимое множество непусто, т.е. существует сетка Z такая, что Fq(Z) < +оо. Пусть на каждом шаге градиентного спуска (9), (10) выполнено условие существенного убывания

F£t(Zl+1)^(l-a)F£l(Zl),

где 1 > а > 0 - это постоянная из равенства (11). Тогда через конечно число шагов L будет выполнено Fq(Zl) < +оо.

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

В главе 5 описаны численные эксперименты по распутыванию трехмерных сеток.

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

Все результаты численных экспериментов приводятся для неявного метода. Для сравнения алгоритмов распутывания был предложен жесткий тест, в котором строится деформация упругого материала между двумя кубами, причем внутренний жесткий куб поворачивается вокруг вертикальной оси на углы а = 0,7г/8,37г/8,7г/2,77г/8,7г. При этом сторона внешнего куба равна 1, а внутреннего - 1/\/2, что не позволяет построить гомотопию из начального состояния в конечное в допустимом множестве. На рис. 5 вверху показаны ряды ячеек сетки размером З23 и их деформация при поворотах внутреннего куба, а также координатная поверхность г'з = 4. Снизу на рис. 5 показано, как деформируются три различных координатных поверхностей при повороте внутреннего куба.

Таблица 1. Результаты распутывания

Ос тг/8 Зтг/8 тг/2 7Г*/2 7тг/8 7Г

Minit 19264 22400 31192 124128 32032 34157

Л/щах 19264 36029 82330 663436 213554 126644

niter 140 8160 2120 9240 63600 56000

tu 164 8243 2983 67654 84562 67928

Фтт 4.34 Ю-2 1.72 Ю-3 1.97 Ю-3 7.76 Ю-4 1.02 Ю-4 2.65 Ю-4

Фт'т 1.06 Ю-1 7.0 Ю-3 1.48 Ю-2 9.07 Ю-3 3.05 Ю-4 1.87 Ю-3

В Таблице 1 М(пц - это число отрицательных обобщенных тетраэдров, т.е. число квадратурных узлов с отрицательным значением детерминанта матрицы Якоби, Мтах - максимальное число обобщенных отрицательных тетраэдров во время распутывания, niter - число итераций распутывания для достижения числа отрицательных тетраэдров менее 100 (после этого задача распутывания решается локально), tu -процессорное время для niter шагов (одно ядро Intel 17 2200ГГц). Величина фщ'т - это минимальное значение меры качества формы для конечной сетки detC/(| trCTC)5, где С - матрица Якоби, a Vmin -минимальное значение меры качества объема 2detC/(l + detC2). Вариант, отмеченный * соответствует сетке 643.

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

Рис. 5. Деформация ячеек сетки и координатных поверхностей.

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

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

Рис. 6. Начальная тесселяция и криволинейная сетка.

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

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

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

Рис. 7. Последовательные стадии распутывания для тела с крыльями и

рулями.

Рис. 8. Сетка, адаптированная к кривизне и поле дискретной средней

кривизны.

В главе 7 рассматривается применение вариационного метода для построение толстых призматических слоев.

Метод упругой разгрузки для построения толстых сеточных призматических слоев формулируется так. Сначала строится тонкий слой призматических ячеек. Затем для каждой призмы в лагранжевых координатах задается целевой метрический тензор С^ такой, что после упругой разгрузки посредством минимизации функционала (1) получается тонкий слой. Поскольку целевые формы ортогональны,

то {&*£}13 = = 0. Далее можно постепенно увеличивать

элемент {С^}зз, и каждый раз приближенно решать вариационную задачу (1), пока он не достигнет заданной величины Н2, где II -искомая толщина призматического слоя, см. рис 9. В областях самоналожения слоев строится приближенная срединная поверхность. Результатом работы алгоритма, в частности, является некоторый аналог медиальных осей, т.е. набора обобщенных срединных поверхностей, поведение которых сильно отличается от медиальных осей. В частности, они весьма устойчивы к возмущениям поверхности.

(а)

(б)

Рис. 9. (а) Тонкий начальный слой, (б) промежуточный слой, (в) толстый слой, (г) слой с удаленными самопересечениями.

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

Рис. 10. (а) Слой после сглаживания при помощи оператора Лапласа-Бельтрами, (б) разбиение слоя на два, (в) ортогонализация внутреннего подслоя, (г) конечная многослойная сетка.

В заключении приведены основные результаты диссертации, выносимые на защиту.

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

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

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

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

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

Работа поддержана грантом РФФИ 14-07-008-05, грантом Президиума РАН П-18, а также грантом по программе "О мерах по привлечению ведущих учёных в российские образовательные учреждения высшего профессионального образования" (контракт №11.G34.31.0072)

Список публикаций автора по теме диссертации

1. Гаранжа В. А., Кудрявцева Л. Н. Построение трехмерных сеток Делоне по слабоструктурированным и противоречивым данным // Ж. вычисл. матем. и матем. физ. - 2012. - Т. 52, №3 - С. 499-520

2. Garanzha V.A., Kudryavtseva L.N., Utyzhnikov S.V. Untangling and optimization of spatial meshes // Journal of Computational and Applied Mathematics. - 2014. - October. - V. 269 - P. 24-41.

3. Гаранжа В.А., Забарко Д.А., Котенёв В.П., Кудрявцева Л.Н. Построение блочных расчётных сеток с использованием вариационного метода вокруг тел с рулями и крыльями // Труды секции 22 имени академика В.Н. Челомея XXXVIII Академических чтений по космонавтике: "Ракетные комплексы и ракетно-космические системы -проектирование, экспериментальная отработка, лётные испытания, эксплуатация". - Реутов: ОАО "ВПК "НПО машиностроения" , 2014. - С. 84-91

4. Белокрые-Федотов А.И., Гаранжа В.А., Кудрявцева Л.Н., Утюжников C.B. Построение толстых призматических сеточных слоев около тел сложной формы // Сборник научных трудов Международной конференции «Разностные схемы и их приложения», посвященной 90-летию профессора В.С.Рябенького. - Москва: ИПМ им. М.В. Келдыша РАН, 2013 г. - С. 48-50.

5. Белокрыс-Федотов А.И., Гаранжа В.А., Кудрявцева JI.H., Тита-рев В.А., Утюжников С.В. Построение трехмерных расчетных сеток для вычислительного комплекса по математическому моделированию задач высотной гиперзвуковой аэродинамики лаборатории Flowmodellium // Труды 56-й научной конференции МФТИ: Управление и прикладная математика. Т. 2. - Москва: МФТИ, 2013. - С. 86-87

6.Гаранжа В.А., Кудрявцева Л.Н., Утюжников С.В. Построение поверхностных и объемных сеток вариационным методом с адаптацией к кривизне поверхности // Тезисы XI Международная конференция "Забабахинские научные чтения" (ЗНЧ-2012). - Снежипск: РФЯЦ-ВНИИТФ, 2012. - С. 308.

7. Белокрыс-Федотов А.И., Гаранжа В.А., Кудрявцева JI.H. Построение тетраэдральных сеток при неточном и противоречивом задании входных данных / / Тезисы XI Международная конференция "Забабахинские научные чтения" (ЗНЧ-2012). - Снежинск: РФЯЦ-ВНИИТФ, 2012. - С.309.

8.Белокрыс-Федотов А.И., Гаранжа В.А., Кудрявцева JI.H. Построение тетраэдральных и гексаэдральных сеток в неявных областях // Тезисы XIII Международного семинара "Супервычисления и математического моделирование". - Саров: ФГУП РФЯЦ-ВНИИЭФ, 2011. - С. 43-45

9. Гаранжа В.А., Кудрявцева JI.H. Построение трехмерных сеток Делоне по слабоструктурированным и противоречивым данным // Оптимизация и приложения: сборник статей. - М.: ВЦ РАН, 2010. - С. 42-74.

10. Белоусова JI.H., Гаранжа В.А. Построение сеток Делоне в неявно заданных областях с негладкой границей // Труды 51-й научной конференции МФТИ: Часть VII. Управление и прикладная математика Том 2. - Москва: МФТИ, 2008. - С. 98-101.

11 .Белоусова Л.Н., Гаранжа В.А. Сравнение алгоритмов глобальной оптимизации расчетных сеток // Труды XIV Международной Байкальской школы-семинара "Методы оптимизации и их приложения". Т. 3. Вычислительная математика. - Иркутск: ИСЭМ СО РАН, 2008. ISBN 978-5-93908-052-1. - С. 21-26.

Кудрявцева Людмила Николаевна

МЕТОДЫ САМООРГАНИЗАЦИИ И ОПТИМИЗАЦИИ ДЛЯ ПОСТРОЕНИЯ ТРЕХМЕРНЫХ РАСЧЕТНЫХ СЕТОК

Автореферат

Подписано в печать 09.10.2014. Формат 60x84 1/16. Усл. печ. л. 1,0. Тираж 100 экз. Заказ № 375.

Федеральное государственное образовательное автономное учреждение высшего профессионального образования "Московский физико-технический институт (государственный университет)" Отдел оперативной полиграфии "Физтех-полиграф" 141700, Московская обл., г.Долгопрудный, Институтский пер., 9.