Содержание к диссертации
Введение
Глава 1. Измельчение триангуляции вблизи границы области и аппроксимация функций с особенностью 14
1.1. Измельчение триангуляции вблизи границы 14
1.2. Описание измельчения триангуляции с помощью таблиц инци-денций
1.3. Отображение триангуляции на криволинейную границу . 35
1.4. Об аппроксимации функций с особенностью на границе . 39
Глава 2. Симплициальное подразделение области с измельчением симплексов к границе области; аппроксимация функций с особенностью 45
2.1. Симплициальное подразделение полосы в пространстве R3 с измельчением симплексов 46
2.2. Второй способ симплициального подразделения полосы 76
2.3. Третий способ подразделения полосы 81
2.4. Измельчение симплициального подразделения полосы в двугранном угле 87
2.5. Другие варианты измельчения в двугранном угле 93
2.6. Алгоритм измельчения симплициального подразделения полосы в трехгранном угле 101
2.7. О курантовской аппроксимации функций с вырождением на границе 106
Глава 3. Адаптивные сплайн-вэйвлетные разложения двумерных потоков числовой информации 112
3.1. Локальное укрупнение триангуляции 112
3.2. О барицентрических звездах исходной триангуляции 116
3.3. Структура барицентрических звезд укрупненной триангуляции 117
3.4. Калибровочные соотношения для функций Куранта 119
3.5. Биортогональная система и ее значения на базисных функциях объемлющего пространства 124
3.6. Общая структура вэйвлетного разложения 126
3.7. Вэйвлетное разложение при укрупнении триангуляции 130
3.8. О вэйвлетных разложениях при измельчении триангуляции 132
Заключение 138
Литература 140
Приложение А. Программная реализация симплициального подразделения полосы в пространстве R3 с измельчением симплексов 149
- Описание измельчения триангуляции с помощью таблиц инци-денций
- Об аппроксимации функций с особенностью на границе
- Второй способ симплициального подразделения полосы
- О барицентрических звездах исходной триангуляции
Введение к работе
Актуальность работы. Решение задач в гидродинамике, электродинамике, газовой динамике, теории упругости (в частности, прогнозирование климата, ураганов, цунами и т.д.) сводится к получению численных данных, задающих коэффициенты соответствующих начально-краевых задач, и к решению этих задач численными методами, а именно, методами сеток, методами конечных элементов и методами Ритца-Галеркина.
Поскольку сложные задачи часто характеризуются функциями с нерегулярным поведением (например, неограниченным ростом функций или их производных вблизи границы рассматриваемой области или переходами от медленного изменения к быстрому), то возникает задача построения аппроксимаций этих функций, учитывающих их нерегулярное поведение. Сплайновые и конечно-элементные аппроксимации представляют собой линейную комбинацию большого числа базисных функций с малым носителем; базисные функции строятся стандартным способом и определяются сеткой узлов в некоторой области евклидова пространства, а коэффициенты линейной комбинации рассматриваются как числовой поток, подлежащий обработке. Для экономного использования ресурсов вычислительной системы прибегают к вэйвлетному разложению упомянутого исходного потока на основной поток и уточняющие (вэйвлетные) потоки. В классической теории вэйвлетов рассматриваются ортогональные вэйвлетные (всплесковые) разложения (в пространстве L2), связанные с равномерной сеткой, что позволяет эффективно использовать непрерывное и дискретное преобразования Фурье. При аппроксимации функций с особенностями естественно применение неравномерной сетки, сгущающейся вблизи особенностей; в этом случае применение преобразования Фурье для всплесковых разложений затруднительно. Для неравномерной сетки развит существенно иной подход — построение вложенных пространств и оператора проектирования на основе аппроксимационных соотношений. Построению вложенных пространств сплайнов предшествует построение вложенных адаптивных сеток. Для одномерного случая рассматриваемое множество сеток должно обладать свойством локальной квазиравномерности, а в случае многих измерений требуется топологическая правильность соответствующего симплициального подразделения и равномерная ограниченность (снизу) углов между соседними ребрами каждого симплекса этого подразделения. Вопросам построения сеток посвящены известные работы Л.А.Оганесяна, С.Г.Михлина, Ю.К.Демьяновича, В.Г.Корнеева, Иезерентанта и др. Для адаптивности вэйвлетного разложения (для учета свойств аппроксимируемой функции при аппроксимации) важно локальное укрупнение или измельчение подразделения в зависимости от
локальных свойств упомянутой функции. В частности, для выделения основного потока при вэйвлетном разложении возникает задача локального укрупнения уже имеющегося симплициального подразделения; в многомерном случае такое укрупнение с сохранением топологической правильности не всегда возможно, так что возникает задача построения подразделений, допускающих упомянутое укрупнение. Неограниченное измельчение симплициального подразделения важно для аппроксимации функций с особенностями, а на основе таких подразделений получаются весовые оценки аппроксимации. Цель диссертационной работы.
Разработка методов измельчения триангуляции пограничной полосы вблизи границы двумерной области с сохранением свойства невырожденности.
Разработка способов построения невырожденного симплициального подразделения, измельчающегося вблизи границы трехмерной области.
Получение весовых оценок аппроксимации для функций с особенностью.
Построение адаптивных вэйвлетных разложений курантовских пространств на локально укрупняющихся сетках, получение формул декомпозиции и реконструкции.
Методы исследования. В диссертации используются методы линейной алгебры, дифференциальной геометрии и функционального анализа. Для построений вэйвлет-раз-ложений применён метод аппроксимационных соотношений.
Научная новизна. Все основные результаты работы являются новыми.
Теоретическая и практическая значимость. Работа носит теоретический характер, а также представляет практический интерес. Алгоритмы построения симплициального подразделения в двумерном и трёхмерном случаях могут быть применены в практических задачах, решаемых методом конечных элементов, где искомая функция решения или ее производные неограниченно растут при приближении к границе. Предложенные методы обеспечивают построение невырожденных сеток, аппроксимацию функций с вырождением и вэйвлетное разложение. Результаты работы могут быть использованы при решении различных прикладных задач при сжатии и последующем восстановлении с заданной точностью больших потоков информации (цифровых сигналов) с резко меняющимися характеристиками, а также при построении параллельных форм алгоритмов упомянутых задач.
Результаты, выносимые на защиту.
Методы измельчения триангуляции пограничной полосы вблизи границы двумер
ной области с сохранением свойства невырожденности.
Способы построения невырожденного симплициального подразделения, неограниченно измельчающегося вблизи границы трехмерной области.
Весовые оценки аппроксимации для функций с особенностью.
Адаптивные вэйвлетные разложения курантовских пространств на локально укрупняющихся сетках, формулы декомпозиции и реконструкции.
Апробация работы. По результатам работы были сделаны доклады на XXXIX, XL международных научных конференциях "Процессы управления и устойчивость" 2008 г., 2009 г. [1, 2] и на 2-ой межвузовской научной конференции по проблемам информатики "СПИСОК-20П" (27-29 апреля, 2011 г.).
Публикации. Основные результаты опубликованы в 8 работах, из них 4 статьи (см. [А1-А4]) опубликованы в журналах, рекомендованных ВАК.
Личный вклад автора. В совместных работах [3, 4], [А1, А2, А4] научному руководителю принадлежит общая постановка задачи и указание на идею исследования, а детальная реализация идеи принадлежит диссертанту.
Структура и объем диссертации. Работа объемом 163 страницы состоит из введения, трех глав, разбитых на девятнадцать параграфов, заключения, списка литературы, одного приложения и 19 рисунков. Внутри каждой главы своя нумерация параграфов.
Описание измельчения триангуляции с помощью таблиц инци-денций
Решение задач в гидродинамике, электродинамике, газовой динамике, теории упругости (в частности, прогнозирование климата, ураганов, цунами и т.д.) сводится к получению численных данных, задающих коэффициенты соответствующих начально-краевых задач, и к решению этих задач численными методами, а именно, методами сеток [1, 10, 12, 27, 36, 40, 50, 53], методами конечных элементов и методами Ритца-Галеркина [25, 28, 42, 43, 48, 49, 63, 67, 79].
Поскольку сложные задачи часто характеризуются функциями с нерегулярным поведением (например, неограниченным ростом функций или их производных вблизи границы рассматриваемой области или переходами от медленного изменения к быстрому), то возникает задача построения аппроксимаций этих функций, учитывающих их нерегулярное поведение. Сплай-новые и конечно-элементные аппроксимации представляют собой линейную комбинацию большого числа базисных функций с малым носителем; базисные функции строятся стандартным способом и определяются сеткой узлов в некоторой области евклидова пространства, а коэффициенты линейной комбинации рассматриваются как числовой поток, подлежащий обработке. Для экономного использования ресурсов вычислительной системы прибегают к шйвлетному разложению упомянутого исходного потока на основной поток и уточняющие (вэйвлетные) потоки [13, 24, 33, 39, 51, 75-77]. Как правило, основной информационный поток значительно менее плотный, чем исходный поток информации, поэтому его можно передать быстро. Уточняющий ин формационный поток (его иногда называют вэйвлетным потоком) не во всех случаях необходим, его можно передавать фрагментарно, в зависимости от потребностей. Наконец, поток с несущественной информацией вообще может быть отброшен, тогда исходный поток должен однозначно восстанавливаться по основному и вэйвлетному потокам. Естественный вопрос о разделении информации на основную, уточняющую и несущественную части выходит за рамки математических исследований и должен решаться в каждом отдельном случае специалистом данной предметной области. В классической теории вэйвлетов рассматриваются ортогональные вэйвлетные (всплес-ковые) разложения (в пространстве I ), связанные с равномерной сеткой, что позволяет эффективно использовать непрерывное и дискретное преобразования Фурье ( см. [32] и имеющуюся там библиографию). При аппроксимации функций с особенностями естественно применение неравномерной сеткп, сгущающейся вблизи особенностей; в этом случае применение преобразования Фурье для всплесковых разложений затруднительно. Для неравномерной сетки развит существенно иной подход — построение вложенных пространств и оператора проектирования на основе аппроксимационных соотношений [18,19, 54, 55, 64, 65]. Большой вклад в развитие теории всплесков внесли учёные: И. Добеши, И. Мейер, С. Малла, Г. Стренг, Ж. Баттле,,П. Ж. Лемарье, Ч. Чуй, Р. Койфман, В. Свелденс, С. Б. Стечкпн, В. А. Рвачев, И. Я. Новиков, В. Н. Малозёмов, А. П. Петухов, М. А. Скопина, Е. Е. Тыртышни-ков, Ю. К. Демьянович, И. В. Оселедс, В. А. Жёлудев и др. Построению вложенных пространств сплайнов предшествует построение вложенных адаптивных сеток. Для одномерного случая рассматриваемое множество сеток должно обладать свойством локальной квазиравномерности, а в случае многих измерений требуется топологическая правильность соответствующего симпли-цпального подраздатения и равномерная ограниченность (снизу) углов между соседними ребрами каждого симплекса этого подразделения. Вопросам по строения сеток посвящены известные работы Л.А.Оганесяна, С.Г.Михлина, Ю.К.Демьяновича, В.Г.Корнеева, Йезерентанта и др. Для адаптивности вэй-влетного разложения (для учета свойств аппроксимируемой функции при аппроксимации) важно локальное укрупнение или измельчение подразделения в зависимости от локальных свойств упомянутой функции. В частности, для выделения основного потока при вэйвлетном разложении возникает задача локального укрупнения уже имеющегося симплициального подразделения; в многомерном случае такое укрупнение с сохранением топологической правильности не всегда возможно, так что возникает задача построения подразделений, допускающих упомянутое укрупнение. Неограниченное измельчение симплициального подразделения важно для аппроксимации функций с особенностями, а на основе таких подразделений получаются весовые оценки аппроксимации.
Об аппроксимации функций с особенностью на границе
Под "сеткой" обычно понимают некоторое топологическое множество точек ("вершин", "узлов"), связанных между собой "ребрами" - отрезками прямых (а в некоторых случаях и кривых) линий таким образом, что исходная область разбивается на элементы определенной формы. При этом в качестве элементов сетки, если речь идет о геометрически сложных областях, обычно используются симплексы, т. е. треугольники в двумерном и тетраэдры в трехмерном случае. Процесс построения сетки обычно называется, дискретизацией или триангуляцией (иногда даже в том случае, если речь идет о трех измерениях).
Все методы триангуляции по принципу построения можно разбить на две большие группы: прямые методы и итерационные методы [14, 15]. В прямых методах сетка строится за один этап, причем ее топология (иначе говоря, граф связей между узлами) и координаты всех узлов известны изначально. В итерационных методах сетка строится последовательно; на каждом шаге добавляется один или несколько элементов, причем изначально не известны ни координаты узлов, ни топология сетки. Кроме того, координаты узлов и топология могут меняться прямо в процессе построения.
Прямые методы условно могут быть разделены на две тесно связанные группы: методы на основе шаблонов [52, 60, 66, 71, 73] и методы отображения (изопараметрические) [2,11,16, 52]. Методы на основе шаблонов подразумевают разбиение областей заданного вида (прямоугольник, треугольник, параллелепипед, шар, цилиндр, и т.д.). Соответственно, для каждого вида области используется свой шаблон, то есть принцип размещения узлов и установки связей между ними. Если возможно построить взаимнооднозначное отображение между заданной областью и какой-либо простой геометрической формой, то, разбив последнюю, можно отобразить полученную сетку на исходную область. Очевидным недостатком этого подхода является искажение сетки при отображении, которое может существенно снизить качество триангуляции. Сетки, полученные прямыми методами, являются структурированными, т.е. их топология полностью определяется некоторым набором правил. Это означает, что зная только индексы узла, можно определить все соседние узлы, а также вычислить их координаты. Это важное свойство позволяет существенно экономить компьютерные ресурсы.
В итерационных методах разработано несколько различных подходов, которые можно разделить на три подкласса: методы граничной коррекции [26], методы на основе критерия Делоне [45, 46, 58, 61, 62, 68, 74] и методы исчерпывания [69, 70 , 72]. Методы граничной коррекции являются самыми быстрыми из итерационных методов, но, к сожалению, имеют ряд недостатков. Построение сеток в этих методах осуществляется в два этапа. На первом этапе производится триангуляция некоторой простой "супер-области", полностью включающей в себя заданную область. Как правило, эта супер-область представляет собой параллелепипед (прямоугольник), триангуляция которого осуществляется на основе одного из шаблонов. На втором этапе все узлы полученной сетки, лежащие вблизи границы заданной области, проецируются на поверхность границы; а узлы, лежащие вне заданной области — удаляются. Для того, чтобы компенсировать неизбежные геометрические искажения элементов сетки вблизи границ, часто дополнительно проводят еще один этап — этап оптимизации сетки, что в итоге позволяет получить достаточно хорошие результаты. Очевидно, что данный метод нельзя применять для дискретизации областей с заданной триангуляцией границ. Это существенное ограничение, а также другие сложности снижают популярность метода, сводя на нет его основное преимущество — высокую скорость работы. Сущность методов исчерпывания заключается в последовательном "вырезании" из заданной области фрагментов тетраэдрической формы до тех пор, пока вся область не окажется "исчерпанной". В англоязычной литературе этот метод получил название "advancing front", что также хорошо отражает идею метода. Исходными данными на каждой итерации является "фронт", то есть триангуляция границы еще не "исчерпанной" части области. Каждый треугольник этой триангуляции является основанием извлекаемого из области тетраэдра; причем на каждой итерации может извлекаться либо один тетраэдр, либо сразу целый слой тетраэдров. После изъятия тетраэдра (-ов) "фронт" обновляется, после чего происходит переход к следующей итерации. Методы исчерпывания используются в программном комплексе ANSYS. Вместе с тем следует отметить их высокую ресурсоемкость и низкую скорость работы. Методы на основе критерия Делоне часто называют просто методами Делоне. Идеей этого класса методов является размещение в заданной области узлов и последующая расстановка между ними связей согласно критерию Делоне (либо иному схожему критерию). В двумерном случае этот подход получил наибольшую популярность, поскольку он позволяет быстро и эффективно конструировать сетки с априори высоким качеством триангуляции. Однако при переходе к трем измерениям исследователи столкнулись с рядом проблем, затрудняющих использование этого критерия.
Второй способ симплициального подразделения полосы
Зачастую в современных алгоритмах построения сеток используются комбинации различных прямых и итерационных методов. Так сетки, построенные с помощью прямых методов, могут быть использованы и в итерационных методах. В первую очередь это касается методов граничной коррекции. Размещение узлов в методах на основе критерия Делоне нередко осуществляется с помощью одного из прямых алгоритмов (с последующей коррекцией).
Как правило, при моделировании физических процессов, существенное и резкое изменение параметров происходит на небольших участках рассматриваемой области, часто на границе области. В этих зонах необходимо сильно измельчать сетку, для того, чтобы получить численное решение с заданной точностью. Но использование подробной равномерной сетки во всей области приводит к неоправданно большим затратам ресурсов ЭВМ, времени счёта и оперативной памяти. А значит актуальным и важным разделом сеточных методов является построение адаптивных сеток, сгущающихся в зонах больших градиентов решения физической задачи. Поэтому разработка методов построения адаптивных сеток для численного решения прикладных задач является актуальной проблемой вычислительной математики, привлекающих многих исследователей. В настоящее время отмечается неослабевающий поток новых публикаций, посвященных модификации известных и конструированию новых методов построения адаптивных сеток, а также созданию алгоритмов расчета на этих сетках. В работе [30] описан метод построения треугольных адаптивных сеток посредством вставки дополнительных узлов в исходную триангуляцию. Работы [31, 37] предлагают способ построения подвижных и неподвижных регулярных адаптивных сеток методом эквираспределения. В работе [44] описана процедура триангуляции многосвязной области произвольной конфигурации со сгущением сетки в соответствии с заданным законом и с разбивкой контуров области на одномерные конечные элементы. В работе [38] предложено усовершенствование метода, описанного в [44]. В работе [26] предложен алгоритм разбиения двумерных многосвязных областей на треугольники, использующий итерационный метод граничной коррекции совместно с методом шаблонов, результатом работы этого алгоритма является последовательность неравномерных вложенных друг в друга сеток. В работах [2, 29] построены адаптивные структурированные (гексаэдральные) сетки в трёхмерных областях с помощью методов отображений, учитывающих форму ячеек. Работа [41] посвящена специализированным алгоритмам быстрого перестроения сетки с возможностью её адаптации к особенностям искомого решения. В работе [3] предложен алгоритм поблочной дискретизации плоской области со сгущением к границе области. Целью диссертационной работы является: 1) Разработка методов измельчения триангуляции пограничной полосы вблизи границы двумерной области с сохранением свойства невырожденности. 2) Разработка способов построения невырожденного симплициального подразделения, измельчающегося вблизи границы трехмерной области. 3) Получение весовых оценок аппроксимации для функций с особенностью. 4) Построение адаптивных вэйвлетных разложений курантовских пространств на локально укрупняющихся сетках, получение формул декомпозиции и реконструкции.
Проведём краткий обзор содержания диссертации. Работа объемом 163 страницы состоит из введения, трех глав, разбитых на девятнадцать параграфов, заключения, списка литературы, одного приложения и 19 рисунков. Внутри каждой главы своя нумерация параграфов. Во введении обосновывается актуальность работы и излагаются основные результаты исследования.
О барицентрических звездах исходной триангуляции
Описание метода распадается на несколько частей. В первом параграфе даётся описание одного из способов симплициального подразделения с измельчением симплексов при приближении к одному из оснований. Во втором и третьем параграфах даётся описание других способов симплициального подразделения с измельчением симплексов к одному из оснований. Четвертый и пятый параграфы посвящены описанию совместного применения трех первых способов для симплициального подразделения с измельчением симплексов в двугранном угле. В шестом параграфе описывается алгоритм измельчения симплициального подразделения полосы в трехгранном угле (совместно используются способы, описанные в предыдущих параграфах). Во всех упомянутых случаях доказывается, что описываемое симплициальное подразделение будет невырожденным. В седьмом параграфе второй главы получена весовая оценка курантовской аппроксимации для функции и(г) с растущими вторыми производными при приближении к границе трехмерной области О, с дважды непрерывно дифференцируемой границей. В первом параграфе первой главы описывается метод измельчения триангуляции пограничное полосы с сохранением свойства невырожденности при приближении к границе в случае, когда граница прямолинейная. Во втором параграфе первой главы рассматриваются различные варианты измельчения триангуляции при приближении к границе с угловыми точками (случаи внешних и внутренних углов). В третьем параграфе упомянутая пограничная полоса отображается на пограничную полосу в случае криволинейной границы и проверяется сохранение свойства невырожденности. В четвертом параграфе получена весовая оценка курантовской аппроксимации для функции и(т) с растущими вторыми производными при приближении к границе. Во второй главе описывается метод бесконечного симилициального подразделения, измельчающегося к границе трехмерной области с сохранением невырожденности: углы между ребрами симплексов этого подразделения лежат в-интервале (9, ж — в), где в — фиксированное число, 0 Є (0, тг/4). В третьей главе с первого по третий параграф рассматриваются триангуляции области, допускающие локальное укрупнение с сохранением правильности. В четвертом параграфе устанавливаются калибровочные соотношения, которые дают представление координатных функций Куранта на укрупнённой сетке в виде линейной комбинации координатных функций Куранта на исходной сетке. В пятом параграфе рассматривается система функционалов, биортогональная системе базисных функций объемлющего пространства. В шестом параграфе дается общая структура вэйвлет разложения, выводятся соответствующие формулы реконструкции и декомпозиции. В седьмом параграфе выводятся формулы реконструкции и декомпозиции для локального укрупнения исходной триангуляции. В последнем параграфе третьей главы построены адаптивные сплайн-вэйвлетные разложения на измельчающейся двумерной сетке. В заключении перечислены основные результаты исследования. Научная новизна. Все основные результаты работы являются новыми. Теоретическая и практическая значимость. Работа носит теоретический характер, а также представляет практический интерес. Алгоритмы построения симплициального подразделения в двумерном и трёхмерном случаях могут быть применены в практических задачах, решаемых методом конечных элементов, где искомая функция решения или ее производные неограниченно растут при приближении к границе. Предложенные методы обеспечивают построение невырожденных сеток, аппроксимацию функций с вырождением и вэйвлетное разложение. Результаты работы могут быть использованы при решении различных прикладных задач при сжатии и последующем вос становлении с заданной точностью больших потоков информации (цифровых сигналов) с резко меняющимися характеристиками, а также при построении параллельных форм алгоритмов упомянутых задач. На защиту выносятся следующие основные результаты: 1) Методы измельчения триангуляции пограничной полосы вблизи границы двумерной области с сохранением свойства невырожденности. 2) Способы построения невырожденного симплициального подразделения, неограниченно измельчающегося вблизи границы трехмерной области. 3) Весовые оценки аппроксимации для функций с особенностью. 4) Адаптивные вэйвлетные разложения курантовских пространств на локально укрупняющихся сетках, формулы декомпозиции и реконструкции. Основные результаты опубликованы в 8 работах [4-9, 56, 57], из них 4 статьи в журналах [6-9], рекомендуемых ВАК. По результатам работы были сделаны доклады на XXXIX, XL международных научных конференциях "Процессы управления и устойчивость" в 2008 г., 2009 г. [4, 5], и на 2-ой межвузовской научной конференции по проблемам информатики " СПИ-СОК-2011" (27-29 апреля, 2011 г.). Автор выражает глубокую благодарность своему научному руководителю профессору Демьяновичу Ю.К. за помощь в постановке задачи и анализе полученных результатов, а также за постоянное внимание в процессе работы над диссертацией.
