Вэйвлет-сплайновая аппроксимация функций с особенностями

Арсентьева, Евгения Петровна

Вэйвлет-сплайновая аппроксимация функций с особенностями тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

Арсентьева, Евгения Петровна АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Санкт-Петербург МЕСТО ЗАЩИТЫ

2011 ГОД ЗАЩИТЫ

01.01.07 КОД ВАК РФ

Диссертация по математике на тему «Вэйвлет-сплайновая аппроксимация функций с особенностями»

Автореферат диссертации на тему "Вэйвлет-сплайновая аппроксимация функций с особенностями"

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

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

АРСЕНТЬЕВА Евгения Петровна

В ЭЙВ ЛЕТ-СП Л АЙНОВ АЯ АППРОКСИМАЦИЯ ФУНКЦИЙ С ОСОБЕННОСТЯМИ

01.01.07 - Вычислительная математика

АВТОРЕФЕРАТ

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

1 3 ОКТ 2011

Санкт-Петербург 2011

485693Ь

4856936

Работа выполнена на кафедре параллельных алгоритмов математико-механического факультета Санкт-Петербургского государственного университета

Научный руководитель: доктор физико-математических наук,

профессор Демьянович Юрий Казимирович Официальные оппоненты: доктор физико-математических наук,

профессор Рябов Виктор Михайлович (Санкт-Петербургский государственный университет)

доктор физико-математических наук, профессор Вагер Борис Георгиевич (Санкт-Петербургский государственный архитектурно-строительный университет) Ведущая организация: Московский государственный университет

имени М.В.Ломоносова

<Г 3--

Защита состоится « ъ ОЩп^Я^/иЛ. 2011 г. в ^ часов на заседании совета Д.212.232.49 по защите докторских и кандидатских диссертаций при Санкт-Петербур] ском государственном университете по адресу: 198504, Санкт-Петербург, Старый Пете! гоф, Университетский пр., 28.

С диссертацией можно ознакомиться в Научной библиотеке им. М. Горького Санкт Петербургского государственного университета по адресу: Санкт-Петербург, Университетская набережная, д. 7/9 .

Автореферат разослан ^¿¿■/ъД^Л 2011 г.

Ученый секретарь диссертационного совета, доктор физ.-мат. наук, профессор

Архипова А.А.

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

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

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

Цель диссертационной работы.

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

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

• Получение весовых оценок аппроксимации для функций с особенностью.

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

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

Научная новизна. Все основные результаты работы являются новыми.

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

Результаты, выносимые на защиту.

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

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

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

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

Апробация работы. По результатам работы были сделаны доклады на XXXIX, XL международных научных конференциях "Процессы управления и устойчивость" 2008 г., 2009 г. [1, 2] и на 2-ой межвузовской научной конференции по проблемам информатики "СПИСОК-2011" (27-29 апреля, 2011 г.).

Публикации. Основные результаты опубликованы в 8 работах, из них 4 статьи (см. [А1-А4]) опубликованы в журналах, рекомендованных ВАК.

Личный вклад автора. В совместных работах [3, 4], [AI, А2, A4] научному руководителю принадлежит общая постановка задачи и указание на идею исследования, а детальная реализация идеи принадлежит диссертанту.

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

Содержание работы

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

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

В плоскости Rjs Tj рассмотрим прямоугольник

П(,,т)"='{(«,т) | - S < s < S, 0 < т < г.}.

Рассмотрим прямые А, : {(s, т) | — S < s < S, т = т,/2'}, разбивающие прямоугольник П(3,т) на части {(s, т)\ - S < s < S, r„/2i+1 < т < т,/2'}, называемые полосами.

Треугольники, у которых две вершины лежат на кривой Aj, назовем нечетными треугольниками триангулированной полосы По, а треугольники с одной вершиной на А!

— четными треугольниками этой полосы.

Пусть нулевая полоса П0 разделена на четные и нечетные треугольники. Пусть ААВС — один из нечетных треугольников полосы П0 с вершиной В на прямой Ао и с вершинами А и С на кривой Ль Через середину В ' отрезка АС проведем прямые, параллельные прямым АВ и ВС до пересечения с прямой Л2. Точки пересечения обозначим В " и В "' соответственно. Построим прямолинейные отрезки АВ ", В "В ', В 'В "', В '"С к В'В.

Проделаем аналогичные действия для всех нечетных треугольников нулевой полосы. Построение триангуляции полосы Щ заканчивается соединением прямолинейными отрезками каждой пары соседних точек, полученных на прямой Л2- Аналогично по триангуляции полосы П( построим триангуляцию полосы Ц+i, г = 0,1, —

Указанный способ триангуляции полосы назовём методом (Ti).

Теорема 1. Если при некотором в 6 (0,7г/4) углы треугольников полос П0, Щ лежат в интервале (в,п — 9), то углы треугольников всех полос Щ i = 2,..., также лежат в этом интервале.

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

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

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

дП: r = p(s), se[-S,S),

где г = (х,у), s — натуральный параметр (длина кривой), p(s) — дважды непрерывно дифференцируемая вектор-функция. Пусть 0 < т* < inf„£[_s,s) |i?(s)|, где R(s) — радиус кривизны кривой dû в точке s. В плоскости (s, т) рассмотрим прямоугольник

Пм tf {(s, г) | - S < s < S, -т. < г < т,},

и пограничную полосу границы dû

n[x,s)d= {г |г = p(s) + rn(s), -S<s<S, -г, < т < т.};

здесь n(s) — внутренняя нормаль к кривой dû в точке s. Пусть Ф — отображение П[3,т] в П[х,„], задаваемое формулой

Ф : (s, т) i—► г = p(s) + rn(s).

В П[,,т] рассмотрим невырожденный треугольник с вершинами в точках А(а,6), B(i7 + ecos p,S + £ sin p), С (a + 77 cos g, 5 + r¡ sin q) и через а обозначим его внутренний угол при вершине А. В П[1Л] рассмотрим невырожденный (прямолинейный) треугольник с вершинами А' = Ф(А), В' = Ф(В) и С" = Ф(С); через а' обозначим его внутренний угол при вершине А '.

Теорема 2. Если 9П 6 С2[—5, 5], то справедливо соотношение

lim cos а ' = cos а,

е->0, ä->0,!)-.0

причем стремление к пределу происходит равномерно относительно а 6 [—5,5].

Построим невырожденную триангуляции в прямоугольнике П(,,т) описанным выше методом (Ti): углы всех треугольников этой триангуляции лежат в интервале (в, п—0) при некотором в е (0, 7г/4); с помощью отображения Ф отобразим все вершины триангуляции в полосу

n(l,¡,)='{г |г = p(s) + rn(s), -5 < s < S, 0 < т < т.};

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

Ввиду теоремы 2 углы а треугольников полученной триангуляции (вблизи криволинейной границы) обладают свойством

ае (0/2, тг-0/2).

(1)

В четвертом параграфе получена весовая оценка курантовской аппроксимации для функции и(г) с растущими вторыми производными при приближении к границе. Пусть и(т) £ С2(П), где П — открытая область с дважды непрерывно дифференцируемой границей. В области П рассмотрим измельчающуюся при приближении к границе триангуляцию Т со свойством (1), исчерпывающую область П, так что П = Т. Для каждого треугольника Т триангуляции 7* положим

' ' д2и

IHIô(T) =

и введем весовую полунорму

-(г')

дх2 >

дхду

(г')

dyi[

1М1йт=' SUP \Hd(T)hT-тег

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

Пусть Т„ — в-кратное стандартное измельчение триангуляции Т, а й, — курантов-ская интерполяция функции и на. % (т.е. непрерывная кусочно-линейная функция, совпадающая сив вершинах триангуляции Та и линейная на каждом треугольнике этой триангуляции).

Теорема 3. Справедлива оценка

Кг) - «,(г)| < С2{9)2-*'\\и\\е(г) Чт е П, где Сг(0) от в и от и не зависит.

Во второй главе описывается метод бесконечного симплициального подразделения, измельчающегося к границе трехмерной области с сохранением невырожденности: углы между ребрами симплексов этого подразделения лежат в интервале (в,л - в), где в — фиксированное число, в 6 (0,7г/4).

Рассмотрим параллелепипед

П = {(х,у, г)| — 5 < а: < 5, 0 < у < у„ 0 < г < г,}. (2)

Описание метода распадается на несколько частей. В первом параграфе даётся описание одного из способов симплициального подразделения с измельчением симплексов при приближении к одному из оснований. Параллелепипед (2) разбивается слоями А.' = {(!,«/, г) |-5<г<5, 0 < у < у,, г = 2,/2'} на части, называемые далее полосами: П? = {(*, у, г) | - 5 < х < 5, 0 < у < у,, г,/2<+1 < г < г./2«}.

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

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

симплекса, причем двойные верхние индексы соответствуют вершинам - точкам деления ребер, соединяющих вершины с соответствующими одинарными индексами (например, вершина <!"•'" является внутренней точкой ребра, соединяющего вершины и й'"). При разбиении призм полосы Щ используются следующие формулы для нечётной призмы

д.' <1" д."

и' и" и'"

и"

й" и"

д.'*'" и"

и"

й' и" и"'

Л'" и" и'"

и для четной призмы

и' и'" и1У

и' и,у и'" й1У

4' и'"

¿IV,,,, и'"

¿IV,т <Г" и'"

¿IV,,,, и'"

и' и'"

Описанное выше построение сначала приведет к комплексу П0, состоящему из треугольных призм, а затем — к симплициальному подразделению полосы Щ. Продолжение процесса симплициального разбиения приведет на 5-м шаге к появлению комплексов Щ, состоящих из треугольных призм: в каждом из них можно рассматривать четные и нечетные призмы; здесь а = (а1,а2,...,а„+1) — двоичный вектор, сц € {0,1}, г = 1,2,...,в +1. Фактически получается бинарное дерево указанных комплексов, согласованные симпли-циальные подразделения которых могут быть построены последовательным применением описанного выше алгоритма симплициального разбиения полосы.

Теорема 4. Если при некотором в € (0, тг/4) углы симплексов нулевой полосы лежат в интервале (в, ж — в), то углы симплексов всех полос П{, i = 1,2,3,..., также лежат в упомянутом интервале.

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

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

В последнем параграфе второй главы получена весовая оценка курантовской аппроксимации для функции и(т) с растущими вторыми производными при приближении к границе трехмерной области П с дважды непрерывно дифференцируемой границей. Сначала рассматривается измельчающееся при приближении к границе симплициальное подразделение 7* области П, утлы между ребрами симплексов которого лежат в интервале (в, ж—О), в € (0, тг/4). Для каждого симплекса <5 подразделения Т положим

1М1б(5) =' .

шах тах '+]+к=2 Г'£5

—м

вводим весовую полунорму

1Ий(Т)= 8ир||и||£(г)/%

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

Теорема 5. Если % — в-кратное стандартное измельчение симплициального подразделения Т, а и, — курантовская интерполяция функции и на Т3, то справедлива оценка

Кг) - 5.(г)| < С3(0)2-2>||й(т) Уг € о,

где Сз(в) от в и от и не зависит.

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

Введем обозначения = | г 6 2 V? б 2}, 2г,2^) | г 6 2 V; е 2},

+ + у?ег},

Пусть фиксированы числа к' > 0, к" > 0. Обозначим М^ точки с координатами {гк'^к"), (г,.?) € 1} и рассмотрим прямоугольники вида П^-™{(х,у) \ М < х < (г + 2)Л', < х < (] + 2)Л"}, где (г,]) 6 2ц. Пусть X* — некоторое (конечное или

бесконечное) множество пар четных целочисленных индексов: X* С Ъц\ рассмотрим замкнутую область П=' и^^ех- (в частности, П совпадает со всей плоскостью К2, если X* = 2о). Через X обозначим множество индексов (г, ]) в и таких, что точки М^ = (М,]1>!') лежат в П; только что упомянутые точки М^ будем называть узлами исходной сетки, они явятся вершинами определяемой ниже исходной триангуляции. Узел Л/г;,,,г*, называется внутренним узлом для П, если он является внутренней точкой в П. Множество пар (г,6 X*, для которых М^ — внутренний узел, обозначим Х0. Очевидно, что Х0 С X* С X С 22.

Рассмотрим триангуляцию, которая получается объединением таблиц

Му Мгн4

Л/г+м Л/ж.ж

Л/2+«,2+; Л/1+1,1+^

Мч Л/ж,Ж

У(»,з) € К

(3)

Укрупнение триангуляции будем производить объединением двух соседних (т.е. имеющих общую сторону) треугольников. Не нарушая общности, в дальнейшем предполагаем, что Л/0,о — внутренний узел в П, т.е. (0,0) 6 Х0. Рассмотрим такое укрупнение, при котором вершину Л/0,0 будут окружать лишь укрупненные треугольники.

Итак, укрупнение зададим следующим преобразованием таблицы инциденций.

Л/0,0 М- 2,0 Л^—1,1 Л/_ 2,2 Л/_ 2,0 Л^-1,1

Мор Л/_ 2,0 М_2

М_ 2,2 Мо, 2 М-1,1 М),0 Л/0,2 Л/-1Д

|| М | Мо,о Л/о,2 А/1,1

• Л/о,о Л/0,2 М-2,2 | > 1I

" Л/2,2 Л/о,2 Л/1,1

Л/г,2 Л/2,о Л/1,1

Л/о,о Л/2,0 ми

Л/о,о Л/2,0 Л/2,—2 II'

л/о,о Л/о,—2 Л/_1,_1 Л/_ 2,-2 Л/о,-2 Л/_ 1,-1

Л/0,0 Л/2,0 Л/2,2 ,

л/г,-2 Л/о,_2 Л/1,-1

Л/о,о Л/о,-2 Л/1,-1

ч д л Л . л „ ., || ■••■■и.и "•■и.г "*2,2 ||'

Л/о,о Л/2,0 Л/1,-1 Л/2,—2 Л/2,0 Л/1,-1

Л/о,о Л/о,_2 Л/2,—2 >

Л/о, о Л/_2,0 Л/- 2,-2 I

Л/_ 2,-2 Л/_2,0 Л/-1-1 Л/о,о Л/—2,0 Л/-1-1

Л/0,0 Л/_:

2,0

л/_

2,-2

Исходную триангуляцию (3) обозначим Т, описанную только что укрупненную триангуляцию обозначим То, а переход от исходной триангуляции к укрупненной обозначим

В четвертом параграфе устанавливаются калибровочные соотношения, которые дают представление координатных функций Куранта на укрупнённой сетке в виде линейной комбинации координатных функций Куранта на исходной сетке.

Введем обозначения Ii"= {(0,0), (1,1), (-1,1), (1,-1), (-1, -1)}, 1\ = 1Д(0,0). Функцию Куранта, соответствующую выделенной вершине Mij исходной триангуляции, обозначим Wjj(t), (г, j) 6 X, t € R2. Для укрупненной триангуляции функцию Куранта, соответствующую выделенной вершине JVfjj, будем обозначать Заметим, что не все вершины исходной триангуляции участвуют в укрупненной триангуляции, а именно, индексы (г, j) пробегают не все множество X, а лишь его часть: (i,j) 6 Х\П'[. Обозначим Y=fX\I j.

Теорема 6. Справедливы следующие соотношения

wy(i) = wy(0 V(»,j) еХ^ДЯь (4)

wo,o(i) = wo,o(t) + + + + ^w-i^t), (5)

W2i(t)2W2,2(!) + ^U(i), 2_2,2(t)=o;-2,2(t)+^_M(t), (6)

£>2,-2 (t) = W2.-2 (t) + ^Wi-i(t), ,-2(i) = W-2,-2(t) + (7)

В дальнейшем вектор (г, j) будем обозначать через а; в соответствии с этим обозначением положим Ma'=Mij, Ua^uiij, u>a =fSjj, 0d= (0,0), ed=(l,l), e*d= (—1,1). В этих обозначениях имеем Ij = {0, е,е*, —е, — е*}, IJ = 1Д0, 2Ii = {0,2е, 2е", —2е, — 2е*}, так что формулы (4) - (7) принимают вид:

D«(t) ее £ р„л w7(i) Va е Y, (8)

7£Х

где ра,7 ='ia,7 при aeX\Ii\2Ii, 7 е X, p2a,2a =' 1 при a ell, po,a='l/2i P2a,a = 1/2 при a £ IJ; здесь 6aa> — символ Кронекера.

Обозначим матрицу фо='(Ра,7), где a 6 Y — номер строки, а 7 € X — номер столбца.

Как следствие из теоремы 6 получим вложенность соответствующих линейных пространств St'Clp £({w7 IV7 € X}), Sot'Ci,, £({£a I Va e Y}); S0 С S.

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

В пространстве C(R2) зададим систему линейных ограниченных функционалов ду для V7 € X формулами (д-,,и) ='и(М7), (э7,wy) = <S7i7. V7,7' £ X. Аналогичным образом задается система функционалов для Va 6 Y формулами {ga,u)á¿u{Ma), (да,ша') = 5а,а, Va.a'eY.

Пусть Ü0 — матрица с элементами qai7 =f (ga, w7) Va e Y V7 € X, где a — номер строки, а 0 — номер столбца.

Теорема 7. Справедливы соотношения qa,7 = <5a,7 Va е Y V7 G X. Рассмотрим оператор Р0 проектирования пространства С(П) на подпространство So, задаваемый формулой Р0«=' £ {5а,«> , Vu 6 C(Q), и введем оператор Q0 = I - ío, где I — тождественный в С(П) оператор.

Проащмнстном в:>йвлетов (всплесков) называется пространство Wo = <?oS, а прямое разложение

S = So+Wo (9)

— сплайн-вэйвлетным разложением пространства §.

Пусть и е S; согласно формуле (9) имеем и = £ ~ Е acfia + X) fys^/Ji ГДС

76Х q€Y /ЗеХ

aa='(5a,u), b¡3, c-, 6 R1. В соответствии с указанной ранее упорядоченностью рассмотрим вектор-столбцы ad= (аа)а6у, Ь ='(6,з)/зех, с ='(^чех-Теорема 8. Формулы декомпозиции имеют вид

b = с - ф£О0с, а = Д0с, (Ю)

а формулы реконструкции могут быть представлены в виде

с = Ь -i- Фоа- (И)

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

Теорема 9. При локальном укрупнении триангуляции [Т i—► %] в вэйвлетпом разложении (9) формулы декомпозиции имеют вид

Ьа = 0, аа = са а в Y, (12)

11, 11 6_е. = С_е. --с_2е. --со, = С_е - - С_2е - - Со, (Id)

1 1 11

Ъе =Се - -с2е - j Со. V = Се-- - с2е-- j со- li4J

Теорема 10. Для локального укрупнения [Т i—► вэйвлетному разложению (9) соответствуют формулы реконструкции

са = аа Va 6 Y, (15)

с_е. = Ь_е. + ^ a_ + с_е = 6_е + ^ а_2е + ^ ао, (16)

ce = be + 7;a2e + 7¡ao> Се' = Ье' + \ °2е- + ^ «о- (17)

В последнем параграфе третьей главы построены адаптивные сплайн-вэйвлетные разложения на измельчающейся двумерной сетке.

В Заключении перечислены основные результаты исследования.

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

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

А1. Арсентьева Е. П., Демьянович Ю. К. О невырожденной триангуляции со сгущением к границе области // Проблемы математического анализа. 2010. Вып. 48. С. 3-14.

А2. Арсентьева Е. П., Демьянович Ю. К. Алгоритмы невырожденного симплициально-го подразделения с измельчением вблизи границы // Компьютерные инструменты в образовании. 2010. № 6. С. 23-30.

АЗ. Арсентьева Е. П. Об измельчении триангуляции вблизи границы области // Вестник Санкт-Петербургского университета, Сер. 10. 2011. Вып.1. С. 77-85.

А4. Арсентьева Е. П., Демьянович Ю. К. Адаптивные сплайн-вэйвлетные разложения двумерных потоков числовой информации // Проблемы математического анализа. 2011. Вып. 50. С. 3-10.

Другие публикации:

1. Арсентьева Е. П. О погрешности приближения функций с растущими производными // Процессы управления и устойчивость: Труды 39-й международной научной конференции, 7-11 апреля 2008 г. / Под ред. Н.В.Смирнов, Г.Ш.Тамасян. Спб.: Издат. Дом С.-Петерб. Гос. Ун-та, 2008. С. 105-110.

2. Арсентьева Е. П. О невырожденной триангуляции и её измельчении вблизи границы области // Процессы управления и устойчивость: Труды 40-й международной научной конференции, 6-9 апреля 2009 г. / Под ред. Н.В.Смирнов, Г.Ш.Тамасян. Спб.: Издат. Дом С.-Петерб. Гос. Ун-та, 2009. С. 104-107.

3. Arsent'eva Е., Dem'yanovich Y. On nondegenerate triangulation with condensation at the boundary of a domain // Journal of Mathematical Sciences. 2010. Vol. 169, no. 2. Pp. 131-144.

4. Arsent'eva E., Dem'yanovich Y. Adaptive spline-wavelet decomposition 2d flow of numeric information // Journal of Mathematical Sciences. 2011. Vol. 175, no. 3. Pp. 211-228.

Подписано к печати 06.09.2011. Формат бумаги 60 х 84 'Лб- Бумага офсетная. Печать цифровая. Усл. печ. л. 1,00. Тираж 100 экз. Заказ 5241. Отпечатано в отделе оперативной полиграфии Химического факультета СПбГУ. 198504, Санкт-Петербург, Петродворец, Университетский пр. 26

Содержание диссертации автор исследовательской работы: кандидата физико-математических наук, Арсентьева, Евгения Петровна

Введение

Глава 1. Измельчение триангуляции вблизи границы области и аппроксимация функций с особенностью

1.1. Измельчение триангуляции вблизи границы.

1.2. Описание измельчения триангуляции с помощью таблиц инци-денций

1.3. Отображение триангуляции на криволинейную границу

1.4. Об аппроксимации функций с особенностью на границе

Глава 2. Симплициальное подразделение области с измельчением симплексов к границе области; аппроксимация функций с особенностью.

2.1. Симплициальное подразделение полосы в пространстве М3 с измельчением симплексов.

2.2. Второй способ симплициального подразделения полосы.

2.3. Третий способ подразделения полосы.

2.4. Измельчение симплициального подразделения полосы в двугранном угле.

2.5. Другие варианты измельчения в двугранном угле.

2.6. Алгоритм измельчения симплициального подразделения полосы в трехгранном угле.

2.7. О курантовской аппроксимации функций с вырождением на границе.

Глава 3. Адаптивные сплайн-вэйвлетные разложения двумерных потоков числовой информации.

3.1. Локальное укрупнение триангуляции.

3.2. О барицентрических звездах исходной триангуляции.

3.3. Структура барицентрических звезд укрупненной триангуляции

3.4. Калибровочные соотношения для функций Куранта.

3.5. Биортогональная система и ее значения на базисных функциях объемлющего пространства.

3.6. Общая структура вэйвлетного разложения.

3.7. Вэйвлетное разложение при укрупнении триангуляции.

3.8. О вэйвлетных разложениях при измельчении триангуляции

Введение диссертация по математике, на тему "Вэйвлет-сплайновая аппроксимация функций с особенностями"

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

Актуальность работы. Решение задач в гидродинамике, электродинамике, газовой динамике, теории упругости (в частности, прогнозирование климата, ураганов, цунами и т.д.) сводится к получению численных данных, задающих коэффициенты соответствующих начально-краевых задач, и к решению этих задач численными методами, а именно, методами сеток [1, 10, 12, 27, 36, 40, 50, 53], методами конечных элементов и методами Ритца-Галеркина [25, 28, 42, 43, 48, 49, 63, 67, 79].

Поскольку сложные задачи часто характеризуются функциями с нерегулярным поведением (например, неограниченным ростом функций или их производных вблизи границы рассматриваемой области или переходами от медленного изменения к быстрому), то возникает задача построения аппроксимаций этих функций, учитывающих их нерегулярное поведение. Сплай-новые и конечно-элементные аппроксимации представляют собой линейную комбинацию большого числа базисных функций с малым носителем; базисные функции строятся стандартным способом н определяются сеткой узлов в некоторой области евклидова пространства, а коэффициенты линейной комбинации рассматриваются как числовой поток, подлежащий обработке. Для экономного использования ресурсов вычислительной системы прибегают к шйвлетному разложению упомянутого исходного потока на основной поток н уточняющие (вэйвлетные) потоки [13, 24, 33, 39, 51, 75-77]. Как правило, основной информационный поток значительно менее плотный, чем исходный поток информации, поэтому его можно передать быстро. Уточняющий информационный поток (его иногда называют вэйвлетным потоком) не во всех случаях необходим, его можно передавать фрагментарно, в зависимости от потребностей. Наконец, поток с несущественной информацией вообще может быть отброшен, тогда исходный поток должен однозначно восстанавливаться по основному и вэйвлетному потокам. Естественный вопрос о разделении информации на основную, уточняющую и несущественную части выходит за рамки математических исследований и должен решаться в каждом отдельном случае специалистом данной предметной области. В классической теории вэйвлетов рассматриваются ортогональные вэйвлетные (всплес-ковые) разложения (в пространстве £>2), связанные с равномерной сеткой, что позволяет эффективно использовать непрерывное и дискретное преобразования Фурье ( см. [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 рисунков. Внутри каждой главы своя нумерация параграфов.

Заключение диссертации по теме "Вычислительная математика"

Заключение

В рамках данной работы получены следующие основные результаты:

1. Разработан алгоритм невырожденного измельчения триангуляции пограничной полосы в случае прямолинейной границы области, а также в случае внутренних и внешних углов на границе. Рассмотрено отображение триангуляции пограничной полосы в случае криволинейной границы области. Доказано, что свойство невырожденности углов сохраняется и при отображении. Устанавливается, что если в исходном треугольнике уменьшать стороны угла а и при этом сам треугольник приближать к (прямолинейной) границе, то для образа при указанном отображении справедливо предельное соотношение а' —> а.

Рассмотрена аппроксимация Куранта для функций с особенностью на границе. Получена оценка курантовской аппроксимации функции на измельченной триангуляции.

2. Разработан алгоритм невырожденного симплициального топологически правильного подразделения параллелепипеда при измельчении симплексов с приближением к его основаниям. При этом углы симплексов содержатся в интервале (0,7Г — 0), где число 0 е (0,7г/4) фиксировано.

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

3. Рассмотрены триангуляции двумерной области, допускающие локальное укрупнение с сохранением правильности. Установлены калибровочные соотношения, которые дают представление координатных функций Куранта на укрупнённой сетке в виде линейной комбинации координатных функций Куранта на исходной сетке. Используя систему функционалов, биортогональную системе базисных функций объемлющего просранства, построено вэйвлетное разложение и выведены соответствующие формулы реконструкции и декомпозиции. Получены формулы реконструкции и декомпозиции для локального укрупнения исходной триангуляции.

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

4. Отдельно стоит отметить, что в 2011 году студентом кафедры параллельных алгоритмов Хрусталевым Д. М. в рамках дипломной работы сделана программная реализация параллельной версии разработанного в пункте 2.1 алгоритма симплициального подразделения параллелепипеда с измельчением симплексов при приближении к одному из оснований. Студентом Хрусталевым разработан программный пакет, реализующий предложенный алгоритм посредством языка С++.

Список источников диссертации и автореферата по математике, кандидата физико-математических наук, Арсентьева, Евгения Петровна, Санкт-Петербург

1. Азаренок Б. Н. О применении вариационного барьерного метода в гиперболических задачах газовой динамики // Ж. вычисл. матем. и матем. физ. 2003. Т. 43, № 7. С. 1072-1096.

2. Азаренок Б. Н. О построении структурированных сеток в двумерных невыпуклых областях с помощью отображений // Ж. вычисл. матем. и матем. физ. 2009. Т. 49, № 5. С. 826-839.

3. Алейников С. М., Седаев А. А. Алгоритм генерации сетки в методе граничных элементов для плоских областей // Математическое моделирование. 1995. Т. 7, № 7. С. 81-93.

4. Арсентьева Е. П. Об измельчении триангуляции вблизи границы области // Вестник Санкт-Петербургского университета, Сер. 10. 2011. Вып.1. С. 77-85.

5. Арсентьева Е. П., Демьянович Ю. К. Алгоритмы невырожденного симплициального подразделения с измельчением вблизи границы // Компьютерные инструменты в образовании. 2010. № 6. С. 23-30.

6. Арсентьева Е. П., Демьянович Ю. К. О невырожденной триангуляции со сгущением к границе области // Проблемы математического анализа. 2010. Вып.48. С. 3-14.

7. Арсентьева Е. П., Демьянович Ю. К. Адаптивные сплайн-вэйвлетные разложения двумерных потоков числовой информации // Проблемы математического анализа. 2011. Вып.56. С. 3-17.

8. Барахнин В. Б., Хакимзянов Г. С. Численное моделирование косого наката уединенной волны // ПМТФ. 1999. Т. 40, № 6. С. 17-25.

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

10. Бенерджи П., Баттерфильд Р. Метод конечных элементов в прикладных науках. М.: Мир, 1984. С. 494.

11. Вагер Б. Г., Серков Н. К. Сплайны при решении прикладных задач метеорологии и гидрологии. Л.: Гидрометеоиздат, 1987. С. 160.

12. Галанин М. П., Щеглов И. А. Разработка и реализация"алгоритмов трехмерной триангуляции сложных пространственных областей: итерационные методы // Препринт ИПМ им. М.В. Келдыша РАН. 2006. № 10. С. 32.

13. Галанин М. П., Щеглов И. А. Разработка и реализация алгоритмов трехмерной триангуляции сложных пространственных областей: прямые методы // Препринт ИПМ им. М.В. Келдыша РАН. 2006. № 9. С. 32.

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

15. Демьянович Ю. Локальная аппроксимация на многообразии и минимальные сплайны. СПб: Изд. СПбГУ, 1994. С. 356.

16. Демьянович Ю. Локальный базис всплесков на неравномерной сетке // Зап. научн. сем. ПОМИ. 2006. Т. 334. С. 84-110.

17. Демьянович Ю. Всплесковые разложения на неравномерной сетке // Труды С.-Петерб. матем. о-ва. 2007. Т. 13. С. 27-51.

18. Демьянович Ю. Вэйвлеты на многообразии // Доклады РАН. 2009. Т. 421, № 2. С. 1-5.

19. Демьянович Ю., Зимин А. Аппроксимации курантового типа и их вэй-влетные разложения // Проблемы математического анализа. 2008. Т. 37. С. 3-22.

20. Демьянович Ю., Михлин С. О сеточной аппроксимации функций соболевских пространств. Численные методы и функциональный анализ // Зап. научн. сем. ЛОМИ. 1973. Т. 35. С. 6-11.

21. Демьянович Ю. К. Симплициальные распространения сеточных функций // Методы вычислений. 1973. Вып.8. С. 32-50.

22. Добеши И. Десять лекций по вейвлетам. Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001. С. 464.

23. Зенкевич О. Метод конечных элементов в технике. М.: Мир, 1975. С. 541.

24. Ищенко А. В., Киреев И. В. Алгоритм построения двумерных вложенных сеток // Журнал Сибирского Федерального университета. Сер. «Математика и физика». 2009. Т. 2, № 1. С. 83-90.142

25. Квитка А. Л., Ворошко П. П., Бобрицкая С. Д. Напряженно-деформированное состояние тел вращения. Киев: Наук, думка, 1977. С. 208.

26. Корнеев В. Г. Схемы метода конечных элементов высоких порядков точности. Л.: Изд. Ленингр. ун-та, 1977. С. 206.

27. Котеров В. Н. Построение пространственных сеток в многоступенчатых осевых турбинах с использованием вариационного барьерного метода // Ж. вычисл. матем. и матем. физ. 2005. Т. 45, № 8. С. 1374-1382.

28. Лебедев А., Лисейкин В. Д., Хакимзянов Г. Разработка методов построения адаптивных сеток // Вычислительные технологии. 2002. Т. 7, К2 3. С. 29-43.

29. Лисейкин В. Д., Молородов Ю. И., Хакимзянов Г. Об интерактивном комплексе программ построения двумерных структурных сеток // Вычислительные технологии. 2000. Т. 5, № 1. С. 70-84.

30. Малла С. Вейвлеты в обработке сигналов: Пер. с англ. М: Мир, 2005. С. 671.

31. Малоземов В. Н., Певный А. Б. Полиномиальные сплайны. СПб: Изд. СПбГУ, 1986. С. 120.

32. Малоземов В. Н., Певный А. Б., Третьяков А. А. Быстрое вейвлетное преобразование дискретных периодических сигналов и изображений // Проблемы передачи инф. 1998. Т. 34. Вып. 2. С. 77-85.

33. Милькова Н. И. Особенности дискретизации области при решении задач концентрации напряжений методой конечных элементов // Машиноведение. 1979. № 2. С. 67-71.

34. Михлин С. Вариационно-сеточная аппроксимация // Зап. научн. семинаров ЛОМИ АН СССР. 1974. Т. 48. С. 32-188.

35. Молородов Ю. И., Хакимзянов Г. Построение и оценка качества регулярных сеток для двумерных областей // Вопросы атомной науки и техники. Сер. Мат. моделирование физ. процессов. 1998. Вып.1. С. 19-27.

36. Немировский Ю. В., Пятаев С. Ф. Автоматизированная триангуляция многосвязных областей со сгущением и разрежением узлов // Вычислительные технологии. 2000. Т. 5, № 2. С. 82-91.

37. Новиков И., Стечкин С. Основы теории всплесков // Успехи математич. наук. 1998. Т. 53, № 6. С. 53-128.

38. Оганесян Л., Руховец Л. Вариационно-разностные методы решения эллиптических уравнений. Ереван: Изд. АН АССР, 1979. С. 235.

39. Попов И. В., Поляков С. В. Построение адаптивных нерегулярных треугольных сеток для двумерных многосвязных невыпуклых областей // Математическое моделирование. 2002. Т. 14, № 6. С. 25-35.

40. Рыжов Э. В., Сакало В. И., Подлеснов Ю. П. Решение контактных задач релаксационным методом конечных элементов // Машиноведение. 1980. № 6. С. 64-69.

41. Сабоннадьер Ж.-К., Кулон Ж.-Л. Методы конечных элементов и САПР. М.: Мир, 1989. С. 190.

42. Сакало В. И., Шкурин А. А. Универсальная программа триангуляции двумерной области произвольной формы со сгущениями сетки // Проблемы прочности. 1985. № 1. С. 106-108.

43. Скворцов А. Алгоритмы построения триангуляции с ограничениями // Вычислительные методы и программирование. 2002. № 3. С. 82-92.

44. Скворцов А. Обзор алгоритмов построения триангуляции Делоне // Вычислительные методы и программирование. 2002. № 3. С. 14-39.

45. Столниц Э., Роуз Т. Д., Салезин Д. Вейвлеты в компьютерной графике. Теория и приложения. Москва-Ижевск: Изд. PXD, 2002. С. 272.

46. Стренг Г., Фикс Д. Теория метода конечных элементов. М.: Мир, 1977. С. 349.

47. Сьярле Ф. Метод конечных элементов для эллиптических задач. М.: Мир, 1980. С. 512.

48. Хакимзянов Г. С., Шокин Ю. И., Барахнин В. В., Шокина Н. Ю. Численное моделирование течений жидкости с поверхностными волнами. Новосибирск: СО РАН, 2001.

49. Чуй К. Введение в вэйвлеты. М: Мир, 2001. С. 412.

50. Шайдуров В. В. Многосеточные методы конечных элементов. М.: Наука, 1989. С. 288.

51. Шокин Ю. И., Яненко Н. Н. Метод дифференциального приближения. Применение к газовой динамике. Новосибирск: Наука. Сиб. отд-ние, 1985. С. 364.

52. Aldroubi A., Cabrelli С., Molter U. Wavelets on Irregular Grids with Arbitrary Dilation Matrices, and Frames Atoms for L2(M.d) // Appl. Comput. Harmonic Anal. 2004. Vol. 17. Pp. 119-140.

53. Aldroubi A., Sun Q., Tang W.-S. Non-uniform average sampling and reconstruction in multiply generated shift-invariant spaces // Constr.Approx. 2004. Vol. 20. Pp. 173-189.

54. Arsent'eva E., Dem'yanovich Y. On nondegenerate triangulation with condensation at the boundary of a domain // Journal of Mathematical Sciences. 2010. Vol. 169, no. 2. Pp. 131-144.

55. Arsent'eva E., Dem'yanovich Y. Adaptive spline-wavelet decomposition 2d flow of numeric information // Journal of Mathematical Sciences. 2011. Vol. 175, no. 3. Pp. 211-228.

56. Baker T. Automatic Mesh Generation for Complex Three-Dimensional Regions Using a Constrained Delaunay Triangulation // Engineering With Computers. 1989. no. 5. Pp. 161-175.

57. Bansch E., Mikula K. A Coarsening Finite Element Strategy in Image Selective Smoothing // Comp. Visual Sci. 1997. Vol. 1. Pp. 53-61.

58. Bern M., Eppstein D. Mesh Generation and Optimal Triangulation // Computing in Euclidean Geometry. 1995. Pp. 23-90.

59. Blandford D., Blelloch G., Cardoze D., Kadow C. Compact Representations of Simplicial Meshes In Two and Three Dimensions // Proceedings of 12th International Meshing Roundtable, Sandia National Laboratories, Sept. 2003. Pp. 133-141.

60. Borouchaki H., Lo S. Fast Delaunay Triangulation In Three Dimensions // Computer Methods In Applied Mechanics And Engineering. 1995. Vol. 128. Pp. 153-167.

61. Courant R. Variational Methods for Solution of Equilibrium and Vibration // Bull. Am. Math Soc. 1943. Vol. 49. Pp. 1-43.

62. Daubechies I., Guskov I., Sweldens W. Commutation for irregular subdivision // Constr.Approx. 2001. Vol. 17, no. 4. Pp. 479-514.

63. Daubechies I., Schroder P., Guskov I., Sweldens W. Wavelets on Irregular Point Sets // Phil. TVans. R. Soc. Lond. A. 1999. Vol. 357. Pp. 2397-2413.

64. George P. TET MESHING: Construction, Optimization and Adaptation // Proceedings of 8th International Meshing Roundtable. 1999. Pp. 133-141.

65. Ho J. Generation of Patient Specific Finite Element Head Models. Doctoral Thesis. TritarSTH Report: Dr. Sci. dissertation. 2008. P. 39.

66. Joe B. Construction Of Three-Dimensional Delaunay Triangulations Using Local Transformations // Computer Aided Geometric Design. 1991. Vol. 8. Pp. 123-142.

67. Lo S. Volume Discretization into Tetrahedra II. 3D Triangulation by Advancing Front Approach // Computers and Structures. 1991. Vol. 39, no. 5. Pp. 501-511.

68. Lohner R. Generation Of Three-Dimensional Unstructured Grids By The Advancing Front Method // Proceedings of the 26th AIAA Aerospace Sciences Meeting, Reno, Nevada, 1988.

69. Owen S. A Survey of Unstructured Mesh Generation Technology // Proc. of 7th Int. Meshing Roundtable, Oct, 1998. Dearborn, MI. Pp. 239-269.

70. Rassineux A. Generation and Optimization of Tetrahedral Meshes by Advancing Front Technique // International Journal for Numerical Methods in Engineering. 1998. Vol. 41. Pp. 651-674.

71. Rivara C. M., Vemere M. Cost analysis of the longest-side refinement algorithm for triangulations // Engineering with Computers. 1996. no. 3-4. Pp. 224-234.

72. Shewehnk J. R. Delaunay refinement algorithms for triangular mesh generation // Computational Geometry. 2002. Vol. 22. Pp. 21-74.

73. Skopina M. Multiresolution Analysis of Periodic Functions // East Journal on Approximations. 1997. Vol. 3, no. 2. Pp. 203-224.

74. Strang G. Wavelets and dilation equations: a brief introduction // SIAM Rev. 1989. Vol. 31. Pp. 614-627.

75. Strang G., Fix G. Fourier Analysis of the finite element method in Ritz-Galerkin Theory // Stud. Appl. Math. 1969. Vol. 48, no. 3. Pp. 265-273.

76. Xu J., Zhou A. Some multiscale methods for partial differential equations // Contemporary Mathematics. 2002. Vol. 306. Pp. 1-27.

77. Yserentant H. Two preconditioned based on the multi-level splitting of finite element spaces // Numer. Math. 1990. Vol. 58, no. 2. Pp. 163-184.