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

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

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

Зимин Александр Владимирович

О ВСПЛЕСКОВЫХ РАЗЛОЖЕНИЯХ ПРОСТРАНСТВ СПЛАЙНОВ

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

АВТОРЕФЕРАТ ии344С152

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

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

003446152

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

НАУЧНЫЙ РУКОВОДИТЕЛЬ

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

ОФИЦИАЛЬНЫЕ ОППОНЕНТЫ

доктор физико-математических паук, профессор Вагер Борис Георгиевич

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

ВЕДУЩАЯ ОРГАНИЗАЦИЯ

Научно-исследовательский вычислительный центр Московского государственного университета им М В Ломоносова (НИВЦ МГУ)

Защита состоит« я 2 октября 2008 г в 15 час ов на ча< едании дш < ертацион-ного совета Д 212 232 49 по защите докторских и кандидатских диссертаций при Санкт-Петербургском государственном университете по адресу 198504, Санкт-Петербург, Петродворец, Университетский пр , 28, математико-меха-нич('( кий факультет, ауд 405

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

Автореферат разослан " " СО^^иг^л 2008 г

Ученый секретарь

диссертационного совета, профессор А А Архипова

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

Актуальность темы Теория всплесков (вэйвлетов) появилась полтора десятилетия назад и интенсивно развивается Большой вклад в развитие этой теории внесли ученые И Добеши, И Мейер, С Малла, Г Стрспг, Ж Баттле, П Ж Лемарье, Ч 4>и, Р Койфман, В Свелденс, С Б Стечкин, В А Рвачев, И Я Новиков, В Н Малоземов, А П Петухов, М А Скопипа, Е Е Тыртышников, Ю К Демьянович, И В Оселедс, В А Желудев и др Вэйвчеты широко применяются при решении задач вычислительной математики и цифровой обработки сигналов Как правило, в подобных задачах требуется найти коэффициенты разложения функции но некоторому базису с целью извлечения информации о функции, для последующей обработки или анализа В теории вэйвлетов изучаются различные базисы, посчсдовательности базисов, посчсдоватсчыгости вложенных пространств, а также алгоритмы преобразования коэффициентов разчожений функций по этим базисам Вложенность позвочяет получить представление исходного пространства в виде, прямой (а иногда и ортогональной) с>ммы его подпространств

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

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

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

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

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

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

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

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

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

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

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

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

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

Апробация работы Полученные результаты обсуждались на семинарах кафедры параллельных алгоритмов (2005-2008 гг), кафедры вычислительной математики (2008 г) и докладывались на XXXVIII международной научной конференции "Процессы управления и устойчивость", С-Петербург, 10-13 апреля 2006 г, и на конференции "Космос, астроно- ' мия и программирование" (Лавровские чтения), С-Петербург, 20-22 мая 2008г

Публикация результатов По теме диссертации опубликовано 5 работ В работе [1] научному руководителю принадлежит идея построения всплескового разложения с помощью биортет опальной системы, соискателю принадлежат вывод формул декомпозиции и реконструкции и фактическое построение всплескового разложения В статье [3] научному руководителю принадлежит идея построения вэйвлетного разложения, соискателю принадлежит построение всплескового разложения сплайнов эрмитова типа и вывод

расчетных формул декомпозиции и реконструкции В статье [4] научному руководителю принадлежит идея построения оснащения клеточного подразделения, соискателю принадлежит реализация вэйвлетного разложения для к>сочно-носюянных сплайнов Работа [1] опубликована в журнале, имеющемся в перечне ВАК на момент публикации

Структура и объем работы Диссертация объемом 101 страница состоит из введения, четырех глав и списка литературы, а также одной таблицы и 5 рисунков

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

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

В первой главе рассматриваются всплесковые разложения пространств сплайнов лагранжева тина Пусть % - множество цечых чисел, обозначим п тп множество целых чисел от п до гп включительно На вещественной оси К рассмотрим бесконечную сетку узлов X = х] < дчя которой 1ш1 х, = а, 1нп х, = /3, здесь не исключают-

*-оо .7—*+оо

ся случаи, когда а = —оо, /3 = +оо Линейное пространство функций, I раз непрерывно дифференцируемых в точках открытого интервала (а,/3), обозначим С1(а,/3) Рассмотрим полиномиальный сплайн второй степени ш3, определяемый однозначно (с точностью до некоторой ненулевой константы) условиями и3 £ С1 (а, /3), эирр = В про-

странстве С1(а,Р) рассмотрим линейные функционалы д'1', г 6 2, определяемые формулой

(д{'\и) = и(х1+1) + ±(х,+2-х1+1)и'{х1+1), иеС\а,0) (1)

Система функционалов д = {</''},биортогональна системе функций ш = (при

указанном в диссертации выборе функции = <5У Удаляя узел хк из сетки

X, положим х3 = X], ] < к, х3 = х]+1, } ^ к, и рассмотрим новую (укрупненную) сетку X = {хг}1£х Обозначим и, полиномиальный сплайн второй степени на сетке X с носителем [х,,х,+з] из пространства С1 (а,/3), а за й'1' обозначим функционал, опредечяемый формулой, полученной из (1) заменой х} на х3, таким образом (д^1',^) = 5,} Справедливо представление

= (2) где числа 4) отыскиваются по формулам

¿ч = I г < к — 3,

4-з, к-3 = 1: 4-з,к-2 = ————, 4-3,; = о, ] (£к-3 к- 2,

Хк+1 - Хк—2

Хк — Х^-2 , Хь+1 — Хк I

<1к-2к-2 = -, 4-2 4-1 = -, 4-2,1 = и, ] ф. К — I К — 1,

Хк+1 ~ Хк-2 Хк+2 ~ Хк-1

4-1 к-1 = ---Ц 4-1,*; = 1, 4-1,;, = 0, ] к - 1 к,

Хк+2 ~ Хк-1

4 = г > к - 1

Соотношения вида (2) называются калибровочными соотношениями

Рассмотрим пространство V(X), являющееся линейной оболочкой функций ш3,

Т(Х) = | и | и = ^djWj, a,j £й|, j

и пространство

Р{Х) = {й\ а, eK}

i

Ввиду калибровочных соотношений справедливо включение V{X) С V{X) Введем оператор Р проектирования пространства V(X) на подпространство V{X)

Pu = YJ(9b\u)üJ, ueV(X),

j

и оператор Q = / — Р, где I — тождественный оператор Пространством всплесков (вэй-влетов) называется пространство VV = QV{X), а получаемое прямое разложение

V{X) = P(X) + W

называется сплайн-вэйвлетным разложе7шем пространства V(X) Доказывается, что пространство W одномерно, и что W = | 6j._i е М}

Пусть известны коэффициенты й, и 1 в разложениях проекций элемента и е PC-Y) на пространства V(X) и VV Для чисел а, получаем формулы реконструкции

dj = äj, j ^ k — 3, ®k-2 = <4-2 k -2 + <4-2 ifc-1 ak-l, ik-1 = dk-i,k-\ Qifc-i + cffe-i,fcßfe +

dj — dj-i, J ^ k

Если же известны коэффициенты а} в разложении элемента и € "Р(Х) по базису V(X), то а, = а,, г^к — 3, а, = а,+1, г ^ к — 1,

- хк .тА_2 -

а/с-2 =-«fc-j Н--ßfc-2,

xfc_2 - Zfc-2 - Zfc

Ь,=0, jjifc-1,

bk-1 = d/t-1 — {dk-2,k-l(lk-2 + dfc-l.k-lfl/fc-l) =

= öfc-l — (dk-2,k-l(gk-2,k-1ak-3 + 9k-2,k-2ak-2) + dk-l,k-lak),

эти формулы называются формулами декомпозиции

Далее на сетках А" и Л" рассматриваются полиномиальные кубические сплайны ш} и Wj, однозначно (с точностью до ненулевых постоянных множителей) определяемые условиями Uj,bJj G C2(a,ß), supp Uj = [xjjXj+h], supp £>_, = [xj,xj+4], между и 25, имеются калибровочные соотношения, аналошчные рассмотренным выше Вводятся также системы функционалов д = {<?'''} и д = {s'1'}, биортогональные системам функций {ш^} и {со,} соответственно, строится всплссковос разложение Р(Х) = P(X)-|-VV пространства выводятся формулы реконструкции и декомпозиции Аналогичным образом рассматривается случай периодических кубических сплайнов на (вообще говоря, неравномерной) периодической сетке Далее доказываются теоремы об устойчивости и аппроксимации

Теорема 1 (об устойчивости) Для любой сетки X верно неравенство

max|a,| ^ тах|а,| + |bj._i|, jez tez

а если сетка X локально квазиравномерна, m е удовлетворяет наравенству j¡ ^

^ M при некотором M ^ 1, справедлива оценка

шах |й,| < (2Л/3 + 2М2 + 2М + 1)шах|о,|

jez iez

Теорема 2 (об аппроксимации в С) Если / G С4(а,/3), [xk,xk+i] С (а,/3) и u(t) = f) tjjj(t), то при t 6 верна оценка

jez

|/(t)-«i(t)l «S max |/(4)(0I-

(фк-2 Util

где h = Xk+з ~ Xk-2

Теорема 3 (об аппроксимации в L2) Если / £ IV^a,/?), [х*_2, i/t+i] С (а,/5), u(¿) =

2 /) mo верпа оценка

jez

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

+ (р]+1 ш2;(0) = ф),

]

вирр (¿2,-1 С [¿„Х,+2}, яирр Ш2} С [х},Х]+2],

где 1^(4) — четырех-компонентная вектор-функция класса С1(а, /3), удовлетворяющая при х, у £ (о, /3), а: ф у, условию

Щх, у, р) = с!е%(:г), </(*), /Ы) Ф О, (Л)

а ^ = (аг^), ^ = х}) При сформулированных условиях функции определяются однозначно из аппроксимационных соотношений и могут быть продолжены по непрерывности на интервал (а,/3) до функции класса С1 (а,0), кроме того выполнены интерполяционные соотношения ,

= 1^2,-1(^+1) = 0, ш2,_1(х,+2) = О,

"г,-^1?) =0, " 2,-1(^9+1) = -1(^+2) = 0,

= 0, Ш2д(хд+1) = 1, М2д(Хд+г) = 0,

Ш2«г(^)=0. = 0, =°>

Пусть ^ € (х/с, х/с-ц), введем обозначения х_, = у ^ к, х^+1 = х, = ] > к + 2, А* = Аналогично предыдущему построим функции на сетке X

Теорема 4 Если выполнено условие (А), то при Ь 6 (а, /?) справедливы калибровочные соотношения

где

= 5г], г ^ 2к — 4, = <5М_2> г ^ 2А: + 1,

= ¿2к-2 } = &2к-2 ],

] Ф 2к — 1,2к,

¿2к-3,2к-\ = ш2к-зЮ> Фгк-3,2к = ш2*-з(0>

Лгк-2,2к-1 = <^2к-22к = ^2/с-2(£)>

= ¿2к-1.,2к = ш2*:-1(£)> d2i.2A.-l = ¿2к,2к = Ь>2кШ

Далее в диссертации вводится система линейных функционачов г/1' над С'(а,/3) согласно формулам = и'(х?+1), = д е 2 Вычисчяются чисча 9ч = и устанавливается, что матрица С = является левой обратной к матрице где Ю = {(11])г]ех На основании упомянутых результатов получается всплес-ковое разложение пространства

= { -и | и = ^^а^ал,, а, £ К }

в прямую сумму пространства

= { и | и = ^ а^ ш,, а^ е К }

и двумерного вэйвлетного пространства УУ = { Ь2к-1^2к-1 + Ь2к^2к | ЬгА-ъ Ь2к £ К }

Теорема 5 (формулы декомпо зиции) Для всплескового разложения справедливы следующие соотношения

а,=а„ г^2к — 2, а, = а1+2, г^2к—1, Ь} = 0, ]^2к — 1,к,

Ь2к = &2к — ^2к-з{0 &2к-3 ~ ^2к-2(0^2к-2 ~ ^2к-1 (5) — Ш2к{0^к+2

Теорема 6 (формулы реконструкции) Для всплескового разложения формулы реконструкции имеют вид

а3 = а], } ^ 2к — 2, а, = ] ^ 2к + 1,

а2к-1 = Ь2к-1 +а»2*_з(0 а2к-3 + ш'2А._2(£)а2к-2 <12*:-1 Ш 2А:(С) а2/с,

= ь2к + Ш2к-з{0 0.2к-3 + ^2к-2(Оа2к-2 + (?) а2*-1 + Я21с

Далее рассмотренные формулы конкретизируются для случая <р = (1, £, t2, t3)T, который соответствует полиномиальным эрмитовым сплайнам

В третьей главе рассматривается всплесковое разложение на гладком многообразии Пусть покрытие мноюобразия Ш задано семейством множеств в = {6j}j(Ej, каждое из которых гомеоморфно открытому n-мериому шару и имеет кусочно-гладку ю границу Буквами 1,J,K.~ будем обозначать некоторые упорядоченные индексные множества Для каждой точки £ £ ЯЛ обозначим содержащее ее множество £(() = Совокупность

€ различных множеств <Г(1) конечна или счетна В дальнейшем будем обозначать их Сд., к & К. Итак, C = {Cfc|A;e£} Справедливы соотношения Л = 0, к', к" G 1С, к' ф к",

С1(в3)= (J Cl(Ck), Ci(lJCt) =СЦЭП)

IkCSj к£К.

где симвоч С1 означает замыкание Для фиксированной точки £ £ ЯЛ мощность к, множества { j [ £ 6 6j } называется кратностью накрытия точки £ семейством в Пусть существует натуральное число к такое, что почти для всех точек £ £ ЯЛ енраведтиво равенство Kt = /с, тогда семейство © называется к-иакрывающим Если для почти всех точек £ £ ЯЛ система вектров Ащ = { | £ £ } является базисом пространства К', будем говорить что семейство подмножеств в = {S_,}_,(= j многообразия ЯЛ оснащено q-полпой системой векторов А = { а; | j 6 J, aj 6 R'} В этом случае система векторов А называется g-полным оснащением семейства S

Для д-пакрывагощего семейства в д-полное оснащение А называется просто полным оснащением Для полного оснащения А введем обозначение At = Лу), i 6 Рассмотрим вектор-функцию <р ЯЛ —> Mm+1 с компонентами из пространства Х(ЯЛ)

Теорема 7 Пусть в = {SjJjej- - m + 1 -накрывающее семейство, а система вектор-столбцов А = {zjjjzj - полное оснащение семейства © Тогда существует единственная вектор-функция (столбец) ш(£) = t 6 ЯЛ, почти везде удовлетворяющая соотношениял1

иТА = у, (3)

u3(t) = 0, J€j (4)

Соотношения (3)-(4) называются аппроксилшционнъши, линейная оболочка функций ¡¿jj, j £ J", пространством (Л, tp, 6)-сптайнов

Теорема 8 Пусть & и © - т + 1 -нарывающие семейства, а системы вектор-столбцов А = {aj}jej и А — {а,},е1 - соответствующие полные оснащения Если матрица D такова, что DТА = A, [Dlj],(£) = 0, £ ф 6,, г £ I, то

5=Dw (5)

где [<р\, обозначает г-ю компоненту вектора tp 1

Следствие Пусть система функций и = линейно независима и имеется биор-

тогоналъная к ней система функционалов g = guF = I Тогда D = (дй>Т)Т

В пространстве Х(ЯЛ) рассмотрим две линейно независимые системы элементов и> = И<^ = Положим

V — | и I и = ^^ OjUij, а^ 6 r| , 7> = j й I и = ^^ oJj, а, £ к|

1 £J tez

Пусть выполнено соотношение (5), так что РС?иР = Р+И' Обозначим д = {з^'Ье^ и 9 — системы функционалов, биортогоналыгые ш и ш дшт = дшт = I

Теорема 9 Пусть функционалы длинейно продолжены на пространство V, тогда матрица в = ди)Т является левой обратной к матрице

Теорема 10 В условиях теоремы 9, пусть элемент и 6 V записан в виде суммы и = и + ю, й & Т, и) £ У\> Тогда для векторов а, а и Ь, определяемых равенствами и = и>Та, й = йта, гп = штЬ, справедливы формулы декомпозиции

а = Со, (6)

Ъ = а - ОтС а (7)

и формулы реконструкции

а = ЪТа + Ь (8)

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

Остальная часть третьей главы посвящена построению всплесконого разложения пространств курантова типа Рассмотрим (при т = п) п+ 1-компонентную вектор-функцию класса С"(П), где П - область в К" Будем считать область П симшгациалыю подразделенной, пусть Т = {тр}ре/с — соответствующий симплициальпый комплекс (возможно, криволинейный) с конечным или счетным множеством открытых га-мерных симплексов Множество вершин (нульмерный остов комплекса) обозначим X, а сами вершины х, г £ 3, множество X называется сеткой, а вершины х, — узлами этой сетки Множество индексов, соответствующих вершинам симплекса тр обозначим Зр = {г | х, 6 С1(тр)} На каждом симплексе тр введем локальную нумерацию с помощью взаимно однозначного отображения у О п->1 Положим

г

= йе^^х^о)), <р(хХр(1)), , ¥>(Ххр(п))).

^р.М=^(»з(хХр(о)),¥(хХ1(,)), Мххры) II "¥>М), 1 = 0 п,

где символ || " </?(!) означает замену г-го столбца (,)) в рассматриваемом определителе на столбец Предположим, что выполнено условие

3 е > 0 такое, что для любого симплекса тр € Т, |4р1 ^ £ (В)

Рассмотрим функции определяемые соотношениями

, ^(х,)^)^), ьетр,{ (9)

!€jp

= 0, (10)

Из предположения (В) следует, что функции ш,^) однозначно определены на всех симплексах тр, так что

ич Г^.р.х-Ч'К4)/ * е Тр С в„

= \ " , I11

[О, tф6¡

Обозначим П,1р первую частную производную функции ф по г-й координате [х], переменной х Пусть Д;(хо) = { х | ||х — х0||и» < <5}, в случае, когда положение центра шара значения не имеет, используется обозначение без указания его центра Предположим, что выполнено условие

3 г > 0, что | <3е%^), А ¥>(*)> , ^ е, Vt € СЩ (Сс)

Лемма 1 Если е СЧ(С1{П)), 5 > 1, С7(П) — компакт, и выполнено условие (С£), то каково бы пи было число с > 0, существует <5 = 5(е, с) > 0 такое, что при любых векторах Хо,х1; , х„ е П П, удовлетворяющих неравенству | det(x1 — Хо, Х2 — Хо, ,х„—х0)| ^ с&", верно соотношение | скЧ(^(хо), ^(Хп))! ^ §

Введем множество С. = { 1 6 К" | с1е1((^(<;), ¥>(хо), , </?(х:„-1)) = 0 }, и вектор g, такой что

йтх = йе1(х,х! - х0, х2 - х0, ,х„_1-х0), V х 6 К"

Лемма 2 Если у 6 С3(С1(Л)), 5 > 1, С1(С1) — компакт, выполнено условие (С£), то для любого с > 0 существует 5 = <5(е,с) > 0, что при любых векторах х0, XI, , х„ 6 Д;ГШ, удовлетворяющих неравенству | | > с й"-1, лшоэ/сссгпво С П В/ П представляет собой простую п — 1-мерную поверхность класса Cs (т с 5-диффеоморфную п — 1-мерному шару)

Пусть т — п-мерный прямолинейный сичптекс с вершинами Хо,Х], ,х„ Радиусы вписанного и описанного шаров для симплекса Т обозначим гт и Ят соответственно Введем условие

3 ,, > 0, что > 7? (Д,)

т

На основании упомянутых вспомогательных утверждений устанавливаются следующие теоремы

Теорема 11 Если ¡р £ С®(С7(П)), 5 > 1, С1(С1) компакт, и выполнено условие (СЕ), то каково бы ни было г] > 0, найдется 5 = 5(е, г/) такое, что для любого прямолинейного симплициалъного подразделения Т, все п-мерные симплексы т которого удовлетворяют условию (О?,) и неравенству II <5, существует криволинейное симплициальное подразделение Т с теми оке вершинами, криволинейные симплексы т которого определяются п — 1-мерными гранями класса С5, задаваемыми аналогично С.

Теорема 12 Пусть в условиях теоремы И выполнено условие (В), тогда на криволинейном симплициальном подразделении Т функции и)3 определены и непрерывны в области С1{П)

Из условия (СЕ) слезет, что система функций [</?],, г € 0 тс, линейно независима на любом симплексе тр подразделения Т, благодаря этому система функций также

является линейно независимой Система функционалов заданная на простран-

стве С(Г2) формулами {д('\и) = и(х,), г 6 ¿7, и 6 С(С1), биортогональна системе функций

НЬ £3 _

Рассмотрим симплициальное подразделение Т = {тч} области П, которое является измельчением подразделения Т Для Т рассмотрим построения, аналогичные тем, которые были сделаны для Т Нульмерный остов (множество вершин) симплициального комплекса Т обозначим X, а сами вершины — символами хл 6 ¿Г Множество индексов,

соответствующих вершинам симплекса т„ обозначим Jq На каждом симплексе т9, как и прежде, вводится локальная нумерация с помощью биекции г) 0 п —» Jq Положим

dv,q = det(v(x,î(0)), ¥>(х,ч(1)), ,

<W(X) = det o)),y(x,,(i)), ,<Р{Щ,м) Il " vW)

Рассмотрим функции ZUj (t), определяемые соотношениями

5^¥»(xJ)57J(t)=¥>(t), ter,, ¡3,(1) = 0, } ej.

При сделанных предположениях функции ûJ,(t) определяются однозначно,

?,ч_10) W/ ^<Л9> t S г? С в,,

= , -' 0,

и непрерывны в области П

Рассмотрим систему функционалов {э'1'},^, заданную на пространстве С(П) формулами (1,г») = «(х,), г € ¿7, и 6 С(Г!), = 8г], г,] € 3 Введем вектор-столбцы ^ = д = Ъ = 9 = (э0")^;?. отображение г/ так что х7 = х„0), и рассмотрим матрицу Б = (дшт)т

Теорема 13 В условиях теоремы 11 для систем ш, и справедливы калибровочные соотношения

формулы декомпозиции (6)-(7) могут быть записаны в виде

а, = «,?(>)> Ь3 = а3- ^ {дь}, ш,) ] е ¿Г,

а формулы реконструкции (8) в виде

Теоретические результаты проиллюстрированы на нескольких модельных примерах Рассмотрен двумерный случай В плоскости М2 симплициалыюе подразделение представляет собой триангуляцию Предположения теоремы 11 принимают вид £>1<р(х), £>2</>(х)) ^ £ > 0, х е С1(й) Устанавливаются некоторые вспомогательнвые утверждения, которые позволяют установить необходимые и достаточные условия отличия от нуля угла между кривыми рассматриваемой криволинейной триангуляции Рассмотрен иллюстративный пример с использованием функций Куранта Здесь вычисляются коэффициенты матрицы декомпозиции дг] = о7;(х,), г Е 3, ] 6 3,

(о, ге3,зе3\3, 9%3 I «а

à3i =

x3 i /ni(6,), iej,j£j, xj 6 Int(e,),

Элементы ¿^ матрицы имеют вид

0 * ^

1 г=]

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

Четвертая глава посвящена реализации всплескового сжатия на некоторых модечьпо-го примерах в одномерном случае В первой части этой главы рассматривается алгоритм укрупнения исходной сетки В качестве исходной бралась равномерная сетка х3 — Предложены формулы для количества удаляемых узлов мелкой сетки {х3} За каждым сохраняемым узлом хд следует сохраняемый узел х1+§ исходной сетки, таким образом, уз ты в количестве 5 — 1 удаляются Укрупненная сетка х, выбиралась таким образом, чтобы "степень ее густоты' была пропорциональна производной (или разностному отношению) исходной функции (соответственно, числового потока) Дчя чиста 5 предчожены различные формулы Самый простой вариант дает формула

S =

lb \f'(x)\dx Mh\f'(x)\

1де (а, Ь) - интервал, на котором предполагается сохранить M узлов укрупненной сетки В другом варианте рассматривается формула, основанная на использовании интегрального среднего Здесь рассматривается количество £(с, d) удаляемых узлов на интервале (с, d) С (а,Ъ), где

S{c d)~

К возможным неприятностям с использованием предыдущих формул относятся случая когда f(x) постоянна В этих случаях заменатель может обратиться в ноль, поэтому рассматривается модификация этих формул вида

S" =

С

Г

\qh h

x+qh

\nm+j

где где х — рассматриваемая точка, Р — относительное кочичество сохраняемых узлов (О < Р < 1), h — шаг исходной мелкой сетки, h > 0, q — параметр усреднения (q ^ 1), определяющий длину промежутка усреднения (эта дчина равна ah ^ 0), g — параметр (целое число, g ^ 1) , характеризующий максимальное количество единовременно удаляемых узлов (это количество в дальнейшем полагается равным д), С = J-6 \f'(t)\dt, эта константа решающего значения не имее'г В соответствие с последней формулой прибчи-жепное значение S для S* определяется по формуче

S =

С

Р ( ± V

- \ я ¿>J=i

1+5-1

\fbh) i + f;

-1 Ч/'Ы!,

где г Е 0 N—1 — номер рассматриваемого узла сетки X = дг, С ~ к

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

Входной поток образуем с помощью чисел а3, а3 = и 6 С1 (ct,/3) Функцию

u{t) назовем функцией, генерирующей числовой поток {а,} или просто - генерирующей функцией

В проведенном численном эксперименте рассматривался отрезок [0,7г] (а = О, Ь = 7г), исходная сетка X = {xj} бралась равномерной, Xj = jh, а сетка X - неравномерной Сетки строились с тем расчетом, чтобы во внешности рассматриваемого отрезка [а, Ь] имелось по крайней мере по три сеточных узла справа и слева от него

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

Рассмотрены два подхода к исследованию эффективности предложенного алгоритма Первый подход состоит в том, что исходной является аналитически заданная или таблично заданная функция }(t) (в последнем случае таблица должна быть настолько плотной и точной, чтобы такое задание в пределах необходимой точности давало бы тот же результат, что и аналитическое, в частности, первые производные должны вычисляться но разностям с большой точностью) Первым шагом алгоритма является аппроксимация па исходной равномерной сетке и оценка нормы уклонения сплайна от функции /(i) Второй шаг — укрупнение сетки, получение основного и вэйвлетного потоков по формулам декомпозиции Третий шаг построение сплайна по основному потоку, приближенное восстановление входного потока по построенному сплайну, оценка уклонения этого потока от генерирующей функции f(t) Четвертый таг — восстановченис входного потока по формулам реконструкции, оценка уклонения резутьтата восстановления от входного потока

При втором подходе предполагается, что после генерации входного потока х^енерирую-щая функция /(£) становится недоступной Последовательность действий в этом случае та же самая но вместо оценки уклонения от генерирующей функции рассматривается оценка уклонения от сплайна, рассмотренного на первом шаге

В качестве генерирующих функций брались функции t\ —sm(t), szn(lOi) Число узлов исходной сетки во всех случаях равнялось 1200, число узлов укрупненной сетки колебалось от 120 до 150 Коэффициент сжатия входного потока, те отношение объема выходного потока (в байтах на диске) к объему входного потока, колебался от 0 11 до 0 15 Полученные численные результаты показали полное согласие с полученными в работе теоретическими результатами

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

|)| JU мьлновлч 10 К, Знмнн Л J3 И< iuu t юно/ (н >uhju mili» ) рилом t юн прттрни шн ш ¡motlivii i ли/ J)-< платит второй i пи ш на ни ui равном* рнои 11 шк< ^ Нес шикС'Пб-l'V Серии 1 Иьшу< к i ¿0()(> ('72-77

[2| Зимни ABO построении вэйвлет-разложспия на nepuotkmccKou неравномерной сетке // Тр 37-и между н научной конф аспирантов и студентов СПб , 10-13 апреля 2006 г / Под ред А В Платонова, Н В Смирнова - СПб , Изд-во С-Петерб ун-та, 2006 С 150-155

[3] Демьянович Ю К , Зимин А В О встыесковом разложении сплайнов эрмитова типа // Проблемы матем анализа 2007 Т 35 С 33-45

[4] Демьянович Ю К, Зимин А В Взйвлетные разложения на многообразии // Зап на>чн семин ПОМИ, 2007, Т 346 С 1-13

|Г>| Зи\:нн А В И Н1НЛ1 т пая (илт, oí ■повинная на u.nnjint.f плтцни ьуби'к i ьилш Н-( илпипамн на w равшни'риои ниш // Об Меюды вы чис пении - СПб И-»д-вч (МКчерб vh-ы ¿008 T2Í С4 Г>(>-ТЛ

Подписано в печать 06 08 08 Формат бумаги 60 х 84 'Дб Бумага офсетная Гарнитура Тайме Печать ризографическая Уел печ я 1,0 Тираж 100 зкз Заказ 4268 Отпечатано в отделе оперативной полиграфии химического факультета СПбГУ 198504, Санкт-Петербург, Старый Петергоф, Университетский пр 26

Введение

1 Всплесковое разложение пространств сплайнов лагранжева типа

1 Всплесковое разложение пространств сплайнов второй степени

2 Аппроксимационные соотношения для кубических сплайнов

3 Биортогональная система функционалов.

4 Калибровочные соотношения.

5 Всплесковое разложение.

6 Формулы реконструкции и декомпозиции.

7 Случай периодических сплайнов.

8 Оценки устойчивости

9 Оценки аппроксимации.

2 Всплесковое разложение пространств сплайнов эрмитова типа

1 Сплайны эрмитова типа.

2 Калибровочные соотношения для сплайнов эрмитова типа

3 Биортогональная система функционалов.

4 Всплесковое разложение.

5 О формулах декомпозиции и реконструкции для эрмитовых сплайнов.

3 Всплесковое разложение на многообразии

1 Определения и обозначения.

2 Пространство сплайнов на многообразии.

3 Калибровочные соотношения.

4 Формулы реконструкции и декомпозиции.

5 О биортогональной системе.

6 Всплесковое разложение пространств кусочно-постоянных сплайнов.

7 Полное оснащение симплициального подразделения.

8 Функции курантова типа.

9 Вспомогательные утверждения.

10 Криволинейное симплициальное подразделение и непрерывность функций курантова типа.

11 Измельчение симплициального подразделения и калибровочные соотношения

12 О матрицах всплескового разложения пространств аппроксимаций курантова типа.

13 Некоторые замечания в случае плоскости.

4 Реализация всплескового сжатия

1 Алгоритмы выбора сетки.

2 Описание численных экспериментов.

Теория всплесков (вэйвлетов) появилась полтора десятилетия назад и интенсивно развивается. Ключевой работой в этой области принято считать книгу И. Добеши [1]. Большой вклад в развитие этой теории внесли учёные: И. Мейер, С. Малла, Г. Стренг, Ж. Баттле, П. Ж. Лемарье, Ч. Чуй, Р. Койф-ман, В. Свелденс, С. Б. Стечкин, В. А. Рвачев, И. Я. Новиков, В. Н. Малозёмов, А.П. Петухов, М.А. Скопина, Е. Е. Тыртышников, Ю.К.Демьянович, И. В. Оселедс, В. А. Жёлудев и др.

Вэйвлеты широко применяются при решении задач вычислительной математики и цифровой обработки сигналов. Как правило, в подобных задачах требуется найти коэффициенты разложения функции по некоторому базису с целью извлечения информации о функции, для последующей обработки или анализа. В теории вэйвлетов изучаются различные базисы, последовательности базисов, последовательности вложенных пространств, а также алгоритмы преобразования коэффициентов разложений функций по этим базисам. Вложенность пространств Vi С К'+ь позволяет ввести подпространства Wi С Vi+1 так, что Vi+1 может быть представлено в виде прямой (а иногда и ортогональной) суммы: 1 = Wi + Vi. Всплесковым (вэйвлет-ным) разложением пространства Vi+i называется разложение вида V{+i = Wi+. .'+Wi-S.\-Vi-S. Обычно пространство Vi рассматривают как несущее основную информацию о функции, a Wi как несущее уточняющую информацию.

Классические подходы к построению вэйвлетного разложения связаны с использованием преобразования Фурье и кратно-масштабного анализа (см., например, [1]-[8]), а также теории сплайнов ([9]-[19]). Преобразование Фурье эффективно для равномерной сетки, однако при обработке сигналов с резко меняющимися характеристиками целесообразно использовать неравномерную сетку, приспосабливаемую к обрабатываемому потоку. Для неравномерной сетки вэйвлеты рассматривались в работах [20], [23]-[26], [30], [34]. Весьма важны случаи, когда исходные данные естественным образом связаны с некоторым многообразием (примерами могут служить цифровые потоки значений мощности излучения от поверхности тел различной формы: сферической, тороидальной и др.)

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

Приведём пример, связанный с обработкой информации от чёрно-белого изображения. Пусть упомянутое изображение имеет К = т х п пикселей, где т - количество строк, п - столбцов. Каждому пикселю приписывается определённая яркость, так что, занумеровав пиксели по строкам, получим числовую последовательность: со,., ск-1- Если К велико, то передача изображения по каналу связи может занять много времени. В связи с этим, возникает задача уменьшения количества передаваемых чисел. Пусть К = 2L; предполагая что соседние числа близки, можно было бы передавать, например, только числа с нечётными номерами: с1,сз,. ,C2L-i- В таком случае, приёмное устройство расширяет полученый числовой поток дублированием принятых значений так, чтобы в результате на местах с чётным и со следующим нечётным номером находились одинаковые числа. В результате на экране воспроизводится изображение, полученное с помощью числового потока вида ci, ci, сз, сз, С5, сз, С7,., C2L—I1C2L-1- Тем самым «восстановление» исходного потока производится с погрешностью, причём информация теряется необратимым образом (т.е. без передачи дополнительной информации приёмное устройство, вообще говоря, не в состоянии восстановить исходный поток). Такой приём (английский эквивалент downsampling - сгущение) оправдан, если полученное изображение мало отличается от исходного.

Недостатки описанного подхода состоят в следующем: 1) он применим лишь к достаточно медленно меняющемуся потоку, 2) отсутствует учёт характеристик числового потока (в некоторых частях числовой поток может меняться очень медленно, и можно было бы выбрасывать много чисел подряд, а в других частях при быстром изменении потока любые выбрасывания чисел могут существенно испортить передаваемое изображение), 3) нет средств для уточнения передаваемого потока.

Идея вэйвлетного подхода иллюстрируется следующим образом. Из исходного числового потока формируется два числовых потока а. = з^зщ ^ (1)

6j = C2,72J+1, j = 0.L- 1. (2).

Нетрудно видеть, что c2j = Qj 4- bj, c2j+1 = aj -bj, j = 0,., L - 1. (3)

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

Общее количество чисел в потоках (1)-(2) и (3) совпадает, однако заметим, что если соседние числа в исходном потоке близки, то поток (2) состоит из чисел, близких к нулю, так что может оказаться, что этот поток вообще не нужен и его можно отбросить. Если некоторые фрагменты потока (1) не дают достаточной точности, то можно использовать соответствующие фрагменты (с теми же диапазонами индексов) потока (2), и произвести расчёты по формулам (3); это приведёт к точному восстановлению исходного потока на соответствующих участках (подобная технология передачи используется, в частности, при передаче изображений в Интернете: сначала появляются основные контуры изображения, позволяющие оценить его содержание и прервать передачу, если в ней нет необходимости, и лишь затем происходит уточнение, и окончательное завершение передачи изображения). Поток чисел (1) называют основным, а поток (2) — вэйвлетным (всплесковым) потоком. Полученный основной поток можно рассматривать как сжатие исходного потока, а поток (2) как поправку к основному потоку, позволяющую восстановить исходный поток.

Если поток (1) ещё велик для передачи, то аналогичной процедурой его расщепляют на два потока: новый основной поток и соответствующий вэй-влетный поток. Возможно дальнейшее продолжение процесса расщепления; на к-м шаге получим расщепление исходного потока на к + 1 потоков: основной и к вэйвлетных потоков, последовательное добавление которых к основному потоку приводит к последовательному уточнению результата сжатия вплоть до полного восстановления исходного потока. Излагаемая методика похожа на разложение по формуле Тейлора, где производные заменены соответствующими разностями. Такой процесс расщепления иногда применяют и к упомянутым вэйвлетным потокам; получающийся результат называют вэйвлет-пакетом.

Цель- диссертационной работы состоит в том, чтобы

1. построить пространства сплайнов лагранотева и эрмитова типов на неравномерной сетке и сплайнов на многообразии на основе аппрокси-мационных соотношений;

2. построить вэйвлетное разложение и получить формулы декомпозиции / реконструкции в упомянутых случаях;

3. установить оценки устойчивости и порядка аппроксимации;

4■ представить результаты апробации теоретических результатов на модельных примерах.

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

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

1. 1. Daubechies Ten Lectures on Wavelets. SIAM, Philadelphia, PA, 1992. (Пер. на русский: И. Добеши Десять лекций по вейвлетам. Ижевск: НИЦ "Регулярная и хаотическая динамика", 2004. 464 с.)

2. С. К. Chui An Introduction to Wavelets. Academic Press, NY, 1992. (Пер. на русский: К. Чуй Введение в вэйвлеты. М.: Мир, 2001. 412 с.)

3. S. Mallat A wavelet tour of signal processing. Academic Press. 1999. (Пер. на русский: С. Малла Вэйвлеты в обработке сигналов. М.: Мир, 2005. 671 с.)

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

5. Новиков И. Я., Протасов В. Ю., Скопина М. А. Теория всплесков. М.: Физматлит, 2005. 612 с.

6. Skopina М. Multiresolution analysis of periodic functions./ / East Journal on Approximations. 1997. Vol.3, №2. P.614-627.

7. Петухов А. П. Введение в теорию базисов всплесков. СПб., 1999. 132 с.

8. Малозёмов В. Н., Машарский С. М. Основы дискретного гармонического анализа. СПб.: НИИММ, 2003.

9. Завьялов Ю. С., Квасов Б. И., Мирошниченко В. Л. Методы сплайн-функций. М.: Наука, 1980.

10. Малозёмов В. Н., Певный А. Б. Полиномиальные сплайны. Л., 1986.120с.

11. Schumaker L. L. Spline Functions. Basic Theory. Waley Interscience, NY. 1981. 548 p.

12. Максименко И. E., СкопинаМ.А. Многомерные периодические всплески // Алгебра и анализ (2003), Т. 15. №2. С.1-39.

13. Стечкин С. Б., Субботин Ю. Н. Сплайны в вычислительной математике. М., 1976. 248 с.

14. Малозёмов В. Н., Селянинова Н. А. Прямая лифтинговая схема. // Семинар «DHA & CAGD». Избранные доклады. 26 апреля 2005 г. http://www.dha.spb.ru/

15. Морозов В. А. Теория сплайнов и задача устойчивого вычисления значений неограниченных операторов. // Ж. выч. матем. и матем. физики. 1971. Т. И т. С. 545-558.

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

17. ЖёлудевВ.А. О вэйвлетах на базе периодических сплайнов, j j Докл. РАН. 1994. Ш. С.9-13.

18. Жёлудев В. А., Певный А. Б. Биортогональные вейвлетные схемы, основанные на интерполяции дискретными сплайнами // Журн. выч. мат. и матем. физ. 2001. Т. 41. №4. С. 537-548.

19. Певный А. Б. Дискретные сплайны и вейвлеты: Учебное пособие. Сыктывкар: Изд-во Сыктывкарского университета. 2004. 166 с.

20. J.M.Ford, I.V. Oseleds, Е. Е. Tyrtyshnikov. Matrix approximations and solvers using tensor products and non-standard wavelet transforms related to irregular grids. Rus. J. Numer. Anal, and Math. Modelling. Vol.19, No.2 (2004), 185-204.

21. Оселедс И. В. Применение разделённых разностей и В-сплайнов для построения быстрых дискретных преобразований вейвлетовского типана неравномерных сетках. // Ж. Математические заметки. 2005. Т. 77, вып.5. С.743-752.

22. Тыртышников Е. Е. Методы численного анализа. М., Изд. центр «Академия», 2007. 320 с.

23. Wim Sweldens The Lifting Scheme: A new philosophy in biorthogonal wavelet constructions // Wavelet applications in signal and image processing III. pp. 68-79. Proc. SPIE 2569. 1995.

24. Wim Sweldens, Peter Schroeder Building your own wavelets at home. In "Wavelets in Computer Graphics", ACM SIGGRAPH Course Notes, 1996.

25. Wim Sweldens The lifting scheme: A construction of second generation wavelets. // SIAM J. Math. Anal., 29(2):511546, 1997.

26. Daubechies I., Guskov I., Sweldens W. Commutation for Irregular Subdivision. // Const. Approx., 17(4),(2001). P.479-514.

27. Демьянович Ю.К. Локальная аппроксимация на многообразии и минимальные сплайны СПб, 1994. 356 с.

28. Бурова И. Г., Демьянович Ю. К. Теория минимальных сплайнов. СПб, 2000. 316 с.

29. Демьянович Ю. К. Всплески и минимальные сплайны СПб, 2003. 200 с.

30. Демьянович Ю. К. Всплесковые разложения в пространствах сплайнов на неравномерной сетке. // Докл. РАН. 2002. Т. 382. №3. С. 313-316.

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

32. Демьянович Ю. К. Сплайн-вэйвлетные разложения на многообразии. Проблемы математического анализа. 2007. Т. 36. С. 15-22.

33. Демьянович Ю. К. Калибровочное соотношение для В-сплайнов на неравномерной сетке. // Математическое моделирование. 2001. Т. 13. №9. С. 98-100.

34. Демьянович Ю. К. Гладкость пространств сплайнов и всплесковые разложения. // Доклады РАН. 2005. Т.401, Ж. С. 1-4.

35. Демьянович Ю. К., ЗиминА. В. Всплесковое (вэйвлетное) разложение пространств периодических В-сплайнов второй степени на неравномерной сетке. // Вестник СПбГУ, Серия 1. 2006. №4. С.72-77.

36. Демьянович Ю. К., Зимин А. В. О всплесковом разложении сплайнов эрмитова типа, // Проблемы матем. анализа. 2007. Т. 35. С.33-45.

37. Зимин А. В. Вэйвлетная схема, основанная на аппроксимации кубическими В-сплайнами на неравномерной сетке сб. Методы вычислений. 2008. Т. 23. С.56-73.

38. Демьянович Ю. К., Зимин А. В. Вэйвлетные разложения на многообразии. Зап. научн. семин. ПОМИ, 2007, Т. 346. С.1-13.

39. Макаров А. А. Об одном алгебраическом тождестве в теории В<р-сплайнов второго порядка. // Вестн. С.-Петерб. ун-та. Сер. 1. 2007. Вып. 1. С. 96-98.