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

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

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

Макаров Антон Александрович

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

05 13 18 — математическое моделирование, численные методы и комплексы программ

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

ООЗ шиэо^

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

2007

003160582

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

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

профессор Демьянович Юрий Казимирович

Официальные оппоненты доктор физико-математических наук,

профессор Малоземов Василий Николаевич

доктор физико-математических наук, профессор Репин Сергей Игоревич

Ведущая организация Научно-исследовательский

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

Защита состоится ___ 2007 г в

часов на заседании диссертационного совета Д 212 232 51 по защите диссертаций на соискание ученой степени доктора наук при Санкт-Петербургском государственном университете по адресу 198504 Санкт-Петербург, Старый Петергоф, Университетский пр , 28

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

Автореферат разослан 2007 г

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

профессор Мартыненко Б К

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы

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

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

Многие типы известных вэйвлетов обеспечивают быстрое, но весьма неточное сжатие В данной работе используются сплайн-вэйвлетные системы с гарантированно высокой точностью приближения гладких цифровых потоков Они приводят к эффективному сжатию и к достаточно точному результату, ибо учитывают "гладкость" обрабатываемого потока цифровой информации Стимулом к изучению этого направления исследований стали работы С Г Михлина и Ю К Демьяновича, поскольку исходными здесь являются аппроксимационные соотношения

В случае, когда (а,/3) = К1, а сетка - равномерная, удается применить мощный аппарат гармонического анализа (в пространстве функций Ь2(М1) и пространстве последовательностей I2) Этому случаю посвящено большое ко-чичество исследований При обработке цифровых потоков с резко меняющимися характеристиками (со сменой плавного поведения на скачкообразное и наоборот) целесообразно использовать неравномерную сетку, приспосабливаемую к обрабатываемому потоку Применение неравномерной сетки позволяет улучшить приближение функций без усложнения вычис тений Более того, для улучшения приближения могут понадобиться различные степени измельчения сетки в разных частях рассматриваемого промежутка

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

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

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

Методы исследования

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

Достоверность и обоснованность

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

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

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

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

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

4 Для функции из пространства С4 построена аппроксимация в виде линейной комбинации базисных сплайнов, коэффициентами которой являются значения аппроксимационных функционалов Дано представление остатка приближения Найдены асимптотические оценки для аппроксимационных функционалов и Д^-сплайнов Рассмотрены оценки погрешности аппроксимации Др-сплайнами, в том числе и оценки, обладающие свойством гочносш на компонентах векгор-функции 99

5 Доказан ряд алгебраических тождеств, связанных с построением Д^-сплапнов второго порядка Исследованы свойства Д^-сплайнов второго и третьего порядков

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

Научная новизна

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

Теоретическая и практическая полезность

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

Апробация работы

Основные результаты были доложены на следующих конференциях и семинарах

1 Процессы управления и устойчивость XXXVII международная научная конференция аспирантов и студентов, С -Петербург, Россия, 10-13 апреля

2006 г

2 Высокопроизводительные вычисления на кластерных системах 6й международный научно-практический семинар, С -Петербург, Россия, 12-16 декабря, 2006 г

3 12th International Conference m Approximation Theory San Antonio, Texas, USA, March 4-8, 2007

4 Процессы управления и устойчивость XXXVIII международная научная конференция аспирантов и студентов, С -Петербург, Россия, 9-12 апреля

2007 г

5 Нелинейный динамический анализ - 2007 Международный конгресс, С -Петербург, Россия, 4-8 июня, 2007 г

6 Всероссийская конференция по вычислительной математике КВМ-2007, Академгородок, Новосибирск, Россия, 18-20 июня 2007 г

7 Leonhard Eulet Congress Thud International Workshop on Reliable Methods of Mathematical Modeling, St Peteishurg, Russia, July 24-27, 2007

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

Публикации

Основные результаты опубликованы в 11 работах (см раздел "Список опубликованных работ по теме диссертации" в конце автореферата)

Структура и объем работы

Диссертация объемом 178 страниц состоит из введения, шести пав, заключения и списка литературы, а также 5 табчиц и 29 рисунков

СОДЕРЖАНИЕ РАБОТЫ Во введении обосновывается актуальность диссертационной работы и излагаются основные результаты исследования

В первой главе рассматриваются обобщенные сплайны третьего порядка, имеющие минимальный носитель

Пусть Ж — множество целых чисел, Ж1 — множество вещественных чисел Будем использовать четырехмерное векторное пространство К4, причем векторы в нем будем отождествлять с одностолбцовыми матрицами и применять к ним обычные матричные операции, в частности, для двух векторов а, b е R4 выражение атЬ представляет собой евклидово скалярное произведение этих векторов, то есть aTb = ]Cs=o[abMs, гДе в квадратных скобках - компоненты векторов Квадратная матрица, столбцами которой являются векторы a,b,c,d е R4 (в указанном только что порядке), обозначается символом (а, b, c,d), а выражение det(a, b, с, d) означает ее определитель

Упорядоченное множество Ad= {aj}j€Z векторов а3 6 R4 будем называть цепочкой векторов Цепочка А называется полной цепочкой векторов, если матрица A,d= (äj-з, является неособенной матрицей при любом j е Z Совокупность всех полных цепочек будем обозначать А На интервале (a,ß) С R1 рассмотрим сетку {xj}jSz,

X < Х-\ < хо < Х\ < , пусть ad= lim х, ßä£ lim ж, (1)

3->—oo }—>+cx>

Введем обозначения Md= Uj6z (x3,x3+i), S/= [x3,xJ+i] Jkd£{k - 3, k - 2, k- 1 ,k}, k,j eZ

При K0 > 1, Kg € R1 обозначим X(K0,a, ß) класс сеток вида (1) со свойством локальной квазиравномерности Kg1 < (xJ+1 — х3)(х3 — a^-i)-1 < Kg Vj € Z и положим hx =f supJgZ (xJ+\ — x3)

Пусть X(M) — линейное пространство вещественнозначных функций, заданных на множестве М Для любого неотрицательного целого числа S пусть Cs(a,ß) — линейное пространство функций, непрерывных вместе со всеми производными до порядка S во внутренних точках интервала (a,ß) Также нам потребуется обычно используемое нормированное просхранство Cs[a ß\

Рассмотрим вектор-функцию <р (а ß) i-> К4 с компонентами из Х(М) Если А 6 А, го функции ujj(t), t 6 М, j € Z, однозначно определяются из аппрокси-мацнонных соотношений

а}>uy(t) = ip(t) Vi е {xk, xk+i), keZ, ujj(t) = 0 Vi $ S, П M (2)

/e jk

Из соотношения (2) ясно, что supp ш} С Sj

В линейном пространстве Х(М) содержится линейное пространство

={и | «(i) = EW*) Vi е л/. е к1},

jez

называемое пространством минимальных (X, А, (р)-сплайнов (третьего порядка), функции Wj, j е Z называются образующими пространства Х(Х,А,<р) Функция <р называется порождающей для сплайнов cjj, а цепочка векторов А — определяющей для этих сплайнов

В дальнейшем для вектор-функции tp е Cs(a,/3) положим

Ч>"Ф,), Ч^-^Чх,), г = 0,1, ,5, je2

При у? е С2(а,/3) рассмотрим последовательность векторов D^r, vd= {dj}jez, где векторы dj е R4 задаются тождеством

dfx s det(%, ip "v х), xel4,;eZ

Теорема 1 Пусть <р е C2(a,f3), ti Их,<р € А ТогЛг при достаточно малом hx во множестве | А е 4} существует единственное пространство сплайнов, продолжимых до функций пространства С2{а,/3)

При выполнении условий теоремы 1 пространство содержащееся в

С2(а, /?), будем называть пространством минимальных В v-сплайнов (третьего порядка) и обозначать ВДХ)

Рассмотрим произвольные векторы х, х', х", у, у', у", z, z', z" из пространства R4 и полилинейную вектор-функцию а*, задаваемую символическим определителем

a*(x,x',x",y,y',y",z,z',z")d=f / X х' х" \

det(y,y',y",x) det(y,y',y",x') det(y,y',y",x")

V det(z, z', z", x) det(z, z', z", x') det(z, z', z", x") / С помощью функции а* введем векторы а* по формуле

a^l?а*(<^+1, ¡р <р"+1, Vj+2, V j+21 ¥>"+2- ¥>j+3, V j+3' ^"+3). J 6 z

При ^>(f) 6 C3(a, /?) рассмотрим вронскиан W(t) = det(y>, ^ ', ip ", ip '"){£)

Теорема 2 Если ip e C4[a 0], W{t) ф 0 Vi € [aj], и X e «,/?) некоторого Ко > 1, то существует е > 0 такое, что при hx < е линейная оболочка функций ш*, j 6 Ъ, полученных по формулам (2) при ajd= а*, совпадает с пространством Вр(Х)

Заметим, что при сделанных в теореме 2 предположениях, цепочка а* является полной

Теорема 3 Если цепочш векторов а.* полная, то функции ш*3{Ь) дважды непрерывно дифференцируемы на интервале (а,{3), и справедливы формулы

^ М= при *е1хз>хз+1)' (3)

<^4

, _ ^(о ^а;-, , от , ,5)

3+4 ^ аз+За3-1

= пРи *е [^Н-З.^-м] (6)

Во второй главе рассматривается измельчение исходной сетки Она посвящена калибровочным соотношениям и вложенности пространств Д^-сплайнов в этом случае Выясняется, что упомянутые соотношения связаны с некоторыми алгебраическими тождествами, которые, по-видимому, представляют самостоятельный интерес Для сетки X е Х(К0 а, ¡5), полученной из сетки X добавлением одного узла, описанным выше способом строятся В^-сплайны й*г Устанавливаются калибровочные соотношения (обобщающие кратно-масштабное уравнение), выражающие построенные ранее Д^-сплайны (для сетки X) в виде линейной комбинации сплайнов ш* Последовательное добавление узлов позволяет рассмотреть любую пару сеток X а X, где X, X е Х(Ко,а,0), и утверждать, что В^(Х) С В^Х)

В этой главе исходная сетка X допочняется новым узлом и на полученной таким образом сетке X рассматриваются В^-сплайны £>*<(£) Итак, пусть £ — упомянутый новый узел, £ € (2^,2^+1), ах3 — узлы вновь полученной сетки

х3л^х3 при ] < к ждн-1=!£ х3й=х}-1 при ] > к + 2, Хл= {х3 \ у е 1,} (7)

Функции ш* зависят от узлов х3,х3+1,х3+2,х3+з,х3+4,, так что нетрудно указать функцию шести вещественных переменных £) (см формулы (3) - (6)) такую, что

ш*(р) = Ш(Х3,х}+1,Х,+2,Х]+З,Х3+4,£) УЗ еХ

На новой сетке рассмотрим функции

ш](Ь)и>{х3, Х3+х,Х3+2, х3+3,х3+4, 4)

Условимся надчеркивать обозначения всех ранее введенных объектов, определяемых новой сеткой X, в частности, положим

— /— \ — / def / /_ \ — // с1е£ // /— \

<Р3=Фз), <Р3=ф {х3),

с!е£ ^ ' / _ц я ^ I _ц ___I _ц ч

=а ((Р]+1>'Р з+ъРз+г'Ъ+ъ? ^Ъ+З,1? з+з^з+з), с^х"= ёе^,Тр'3,Тр",х), где х е К4

Для ш*{€) справедливы формулы (3) - (6), если в последних сделать очевидные замены Таким образом,

= - при

а^а; а;+1а;+1

аГ+^-г а^ед

-тТ -тТ

при ге[х,+их]+2),

<

—71

= ^ при 4 € [¡С,+3,^+4]

Теорема 4 Для 4 е (а /?) справедливы калибровочные соотношения

= 5^(4) при] <к- 4, (8)

ш*(4) = ш*+1(4) при з > к + 1, (9)

ЦЕ-зМ = + (Ю)

ш*к-= Р/Ь-2,*-2ш£-2М + (11)

= + Ра;-1,^(4), (12)

и£(«)=Рм^(4)+<51+1(«), (13)

где

__1Р

Рк-3,к~2 = ¿А-.-г^-гМи-г^-З; (I4)

—Т

(-тг -тТ ¿^а^Х „ . .

<*к+2ак~3' _X _т

Рк-2,к-1 = &к+зЧ-\/Ак+з&к-2, (16)

_у _

Pfc-i.it-1 = (17)

Р(=-г,к = Ы^Щ; - а^а^!^^-^) /а^х.!, (18)

Рк,к = а[а*/Н^а*+1 (19)

Дадим другой вариант формулировки теоремы 4 Введем бесконечномерные вектор-столбцы, компонентами которых являются функции о;*(£) и ¡1^(4)

а/(4) = (

ёЭ*(0 = ( .оЯаЮ.И^Ю.эгЮ.аЭД) ^(4),

)Г, \Т

Теорема 5 Справедливо соотношение

ш'Ц) = ф5Г(«),

где - бесконечная матрица вида (рг,3)г,3ег> элементы которой задаются равенствами

Ру = пРи 1 <к — 4, рьз = 5^-х при г > к + 1,

при рк^3=0 при у ф {к-2,к-1},

Рк-1,} = 0 при з £{к- 1, к}, рк,3 = 4+1,? при з ^ к а также формулами (Ц) - (19)

Третья глава посвящена вэйвлетным разложениям Построена система функционалов биортогональная системе {ш*<(£))у<=г и система функ-

ционалов {д^}3ех биортогональная системе {о>*,(4)}уе2, те

= 5]У, {дЬ\ и;,) = где е 2

В соответствии с определением В^Х) является пространством В^-сплайнов третьего порядка на сетке X (см соотношения (7)),

3

Согласно калибровочным соотношениям (8) - (13) справедливо включение Ву{Х) с Вр(Х) Рассмотрим оператор Р проектирования пространства ДДХ) на подпространство В1р(Х), задаваемый формулой Рй% ^Зазшз'аз = для всех и € В^(Х), и введем оператор <2 = / — Р, где I — тождественный оператор Пусть далее q{д^г\ш*3), г,з е Ъ

Пространство ]¥ -(¿В^Х) называется пространством вэйвлетов (всплесков), а прямое разложение

= (20)

называется сплайн-вэйвлетным разложением пространства ДДХ)

Согласно формуле (20) имеем й = 1£1г агЦ*+£г, Ь,>ш*, = +Ьг<)й?г,,

так что для чисел с3 = получаем

с3 = + Ъ3, з еЪ

г

Пусть известны коэффициенты с3 в разложении элемента и е В^Х) но элементам базиса ш* Тогда верны формулы

а, = (21)

г'

Ьз=сз- Хд ХХ^')1^ (22)

г' ^ г '

называемые формулами декомпозиции

Теорема в Для сплайн-вэйвлетного разлоо/сения (20) пространства Др{-Ю формулы декомпозиции (21) - (22) имеют вид

аг = сг при г < к — 3, аг = Сг+х при г > к,

0-к-2 = Чк-2,к-3 ск-3 + Йк—2,к~2 Ск-2, 0-к-1 = Цк—1,к—3 Ск-3 + 2 Ск-2 + <\к-1,к-1 Ск-1,

Ь3 = О при з фк, (23)

Ьк = Ск - рк-1,к{Цк-1,к-ЗСк-3 + 44-1,^-2^-2+

+Я*-1,*:-1Ск-1) ~ Рк,кСк+1 (24)

Следствие 1 Согласно формулам (23) - (24) вэйвлетным базисом пространства \¥ служит Вр-сплайн ш*к, т е IV = {ЬаЗ*к \ Ь е К1}

Пусть теперь известны коэффициенты аг и Ь в разложениях проекций элемента и е на пространства В^Х) и ]У Ри = ^2гаги>*, Ой = Ьш*к Найдем формулы для опреде тения коэффициентов с3 для представления элемента и в виде суммы и = Щ) эти Ф°рмулы называются формулами реконструкции

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

Сг = аг при г < к — 3, сг = аг_1 при г > к + 1,

Ск-2 = Рк-3,к-2(1к-3 + Рк-2,к-2<1к-2

Ск-1 = Рк-2,к-1Як-2 + Рк-\,к~1&к-1, Ск = Ьк+ Рк-1,кО-к~1 + Рк,к1к

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

В четвертой главе для ф> нкции из пространства С4 строится аппроксимация в виде линейной комбинации базисных сплайнов, коэффициентами которой являются значения аппроксимационных функционалов Выводятся асимптотические оценки для аппроксимационных функционалов и Б^-сплайнов С помощью обобщенной формулы Тейлора полу чается оценка аппроксимации порядка 1г\, точная на компонентах вектор-функции ¡р

В пятой главе рассматривается другой подход к построению В^-снлайнов второго порядка Доказан ряд алгебраических тождеств Сформулируем одно из них

Теорема 8 Для произвольных векторов Р, Q, R, S, Т из К3 справедлива формула

det(P, Q R)det(R, S, Т) + det(Q, R, S)det(P, R, T) = =■ det(Q, R, T)det(P, R, S)

В этой главе также исследованы свойства Д^-сплайнов второго и третьего порядков

Шестая глава посвящена моделированию полиномиальных и неполиномиальных Д^-сплайнов (при y>(i)d=(l,t, í2,í3)T и <p(t)d= (1, smí,cosí,sm2t)T соответственно) Получены формулы для вычисления базисных сплайнов Проиллюстрирована вложенность пространств при одном варианте измельчения сетки и конкретизированы калибровочные соотношения в данной ситуации Далее моделируется аппроксимируемая функция из пространства С4 в виде линейной комбинации образующих сплайнов (тригонометрических), коэффициентами которой служат значения аппроксимационных функционалов на упомянутой функции Даны результаты приближения в случае сплайн-вэйвлетной модели аппроксимации Приведены результаты применения алгоритмов декомпозиции и реконструкции к сжатию и восстановлению модельных числовых потоков

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

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

[1] Макаров А. А. Об алгебраических тождествах в теории Д^-сплайнов // Процессы управления и устойчивость Тр 37-й междунар науч конф аспирантов и студентов СПб , 10-13 апреля 2006г / Под ред А В Платонова, Н В Смирнова - СПб Изд-во С -Петерб ун-та, 2006 С 164-166

[2] Демьянович Ю. К , Макаров А А. Калибровочные соотношения для неполиномиальных сплайнов // Проблемы математического анализа Вып 34 Межвуз сб / Под ред Н Н Уральцевой - Новосибирск Тамара Рожковская,

2006 С 39-54

[3] Макаров А. А. Новые методы сжатия информации // Высокопроизводительные параллельные вычисления на кластерных системах Материалы шестого Международного научно-практического семинара Том 2 /' Под ред проф Р Г Стронгина - СПб Изд-во С -Петерб ун-га, 2007 С 32-34

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

[5] Demjanovich Yu К , Kosogorov О М., Makarov A A Wavelet Decomposition foi Adaptive Irregular Gilds // Twelfth International Conference m Appioximation Theory San Antonio, Texas, USA March 4-8 2007 Abstracts, p 36

[6] Demy'anovich Yu К , Makarov A A. Calibration relations for non-polynomial splines // Journal of Mathematrcal Sciences (New York), Vol 142, No 1,

2007 P 1769-1787

[7] Макаров А А Вложенность пространств Д^-сплайнов третьего порядка и вэйвлетные разложения // Процессы управления и устойчивость Тр 38-й междунар науч конф аспирантов и студентов СПб , 9-12 апреля 2007 г ' Под ред А В Платонова, Н В Смирнова - СПб Изд-во С -Петерб ун-та, 2007 С 171-174

[8] Демьянович Ю К., Макаров А. А. Калибровочные соотношения для неполиномиальных сплайнов лагранжева типа // Нелинейный динамический анализ-2007 Тезисы докладов международного конгресса, Санкт-Петербург, 4-8 июня 2007 г - СПб Изд-во С -Петерб ун-та, 2007 С 273

[9] Демьянович Ю. К., Макаров А. А. Калибровочные соотношения для неполиномиальных сплайнов // Всероссийская конференция по вычислительной математике КВМ-2007 Тезисы докладов, Академгородок, Новосибирск, Россия, 18-20 июня 2007 г

http / /www-sbras nsc ru/\vs/sho\v_abstract dhtml?ru-rl64+11935

[10] Demjanovich Yu K., Makarov A. A System of Embedded Spaces for Non-polynomial Splines // Third International Workshop on Reliable Methods of Mathematical Modeling, St Petersburg, Russia, July 24-27, 2007 Abstracts, p 11

[11] Демьянович Ю. К., Макаров А. А. Система вложенных пространств неполиномиальных сплайнов // Питания оптимизацп обчислень (ПОО -XXXIII) Пращ м1жнародного симпозгуму, смт Кацивел1, Велика Ялта, Крим, Украша, 23-28 вересня 2007 р - Кшв 1нститут шбернетики 1мен1 В М Глуш-кова, 2007 С 92

В совместных работах [2, 5, 6, 8-11] научному руководителю принадлежит общая постановка задач и указание на идею исследования, а детальная реализация идеи точностью принадлежит диссертанту

Подписано к печати 25 09 2007 Формат бумаги 60x84 1/16 Бумага офсетная Печать цифровая Объем 1 п л Тираж 100 экз Заказ 4006 Отпечатано в отделе оперативной полиграфии НИИХ СПбГУ с оригинал-макета заказчика 198504, Санкт-Петербург, Старый Петергоф, Университетский пр , 26

Введение

1 Обобщенные сплайны третьего порядка

1.1 Предварительные обозначения и вспомогательные утверждения

1.2 Пространства (X, А, у?)-сплайнов.

1.3 Пространства .£? ^-сплайнов.

1.4 О представлении Б^-сплайнов.

2 Калибровочные соотношения и вложенность пространств В^-сплайнов

2.1 Измельчение сетки.

2.2 Калибровочные соотношения. Представление функциио>£(£) с помощью линейной комбинации функций Щ{Ь) и

2.3 Представление функции со1г с помощью функций и Щ

2.4 Представления функций и ш12(1).

2.5 Сводная теорема о калибровочных соотношениях.

3 Вэйвлетные разложения

3.1 Биортогональная система функционалов и интерполяционная задача.

3.2 Значения функционалов на образующих объемлющего пространства

3.3 Вэйвлетное разложение. Формулы декомпозиции.

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

3.5 О вариантах телескопических систем и об их вэйвлетных разложениях.

3.6 О распараллеливании вэйвлетных разложений.

4 Аппроксимация Б^-сплайнами

4.1 Представление остатка приближения .•.

4.2 Асимптотические оценки для аппроксимационных функционалов

4.3 Асимптотические оценки для В^-сплайнов.

4.4 Порядок аппроксимации.

4.5 Еще одно замечание об оценках.

5 Другой подход к построению ¿^-сплайнов второго порядка

5.1 В^-сплайны второго порядка.

5.2 Некоторые алгебраические тождества.

5.3 Свойства Д^-сплайнов.

6 Моделирование В ^-сплайнов

6.1 Полиномиальные Б ^-сплайны

6.2 Неполиномиальные В ^-сплайны.

6.3 Сплайн-вэйвлетная модель аппроксимации.

6.4 Некоторые варианты сжатия и восстановления числовых потоков.

Теория вэйвлетов (всплесков) появилась несколько десятилетий назад и имеет значимое приложение к решению практических задач в различных областях науки: математике, физике, медицине, инженерном деле. Вэйвлеты широко применяются при составлении эффективных алгоритмов обработки больших потоков информации или цифровых сигналов (см. [22], [32]). Идея такой обработки состоит в прореживании "по времени" или "по частоте" поступающего цифрового сигнала, что приводит к его сжатию.

В данном случае под эффективностью понимается экономное с точки зрения экономии ресурсов ЭВМ (памяти и времени обработки) разложение потока информации на составляющие таким образом, чтобы можно было выделить основной информационный поток, уточняющий информационный поток и информационный поток с несущественной информацией. Как правило, основной информационный поток значительно менее плотный, чем исходный поток информации; поэтому его можно передать быстро, и при этом не требуется использовать широкополосные линии связи. Уточняющий информационный поток (его иногда называют вэйвлетиым потоком) не во всех случаях необходим, его можно передавать фрагментарно в зависимости от потребностей. Наконец, поток с несущественной 5 информацией вообще может быть отброшен, тогда исходный поток должен однозначно восстанавливаться по основному и вэйвлетному потокам. Естественный вопрос о разделении информации на основную, уточняющую и несущественную выходит за рамки математических исследований и должен решаться в каждом отдельном случае специалистом данной предметной области.

Роль теории вэйвлетов (всплесков) заключается в предоставлении предметному специалисту достаточно широкого набора средств, из которых он может выбрать именно то средство, которое ему подходит для обработки (для разложения на составляющие) интересующего его потока информации (цифрового сигнала). В теории вэйвлетов упомянутыми средствами являются наборы вложенных (основных) пространств функций и их представлений в виде прямой (а иногда и ортогональной) суммы вэй-влетных пространств. Построению и изучению свойств базисов основных пространств и базисов вэйвлетов посвящено большое количество работ (см. [32], [41], [45], [56] и библиографию в них).

В простейшем случае исходный сигнал отождествляется с функцией, заданной на интервале (а, /?) вещественной оси. Для компьютерной обработки используется дискретный сигнал, представляемый сеточной функцией, определяемой как значения исходной функции (или результатов ее сглаживания) в узлах некоторой сетки. Построение сеточной функции позволяет приближать исходную функцию с помощью того или иного аппарата аппроксимации или интерполяции. Далее линейное пространство таких приближений представляется в виде прямой суммы пространств: основного и вэйвлетного. Часто основное пространство связывают с сеткой, получающейся выбрасыванием (или добавлением) узлов из исходной сетки, а подпространство вэйвлетов определяют операцией проектирования исходного пространства на основное. Таким образом, порождается разложение упомянутого приближения на основную и вэйвлетную составляющие. Особое внимание здесь уделяют вложенности основного пространства в исходное и заданию операции проектирования исходного пространства на основное. Представления элементов этого разложения в базисах рассматриваемых пространств порождают соответствующие соотношения между коэффициентами этих представлений. Соотношения, которые позволяют перейти от коэффициентов базиса исходного пространства к коэффициентам базиса основного и вэйвлетного пространств, называются формулами декомпозиции, а соотношения, дающие обратный переход, называются формулами реконструкции. Затем каждое из подпространств иногда также разлагают в прямую сумму некоторых подпространств, возможно, продолжая этот процесс дальше; разложения подобного рода называются в эйвлет-пакетами.

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

НОСТЬ.

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

Многие типы известных вэйвлетов обеспечивают быстрое, но весьма неточное сжатие. В данной работе используются сплайн-вэйвлетные системы (см. [15], [17]) с гарантированно высокой точностью приближения гладких цифровых потоков. Они приводят к эффективному сжатию и к достаточно точному результату, ибо учитывают "гладкость" обрабатываемого потока цифровой информации.

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

В случае, когда (а,0) = М1, а сетка - равномерная, удается применить мощный аппарат гармонического анализа (в пространстве функций

К1) и пространстве последовательностей I2). Этому случаю посвящено большое количество исследований (см, например, [32] и библиографию там). При обработке цифровых потоков с резко меняющимися характеристиками (со сменой плавного поведения на скачкообразное и наоборот) целесообразно использовать неравномерную сетку, приспосабливаемую к обрабатываемому потоку. Применение неравномерной сетки позволяет улучшить приближение функций без усложнения вычислений. Более того, для улучшения приближеиия могут понадобиться различные степени измельчения сетки в разных частях рассматриваемого промежутка. Особой задачей является получение вэйвлетных разложений в случае неравномерной сетки, поскольку обычно применяемое на равномерной сетке преобразование Фурье в условиях неравномерной сетки выполнить затруднительно. Оказалось, что использование биортогоналыюй системы функционалов позволяет построить вэйвлетные разложения и при произвольном измельчении сетки (это ведет к упрощениям и в случае равномерной сетки). Работ по неравномерной сетке не много (см. [18], [19], [57], [58], [60], [61]); непосредственное применение гармонического анализа здесь затруднительно.

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

Первое направление берет свое начало от работ Шонберга (1946г., [65]); здесь исходным моментом является решение какой-либо задачи интерполяции (задачи Лагранжа, Эрмита или Эрмита-Биркгофа) в классе функций с "кусочными" свойствами с определенной гладкостью в узлах рассматриваемой сетки (см. [26], [37], [52], [59], [63], [66]); аппроксимационные свойства и вычислительная простота получаемых сплайнов всякий раз исследуется дополнительно. Сюда относятся современные исследования по обобщенным сплайнам, так называемым ЕСТ-В-сплайнам (см., например, [59], [63]); в этих работах для построения сплайнов на сеточных промежутках используются различные ЕСТ-системы, которые при определенных условиях удается гладко "склеить" в узлах. Для разработки экономичных методов используют локальные функции с минимальным носителем (см. [11], [13], [49]). Существует большое количество публикаций, посвященных как теоретическим исследованиям, так и практическому применению сплайнов (см. [1], [7], [8], [28] и библиографию там).

Второе направление опирается на аппроксимационные свойства получаемых сплайнов, где определение базисных сплайнов связано с решением аппроксимационных соотношений, рассматриваемых как система уравнений (эти исследования появились в связи с теорией метода конечных элементов, см. [6], [12], [14], [16], [17], [20], [21], [39], [62], [68]); при таком подходе интерполяционные свойства и алгоритмы минимизации вычислительной сложности (вложенность пространств и вэйвлетное представление цепочки вложенных пространств) приходится устанавливать дополнительно. Выбор порождающей т-Ы-компонентной вектор-функции </?(£), заданной на интервале (а,/3), определяет семейства конечномерных пространств на элементарных сеточных интервалах рассматриваемой (конечной или бесконечной) сетки X = X С (а, /?), а выбор цепочки А векторов со свойством полноты приводит к пространству (X, А, </?)-сплайнов. Условия гладкости эквивалентны определенным алгебраическим соотношениям между значениями (и ее производных) в узлах сетки и векторами цепочки А. Требование максимальной гладкости сплайнов (при выбранной вектор-функции у?(£) с отличным от нуля вронскианом из ее компонент) однозначно (с точностью до постоянных отличных от нуля множителей) определяет цепочку А; при этом однозначно определяется также пространство (X, А, <^)-сплайнов, которое в этом случае называется пространством В^-сплайнов (см. [17]).

Третье направление относится к теории вэйвлетов, в основе которой лежит вычислительная простота, отражением чего является кратно-масштабное уравнение (см. [22], [32], [41], [45], [57], [67]); исследование последнего приводит к вложенности получаемых пространств и к вэйвлетному представлению соответствующей цепочки вложенных пространств (это ведет к минимизации вычислительной сложности); остальные из перечисленных выше свойств с ббльшим или мёньшим успехом исследуются дополнительно (см., например, [32]).

Согласно [53] истоки вэйвлетов идут от работы К. Вейерштрасса, который в 1873 году описал семейство функций, построенных масштабированием данной базисной функции. В 1909г. А. Хаар построил первую ортонормированную систему функций с компактным носителем, называемую базисом Хаара. В 1940г. Рикер ввел понятие "вэйвлет" для описания процесса возмущения от сильного сейсмического импульса или заряда взрывчатого вещества. В русскоязычной литературе иногда используется термин "всплеск" (предложен К. И. Осколовым) в качестве эквивалента термину "вэйвлет" (англ. wavelet, фр. ondelette). В 1946г. Д. Габор описал неортогональный базис вэйвлетов с неограниченным носителем, построенный по гауссианам. В 1982г. Морле применил функции, определенные Габором, к моделированию сейсмических импульсов. Затем Гроссман и Морле установили как анализировать произвольные сигналы, масштабируя и сдвигая порождающий вэйвлет. Труды И. Мейера и С. Малла привели к появлению теории, названной кратно-масштабным анализом. В 1989г. Малла применил кратно-масштабный анализ в алгоритмах обработки изображений. Далее развитие вэйвлетов осуществляли многие ученые: И. Добеши, Ж. Баттле, П. Ж. Лемарье, Ч. Чуй, А. Коэн, Р. Койфман, Г. Стрэнг и др. (см. [22], [32], [41], [45], [56], [69] и библиографию там).

В России теорией вэйвлетов одним из первых заинтересовался професор С. Б. Стечкин, хотя первой работой по данной тематике в СССР можно считать работу [48] В. JT. Рвачева и В. А. Рвачева, опубликованную в 1971 году. Дальнейшее развитие теории связано с именами ученых: И. Я. Новиков, М. А. Скопина, А. П. Петухов, В. Н. Малоземов, В. А. Желудев, В. Ю. Протасов и др. (см. [2]-[5], [9], [23]- [25], [27], [29], [31], [33]-[36], [38], [40]—[47], [50], [51], [54], [55], [64], [67]).

Конечно, получаемые в этих трех направлениях классы сплайнов имеют непустое пересечение; в нем, в частности, лежат давно известные полиномиальные В-сплайны. Заметим также, что пространства ЕСТ-В-сплайнов находятся среди пространств (X, А, <£>)-сплайнов; они получаются, если в качестве компонент вектор-функции при Ь € (Хк, 1) взять (возможно, различные) ЕСТ-системы (вронскиан ЕСТ-системы всегда отличен от нуля, что важно для построения Д^-сплайнов, являющихся в этом случае ЕСТ-В-сплайнами максимальной гладкости).

Данная работа, продолжая цикл работ [б], [12], [14], [16], [17], [20], [21], [39], [62], [68], относится ко второму направлению. Стимулом к изучению этого направления исследований стали работы С. Г. Михлина [39] и Ю. К. Демьяновича [12], поскольку исходными здесь являются аппрок-симационные соотношения. Предлагаемая работа также связана с третьим направлением: алгоритмы, минимизирующие вычислительную сложность, являются следствием выводимых здесь калибровочных соотношений (эти соотношения играют ту же роль, что и упомянутое выше кратно-масштабное уравнение, см. [14]).

Заметим, что рассматриваемые в упомянутых работах минимальные сплайны включают ЕСТ-В-сплайны, которые активно изучаются рядом авторов (см. [59], [63], [66]).

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

В. Ю. Протасов и др.

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

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

В случае, когда (а, 0) = М1, а сетка - равномерная, удается применить мощный аппарат гармонического анализа (в пространстве функций Ь2(Ж1) и пространстве последовательностей 12). Этому случаю посвящено большое количество исследований. При обработке цифровых потоков с резко меняющимися характеристиками (со сменой плавного поведения на скачкообразное и наоборот) целесообразно использовать неравномерную сетку, приспосабливаемую к обрабатываемому потоку. Применение неравномерной сетки позволяет улучшить приближение функций без усложнения вычислений. Более того, для улучшения приближения могут понадобиться различные степени измельчения сетки в разных частях рассматриваемого промежутка.

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

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

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

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

1. Получены новые аппроксимирующие пространства с локальным базисом - пространства В^-сплайнов. Исследованы свойства Др-сплайнов третьего порядка с минимальным компактным носителем, построенных на неравномерной сетке. Получены формулы для вычисления базисных сплайнов. Представлены результаты моделирования полиномиальных и неполиномиальных Д^-сплайнов.

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

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

4. Для функции из пространства С4 построена аппроксимация в виде линейной комбинации базисных сплайнов, коэффициентами которой являются значения аппроксимационных функционалов. Дано представление остатка приближения. Найдены асимптотические оценки для аппроксимационных функционалов и Д^-сплайнов. Рассмотрены оценки погрешности аппроксимации Би-сплайнами, в том числе и оценки, обладающие свойством точности на компонентах вектор-функции (р.

5. Доказан ряд алгебраических тождеств, связанных с построением В сплайнов второго порядка. Исследованы свойства Д^-сплайнов второго и третьего порядков.

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

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

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

Апробация работы. Основные результаты были доложены на следующих конференциях и семинарах:

1. Процессы управления и устойчивость. XXXVII международная научная конференция аспирантов и студентов, С.-Петербург, Россия, 10-13 апреля 2006 г.

2. Высокопроизводительные вычисления на кластерных системах. 6й международный научно-практический семинар, С.-Петербург, Россия, 1216 декабря, 2006 г.

3. 12th International Conference in Approximation Theory. San Antonio, Texas, USA, March 4-8, 2007.

4. Процессы управления и устойчивость. XXXVIII международная научная конференция аспирантов и студентов, С.-Петербург, Россия, 9-12 апреля 2007 г.

5. Нелинейный динамический анализ - 2007. Международный конгресс, С.-Петербург, Россия, 4-8 июня, 2007 г.

6. Всероссийская конференция по вычислительной математике КВМ-2007, Академгородок, Новосибирск, Россия, 18-20 июня 2007 г.

7. Leonhard Euler Congress. Third International Workshop on Reliable Methods of Mathematical Modeling, St. Petersburg, Russia, July 24-27, 2007.

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

Публикации. Основные результаты опубликованы в И работах (см. раздел "Работы автора по теме диссертации" в конце списка литературы).

Структура и объем работы. Диссертация объемом 178 страниц состоит из введения, шести глав, заключения и списка литературы, а также 5 таблиц и 29 рисунков.

Заключение

В данной работе получены новые аппроксимирующие пространства с локальным базисом - пространства Д^-сплайнов. Рассмотрены Д^-сплай-ны третьего порядка (построенные на неравномерной сетке) с минимальным компактным носителем, занимающим четыре сеточных промежутка. Для них установлены калибровочные соотношения, которые дают представление координатных сплайнов на исходной сетке в виде линейной комбинации координатных сплайнов на сетке, полученной измельчением исходной. Для последовательности измельчающихся сеток получены цепочки вложенных пространств. Используя систему функционалов, биортого-нальную системе базисных сплайнов, построено сплайн-вэйвлетное разложение. Дано представление упомянутых цепочек в виде прямой суммы вэйвлетных пространств с локальным базисом. Получены соответствующие формулы декомпозиции и реконструкции. Приведены параллельные формы для вычисления упомянутых формул. Для функции из пространства С4 построена аппроксимация в виде линейной комбинации базисных сплайнов, коэффициентами которой являются значения аппрок-симационных функционалов. Дано представление остатка приближения. Найдены асимптотические оценки для аппроксимационных функционалов и Д^-сплайнов, Указан порядок аппроксимации. При помощи обоб

166 щенной формулы Тейлора получены оценки погрешности аппроксимации Др-сплайнами, обладающие свойством точности на компонентах вектор-функции (р. Доказан ряд алгебраических тождеств, связанных с построением ^-сплайнов второго порядка. Исследованы свойства Д^-сплайнов второго и третьего порядков. Представлены результаты моделирования полиномиальных и неполиномиальных Д^-сплайнов. Получены формулы для вычисления базисных сплайнов, построены соответствующие графики функций. Проиллюстрирована вложенность пространств при одном варианте измельчения сетки и конкретизированы калибровочные соотношения в данной ситуации. Промоделирована аппроксимируемая функция из пространства С4 в виде линейной комбинации образующих сплайнов (тригонометрических), коэффициентами которой служат значения аппроксима-ционных функционалов на упомянутой функции. Даны результаты приближения в случае сплайн-вэйвлетной модели аппроксимации. Приведены результаты применения алгоритмов декомпозиции и реконструкции к сжатию и восстановлению модельных числовых потоков.

1. Алберг Дж., Нильсон Э., Уолш Дж. Теория сплайнов и ее приложения. М.: Мир, 1972. - 316 с.

2. Астафьева Н. М. Вейвлет-анализ: основы теории и примеры применения // Успехи физических наук. 1998. Т. 166. № 11. С. 1145-1170.

3. Бердышев В. И., Петрак Л. В. Аппроксимация функций, сжатие численной информации, приложения. Екатеринбург: УрО РАН, 1999. 296 с.

4. Берколайко М. 3., Новиков И. Я. О бесконечно гладких почти-всплесках с компактным носителем // Доклады РАН. 1992. Т. 326. № 6. С. 935-938.

5. Берколайко М. 3., Новиков И. Я. Базисы всплесков в пространствах дифференцируемых функций анизотропной гладкости // Докл. РАН. 1992. Т. 323. № 4. С. 615-618.

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

7. Бурова И. Г., Демьянович Ю. К. О сплайнах максимальнойгладкости // Вестн. С.-Петерб. ун-та. Сер. 1. 2005. Вып. 2. С. 5-9.168

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

9. Воробьев В. И., Грибунин В. Г. Теория и практика вейвлет-преобразования. СПб.: Изд-во ВУС, 1999. 208 с.

10. Головкин К. К. О приближении функций в произвольных нормах. Труды математического института В. А. Стеклова. Том ЬХХ. Краевые задачи математической физики. Изд-во Наука. М.-Л. 1964. С. 26-37.

11. Де Бор К. Практическое руководство по сплайнам. М., 1984. 303 с.

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

13. Демьянович Ю. К. О построении пространств локальных функций на неравномерной сетке // Зап. науч. сем. ЛОМИ АН СССР. 1983. Т. 124. С. 140-163.

14. Демьянович Ю. К. О вложенности пространств минимальных сплайнов// Ж. выч. мат. и мат. физ. 2000. Т. 40. № 7. С. 1012-1029.

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

16. Демьянович Ю. К. Всплески к минимальные сплайны. СПб.: Изд-во С.-Петерб. ун-та, 2003. 200 с.

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

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

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

20. Демьянович Ю. К., Иванцова О. Н. Гладкость пространств сплайнов третьего порядка. // Сб. Математические модели. Теория и приложения. Вып. 7. СПб.: ВВМ, 2006. С. 58-64.

21. Демьянович Ю. К., Михлин С. Г. О сеточной аппроксимации функций соболевских пространств // Зап. науч. семинаров ЛОМИ АН СССР. 1973. Т. 35. С. 6-11.

22. Добеши И. Десять лекций по вейвлетам: Пер. с англ. Е. В. Мищенко; под ред. А. П. Петухова. Москва-Ижевск: НИЦ "Регулярная и хаотическая динамика", 2004. 464 с.

23. Желудев В. А. О вейвлетах на базе периодических сплайнов // Докл. РАН. 1994. № 1. С. 9-13.

24. Желудев В. А. О цифровой обработке сигналов при помощи сплайн-вейвлетов и вейвлет-пакетов // ДАН. 1997. Т. 355. № 5. С. 592-596.

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

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

27. Кашин Б. С., Саакян А. А. Ортогональные ряды. М.: АФЦ, 1999.

28. Квасов Б. И. Методы изогеометрической аппроксимации сплайнами. — М.-Ижевск: НИЦ "Регулярная и хаотическая динамика", Институт компьютерных исследований, 2006. 416 с.

29. Кирушев В. А., Малоземов В. Н., Певный А. Б. Вейвлет-ное разложение пространства дискретных периодический сплайнов // Матем. заметки. 2000. Т. 67. Вып. 5. С. 712-720.

30. Коддингтон Э.А., Левинсон Н. Теория обыкновенных дифференциальных уравнений. М. 1958. 474 с.

31. Кравченко В. Ф., Рвачев В. А., Пустовойт В. И. Алгоритм построения "wavelet"-систем для обработки сигналов // ДАН. 1996. Т. 346. ДО 1. С. 31-32.

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

33. Малоземов В. Н., Машарский С. М. Сравнительное изучение двух вейвлетных базисов // Пробл. передачи инф. 2000. Т. 36. Вып. 2. С. 27-37.

34. Малоземов В. Н., Машарский С. М. Формула Глассмана, быстрое преобразование Фурье и вейвлетные разложения // Труды С-Петерб. матем. о-ва. 2001. Т. 9. С. 97-119.

35. Малоземов В. Н., Машарский С. М. Обобщенные вейвлет-ные базисы, связанные с дискретным преобразованием Виленкина-Крестенсона // Алгебра и анализ. 2001. Т. 13. Вып. 1. С. 111-157.

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

37. Малоземов В. Н., Певный А. Б. Полиномиальные сплайны. Л., 1986. 120 с.

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

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

40. Новиков И. Я. Онделетты И. Мейера оптимальный базис в С(0,1) // Матем.заметки. 1992. Т. 52. № 5. С. 88-92

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

42. Новиков И. Я. Константы неопределенности для модифицированных всплесков Добеши // Изв. Тул. гос. ун-та. Сер. Математика. Механика. Информатика. Тула: ТулГУ, 1998. - Т. 4, вып. 1. - С. 107-111.

43. Петухов А. П. Периодические дискретные всплески // Алгебра и Анализ. 1996. Т. 8. № 3. С. 151-183.

44. Петухов А. П. Периодические всплески // Математический сборник. 1997. Т. 188. № 10. С. 69-94. Петухов А. П. Кратномасштабный анализ и всплеск-разложения пространств периодических распределений // Доклады РАН. 1997. Т. 356. № 2. С. 303-306.

45. Петухов А. П. Введение в теорию базисов всплесков. СПб.: Изд-во СПбГТУ, 1999. 132 с.

46. Петухов А. П. Биортогональные базисы всплесков с рациональными масками и их приложения // Труды СПбМО. Т. 7. 1999. С. 168-193.

47. Протасов В. Ю. Кусочно-гладкие масштабирующие функции // Алгебра и Анализ. 2004. - Т. 16, № 5. - С. 98-111.

48. Рвачев В. JI. и Рвачев В. А. Об одной финитной функции // ДАН УССР. 1971. - m 8. - С. 705-707.

49. Рябенький В. С. Об устойчивости конечно-разностных уравнений: Дис. канд. физ.-мат. наук. М., 1952.

50. Скопина М. А. О нормах полиномов по системам периодических всплесков в пространствах Lp // Матем. заметки. 1996. Т. 59. № 5. С. 780-783.

51. Скопина М. А. Ортогональные полиномиальные базисы Шаудера С-1,1] с оптимальным ростом степеней // Мат. сб. 2001. - Т. 192. № 3. - С. 115-136.

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

53. Столниц Э., ДеРоуз Т., Салезин Д. Вейвлеты в компьютерной графике: Пер. с англ. Ижевск: НИЦ "Регулярная и хаотическая динамика", 2002. 272с.

54. Субботин Ю. Н., Черных Н. И. Всплески в пространствах гармонических функций // Изв. РАН. Сер. матем. 2000. Т. 64. № 1. С. 145-174.

55. Фарков Ю. А. Ортогональные всплески на локально компактных абелевых группах. Функциональный анализ и его приложения. -1997. 31, № 4, С. 86-88.

56. Чуй Ч. К. Введение в вэйвлеты. Пер. с англ. Я. М. Жилейкина. М.: Мир, 2001. 412 с.

57. Aldroubi A., Cabrelli С., and Molter U. Wavelets on Irregular Grids with Arbitrary Dilation Matrices, and Frame Atoms for L2(Rd). Preprint. 2004. http://atlas.math.vanderbilt.edu/ aldroubi/IW.ps

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

59. Buchwald В., Mühlbach G. Construction of B-splines for generalized spline spaces from local ЕСТ-systems// Journal of Computational and Applied Mathematics 159 (2003), 249-267.

60. Daubechies I., Guskov I., Schröder P., and Sweldens W. Wavelets on irregular point sets, Phil. Trans. Math., Physical, Engng. Sei. 357 (1999), 2397- 2413.

61. Daubechies I., Guskov I., and Sweldens W. Commutation for irregular subdivision, Const. Approx. 17 (2001), no. 4, 479 514.

62. Go el J. J. Construction of basis functions for numerical utilization of Ritz's method// Numer. Math. 1968. Vol. 12. P. 435-447.

63. Miihlbach G. ECT-B-splines defined by generalized divided differences// Journal of Computational and Applied Mathematics 187 (2006), 96-122.

64. Protasov V. Fractal curves and their applications to wavelets // Proc. of the Int. Workshop on self-similar systems, July 30 August 7, 1998. - Dubna, Russia, 1999. - P. 120-125.

65. Schoenberg I. J. Contributions to the problem of approximation of equidistant date by analytic function // Qaurt. Appl. Math. 1946. Vol. 4. Pt A. P. 45-99; Pt B. P. 112-141.

66. Schumacker L. L. Spline Functions. Basic Theory. Waley Interscience. New York. 1981. 548 p.

67. Skopina M. Multiresolution analysis of periodic functions// East J. Approx. 1997. V. 3, №. P. 203-224.

68. Strang G., Fix G. Fourier analysis of the finite element method in Ritz-Galerkin theory // Stud. Appl. Math. 1969. Vol. 48, №3. P. 265273.

69. Strang G., Strela V. Short wavelets and matrix dilation equations // IEEE Trans. Signal Proc., 1995, v. 3. P. 108-115.

70. Работы автора по теме диссертации:

71. Демьянович Ю. К., Макаров А. А. Калибровочные соотношения для неполиномиальных сплайнов // Проблемы математического анализа. Вып. 34. Межвуз. сб. / Под ред. H.H. Уральцевой. Новосибирск: Тамара Рожковская, 2006. С. 39-54.

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

73. Demjanovich Yu. К., Kosogorov О. М., Makarov A. A. Wavelet Decomposition for Adaptive Irregular Grids // Twelfth International Conference in Approximation Theory. San Antonio, Texas, USA. March 4-8, 2007. Abstracts, p. 36.

74. Demy'anovich Yu. К., Makarov A. A. Calibration relations for nonpolynomial splines // Journal of Mathematical Sciences (New York), Vol. 142, No. 1, 2007. P. 1769-1787.

75. Demjanovich Yu. К., Makarov A. A. System of Embedded Spaces for Non-polynomial Splines // Third International Workshop on Reliable Methods of Mathematical Modeling. St. Petersburg, Russia. July 24-27, 2007. Abstracts, p. 11.

76. В совместных работах 71, 74, 75 , 77-80. научному руководителю принадлежит общая постановка задач и указание на идею исследования, а детальная реализация идеи полностью принадлежит диссертанту.