Авторефераты по всем темам >>
Авторефераты по разное
На правах рукописи
Гаранжа Владимир Анатольевич
ДИСКРЕТНЫЕ КРИВИЗНЫ, КВАЗИИЗОМЕТРИЧЕСКИЕ ОТОБРАЖЕНИЯ И КВАЗИОПТИМАЛЬНЫЕ РАСЧЕТНЫЕ СЕТКИ
01.01.07 вычислительная математика
АВТОРЕФЕРАТ
диссертации на соискание ученой степени доктора физико - математических наук
Новосибирск 2011
Работа выполнена в Учреждении Российской академии наук Вычислительном центре им. А.А. Дородницына РАН
Официальные оппоненты:
доктор физико-математических наук, профессор Миклюков Владимир Михайлович академик РАН Коновалов Анатолий Николаевич доктор физико-математических наук, профессор Копылов Анатолий Павлович
Ведущая организация:
Учреждение Российской академии наук Институт вычислительной математики РАН
Защита состоится 17 февраля 2011 г. в 15-00 на заседании диссертационного совета Д003.015.04 при Учреждении Российской академии наук Институте математики им. С.Л. Соболева СО РАН по адресу: 630090, Новосибирск, пр. Акад. Коптюга, 4.
С диссертацией можно ознакомиться в библиотеке Учреждения Российской академии наук Института математики им. С.Л. Соболева СО РАН
Автореферат разослан 201 г.
Ученый секретарь диссертационного Мирошниченко В. Л.
совета, к.ф.-м.н.
Общая характеристика работы
Цели работы. а) Разработка, обоснование и численная реализация поливыпуклого вариационного метода построения квазиизометрических параметризаций для многомерных нерегулярных многообразий, теоретическое обоснование вариационных методов построения расчетных сеток; б) разработка метода приближения упругих деформаций квазиизометрическими отображениями посредством конструирования гипотетического упругого материала с поливыпуклой внутренней энергией, не допускающего сингулярные деформации, исследование связи поливыпуклости внутренней энергии и гиперболичности нестационарных уравнений теории термоупругости; в) исследование приближения поверхностей ПРВ (представимых разностью выпуклых функций [2]) двойственными многогранными поверхностями, при котором дискретные кривизны приближают кривизну поверхности.
Постановка задачи и актуальность темы диссертации. Если гомеоморфное отображение некоторой области Rd является квазиизометрическим, то отношение длины произвольной спрямляемой кривой к длине ее образа ограничено сверху величиной L, а снизу - величиной 1/L, где L 1 - постоянная квазиизометрии (или постоянная эквивалентности). Оптимальным квазиизометрическим отображением при заданных ограничениях будем называть отображение с наименьшим значением L.
Задача построения оптимальных квазиизометрических координат на криволинейных поверхностях была сформулирована П.Л. Чебышевым в 1856 г. в работе УО черчении географических картФ. При построении расчетных сеток принцип квазиизометричности есть не что иное как математическая формулировка принципа квазиравномерности сеток. Задача разработки численного метода построения квазиизометрических отображений была поставлена С.К. Годуновым в 90-х годах XX века, а первое решение этой задачи в классе конформных отображений было предложено С.К. Годуновым с соавторами в работе [9] применительно к задаче параметризации плоского криволинейного четырехугольника.
Можно сформулировать постановку задачи о построении параметризации в следующем общем виде.
Проблема 1. Сформулировать корректную вариационную задачу для построения квазиизометрических параметризаций многомерных нерегулярных многообразий, решение которой существует, единственно и устойчиво к малым возмущениям входных данных.
Проблема 2. Доказать, что решение дискретной вариационной задачи существует, является квазиизометрическим отображением, единственно и устойчиво к малым возмущениям входных данных, и сходится к решению исходной задачи; получить оценки вычислительной сложности решения и скорости сходимости при измельчении сетки.
В такой постановке эти задачи до сих пор остаются нерешенными.
В данной работе впервые предложено их частичное решение. Основная теоретическая трудность, препятствующая полному решению этих проблем, сформулирована ниже:
Проблема 3. Описать наиболее широкое подмножество класса квазиизометрических отображений, включающее кусочно-аффинные отображения, и такое, что для произвольного отображения из этого подмножества можно построить последовательность кусочно-аффинных квазиизометрических отображений k таких, что константы эквивалентности для композиции отображений -1 сходятся к 1 при k .
k Заметим, что аналогичные задачи не решены и в теории упругости с конечными деформациями. Проблема 3 является весьма частным случаем известной нерешенной проблемы анализа, которую сформулировал Джон Болл [20]: построить сходящуюся последовательность кусочно-аффинных гомеоморфизмов в Rd, аппроксимирующих задан1,p ный соболевский гомеоморфизм в пространстве Соболева W, p > d.
Тот факт, что в качестве класса квазиизометрических отображений, допускающих правильную аппроксимацию кусочно-аффинными гомеоморфизмами потенциально можно рассматривать отображения, представимые в виде разности выпуклых функций [2], [25], и стал поводом для приведенного в работе исследования о правильном приближении поверхностей ПРВ двойственными многогранниками.
Основные результаты диссертации, выносимые на защиту.
1. Предложен метод аппроксимации поверхностей парой локально полярных многогранных поверхностей, позволяющий строить кусочноаффинную аппроксимацию сферического отображения, и, соответственно, кусочно-постоянную аппроксимацию кривизны, в окрестности невырожденных регулярных точек поверхностей ПРВ.
2. Для двумерной кусочно-регулярной поверхности ПРВ M показано, что для площади сферического изображения каждого из двойствен ных аппроксимантов Pk и Pk справедливо разложение Лебега на абсолютно непрерывную компоненту (интеграл от кривизны Урегулярной частиФ многогранной поверхности), на сингулярную компоненту (площадь сферического изображения Уострых реберФ многогранников), и на дискретную компоненту (площадь сферического изображения Уконических вершинФ многогранников). Разложения Лебега для Pk и Pk покомпонентно сходятся к разложению Лебега для M.
3. Предложен поливыпуклый вариационный принцип для построения многомерных квазиизометрических отображений как деформаций гипотетического упругого материала, исключающего сингулярные деформации. Для экстремальной задачи доказана теорема существования минимизирующего отображения, его обратимость и квазиизометричность. В двумерном случае, на основе теории многообразий ограниченной кривизны, доказана теорема существования, не требующая априорных предположений о непустоте множества допустимых отображений.
4. Предложен метод квазиизометрической регуляризации уравнений теории упругости с конечными деформациями, сохраняющий поливыпуклость и постоянные Ламе. Показано, что уравнения теории термоупругости с поливыпуклой внутренней энергией допускают каноническую симметризованную запись С.К. Годунова в лагранжевых и эйлеровых координатах, удовлетворяющую условиям гиперболичности по Фридрихсу.
5. Предложена дискретная аппроксимация поливыпуклого функционала как некоторая мера искажения расчетной сетки. Для класса многомерных кусочно-полиномиальных отображений доказан локальный принцип максимума для поливыпуклых мер искажения, и предложены геометрические квадратуры, которые гарантируют, что непрерывный функционал мажорируется дискретным, так что теоремы существования, обратимости и квазиизометричности напрямую применимы в дискретной постановке, в том числе при измельчении сеток.
6. Предложен и реализован итерационный метод минимизации дискретных функционалов, для которого строго доказана сходимость;
предложена практическая схема сжатия допустимого множества для квазиминимизации постоянной квазиизометрии; предложен вариант функционала, приближенно ортогонализирующий отображения вблизи внешних и внутренних границ; предложен и реализован новый эффективный метод построения допустимых отображений, или, иными словами, метод УраспутыванияФ сеток; на основе предложенного вариационного метода разработан практический алгоритм распластывания поверхностей со свободными границами с квазиоптимальными константами искажения.
Научная новизна. В работе впервые построено теоретическое обоснование вариационных методов построения квазиизометрических расчетных сеток и впервые построена каноническая термодинамически согласованная форма записи уравнений теории упругости в эйлеровых и лагранжевых координатах, гиперболическая по Фридрихсу, при условии, что внутренняя энергия упругого материала является поливыпуклой. Все основные результаты диссертации являются новыми.
Теоретическая и практическая ценность. Предложенный метод построения квазиоптимальных квазиизометрических отображений позволяет строить квазиизометрические параметризации с меньшими константами эквивалентности по сравнению с известными методами. Полученные результаты могут быть использованы в различных прикладных областях, включая численное моделирование, инженерный анализ, вычислительная геология и стратиграфия, вычислительная нейробиология, и др. Задача о приближении кривизны при аппроксимации тел многогранниками возникает практически во всех областях геометрического и численного моделирования.
Достоверность работы и методы исследования. Для доказательства теорем существования минимизирующих отображений (квазиизометрических упругих деформаций) использовался аппарат математической теории упругости с конечными деформациями [18], [19], [16], аппарат теории многообразий ограниченной кривизны [4], [5], [28], [21], [6], включая метод разрезания и склеивания А.Д. Александрова. При исследовании проблемы симметризации и гиперболичности нестационарных уравнений теории термоупругости использовался аппарат преобразований Лежандра и аппарат энтропийных решений [8], [14]. При рассмотрении задачи о приближении многогранниками поверхностей, представимых как разность выпуклых функций, использовался аппарат теории полярных многогранников [3], [23], и разбиений Делоне [12] и Вороного [7].
Апробация работы. Результаты работы докладывались на семинаре Института математики им. С.Л. Соболева СО РАН (рук. С.К. Годунов), 2010 г., 2008 г.; на семинаре В - РАН (рук. А.А. Петров), 2009 г.;
на семинаре ИВМ РАН (рук. В.И. Лебедев), 2009 г.; на семинаре ИПМ РАН, 2009 г.; на семинаре УДискретная геометрия и геометрия чисеФ мех.-мат. факультета МГУ (рук. Н.П. Долбилин), 2009 г.; на семинаре Института математики им. С.Л. Соболева СО РАН (рук. Ю.Г. Решетняк), 2009 г.; на семинаре Института математики им. С.Л. Соболева СО РАН (рук. И.А. Тайманов), 2009 г.; на семинаре Технологического института Хельсинки, Финляндия, 2008 г.; на семинаре Университета Кастилия - Ла Манча (рук. П. Педрегал), 2008 г.; на семинаре Института им. Макса Планка (рук. Х.-П. Зайдель), Саарбрюкен, Германия, 2006 г. и 2002 г.; на семинаре Института технической и прикладной математики им. Фраунгофера, Кайзерслаутерн, Германия, 2003 г.;
на семинаре INRIA (рук. Ж. Жаффре), Рокенкур, Франция, 2002 г.;
на Международной школе-конференции УАнализ и геометрияФ, Новосибирск, 12-17 сентября 2009 г.; на Международной конференции УДифференциальные уравнения и топологияФ, посвященной 100-летию со дня рождения Л.С. Понтрягина, Москва, 17-22 июня 2008 г.; на Международной конференции, посвященной 100-летию со дня рождения С.Л.
Соболева, Новосибирск, 5-12 октября 2008 г.; на Международной конференции УNumerical geometry, grid generation and scientific computing & Voronoi-2008Ф, Москва, 10-13 июня 2008 г.; на XIV Международной Байкальской школе-семинаре УМетоды оптимизации и их приложенияФ, Северобайкальск, 29 июня-6 июля 2008 г.; на Международном семинаре MASCOT07: 7th Meeting on Applied Scientific Computing and Tools, Grid Generation, Approximation and Visualization, 13-14 сентября 20г., Рим, Италия; на Международном симпозиуме 19th Chemnitz FEM Symposium, 1-3 сентября 2006 г., Хемниц, Германия; на Всероссийской конференции УЧисленная геометрия, построение расчетных сеток и высокопроизводительные вычисленияФ, 2006 г., Москва; на Международной школе-конференции по анализу и геометрии, посвященной 75-летию Ю.Г. Решетняка, 23 августа - 2 сентября 2004, Новосибирск.
Публикации. Основные результаты диссертации опубликованы в виде 15 статей в российских и международных рецензируемых журналах, рекомендованных ВАК [29] - [43].
ичный вклад автора. Десять из пятнадцати основных публикаций по теме диссертации написаны без соавторов. Вклад автора в совместные работы состоит в постановке задачи и разработке метода минимизации дискретных функционалов [29], [40], [33], в постановке задачи и теоретическом анализе [37], в постановке задачи и совместной работе над доказательством теорем [32].
Структура и объем диссертации. Диссертация состоит из семи глав, включая введение, и списка литературы. Она изложена на 2страницах текста, набранного в редакционного-издательской системе Latex2e, содержит 149 рисунков и 2 таблицы. Библиография содержит 166 наименований.
Содержание диссертации Общая структура дисссертации. Диссертация разбита на главы, которые, в свою очередь, подразделяются на параграфы. Первая часть каждой главы содержит обзор известных результатов по теме главы, на основе которых далее излагаются результаты автора. Каждая глава завершается выводами.
Глава 1. Введение В данной главе приведена характеристика основных результатов диссертации.
Глава 2. Нерегулярные многообразия и дискретные кривизны В этой главе приведен краткий обзор теории двумерных многообразий ограниченной кривизны (МОК), и классов поверхностей, которые являются МОК в смысле внутренней геометрии, в том числе поверхностей ПРВ (представимых в виде разности выпуклых функций). Из обширной теории МОК, разработанной в работах А.Д. Александрова, Ю.Г. Решетняка, И.Я. Бакельмана, Ю.Ф. Борисова, В.А. Залгаллера, А.В. Погорелова, Ю.Д. Бураго, У. Ланга, М. Бонка, и других авторов (см. монографии [4], [28], [5]), особое внимание в обзоре уделено результатам о существовании квазиизометрических параметризаций МОК, и о пропорциональном приближении МОК многогранными многоообразиями [28], при котором можно найти квазиизометрическое отображение многообразия на многогранный аппроксимант, причем сходимость многогранного многообразия к исходному подразумевает стремление постоянной квазиизометрии к 1.
В данной главе предложена эвристическая оценка константы квазиизометрии параметризации МОК, не использующая тот факт, что положительная часть внутренней кривизны многообразия ограничена сверху величиной 2. Численные эксперименты, описанные в Главе подтвердили практическую полезность этой оценки. Результаты данной главы опубликованы в [39].
Глава 3. Внешние дискретные кривизны на основе принципа двойственности Эта глава посвящена задаче построения УправильнойФ многогранной аппроксимации поверхностей ПРВ. В дальнейшем изложении верхний индекс l будет использоваться для обозначения трехмерных векторов, в то время как величины без индекса l будут использоваться для обозначения проекций этих векторов на плоскость x3 = 0. Таким образом, будут использоваться обозначения xl = (x1 x2 x3)T, x = (x1 x2)T.
Аффинная эквивалентность нормального изображения вершины и ее двойственной грани. Рассмотрим двумерный параболоид 1 P = {x3 = u(x1, x2), u(x1, x2) = (h11x2 + 2h12x1x2 + h22x2) = xT Hx}, 1 2 где H - тензор кривизны параболоида P в начале координат. Предполагается, что симметричная матрица H не является вырожденной.
а) б) oil Fi fkl l pj+pjl pj+Qi qk qk pi pi pj Рис. 3.1. а) Многогранная поверхность, вписанная в эллиптический параболоид, б) двойственная грань и нормальное изображение вершины.
Рассмотрим выпуклые многогранные поверхности Ph и Ph, полярные друг другу относительно эллиптического параболоида P. Полярность, в частности, означает, что произвольная вершина ql поверхности Ph двойственна грани Q поверхности Ph, где плоскость этой грани задается равенством x3+(ql)3 = qT Hx. Соотношения полярности должны быть симметричны, так что в них Ph и Ph можно поменять местами.
На рис. 3.1 а) показаны вписанный многогранник Ph и описанный многогранник Ph, которые являются частным случаем полярных многогранников.
T Предположим, что i-я вершина Ph задается как pl = (pT i), pi = i i 0. Обозначим через V(pl) множество вершин Ph, принадлежащих ребi рам, инцидентным pl, в то время как обозначение V(G) используется i для множества вершин грани G. Вершины pl, принадлежащие ребj T рам Ph, инцидентным pl, задаются равенствами pl = (pT u(pj) + j).
i j j Величины j задают отклонение вершин Ph от поверхности параболоида. Плоскость грани, полярной относительно вершины pl задается j равенством x3 + (pl )3 = pT Hx, в то время как плоскость, полярная j j pl, задается как x3 + i = 0. Обозначим через Qi грань многогранниi ка Ph, двойственную вершине pl. Нормальным изображением вершиi ны pl является выпуклый многоугольник Fi, лежащий на плоскости i x3 = 1 + i. Вершины этого многоугольника являются пересечениями лучей, проходящих через pl и ортогональных граням, инцидентным pl, i i с плоскостью x3 = 1+i. Многоугольники Qi и Fi показаны на рис. 3.б). Справедлива следующая теорема.
Теорема 3.1. Многоугольники Fi и Qi аффинно эквивалентны, т.е.
Qi = (Fi), и матрица Якоби аффинного отображения совпадает i i с -H, где H - это тензор кривизны параболоида P в начале координат.
Следует заметить, что при доказательстве теоремы положительная определенность матрицы H не использовалась. Таким образом, принцип аффинной эквивалентности справедлив и в случае гиперболического параболоида, показанного на рис. 3.2 а) а) б) fkl Fi oil l pj+pil Qi qk qk pjl Рис. 3.2. а) Многогранная поверхность, вписанная в гиперболический параболоид, б) двойственная грань и нормальное изображение вершины.
В диссертации показано, что Теорема 3.1 обобщается на случай dмерного параболоида в Rd+1.
Из принципа двойственности следует, что грань Gk многогранника l l Ph, инцидентная pl, соответствует вершинам qk и fk. Если грани Gm i l l l l и Gk имеют общее ребро, то вершины qm и qk (fm и fk ) следует соединить ребром. Такие рассуждения могут быть применены в том случае, когда границы Fi и Qi являются самопересекающимися замкнутыми ломаными. В этом случае вершину pl можно полагать конической или i острой, поскольку многогранник Ph плохо аппроксимирует параболоид P в окрестности точки pl.
i Локальная полярность и дискретные кривизны. Рассмотрим окрестность невырожденной регулярной точки на двумерной поверхности ПРВ M. В этой точке определен второй дифференциал и невырожденный соприкасающийся параболоид. Можно выбрать декартову систему координат xi так, чтобы поверхность M допускала локальное представление x3 = f(x1, x2), и 2f f(x1, x2) = u(x1, x2) + o(|x|2), hij = (0, 0).
xixj Таким образом, P является соприкасающимся параболоидом в некоторой точке pl поверхности M. Обозначение fl будет использоваться i для функции трех переменных x3 - f(x1, x2). Поверхность M задается равенством fl(xl) = 0. Рассмотрим пару многогранных поверхностей Ph и Ph. Предположим, что локально они приближенно полярны по отношению к P в следующем смысле: пусть T T pl = (o(h2) i + o(h2)), pl = (pT j + u(pj) + o(h2)), (3.1) i j j где |pj| = O(h), j V(Gk), j = i обозначают индексы вершин грани Gk поверхности Ph, инцидентной вершине pl. Параметр h имеет смысл i локальной характерной длины ребер и, одновременно, размера окрестности регулярной точки pl на поверхности M. Плоскости граней Qi, i Qj, полярных pl, pl, соответственно, задаются соотношениями i j x3 + i + o(h2) = 0, x3 + (pl )3 = pT Hx + o(h2). (3.2) j j Соотношения (3.2) справедливы при |x| h, где C0 - некоторая постоянная. На практике матрица H неизвестна, так что для того, чтобы вычислить плоскость, полярную вершине pl, нужно вычислить приj ближенную ортогональную проекцию pl M этой вершины на поверх j ность M, т.е. такую, что существует скалярная величина , удовлетворяющая (pl - pl ) = fl(pl ) + o(h), j j j как показано на рис. 3.3. Здесь fl обозначает односторонний градиент в произвольном направлении. Этот градиент в точке не является единственным, но разность между градиентами в произвольном направлении есть величина порядка o(h).
pil pjl pjl M M j i j ~ ~ pjl pjl ~ pil j j j a i a Рис. 3.3. Вершина и приближенная полярная плоскость.
Плоскость j, полярная точке pl, задается равенством j fl(pl )T (xl - 2pl + pl ) = 0. (3.3) j j j Очевидно, что она удовлетворяет соотношению полярности по отношению к соприкасающемуся параболоиду в точке pl, более того, j удо j влетворяет условиям полярности по отношению к параболоиду P, т.е.
соотношение (3.2) выполнено.
Определение 3.1. Вершина pl многогранной поверхности Ph назыi вается регулярной, если ее двойственная грань Qi и проекция нормального изображения Fi на плоскость Qi являются простыми многоугольниками и содержат внутри себя проекцию точки pl.
i Можно говорить, что регулярная вершина не является конической, поскольку в ней однозначно определена касательная плоскость. То же самое можно утверждать о регулярном ребре, т.е. таком ребре, у которого обе вершины регулярны, и обе инцидентные грани двойственны регулярным вершинам. Регулярное ребро также не является острым, поскольку ему можно приписать касательную плоскость, базис которой образован самим ребром и двойственным ему ребром.
На рис. 3.4 показаны фрагменты триангулированных многогранных поверхностей Ph, вписанных в эллиптический и гиперболический параболоиды, а также их проекции на плоскость x3 = 0. Двойственные многогранные поверхности Ph и их проекции показаны на рис. 3.5. В случае эллиптического параболоида все двойственные грани являются выпуклыми многоугольниками, в то время как в гиперболическом случае Qi является четырехугольником, причем поворот ребер этого четырехугольника со стороны Qi является неположительным.
Рис. 3.4. Триангуляции Рис. 3.5. Двойственные эллиптического и гиперболического многогранные поверхности и их параболоида и их проекции на проекции на плоскость.
горизонтальную плоскость.
Следует заметить, что двойственная многогранная поверхность Ph в случае эллиптического параболоида является в точности женератрисой Вороного [7], и проекция ее граней на горизонтальную плоскость составляет нормальное разбиение на выпуклые многоугольники, являющееся аффинным образом разбиения Вороного, в то время как проекции граней Ph составляют аффинный образ разбиения Делоне [12].
Будем говорить, что форма грани Qi регулярна, если ее двойственная вершина pl является регулярной, и существует триангуляция TiQ i многоугольника Qi, в которой длина L каждого ребра удовлетворяет неравенству Ch L h с некоторой постоянной C > 0, а минимальный угол в триангуляции отделен снизу от нуля постоянной, не зависящей от h. Рассмотрим непрерывное кусочно-аффинное отображение : Qi Fi, которое является линейным на каждом треугольнике из i TiQ. Пусть -A = |T обозначает матрицу Якоби этого отобраim i im жения на треугольнике Tim TiQ.
Теорема 3.2. (О локальной аппроксимации поверхностей ПРВ многогранниками) Рассмотрим окрестность диаметром O(h) регулярной точки c на поверхности ПРВ M. Пусть регулярная вершина pl мноi гогранной поверхности Ph и плоскость двойственной ей грани Qi локально полярны по отношению к соприкасающемуся параболоиду P поверхности M в точке c. Предположим, что регулярные вершины pl, j принадлежащие граням Ph, инцидентным pl локально полярны отноi сительно P граням Qj двойственной поверхности Ph. Предположим, что форма граней Ph, инцидентных pl, и форма грани Qi регулярна.
i Тогда при h A = H + o(1), im где H - это тензор кривизны поверхности M в точке c.
Матрицы A в общем случае не являются симметричными. Так im что для того, чтобы найти приближенные главные кривизны, необходимо использовать сингулярные значения матрицы A, а для вычисim ления приближенных главных направлений необходимо использовать сингулярное разложение (SVD) матрицы A.
im Рис. 3.6. Сферическое изображение и приближенное сферическое отображение двойственных многогранников.
При этом отображение двойственной грани Qi на сферическое изображение вершины pl, которое является простым сферическим многоi угольником, также аппроксимирует точное сферическое отображение поверхности M. Соотношения между сферическим изображением и сферическим отображением локально полярных многогранников показаны на рис. 3.6. В Главе 3 также показано, что если матрица H анизотропна, скажем одно ее собственное значение порядка единицы, а второе сколь угодно мало, то грани многогранных аппроксимантов могут быть вытянуты вдоль направления, соответствующего минимальному собственному значению матрицы H. Параметр h в таком случае есть не что иное, как характерная длина ребер в некоторых УизотропныхФ координатах yi, которые получаются из xi посредством аффинного отображения так, чтобы в координатах yi сингулярная обусловленность тензора кривизны была бы порядка единицы.
Меры кривизны для негладких поверхностей и дискретные кривизны. По аналогии с пропорциональной сходимостью в смысле внутренней геометрии [28], введем понятие внешней или объемлющей пропорциональной сходимости. Будем говорить, что многогранная поверхность Pk сходится к поверхности ПРВ M пропорционально, если существует квазиизометрическое отображение k : R3 R3 такое, что Pk = k(M), (3.4) и постоянные квазиизометрии Lk последовательности отображений k сходятся к 1 при k . Далее, в зависимости от контекста, слова УвнешняяФ или УобъемлющаяФ могут опускаться.
Поскольку пики на поверхности ПРВ невозможны по определению, необходимым условием существования пропорциональной аппроксимации поверхности ПРВ M является отсутствие точек возврата на острых ребрах поверхности.
Определение 3.2. Будем говорить, что окрестность каждой точки p поверхности ПРВ M допускает пропорциональное приближение своим касательным конусом Q в точке p, если для всякого достаточно малого шара B(p) можно определить квазиизометрическое отображение : B(p) R3, которое отображает окрестность B(p) M точки p на окрестность точки p на конусе Q, и постоянная квазиизометрии отображения задается как 1 + (), где () +0 при +0.
Площадь (мера) сферического изображения поверхности ПРВ M является вполне аддитивной функцией борелевских множеств M с ограниченной полной вариацией [1], [2]. Таким образом, для этой меры справедлива теорема Лебега о разложении меры (см., например, [24], [17]) (M) = C(M) + S(M) + D(M), (3.5) где дискретная часть D(M) задана на счетном множестве конических вершин, сингулярная часть S(M) включает в себя площадь сферического изображения острых ребер, а абсолютно непрерывную часть C(M) можно представить как интеграл от измеримой функции - гауссовой кривизны поверхности M.
Согласно классическому определению, сферическое изображение для многогранника сконцентрировано в вершинах [3]. Таким образом, аппроксимация поверхности ПРВ многогранной поверхностью подразумевает аппроксимацию неположительной меры с ограниченной полной вариацией последовательностью дискретных мер. Разумеется, такая аппроксимация возможно только в слабом смысле. Строгие формулировки утверждений о сходимости можно найти в [1], [2], [22]. Основной недостаток подобной слабой сходимости состоит в том, что поточечной сходимости кривизн из нее не следует даже для регулярной поверхности M.
Будем называть поверхность ПРВ M кусочно-регулярной, если:
а) Она склеена из конечного числа элементарных граней Mi. Предполагается, что для каждой грани Mi можно построить локальную сиi i i стему координат y1, y2, y3 такую, что в некоторой выпуклой области i i i i i i i Ci R2 задана функция y3 = ui(y1, y2) = gi(y1, y2) - hi(y1, y2), где gi и hi -выпуклые функции. При этом грань Mi задается как график ui на некоторой односвязной области Ci, которая лежит строго внутри Ci.
б) Граничная кривая Ci - это простая замкнутая кривая c конечной вариацией поворота, склеенная из конечного числа регулярных дуг так, что существует квазиизометрическое отображение qi : Ci Ri, где Ri - некоторый простой многоугольник.
в) Каждая элементарная грань может быть лишь строго выпуклой поверхностью или строго седловой поверхностью с гауссовой кривизной отделенной от нуля, либо разворачиваемой поверхностью, причем предполагается, что соприкасающийся параболоид определен в каждой точке графика функции над Ci.
в) Результатом склейки элементарных граней является поверхность ПРВ, которая допускает пропорциональную аппроксимацию касательными конусами.
Естественная формулировка задачи аппроксимации кусочнорегулярной поверхности должна включать в себя построение последовательности многогранных поверхностей Pk таких, что для каждой из них определена площадь сферического изображения k, причем k(Bk) = Ck(Bk) + Sk(Bk) + Dk(Bk), (3.6) где B M - произвольное борелевское множество, Bk = k(B), а отображение k определено в (3.4). При k + должно быть выполнено Ck(Bk) C(B), Sk(Bk) S(B), Dk(Bk) D(B), Ck(Pk) = Kk d.
Pk (3.7) где Kk имеет смысл гауссовой кривизны многогранной поверхности Pk, и функция Kk сходится к K, как минимум, по мере.
Теорема 3.3. Для двумерной кусочно-регулярной поверхности ПРВ M можно построить последовательность двойственных многогран ных аппроксимантов Pk и Pk, которые сходятся к M пропорционально, причем для каждого из которых можно определить такую площадь сферичеcкого изображения, что для нее справедливо разложение Лебега на абсолютно непрерывную, сингулярную и дискретную компоненту, которые по отдельности сходятся к абсолютно непрерывной, сингулярной и дискретной компоненте площади сферического изображения M.
Практическое применение дискретных кривизн. На рис. 3.показан результат реконструкции дендрита по данным электронной микроскопии, полученным по набору ультратонких срезов, с использованием известной программы Trace (Фиала, Харрис, 2001). Хорошо видны многочисленные топологические и геометрические дефекты.
Рис. 3.7. Рис. 3.8.
Рис. 3.9. Набор Рис. 3.10. Начальная реконструкция и сечений.
последовательное выравнивание сечений.
На рис. 3.8, 3.10 показан результат реконструкции автора, при этом для глобального выравнивания срезов используется метод минимизации некоторой дискретной меры кривизны реконструируемой поверхности.
Результаты данной главы опубликованы в [42], [43].
Глава 4. Вариационные задачи построения квазиизометрических отображений В этой главе описан предложенный автором вариационный принцип для построения квазиизометрических отображений. Для него доказаны теоремы существования с использованием аппарата математической теории упругости с конечными деформациями, разработанного Дж. Боллом [18], [19] (см. также [16]).
Пусть , 1 Rd - ограниченные области с липшицевой границей, такие, что существует квазиизометрическое отображение u0 : 1.
Будем говорить, что функция u(x) : Rd принадлежит допустимому множеству A, если 1,p u(x) W (; Rd), p > d, det(u) - t(u, det(u)) > 0 (4.1) почти всюду в . Здесь : Rdd R R, d/1 (S, ) = tr(STS) + (1 - )(1 + 2), (4.2) d а 0 < 1, 0 < t 1 - некотоpые заданные постоянные. Множество допустимых деформаций дополняется граничными условиями u| = u0|. Сpеди всех отобpажений v A будем искать отображение u(x), доставляющее минимум функционалу Jt(v) f(S) (1 - t), det S - t(S, det S) > 0;
1-tf(S) Jt(v) = ft(v)dx, ft(S) = +, в пpотивном случае;
(4.3) где f(S) = (S, det S)/ det S. Функция f(S) является поливыпуклой, т.е. ее можно записать как выпуклую функцию миноров матрицы S [18].
При этом преобразование f(S) ft(S) сохраняет поливыпуклость.
Теорема 4.1. Пусть и 1 - ограниченные области в Rd с липшицевой гpаницей такие, что существует квазиизометрическое отоб ражение u0 : 1, и для некоторого 0 < t < 1 справедливо Jt(u0) < +. Тогда существует элемент u A такой, что Jt(u) = inf Jt(v), причем u : 1 является квазиизоvA,v|=u0| метрическим отображением.
Из теорем существования И.Я. Бакельмана, М. Бонка и У. Ланга [21], Ю.Д. Бураго [6] в двумерном случае следует существование элемента u0 A, доставляющего конечное значение функционалу Jt при некотором t = t0 > 0, при некоторых дополнительных ограничениях на формы областей и 1.
Функционал для отображения между двумя многообразиями. Пусть y() : Rd - допустимое отображение для функционала ft(y) d. (4.4) Рассмотрим композицию отображений y() = y(x(())), где квазиизометрические отображения y(x) и () заданы, а x() - новая искомая функция вместо y(). Используя обозначения H = , S = x, Q = xy, T = y, J = det T, и правило цепочки, получаем det Q det S T = QSH-1, J =, d = det Hd , det H и функционал (4.4) переписывается в виде ft(QxH-1) det Hd . (4.5) Функция ft(T ) зависит только от ортогональных инвариантов матT рицы T T. Используя равенства T T T = H-T ST GxSH-1, Gx(x) = QT Q, G() = HT H, (4.6) и тот факт, что tr(AB) = tr(BA), получаем, что ft может быть записана через ортогональные инварианты матрицы W = ST GxSG- как (W ) ft(QxH-1) = fe(W ) = (1 - t), (det W ) - t(W ) 1 (W ) = (1 - )( tr(W ))d/2 + (det W + 1), d а Q и H просто задают факторизацию матриц Gx и G согласно (4.6). Таким образом, можно полагать, что минимизирующее отображение для функционала (4.5) есть не что иное, как отображение между областями на многообразиях M и Mx с внутренней метрикой, длина кривых на которых задается линейными элементами с матрицами G и Gx, соответственно. При этом предполагается, что области на этих многообразиях допускают квазиизометрические параметризации () и y(x), соответственно, хотя бы со сколь угодно большими константами квазиизометрии. В данной главе показано, что Теорема 4.1 о существования минимизирующего квазиизометрического отображений может быть обобщена и на случай многообразий с метриками, при условии, что Gx(x) - непрерывная функция в Rd. Более того, справедливы несколько более слабые варианты теорем существования для случая, когда условие совпадения с заданным гомеоморфизмом задается только на (возможно пустой) части границы, а оставшаяся граница является свободной и находится в процессе минимизации. При этом справедливы результаты об обратимости минимизирующего отображения почти всюду, аналогичные [16]. Результаты данной главы опубликованы в [32], [39], [34].
Глава 5. Поливыпуклость и симметризация уравнений теории упругости В данной главе показано, что строгая поливыпуклость, т.е. возможность записи внутренней энергии упругого материала как строго выпуклой функции миноров матрицы Якоби упругой деформации достаточна для того, чтобы нестационарные уравнения теории термоупругости с конечными деформациями допускали каноническую термодинамически согласованную симметризованную запись С.К. Годунова [8], удовлетворяющую условиям гиперболичности по Фридрихсу. При этом естественно получается набор прямых и двойственных переменных для построения энтропийных решений в задачах ударных деформаций материалов.
Ниже при записи уравнений используется соглашение о суммировании по повторяющимся индексам, а использование переменной в качестве нижнего индекса означает дифференцирование по этой переменной.
Каноническая форма записи систем гиперболических уравнений и энтропийные решения. Рассмотрим нестационарную систему дифференциальных уравнений первого порядка j y F (y) + = 0, (5.1) t j j где yT = (y1... yd), yi = yi(1, 2, 3, t), F : Rd Rd.
Говорят, что у системы уравнений (5.1) существует энтропийная пара (см, например, [14]), если можно найти выпуклую функцию : Rd (F )l Qj j R и функции Qj : Rd R, j = 1, 2, 3 такие, что =.
yk yk yl Энтропийным решением системы уравнений (5.1) называют функцию y(, t), для которой выполнено дифференциальное неравенство (y) Qj(y) + 0. (5.2) t j Решение системы (5.1), для которого (5.2) является равенством, называется изэнтропическим решением. Очевидно, что любое гладкое решение (5.1) является изэнтропическим.
В работах С.К. Годунова [8] (см. также [10], [15], [11]) был предложен способ выбора вектора переменных q(y) и специальных потенциалов L(q), Lj(q), с использованием которых многие системы уравнений математической физики можно привести к специальному каноническому виду, который записан ниже в несколько более общем виде по сравнению с [8]. Будем требовать, чтобы функция L(q) была строго выпуклой с положительно определенной матрицей Гессе, а потенциалы Lj допускали бы следующее представление k Lj(q) = Lj (q) + vj (q)k(q), (5.3) k где для k = 1,..., K функции vj составляют бездивергентное векторk vj ное поле vk, для которого справедлив закон сохранения = 0. Обоj значим через Lj следующую неполную производную Lj по q q k Lj = Lj + vj kq. (5.4) q q В качестве обобщенной канонической системы возьмем систему уравнений Lj Lq q + = 0, (5.5) t j которая дополняется энтропийным неравенством (qT Lj - Lj) (qT Lq - L) q + 0, (5.6) t j переходящим в равенство на гладких решениях. При этом дополнительk vj ный закон сохранения = 0 в момент времени t следует из (5.5), при j условии, что он был выполнен при t = 0. Очевидно, что недивергентное представление для системы (5.5) выглядит как qm qm Lq qm + Lj = 0, (5.7) k qkqm t j где неполные производные Lj являются симметрическими, поскольqkqm ку l Lj = Lj + vjlq qm.
qkqm qkqm k Система уравнений (5.7) является симметрической и гиперболической по Фридрихсу, поскольку матрица Lq qm является симметрической и k положительно определенной, а матрицы Lj являются симметричеqkqm скими.
Расширенная запись трехмерных уравнений нелинейной теории упругости в лагранжевых координатах. Пусть полная энергия E = 0 uiui + (C, w, A, S) - это строго выпуклая функция 3 + 9 + 1 + 9 + 1 = 23 переменных u, C, w, A, S с положительно определенной матрицей Гессе, где u(, t) -вектор скоростей, C - матрица Якоби упругой деформации x(, t), i - лагранжевы координаты, а xi - эйлеровы координаты материальной точки, w = det C, A = cof C, S энтропия, 0 - постоянная начальная плотность, а - строго поливыпуклый упругий потенциал. Уравнения теории упругости записываются так:
0ui - (c +aijw+dkmija ) = ij km t j w - aijui = 0 (5.8) t j cij ui - = t j akm - (uidkmij) = 0 (5.9) t j uiui (0 + ) - ui(c +aijw+dkmija ) = 0.
ij km t 2 j akm Здесь dkmij =. Из этой системы вытекают следующие равенства cij aij = 0, dkmij = 0, (5.10) j j т.е. поля aij и dkmij бездивергентны, если они таковы при t = 0.
Приведение уравнений теории упругости в лагранжевых координатах к каноническому виду. Если ES > 0, то можно выразить -S как строго выпуклую функцию 23 аргументов i = 0ui, cij, w, aij, E, которые составляют вектор первичных переменных y R23. При этом порождающий потенциал L строится как преобразование Лежандра выпуклой функции -S(y), т.е. L(q) = (-S) или L = iu + cijc +ww+aija + EE + S.
i ij ij Двойственные переменные q, которые ниже помечаются верхним индексом , задаются как обычно при преобразовании Лежандра посредством q = (-S)y, в то время как первичные переменные выражаются через двойственные симметричным образом: y = Lq. При этом порождающие потенциалы Lj задаются следующим образом u i Lj = (c +aijw+dkmija ).
km E ij В результате уравнения теории упругости приводятся к искомому каноническому виду (5.5). Поскольку преобразование Лежандра сохраняет выпуклость, функция L(q) является строго выпуклой, так что выполнены условия гиперболичности по Фридрихсу. Дополнительное соотношение (5.6) оказывается ни чем иным, как условием неубывания энтропии S 0. Если упругий потенциал не зависит явно от A = cof C, то t зависимость от A можно выбросить, как и дополнительное уравнение (5.9) для A.
Симметризация в эйлеровых координатах. Рассмотрим систему уравнений термоупругости в эйлеровых координатах в переменных fi = ui, , rij = cij, bij, E, где - плотность, E - полная энергия, B = C-1, а упругая деформация ищется в виде (x1, x2, x3, t) fi + ( fifk - ik) = t xk + (fk) = t xk rij + (ukrij - uirkj) = t xk bij + (ulbil) = t xj (E) + (ukE - uiik) = 0.
t xk Эта система уравнений дополняется условием неубывания энтропии (S) + (Suk) 0, t xk которое становится равенством на гладких решениях. Полная энергия E в единичном эйлеровом объеме задается как 1 fifi 1 1 1 S E = (R, , B, S) +, (R, , B, S) = ( R,, B, ).
2 Здесь S = S - энтропия в единице эйлерового объема. Поскольку E - строго выпуклая функция rij, , bij, fi, S, и ES > 0, то функцию -S можно выразить как строго выпуклую функцию rij, , bij, fi, E. Тензор упругих напряжений задается соотношениями alm ik = ckj(c +V (cof C)ij+a ) = -ik2+rkjr +zkipmb, ij lm ij mp cij где apm zkipm = ckjdpmij = ckj.
cij В качестве порождающего потенциала L будем использовать преоб разование Лежандра функции -S по переменным , rij, bij, fi, E :
L = + rijrij + bijb + fifi + EE + S, (5.11) ij а потенциалы Lk задаются следующим образом Lk = (-fk L + fi rkjrij+fizkipmb ), (5.12) mp E где rkj и zkipm играют роль бездивергентных векторных полей в силу равенств rkj zkipm = 0, = 0. (5.13) xk xk Поскольку порождающий потенциал L является строго выпуклым, полученная система уравнений гиперболична по Фридрихсу.
Квазиизометрическая регуляризация упругих потенциалов.
Вновь рассмотрим формулировку в лагранжевых координатах. Симметрическая матрица E, которая задается в виде E = (CT C - I) (5.14) называется тензором деформации Грина - Сен-Венана. Как известно [16], если упругий потенциал (C) изотропного материала есть гладкая функция ортогональных инвариантов матрицы CT C, и достигает абсолютного минимума при C = U, где U - ортогональная матрица с положительным детерминантом, то в случае малых деформаций справедливо следующее представление (закон Гука) (C) = (I) + (tr E)2 + tr E2 + o(||E||2). (5.15) Величины и называются постоянными Ламе упругого материала.
Рассмотрим следующую квазиизометрическую регуляризацию упругого потенциала :
( - 1)2 (I)(C) (C) =, 1 < +, (5.16) (I) - (C) которая аналогична (4.3). Преобразование (5.16) сохраняет поливыпуклость и не изменяет постоянных Ламе. Более того, его использование для достаточно широкого класса упругих потенциалов позволяет доказать аналог Теоремы 4.1 о том, что упругая деформация существует и является квазиизометрическим отображением. При этом нет необходимости требовать, чтобы для (C) выполнялись весьма жесткие условия роста [19], гарантирующие обратимость упругих деформаций в классе соболевских отображений. Известно, что для реальных материалов условия роста [19] не выполняются. Регуляризация (5.16) выражает тот очевидный факт, что cингулярным решениям не могут соответствовать никакие реальные упругие деформации, поскольку в случае достаточно больших деформаций и напряжений необходимо учитывать другие физические эффекты, в первую очередь пластичность и разрушение материала. Можно сделать вывод, что собственно к теории упругости следует относить исследование квазиизометрических упругих деформаций. При этом допустимые константы квазиизометрии (параметр ) можно выбирать настолько большими, чтобы влияние регуляризации было бы пренебрежимо мало по сравнению с другими физическими эффектами. Результаты данной главы опубликованы в [35].
Глава 6. Дискретные меры искажения и квазиоптимальные расчетные сетки Дискретизация мер искажения. Рассмотрим отображение x() из параметрической области Rd на расчетную область. Предположим, что область такова, что допускает пропорциональное приближение последовательностью областей h с многогранной границей.
Будем требовать, в частности, чтобы поверхность была поверхностью ПРВ, допускающей пропорциональное приближение касательными конусами. Предположим, что область h, в свою очередь, такова, что для нее существует нормальное разбиение, состоящее из канонических ячеек Ck. Примеры канонических ячеек - это равносторонние треугольники, квадраты, правильные симплексы, кубы и т.д. В общем случае результатом склейки канонических ячеек будет уже не область в Rd, а полиэдральное многообразие с внутренней метрикой. В этом случае можно полагать, что в области h Rd задана полиэдральная метрика посредством линейного элемента с кусочно-постоянным метрическим тензором.
Для получения конечномерной задачи минимизации естественно приближать искомое отображение x() непрерывным кусочно-гладким отображением xh(), доставляющим конечное значение минимизируемому функционалу, или, другими словами, принадлежащим допустимому множеству. При этом значение функционала (мера искажения отображения xh()) записывается как Jt(xh()) = ft(xh()) d.
Ck Ck Если все канонические ячейки Ck являются симплексами, то отображение xh() на каждом таком элементе можно положить аффинным, а матрицу Якоби - постоянной, что приводит к следующему выражению для дискретного функционала h Jt (xh()) = ft(xh())|C vol(Ck). (6.1) k k h Величину Jt (xh()) естественно называть дискретной мерой искажения отображения xh(), причем для кусочно-аффинного отображения xh() h справедливо равенство Jt (xh()) = Jt(xh()).
Когда локальное отображение не является аффинным, для получения дискретной меры искажения необходимо использовать квадратурные формулы. Для некоторого класса кусочно-полиномиальных отображений предложены геометрические квадратуры, которые гарантируют выполнение неравенства h Jt(xh()) Jt (xh()). (6.2) Поскольку в алгоритме минимизации, предложенном в работе, гарантиh руется ограниченность величины Jt (xh()), получаем, что отображение xh() принадлежит допустимому множеству исходного квазиизометрического функционала, а значит, является гомеоморфизмом, и остается квазиизометрическим в пределе измельчения сеток. Последнее свойство является обобщением принципа барьерности для сеточных функционалов, предложенного в [13]. Квадратуры основаны для следующем принципе максимума для поливыпуклых мер искажения.
Теорема 6.1. Пусть S1,..., Sm - набор из d d матриц, функция f(S) поливыпукла, а U Rd - выпуклая область. Предположим, что матрица Якоби гладкого d-мерного отображения x() : Rd задается равенством m k x() = S = Sjj(), j = I, j 0, (6.3) j=1 j= где j() C() - диагональные матрицы. Пусть S, = 1,..., md - УсоставнаяФ матрица размера d d, k -й столбец которой может быть выбран как k -й столбец любой из базисных матриц Si. Предпо ложим, что неравенство f(S) C, C > 0 справедливо для всех .
Тогда а) f(S) C ; б) можно найти набор коэффициентов md a() 0, a = 1 такой, что =md md S() = a()S, f(x) a()f(S). (6.4) =1 =Заметим, что если в качестве поливыпуклой функции взять ft(S) из (4.3), то можно доказать также взаимнооднозначность отображения x(). Итак, пусть матрица Якоби отображения xh() : Rd ло m кально задается как xh = Sii(), где U - это каноническая i=параметрическая ячейка, которая на практике, как правило, является правильным или полуправильным многогранником. Для построения дискретной меры искажения образа ячейки U предлагается использовать следующую квадратурную формулу:
Nq ft(xh) d qft(Sq) vol(U), q = aq d, Nq = md, vol(U) q=U U (6.5) а aq - это в точности набор коэффициентов из Теоремы 6.1. Искомое неравенство (6.2) непосредственно следует из неравенства (6.4). Полученные геометрические квадратуры точны для постоянных функций и для детерминанта матрицы Якоби, а если каноническая область U и локальное отображение обладают центральной симметрией, то квадратуры точны на линейных функциях. Принцип максимума и критерий обратимости применимы к билинейным четырехугольным ячейкам, трилинейным шестигранникам, к пирамидам и призмам, к квадратичным треугольным и тетраэдральным изопараметрическим конечным элементам, а также к полиномам Бернштейна-Безье произвольного порядка на кубах и симплексах. Заметим, что на практике иногда можно использовать более простые квадратуры, которые можно интерпретировать как приближение несимплициальных ячеек симплициальными разбиениями. В общем случае такой подход не гарантирует справедливости мажорирующей оценки (6.2), но может успешно применяться для решения практических задач.
Рис. 6.1. Гармоническая сетка ([26], Рис. 6.2. Квазиизометрическая [13]). сетка с заданным сгущением.
Примеры квазиоптимальных сеток. Ниже приводится численный пример, который показывает, насколько близки константы искажения в предложенном методе к оптимальным значениям. Рассматривается численное построение отображение прямоугольника на область с изломами (тестовая задача С.К. Годунова, рис. 6.1, 6.2).
В таблице показана постоянная квазиизометрии Lc отображения в зависимости от подробности сетки число вершин 11 11 21 21 41 41 81 Lc 4.46 2.81 2.71 2.Lc|гармонич. 16.2 31.6 52.1 75.Достаточно грубые оценки константы квазиизометрии показывают, что в этой задаче она не может быть меньше чем 2.4, таким образом отличие полученного значения от оптимального заведомо не превышает 10 - 15%. В следующем примере иллюстрируется работа алгоритма распутывания и оптимизации сетки из шестигранных ячеек. Расчетная область является кубом, внутрь которого помещен жесткий куб меньшего размера. Затем внутренний куб поворачивается на угол вокруг вертикальной оси, как показано на рис. 6.3.
Результат работы алгоритма распутывания и оптимизации показан на рис. 6.4. Как и следовало ожидать, в полученной сетке есть очень сильно искаженные шестигранники. Тем не менее трилинейное отображение для каждой ячейки сетки является обратимым. Результаты данной главы опубликованы в работах [29], [30], [36], [37], [40].
Рис. 6.3. Повернутый внутренний Рис. 6.4. Оптимизированная сетка.
куб и УспутаннаяФ начальная сетка.
Глава 7. Параметризация поверхностей и построение квазиоптимальных поверхностных сеток В Главе 7 показано, как применить описанный выше вариационный метод для решения задачи распластывания поверхностей с минимальным искажением, а также для автоматического построения квазиоптимальных сеток на поверхностях сложной формы.
На рис. 7.1 показаны многогранные тестовые поверхности и результаты их распластывания. Величина L при этом обозначает оценку постоянной квазиизометрии, предложенную во второй главе, а Lc обозначает реально полученную величину этой постоянной. В следующем примере на рис. 7.2 демонстрируется зависимость распластывания от формы и размера треугольников поверхностной сетки. Рассматривается триангуляция плохого качества, а также последовательность триангуляций, состоящих из почти равносторонних треугольников практически одинакового размера, от 2526 до 150471 треугольников.
L 1.367, Lc 1.42 L 1.65, Lc 1.41 L 2.8, Lc 2.1Рис. 7.1. Оценки искажения при распластывании многогранных поверхностей.
Рис. 7.2. Различные триангуляции тестовой поверхности.
На рис. 7.3 а) показаны проекции тестовой поверхности на плоскость для плохой триангуляции, для одной из высококачественных триангуляций, а также последовательность граничных кривых для плоских проекций всех сеток, полученные с помощью квазиизометрического метода.
На рис. 7.3 б) для сравнения приведены результаты метода, в котором отображение поверхности на плоскость является аппроксимацией отображения, обратного к гармоническому.
Можно сделать вывод, что несмотря на один и тот же метод дискретизации, квазиизометрический метод существенно слабее зависит от качества и подробности сеток по сравнению с известными методами.
а) б) Рис. 7.3. Распластанные поверхности: а) квазиизометрический функционал, б) гармонический функционал.
Рис. 7.4. Распластывание и параметризация для задач штамповки.
В примере, показанном на рис. 7.4, триангулированная поверхность моделирует автомобильную деталь. Для так называемого обратного метода моделирования процесса штамповки необходимо построить проекцию этой поверхности на плоскость с наименьшим искажением. Эта же проекция может быть использована как способ параметризации поверхности, а значит, и как способ перестроения поверхностной сетки.
В данном примере треугольная сетка на плоскости перестраивается в четырехугольную при помощи алгоритма QMV, разработанного А.В.
Сковпенем, а затем отображается обратно на поверхность. Результаты этой главы опубликованы в [38], [31], [41].
Работа выполнена при поддержке Совета по грантам Президента Российской Федерации (проект НШ-4096.2010.1), ФЦП Научные и научно-педагогические кадры инновационной России на 2009-2013 гг.
(гос. контракт № П2224), и РФФИ (гранта 09-01-12106-офи_м).
ИТЕРАТУРА [1] Александров А.Д. Внутренняя геометрия выпуклых поверхностей.
М.-Л.: Гостехиздат, 1948.
[2] Александров А.Д. О поверхностях, представимых разностью выпуклых функций // Изв. АН Казах. ССР, серия матем. и механ. 1949.
Вып. 3. С.3-20.
[3] Александров А.Д. Выпуклые многогранники. Москва, Ленинград:
Государственное издательство технико-теоретической литературы, 1950.
[4] Александров А.Д., Залгаллер В.А. Двумерные многообразия ограниченной кривизны (основы внутренней геометрии поверхностей).
Тр. Матем. ин-та им. В. А. Стеклова. 1962. Т.63.
[5] Бакельман И.Я., Вернер А.Л., Кантор Б.Е. Введение в дифференциальную геометрию Ув целомФ. М.: Наука, 1973.
[6] Бураго Ю.Д. Билипшицево эквивалентные поверхности Александрова, II // Алгебра и Анализ. 2004. Т.16. Вып.6. С.28-52.
[7] Вороной Г.Ф. Исследования о примитивных параллелоэдрах // Собр. соч. Т.2. Киев: Изд-во АН УССР, 1952. С.239-368.
[8] Годунов С.К. Интересный класс квазилинейных систем // ДАН СССР. 1961. Т.139. №3. C.520-523.
[9] Годунов С.К., Гордиенко В.М., Чумаков Г.А. Квазиизометрическая параметризация криволинейного четырехугольника и метрика постоянной кривизны // Труды Института математики СО РАН. 1994.
Т.26. С.3-19.
[10] Годунов С.К., Роменский Е.И. Элементы механики сплошных сред и законы сохранения. Новосибирск: Научная книга, 1998.
[11] Годунов С.К., Пешков И.М. Симметрические гиперболические уравнения нелинейной теории упругости // Ж. вычисл. матем. и матем.
физ. 2008. Т.48. №6. C.1034-1055.
[12] Делоне Б.Н. О пустоте сферы // Изв. АН СССР. 1934. №4. С.793800.
[13] Иваненко С.А., Чарахчьян А.А. Криволинейные сетки из выпуклых четырехугольников // Ж. вычисл. матем. и матем. физ. 1988. Т.28.
№4. С.503-514.
[14] Кружков С.Н. Квазилинейные уравнения первого порядка со многими независимыми переменными // Матем. сборник. 1970. Т.81.
№2. С.228-255.
[15] Роменский Е.И. Законы сохранения и симметричная запись уравнений теории упругости // Тр. семинара им. С.Л. Соболева. 1984.
Т.1. С.132-143.
[16] Сьярле Ф. Математическая теория упругости. М.: Мир, 1992.
[17] Шилов Г. Е., Гуревич Б. Л. Интеграл, мера и производная. М.: Наука, 1967.
[18] Ball J.M. Convexity conditions and existence theorems in nonlinear elasticity // Arch. Rat. Mech. Analys. 1977. V.63. P.337-403.
[19] Ball J.M. Global invertibility of Sobolev functions and the interpenetration of matter // Proc. Roy. Soc. of Edinburgh. 1981.
V.88A. P.315-328.
[20] Ball J.M. Singularities and computation of minimizers for variational problems. In: Foundations of Computational Mathematics, R. DeVore, A. Iserles and E. Suli, eds., London Math. Society Lecture Note Series.
Cambridge University Press, 2001. V.284. P.1-20.
[21] Bonk M., Lang U. Bi-Lipschitz parameterization of surfaces // Mathematische Annalen. 2003. V.327. N.1. P. 135-169.
[22] Cohen-Steiner D., J.-M. Morvan J.-M. Restricted delaunay triangulations and normal cycle. Proc. 19th Annual ACM Symp.
on Comput. Geometry, 2003. P.237-246.
[23] Edelsbrunner H. Geometry and Topology for Mesh Generation.
Cambridge monographs on Applied and Computational Mathematics.
2001. Vol. 6. New York: Cambridge Univ. Press.
[24] Evans L.C., Gariepy R.F. Measure theory and fine properties of functions. CRC Press, 1992.
[25] Hartman P. On functions representable as a difference of convex functions // Pacific J. Math. 1959. V. 9. №3. P.707-713.
[26] Liseikin V.D. Grid generation methods. 2nd Ed. Berlin, Heidelberg, New York: Springer-Verlag, 2010.
[27] Qin T. Symmetrizing nonlinear elastodynamic system // Journal of Elasticity. 1998. V.50. P.245-252.
[28] Reshetnyak Yu.G. Two-Dimensional Manifolds of Bounded Curvature.
In Geometry IV (Non-regular Riemannian Geometry) Reshetnyak Yu.(ed). 1991. Berlin: Springer Verlag. P.3-165.
Работы автора по теме диссертации.
[29] Гаранжа В.А., Капорин И.Е. Регуляризация барьерного вариационного метода построения расчетных сеток // Ж. вычисл. матем. и матем. физ. 1999. Т.39. №9. С.1489-1503.
[30] Гаранжа В.А. Барьерный метод построения квазиизометрических сеток // Ж. вычисл. матем. и матем. физ. 2000. Т.40. №11. С.16851705.
[31] Гаранжа В.А. Управление метрическими свойствами пространственных отображений // Ж. вычисл. матем. и матем. физ. 2003.
Т.43. №6. С.818-829.
[32] Гаранжа В.А., Замарашкин Н.Л. Пространственные квазиизометричные отображения как решения задачи минимизации поливыпуклого функционала // Ж. вычисл. матем. и матем. физ. 2003. Т.43.
№3. С.854-865.
[33] Гаранжа В.А., Капорин И.Е. О сходимости градиентного метода минимизации функционалов теории упругости с конечными деформациями и барьерных сеточных функционалов // Ж. вычисл. матем.
и матем. физ. 2005. Т.45. №8. С.1450-1465.
[34] Гаранжа В.А. Теоремы существования и обратимости для вариационного построения квазиизометричных отображений со свободными границами // Ж. вычисл. матем. и матем. физ. 2005. Т.45. №3.
С.484-494.
[35] Гаранжа В.А. Поливыпуклые потенциалы, обратимые деформации и термодинамически согласованная запись уравнений нелинейной теории упругости // Ж. вычисл. матем. и матем. физ. 2010. Т.50.
№9. C.1-29.
[36] Garanzha V.A. Barrier variational generation of quasi-isometric grids // Num. Linear Algebra Appl. 2001. V.8. №5. P.329Ц353.
[37] Branets L.V., Garanzha V.A. Distortion measure for trilinear mapping.
Application to 3-D grid generation // Num. Linear Algebra Appl. 2002.
V.9. №6-7. P.511-526.
[38] Garanzha V.A. Maximum norm optimization of quasi-isometric mappings // Num. Linear Algebra Appl. 2002. V.9. №6-7. P.493Ц510.
[39] Garanzha V.A. Variational principles in grid generation and geometric modeling: theoretical justifications and open problems // Num. Linear Algebra Appl. 2004. V.11. №5-6. P. 535-563.
[40] Garanzha V.A., Kaporin I.E., Konshin I.N. Truncated Newton type solver with application to grid untangling problem // Num. Linear Algebra Appl. 2004. V.11. №5-6. P.525-533.
[41] Garanzha V.A. Quasi-isometric surface parameterization // Appl. Num.
Math. 2005. V.55. №3. P.295-311.
[42] Garanzha V.A. Approximation of the curvature of Alexandrov surfaces using dual polyhedra // Rus. J. Numer. Analys. Modeling. 2009. V.24.
№5. P.409-423.
[43] Garanzha V.A. Discrete extrinsic curvatures and approximation of surfaces by polar polyhedra // Ж. вычисл. матем. и матем. физ. 2010.
Т.50. №1. С.71-98.