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

о

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

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

05.13.18 — Математическое моделирование; численные методы и комплексы программ

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

005016187

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

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

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

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

3 МАЙ Ш

005016187

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

Научный консультант:

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

Официальные оппоненты:

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

(Институт математики им. С. Л. Соболева СО РАН)

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

(Институт аналитического приборостроения РАН)

доктор физико-математических наук, профессор Скопина Мария Александровна

(Санкт-Петербургский государственный университет)

Ведущая организация: Московский государственный университет им. М. В. Ломоносова

Защита состоится 2012 г. в

часов на заседании диссертационного совета Д 212.232.51 по защите докторских и кандидатских диссертаций при Санкт-Петербургском государственном университете по адресу: 198504, Санкт-Петербург, Петродворец, Университетский пр., 28, математико-механический факультет, ауд. 405.

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

Автореферат разослан « » _ ___2012 г.

Ученый секретарь диссертационного совета ____Кривулин Н. К.

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

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

Можно считать, что теория сплайнов берет свое начало от работ Л. Эйлера, т. к. ломанную Эйлера можно рассматривать как простейшую онлайновую аппроксимацию. Дальнейшее развитие теории сплайнов связано с именами следующих ученых: Дж. Алберг, П. М. Апселоп, М. Аттья, Р. Варга, Т. Гре-вилл, Дж. Гоэл, К. Де Бор, В. Джепкинс, Э. Нильсон, Дж. Стрэиг, Дж. Уолш, Дж. Фикс, И. Шенберг, Л. Л. Шумсйкср, Б. Г. Вагер, Ю. С. Волков, О. В. Да^ выдов, Ю. С. Завьялов, Б. И. Квасов, В. Н. Малозсмов, В. Л. Мирошниченко, А. Б. Певпый, А. И. Роженко, В. С. Рябенький, С. Б. Стечкип, Ю. Н. Субботин, А. Ю. Шадрин, В. Т. Шевалдин, Н. Н. Япспко и др.

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

' Математики чаще испольчуют термин «игилег.к», инженеры — « типлст* или «нейнлет».

ционным базисом. Весьма важной характеристикой аппроксимации является число входящих в нее производных приближаемой функции. Это число называется высотой аппроксимации. Аппроксимирующий сплайн нулевой высоты использует значения приближаемой функции, по не использует ее производных; такой сплайн называется лагранжевым. Аппроксимирующий сплайн, использующий последовательные г-е производные указанной функции (г = 0,1,..., Н, где к 5 К) называется эрмитовым или сплайном высоты Ь. Обобщению аппрокси-мационных соотношений и развитию на их основе общей теории минимальных сплайнов посвящены работы Ю. К. Демьяновича, И. Г. Буровой и их учеников.

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

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

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

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

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

В случае когда (а,/3) = К1, а сетка — равномерная, удастся применить мощный аппарат гармонического анализа (в пространстве функций ^(К1) и пространстве последовательностей 12)\ здесь используются различные варианты преобразований Фурье (дискретного и непрерывного). Этому случаю посвящено большое количество исследований. В этом направлении была предложена (И. Мейср, С. Малла, И. Добсши) общая теория построения систем всплссков, названная краттюмасштабтлм анализом, (КМА).

В дальнейшем появились способы построения базисов всплесков, не основывающиеся па преобразовании Фурье. Например, лифтинговая схема (Д. Допо-хо, В. Свелдспс) — это способ построения базисов всплссков, который применяется для улучшения свойств всплесков. При помощи управляющей функции и всплсскового потока лифтинговая схема изменяет («поднимает») основной поток (низкочастотную составляющую сигнала), причем все вычисления проводятся «на месте» (т. с. в одном массиве). Еще один способ построения новых базисов всплесков — это всплесковая схема (Ю. К. Демьянович). Ввиду того, что требование вложенности пространств на двукратно измельчающейся бесконечной сетке на вещественной оси приводит к масштабирующему уравнению, решение которого в ряде случаев затруднительно, было предложено заменить требования ортогональности всплсскового базиса на процедуру построения биортогональной (к всплссковому базису) системы функционалов и заменить масштабирующую функцию (удовлетворяющую масштабирующему уравнению) па последовательность функций (удовлетворяющих калибровочным соотношениям).

Некоторой последовательностью всплеск-фупкций также порождаются системы нестационарных всплесков (М. 3. Бсрколайко, И. Я. Новиков) или поч-ти-всплесков (К. Де Бор, Р. ДсВор, А. Рон). Имеется также возможность использовать вместо всплеск-функции вектор-функцию — м,улътивсплсск.

Во многих приложениях приходится рассматривать интервал (с*,/3) С К1, поэтому необходимо строить теорию всплесков па интервале. Это вызывает значительные трудности, т. к. приходится учитывать краевые эффекты. Одним из способов построения являются периодические всплески, основанные либо на периодизации непериодических КМА (И. Мейср, И. Добеши), либо на введении определения периодических КМА (В. А. Жслудсв, А. П. Петухов, М. А. Ско-пипа).

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

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

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

сетках. В них рассматривались сплайны на открытом интервале (с*,/3), определяемые бесконечной сеткой и вектор-функцией, заданной па интервале (а,/3). Бесконечность рассматриваемой сетки (а значит, и числового потока) облегчает теоретические исследования, однако на практике приходится иметь дело с конечными потоками. Соответственно и получаемые пространства сплайнов были бесконечномерны, что пс всегда удобно для численной реализации. В работах О. М. Косогорова., Н. А. Лебединской и Д. М. Лебединского рассмотрены всплесковые разложения некоторых конечных пространств сплайнов второго порядка на. укрупняющихся сетках.

В данной работе для конечномерных пространств сплайнов произвольного порядка, получено сплайн-всплссковос разложение для измельчающихся и укрупняющихся ссток на отрезке [а, /;] с помощью сужения рассматриваемых функций с интервала (а,/3) па отрезок [а,Ь] с («,/3). В результате сплайн-всплескового разложения получаются достаточно простые формулы декомпозиции и реконструкции, определяемые используемыми конечными неравномерными сетками, причем базисные всплески имеют простое аналитическое представление и компактный носитель. Это позволяет производить сжатие, уточнение и восстановление потоков числовой информации с применением адаптивных ссток, приспосабливая последние к аппроксимации быстро меняющихся числовых потоков и существенно улучшая приближение функций, имеющих те или иные точечные особенности.

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

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

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

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

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

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

Основные результаты и научная новизна

Основные результаты, полученные в диссертации, являются новыми. Дадим их краткое описание.

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

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

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

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

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

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

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

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

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

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

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

Основные результаты были доложены на следующих конференциях и семинарах: семинар кафедры параллельных алгоритмов матсматико-механичсс.кого факультета Санкт-Петербургского государственного университета (рук. проф. Ю.К. Демьянович); семинар кафедры вычислительной математики математико-мехапического факультета Санкт-Петербургского государственного университета (рук. проф. В. М. Рябов); семинар «Дискретный гармонический анализ и геометрическое моделирование» (рук. проф. В. Н. Малозёмов); объединенный семинар кафедр высшей математики и прикладной математики и информатики Санкт-Петербургского государственного архитектурно-строительного университета (рук. проф. Б. Г. Вагер); Международная конференция «Высокопроизводительные параллельные вычисления на кластерных системах», С.-Петербург (2006), Н. Новгород (2007), Казань (2008); 12th International Conference in Approximation Thcory, San Antonio, Texas, USA, 2007; Международный конгресс «Нелинейный динамический анализ — 2007», посвященный 150-летию со дня рождения акад. А. М. Ляпунова, С.-Петербург, 2007; Всероссийская конференция по вычислительной математике «КВМ-2007», Академгородок, Новосибирск, 2007; Leonhard Euler Congress, Third International Workshop on Reliable Methods of Mathematical Modeling, St. Petersburg, 2007; Международная научная конференция «Космос, астрономия и программирование (Лавровские чтения)», посвященная 85-летию со дня рождения чл.-корр. РАН С. С. Лаврова, С.Петербург, 2008; International confcrcnr.c «Harmonie analysis and approximations, IV», dcdicatcd to 80th anniversary of ac.adcmician А. A. Talalian, Tsaghkadzor, Armcnia, 2008; International confcrence «Wavelets and applications», St. Petersburg,

2009; International conference «Mathematical and Information technologies MIT 2009», Kopaonik, Serbia, Budva, Montenegro, 2009; М1жнародшй симпоз1ум «Питания оптимизацн обчислепь», смт. Кацивел1, Украша, 2009, 2011; Международная конференция «Теория приближений», С.-Петербург, 2010; Международная научная конференция «Современные проблемы анализа и преподавания математики», посвященная 105-летию акад. С. М. Никольского, Москва, 2010; I Jaen Conference on Approximation, Ubeda, Jaen, Spain, 2010; Международная конференция «Теория приближений», посвященная 90-лстию со дня рождения С. Б. Стечкина, Москва, 2010; Российская конференция «Методы сплайп-фуикций», посвященная 80-летию со дня рождения Ю. С. Завьялова, Новосибирск, 2011; Международная конференция, по Современному Анализу, Донецк, Украина, 2011; International Workshop on.Wavelets, Frames and Applications, India, Delhi, 2011.

Публикации

Основные результаты опубликованы в 20 работах, включая статьи [1-11] в изданиях из «Перечня рецензируемых научных журналов», рекомендованных ВАК, а также монографию [19].

В работе [12] Ю. К. Демьяновичу принадлежит общая постановка задачи и указание на идею исследования, детальная реализация принадлежит А. А. Макарову. В работе [13] Ю. К. Демьяновичу принадлежит общая постановка задачи, указание возможных приложений и модельных примеров, О. М. Косогсь ровым и А. А. Макаровым поставлены численные эксперименты и предложены различные варианты способов распараллеливания всплесковых разложений, нашедших дальнейшее отражение в самостоятельных статьях. В работах [16, 17] отражены результаты совместно поставленных численных экспериментов, выполненных под руководством А. А. Макарова.

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

Диссертация объемом 349 страниц состоит из введения, семи глав, заключения, двух приложений и списка литературы, а также 22 таблиц и 21 рисунка. Список литературы содержит 340 наименований.

Связь работы с научными программами

Исследования были поддержаны грантами РФФИ (№ 07-01-00451-а, № 10-01-00245-а), грантом Президента РФ (МК-5219.2011.1), грантом АВЦП «Развитие научного потенциала высшей школы» (проект № 2.1.2/10824), грантом Санкт-Петербурга в сфере научной и научно-технической деятельности (проект N» 361/09), грантами молодым ученым, молодым кандидатам наук вузов и академических институтов, расположенных на территории Санкт-Петербурга (проекты № 26.05/151/27, № 236/14.11.11), а также отмечены дипломом победителя (1 место) XII конкурса бизнес-идей, научно-технических разработок и научно-исследовательских проектов «Молодые. Дерзкие. Перспективные», проводимого Комитетом по пауке и высшей школе Правительства Санкт-Петербурга.

СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе рассматриваются сплайны произвольного порядка, имеющие минимальный носитель. Пусть N — множество натуральных чисел, Z — множество целых чисел, Z+ =' {j | j ^ 0, j 6 Z}, R1 — множество вещественных чисел. Пусть т е Z+. Векторное (линейное) пространство {т + 1)-мерпых вектор-столбцов обозначим через Rm+1, причем векторы в ием будем отождествлять с одпос.толбцовыми матрицами'и применять к ним обычные матричные операции; в частности, для двух векторов а, b 6 Rm+1 выражение

(а, Ь)цт+1 =Г aTb = ¿[aj¿[b]¿ представляет собой евклидово скалярное ироизве-

i=0

дснис этих векторов, где Т — операция транспонировании, а компоненты векторов обозначаются квадратными скобками и снабжаются индексами 0,1,..., пг, например, а = ([а]0, [а]ь ..., [а]т)т. Квадратная матрица, столбцами которой являются векторы а0, ai,..., am G Rm+1 (в указанном порядке), обозначается символом (ein, ai,..., am), а выражение det(ao, ai,..., am) обозначает ее определитель.

Упорядоченное множество А = {aj}¿ez векторов aj 6 Rm+1 будем называть цепочкой векторов. Цепочка А называется полной цепочкой векторов, если det(aj_m, а;_1тг+1,..., a¿) ф 0 для всех j £ Z. Совокупность всех полных цепочек будем обозначать через А.

Множество всех функций непрерывных па интервале (а, ß) обозначим через С(г*, /3). Для любого числа S £ Z+ введем обозначение Cs(a, ß) =f {и \ и'1' £ С(а, ß) Vi = 0,1,2,..., 5}, полагая С°(а, ß) = С(а, ß). Если компоненты вектор-функции и £ Rm+1 непрерывно дифференцируемы S раз на интервале (а, ß), то будем писать u £ Cs(a, ß). Аналогичные обозначения Cs[а, Ь] и С5[а, Ь] будем использовать для соответствующих пространств на отрезке [а, Ь].

На интервале (а, ß) с R1 рассмотрим сетку X '= {xj}j€z,

X : ... < x_i < х„ < xi < ..., (1)

где а == lim Xj, ß == lim x.j (случаи а = —cv,ß = -foo не исключаются).

j—> — oo j—>-t-oo

Введем обозначения M '= |J (xj,xj+i), Sj '= [xj,xj+m+i], Jk == {fc — m, fc — jez

m+1, ...,k}, где к, j 6 Z.

При K0 ^ 1, Ко 6 R1 обозначим через X(Ko,a, ß) класс сеток вида (1) со свойством локальной квазиравномерности

К-1 < Ei±LZU ^ Ко V j е Z,

Xj - Xj-i

и положим hx =' sup (xj+1 — xj). je г

Пусть X(M) — линейное пространство веществениозпачпых (функций, заданных на множестве М. Рассмотрим вектор-функцию ср : (а, ß) >-> Rm+1 с компонентами из Х(М).

Если цепочка векторов А == {а^} полная, то из условий

з'Ык (2)

О М,

однозначно определяются функции <¿>¿(4), 4 € М, ж. Ясно, что вирри^) с По формулам Крамера из системы линейных алгебраических уравнений (2) находим

= —^-^ УЬ€(хк,хк+1), \ZjeJk, (3)

detía.k-тn, ЯА:-т+1, • • • , аЛ

где символьная запись Ц'-7 означает, что определитель в числителе получается из определителя в знаменателе заменой столбца а^ на столбец (с сохранением прежнего порядка следования столбцов).

Линейная оболочка функций {ш^ег называется пространством минимальных (А, 1р)-сплайнов т-го порядка или пространством минимальных сплайнов лагранжева типа (нулевой высоты) на сетке X и обозначается через

, А,ср) '= {и I и(г) = V« 6 е к1}.

з&ъ

Рассматриваемые бесконечные ряды вида £ ПРИ каждом

з

фиксированном { € (а,/3) содержат не более т + 1 слагаемых, поэтому при любой последовательности {с,}^ упомянутый ряд сходится (в смысле поточечной сходимости). Здесь и далее отсутствие пределов суммирования у знака суммы означает суммирование по всем целым числам.

Условия (2) называются аппроксимационпыми соотношениями, вектор-функция <р называется порождающей для (А, <р)-сплайнов, а цепочка векторов А называется определяющей для этих сплайнов.

В дальнейшем для вектор-функции (р € С3(а,/?),5 £ положим

<Рк

сМ

¥>(**), Ч^4 = <рМ(х*), г = 0,1,..., 5, кеЪ.

Теорема 1. Пусть 5 е ф £ С5'(а,/3), А £ А. Для того, чтобы производные функций { 6 М, У? 6 могли быть продолжены до функций, непрерывных па интервале (а,/3), необходимо и достаточно, чтобы

ае1(ак_,„,а^_т+ь ... =0

Следствие 1. Пусть 6 С'п_1(а, ¡3), А 6 А. Длл того, чтобы все функции шД£), £ € М, V? £ могли быть продолжены до функций класса Ст~1(а, ¡3), необходимо и достаточно, чтобы выполнялись соотношения

йе1(а^_т, а^_т+1,..., у^') = 0, 5 = 0,1,... ,т - 1, Ук 6 2.

Рассмотрим вектор-функцию П(г0, г;,..., гт_1) е М™+1, определяемую тождеством

Пт(гп,гь. .. ,гт_1)г = с!еЬ(г0, гь ... ,гт_1,г) (4)

для всех г, г0, гх,..., гт_! € Ет+1. Вектор-функцию П(го, ..., называют т-местным векторным произведением в пространстве Ш!т+1 и обозначают

через г0 х г] х ... х

При ¡р £ Ст~^(а,(3) рассмотрим векторы, определяемые формулой

, ас! , I]

= Ч>] X X ■ • • х <р)

(т-1)

(5)

Теорема 2. Если ¡р 6 Ст_1(а,/3), А € А и векторы <рк, (р'к,..., у^"1-1' — линейно независимые при любом к 6 Ъ, то для того, чтобы функции 4 € Л/, У; Е 2, м.огли быть продолжены до функций класса Ст~1(а, (3), необходимо и достаточно, чтобы выполнялись соотнои1ения

4+ра^- = 0, р = 1,2,... ,т, V? 6 2.

Пусть <р € С"'(а,/?). Введем следующее обозначение для вронскиана

Определим цепочку векторов А" {а^} формулой

. с!сГ ,

а_, = -с!,

(6)

В приложении 1 изучены свойства цепочки А*, в частности, доказано, что вектору а^ можно придать вид следующего символического определителя

Ъ+г

,Т (т-1)

■•• СЬ+тУУн Теорема 3. Пусть £ Ст(а, ¡5). Если выполнено условие с = соп^г > о У<е(а,/?),

(7)

и сет.ка X 6 Х{Ко, а> /5) для некоторого Кп > 1, то при. дост.ат,очн.о малом Их пространство §(А', А*, (р) лежит в пространстве С"1-1^,/3).

Замечание 1. Если ?ю интервале (а, Р) компоненты, вектор-функции (р образуют фундаментальную систему решений дифференциального уравнения вида и(т+1) + Р1 4- ... 4- рт+1(£)и = 0 с непрерывными коэффициентами,

то условие (7) выполнено.

Следствие 2. В условиях теоремы 3 цепочка векторов является

полной, при этом справедливы соотношения

4 а'^0,

4+т+1а* ф 0.

Пространство S(X,A*,y>) называется пространством минимальных Bv-сплайнов тп-го порядка на сетке X. Сами сплайны будем называть минимальными сплайнами максимальной гладкости.

Теорема 4. Пусть [y(i)]o = 1 для всех t S (а, ¡5). Если цепочку векторов An = {а^} определить формулой

^у dj+i х ... х dJ+,„ 1 [dj+i x ... x di+m]o'

то справедливо тождество

^wj(t) = 1 Vte(a,/3).

з

Пространство S(X, AN, ip) называется пространством нормализованных Bp-сплайнов т-го порядка на сетке X.

Далее рассматриваются различные формулы для представления сплайна на каждом элементарном сеточном промежутке, указывается алгоритм построения сплайнов произвольного порядка и устанавливается связь этого алгоритма с алгоритмом построения элементарных симметрических многочленов. Некоторые из формул для представления сплайнов привлекают узлы, лежащие вне носителя сплайна, что неудобно для практического применения в вычислениях. Сплайн, зависящий от минимального количества узлов, далее обозначается через cj°m(t), где т — порядок сплайна, suppw®m(i) = [xj,xj+m+j].

Теорема 5. Сплайн wjfm(£) онределмегпся узлами своего носителя Xj,Xj+i, ..., Xj+m+i и векторами

ai-LTJ,ai-LTJ+1'''' 'aMfJ-i>aJ+lTJ' dJ+i,..., dJ+m+1, ¥>f, vfX ■■■, v'+L+i, 5 = 0,1,... ,m - 1,

где через [уJ обозначена целая часть числа у.

Приведем примеры сплайнов порядка т = 0,1, 2,3. Рассмотрим измеримую функцию ip : (а,/?) >—> R1 отличную от пуля почти всюду па интервале (а,/3). Сплайнами пулевого порядка называются функции co?g(t), j € Z, удовлетворяющие условиям

o&W = ( ¡?W' (8)

0, иначе. 4 '

Сплайны w®0(i), получаемые для порождающей функции уз € С-1 (а,/9), f(t) ^ 0 для всех t £ по формуле (8), называются кусочно-непрерывными

сплайнами на сетке X, при этом u>f0(t) 6 С~1(а,/3).

Для то = 1 формулы (5) и (6), использующие т-местное векторное произведение (4), для всех ; £ 2 принимают вид = , х), х 6 М2, и а' =Г Сплайны 6 С(а, /3) и справедливы формулы

t 6 [Xj.Zj + i).

— , t&[x}+l,xj+2).

dT

j+2 j

При m = 2 сплайны G С1 (a, /3) и справедливы формулы

djV(t)

=

JJ "J

djy(t)

dJaJ dJ+3V>M

diaî

dja* df+1aj+1'

Î 6 [.Tj,X; + 1),

t e [xj+uxj+2),

t 6 [я:>+2,а;зЧ.з).

При m = 3 сплайны 6 С2(а, /3) и справедливы формулы

t, е fo.aîj+i),

=

d j<p(t) dja-+1 df+1y(Q

Ь aj dj+iaj+i

jT „• jr

d a*

dJ+Mt) dj^a;,, dj+3y>(t)

clJ+-ia; . dJ+4a} d]+3aj_!

t 6 [ij4i,ij+2), t e [xH2,xj+3),

t e [.Tj+s,.^).

Примеры полиномиальных и псполшгамиапытых сплайнов, построенных для различных порождающих вектор-функций <£>, приведены в Приложении 2. При ip(t) = (1 ,i,t2,... ,tm)T сплайны (jfm(t) совпадают с известными полиномиальными В-сплайпами тп-ой степени.

Рассмотрим конечномерные пространства сплайнов на отрезке [а, Ь] С (о:, ß). Введем обозначения

tief . (lof , <lrf [ T , -,

a = x0, b = xn, Jlrbn = {-m, — m + 1,..., n - l,n}.

Из бесконечной сетки X выделим конечную сотку Xn,ri + 1,

Хп : Х-т < ■ ■ ■ < а = Xп < xi < ... < < хп = Ь < ... < хп+т, из полной бесконечной цепочки A* G А выделим конечную цепочку А*,

. * (ÎCI

А„ =

lof |

a-m-LTJ' a-n>-L?J + l' " ' ' an-l+L 15

Для измеримого (по Лебегу) множества M С R1 обозначим через mes (.M) его лебегову меру. Пусть система {gj} состоит из функций gj(t), заданных почти везде на интервале (а, /3), и [а,Ь] С (а, /3). Система функций 1 mes (supp д,- П (а, Ь)) > 0} называется сужением системы {gj} на отрезок [а, Ь].

Сузим все функции пространства S(X, А', ¡р) на множество [а, Ь]. Совокупность этих сужений представляет собой конечномерное линейное пространство

S(X„,A;!¥3)èf{u|u(t)= £ cj^m(t) v^eRSvieMjcC-'-'M].

Теорема 6. Функция un(t) = CjUifm(t), t 6 [a, i>] является следом

jeJm,„-i

функции u(t) d== cj ' ^ (a>P) отрезке [a,b], лежит в простран-

j€'£

стве §(А"„, А*, <р) и полностью определяется набором узлов {xj}j£j„,im+„, »ia-бором векторов S = 0,1,... ,тп — 1, и набором коэффициентов

Следствие 3. Сужения функций u)fn, образуют линейно независимую систему па отрезке [а, Ь], причем dim §(Хп, А*, tp) = п + т.

Во второй главе рассматривается укрупнение и измельчение исходной сетки (бесконечной и конечной). Глава посвящена калибровочным соотношениям и построению соответствующих матриц реконструкции, откуда следует вложенность пространств Bv-crumiïnoD, построенных на различных сетках. На сетке X £ Х(К0, а, /)), полученной из сетки X € Х(К0,а, (3) удалением одного узла, строятся сплайны Устанавливаются калибровочные соотношения (обоб-

щающие масштабирующее уравнение), выражающие сплайны ôjfm (на сетке X) в виде линейной комбинации сплайнов Последовательное удаление узлов позволяет рассмотреть любую пару сеток X С X и утверждать, что справедливо вложение пространств §(Х, А , ip) С §{Х, A*, ip).

Ввиду теоремы 5 существует функция cJxlV,(f, Soi Si> • • ■ j ëm+i)> зависящая от вещественной переменной t € (а,/3) и векторов g0,gi, ■•■,gm+i € Rm+1, такая, что

Из исходной сетки X для фиксированного к 6 Ъ удалим один ^зел \ и на полученной таким образом укрупненной (разреженной) сетке X рассмотрим сплайны ] е 2.

Пусть £ =Г а х^ — узлы вновь полученной сетки X == {х\ ] € Ъ} :

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

¿ел.,«-1

{Cj}j€Jm,n-1-

= ux,v(t, djt di+1,..., dj-+m+i).

(9)

i = 0,1,..., 5, je 2,

—. — / —-{т—1)

Щ С= х 5^+2 X ... X о,-+т.

Функции можно отыскать по формуле (3), заменил узлы исходной

сетки х2 па узлы х^, ] £ 2, при этом й®г„(£) = с1]} г1)+1,..., ф+т-ц).

Введем два множества пар индексов (г, ]), полагая

М0 =Г {(г,;) | г, ] 6 {к - т, к - т. + 1,..., к.}},

'= {(¿-.?) I» = 3,3 ^ к - т - 1} и {(¿,.?) I г = - 1,.; > к + 2}.

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

к

^ 3,Г5*= "¿Г (11 а], ш°т) i = к - т, А: - т, + 1,..., к. (10)

^ = —771 з'=:к — ТП

Теорема 7. Любую функцию г 6 Ж можно представить в виде конечной линейной комбинации функций € 2,

= У':е2' С11)

3

где коэффициенты р^ определяются следующей формулой

?.,/=<! 1, (¿,.7)емь (12)

(.0, (г,.7) £ м„им,.

Соотношения (11) называются калибровочными соотношениями. Дадим их матричное представление. Введем бесконечномерные всктор-столбцы, компонентами которых являются функции и ] е Ъ\

ш"(г) (... ■ ■ ■Г-

¿в{1) Ш (... 1га(0,^т(0,гзвга(0,г^т(0,.. -Г-

Соотношения (11) представимы в виде

£в(г) = фи>д(0, 4б(а,/3), (13)

где ф — бесконечная матрица вида ф == (р;элементы которой задаются формулой (12). Матрица ф называется матрицей укрупняющей (разрежающей) реконструкции или матрицей удаления узла на интервале (а,Р).

находятся из системы (10), (г,.?) 6 Мд,

Замечание 2. Матрицу ф можно представить в виде ... /

к—гг»+1 ...

1™-1 к-тп к - т + 1 к - 1 к к + 1 к + 2

1 0 0 0 0 0 0

0 1 РА;—т,/с—тп+1 0 0 0 0

0 0 Р£-т+1,/Ь-7ГН-1 0 0 0 0

0 0 0 Рк—1,к— 1 0 0

0 0 0 0 Рк,к 1 0

0 0 0 0 0 0 1

/

Аналогичным образом рассматривается измельченная (уточненная ■ими сгущенная) сетка 1С 6 Х{К0, а, ¡5), полученная из сетки X добавлением одного нового узла £ 6 (хь, я/ь-ц). Будем надчеркивать обозначения всех рапсе введенных объектов, определяемых сеткой Х'Ш {*,. I ] 6 ху.

'} ^ к, з = к +1,

4-1, з^к + 2.

(14)

На сетке X строятся сплайны и устанавливаются калибровочные соотношения, выражающие сплайны (на сетке X) в виде линейной комбинации сплайнов Введем бесконечномерный вектор-столбец компонентами

которого являются функции у £

Тогда калибровочные соотношения представимы в виде = фг б (а,-/?),

(15)

где ф =' — матрица измельчающей (уточняющей или сгущающей)

реконструкции или матрица добавления узла на интервале (а,(3).

Последовательное добавление узлов позволяет рассмотреть любую пару сеток X С X, и утверждать, что справедливо вложение пространств §(А", А*, уз) с

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

Предполагая, что к е {0,1,...,тг — 2}, удалим узел хк+1 из сетки Хп; в результате получим укрупненную сетку

Хп

.< ... <а = :г0 <х1 < ... < х„-1 = Ь < ... < ж„+т_1,

где узлы г = —т,..., п + т — 1, определяются формулами (9). Для к € {0,1,..., п — 1} добавим узел £ € (х^, гг^-ц) к сетке Хп\ в результате получим измельченную сетку

Х — ч п

< а = х о < XI < ... < хп+1 = Ь < ... < хп+т+1,

где узлы Xi, г = —т,..., п + т + 1, определяются формулами (14). Введем конечномерные вектор-функции

def (uB —m, mWiW-m+l.mW»- • .V„W)r

2fn)(t) def .„WÄ+UO,--

def im(t),E3?m+lim(t),.. • )wn. ,n(t)Y'-

Ввиду равенства (13) в конечномерном случае калибровочные соотношения для к £ {0,1,. .., п — 2} могут быть записаны в виде

wfn)(i)=VnwfB)(l). ¿6 [а,Ь], (16)

где ф„ — прямоугольная числовая матрица размера (п + т — 1) х (п + т), называемая матрицей укрупняющей (разрежающей) реконструкции на отрезке \а,Ь}.

Ввиду равенства (15) в конечномерном случае калибровочные соотношения для к € {0,1,. .., п — 1} могут быть записаны в виде

где фп — прямоугольная числовая матрица размера (n+m) х (?г+т+1), называемая матрицей измельчающей (уточпяю-ш,ей или сгущающей) реконструкции па отрезке [а, 6].

Далее в этой главе вычисляются коэффициенты p;i3 и pi:l для сплайнов порядка т = 0,1,2,3 и приводятся соответствующие матрицы реконструкции па ин тервале и на отрезке.

Третья глава посвящена построению систем функционалов, биортогональ-ных системам минимальных сплайнов, и нахождению соответствующих матриц декомпозиции. Рассмотрим некоторое линейное пространство И над полем вещественных чисел и сопряженное ему пространство И* линейных функционалов / над пространством Н. Значение функционала f па элементе иб11 обозначим через (/, и). Введем линейное пространство С(с, d), состоящее из функций u(t) пространства C(c,d), которые имеют следующие конечные пределы lim u(i) и

i-ic+O

lim u(t). Введем также пространства

t—>d— О

сх = 0 C(xk, хк+1), С% =f {« I «W 6 Сх, Vi = 0,1,..., 5, 5 £ Z+J.

k€Z

Символом (С®)* обозначается пространство, сопряженное к пространству Cj. При <р Е Сs(a,ß) пространства §(Х, А, Lp) лежат в пространстве

Для функционала / £ (CJ)* будем писать supp/ С [с, d], если значение {/,и) определяется значениями функции и £ С^- па интервале (c,d).

Теорема 8. Пусть £ Cs(a,ß), А £ А и для каждого фиксированного к £ Z определен вектор f/t =f ([f,t]o, [it]i! • • • > [ffc]m)5 , компонентами которого

являются функционалы £ (с^)*. г = 0,1,...,т., такие, что вирр^к]; с [х1с,Х1с+1]- Пусть матрица уз7 со столбцами вида

(<Ио, [<р],), (Иь М;>, • • •, (Ит, М<>)'. * = 0,1, • • •, т,

неособенная. Тогда при каждом фиксированном числе г £ {0,1,... , т} система {ёь.}к.€7. функционалов £ (С^)*, определяемых равенствам,и

1ёк]г = [аТ-г+ш (Ъ-г+т ¥>Т) Ъ-г+т] , к & X,

представляет собой продолжение на С^ системы функциона.п.ов, биортого-нальной системе минимальных (А, <р)-сплайнов {ш^нех! гп• е- .

где 5к,к' ~ сим.вол Кронексра. При. этом эирр ^^¡г с [1ц_г+т_1, хь-г+т]-

Пусть такая система функционалов, что яирр/,- С [1^,3^+1].

Теорема 9. Для того, чтобы система функционалов {/^ег была биорто-гоналъна системе минимальных (А,<р)-сп.пайнов необходим,о и до-

статочно, чтобы

(Л', ¥>) =

Далее будем предполагать, что система функционалов {/у биортогональ-на. системе функций {и$<т}?ег> т. с. = 8^ для всех £ 2, и рас-

смотрим интерполяционную задачу

</,-,«) = ",•, У^'ей, Уие§(Х,А',ср), (18)

где — заданная последовательность чисел (бесконечная в обе стороны).

Теорема 10. В пространстве §(Х, А',<р) существует единственное решение .задачи (18), и это решение дается формулой

= (19)

з

Рассмотрим систему функционалов биортогопальную системе функ-

ций Вычислим значения функционалов на функциях

Пусть

далее

У ^3 £ Ж.

Введем два множества пар индексов (я,полагая

/0 '= {(г,;) | 1 = к - т + 1,..., к - 1,3 = к - т,..., к + 1,3 5 г + 1}, А = {('■, 3) I г = к - т. + 1,..., к - 1, з = к: - т,..., &: + 1, г ^ 3}..

Теорема 11. Для г,к € Ъ справедливы равенства

Чи =

О,

¿'еЛ.УА'

5)

и = к — т,... ,к + 1,г ^ к — т),

(ьз) 6 /о, (¿>5) е Л,

{,7 = к — т,..., к + 1, г ^ к} V + 2,

Матрица Й ^ элементы которой задаются формулами (20), на-

зывается матрицей укрупняющей (разрежающей) декомпозиции па интервале /9).

Замечание 3. Матрицу 0 можно представить в виде

к-т-1 к -тп к - гг. + 1

к -1,1 к-гп и

а**...

О ИЛ' -гп ггИ-1

<1(с-1Д—«

о о

Чк-1,к-т-И 0 о

к - 1 к Ь + 1 1 + 2

0 0 0 0

0 0 0 0

0 0 0 0

0 0 0.

0 0 1 0

0 0 0 1

Пусть =Г (/,-, для всех г,_/ 6 2. Матрица О =' называет-

ся матрицей измельчающей (уточняющей или сгущающей) декомпозиции па интервале (а,/?).

Теорема 12. Матрицы А « 1} являются левыми обратными к матрицам фт и ф соответственно, т. е.

Дф Т = 1, йф =/,

(21)

где I — единичная матрица.

Пусть далее система функционалов {fj}j^z биортогональна системе функций {ш£,„Ь"Ег.

Замечание 4. Справедливы равенства

Рм = (/¿>Ч>.). = <7,-,Ч>.) VI,] £ Ж.

Рассмотрим представление матриц декомпозиции на отрезке [а, Ь]. Выделим из множества функционалов конечный набор из п+т функционалов, из

множества функционалов {fj}j£z конечный набор из п+т — 1 функционалов, из множества функционалов конечный набор из п + т + 1 функционалов.

Теорема 13. Для систем функциона,юв {fi}isJm,,L-¡l {fj}j£Jm,n-2 и {/;}!е./т.п справедливы равенства

= ) 5 '' € Jm,n—íy

= ЛУ 6 -Лп.п-2,

= с, 6 </т,п)

причем, эирр С [о., 6], кирр С [о, 6], яирр /, С [а, Ь].

Прямоугольная матрица £2П (^¡¿),г € ,п-2>] 6 Л»,т>-ь размера (п + т — 1) х (п + т) называется матрицей укрупняют,ей (разрежающей) декомпозиции

на отрезке [а,Ь], а прямоугольная матрица =Г (Ч;^),« £ ■Лп,п-ь.7 € -Л^щ Р33" мера (га + т) х (га + т+ 1) называется матрицей измельчающей (уточняющей) декомпозиции на отрезке [а, 6].

Теорема 14. Для матриц ф„ и 0„, фп и, справедливы, соотношения

8,1 = /п+т-и 5„ С = /„+„„

где /„+„,_], Л1+Г71 — единичные квадратные матрицы порядка п + т — 1 и п + т соответственно.

Далее в этой главе вычисляются коэффициенты и для сплайнов порядка 771 = 0,1,2,3 и приводятся соответствующие матрицы декомпозиции па интервале и на отрезке.

Четвертая глава посвящена построению всплссковых разложений пространств сплайнов. Рассмотрим силайп-всплесковое сжатие на интервале. Согласно калибровочным соотношениям (11) справедливо вложение пространств

В(Х, А,<р) С 8(Х, А',<р).

Рассмотрим оператор Р проектирования пространства А',(р) на подпространство А ,</з), задаваемый формулой

и введем оператор (Э = I — Р, где / — тождественный оператор.

Пространство IV == <3§(Х,А',<р) называется пространством всплесков, а

прямое разложение _

§(Х,А',<р) = §(Х,А,<р) + № (22)

называется сплайн-всплссковым сжатием пространства §(Х, А*,<р). ,

В соответствии с равенством (22) для и 6 §(Х, А*,у>) имеем

и = Й?т + = Ц ( +

г г' ¿'г

<7„

■гак что для чисел с= (/¿/и) получаем

с,- = ^^р^ + Ь,, ;е2.

Пусть известны коэффициенты с,- в разложении элемента и е 8(Х,А',(р) по элементам базиса ш]3,,,, а именно, и =

Формулы

= X] Чм

Рг,^ I с»',

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

Введем вектор-столбцы а (... ,а-1,аи,а1,.. ,)т, Ь = (..., Ь0, Ьь .. .)т, с == (..., с_1, со, С],...)'', и перепишем формулы декомпозиции в матричном виде

а = Д с, Ь = с - фт Й с.

Применяя к предыдущему равенству матрицу Д и используя формулу (21), получаем равенство Й Ь = О, откуда следует, что вектор Ь содержится в ядре оператора О : Ь е кег Д.

. Рассмотрим пространство Ь всех числовых последовательностей, представленных вектор-столбцами 1 = (..., 1-х, Iо, . -)Т, и линейный оператор, определяемый матрицей Д в нем (это определение корректно, ибо упомянутая матрица имеет конечное число ненулевых элементов в каждой строке). Ядро этого оператора представляет собой линейное пространство; обозначим его через Ъ = {Ь | Ь = (..., Ь_ь 60, йь .. ,)т, Й Ь = 0}, т. е. Ъ = кег О.

Рассмотрим еще два экземпляра пространства Ь, обозначая их через А и С. Элементами пространства А являются векторы а, а элементами пространства С являются векторы с. Пусть У — прямое произведение пространств А и Ъ: $ = Ах 3, т. е.

а € А, Ь е В

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

£> : е ►-» У, Я) =

для которого

о

7-фгД У '

а = Д с

Ь = (/ — фтЙ) с '

этот оператор называется оператором декомпозиции.

Пусть теперь известны коэффициенты и iv в разложениях проекций элемента и £ S(X, А*, у) на пространства §(Х, А , ip) и W:

i i'

Найдем формулы для определения коэффициентов Cj для представления элемента и в виде суммы и = упомянутые формулы имеют вид (23)

з

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

Оператор £4 : J н-> С, ОТ =f (ф7" ij , для которого

с = = /) <^с = фт5 + Ь,

называется оператором реконструкции.

Теорема 15. Операторы lüji Щ^взаимно обратны; они реализуют линейный изом,орфизм пространств С и 3".

Рассмотрим сплайн-всплесковое сжатие па отрезке. Согласно калибровочным соотношениям (1С) справедливо вложение пространств

S(Är„,Ä*,v>) С S(X„,A;,¥>).

Рассмотрим оператор Р„ проектирования пространства S(Xn, А*, (р) на подпространство S(X„, A„,ys), задаваемый формулой

РпУ= J2 ÔEÎ = <Л,«>, Vue S(Xn,A;,v),

clef

ie.U.n-

и введем оператор <2„ = /- Р„, где I — тождественный в Б(Х„, А*, <р) оператор.

Пространство \¥п =Г §(Х„, А*, у) называется пространством всплесков, а прямое разложение

§(Х„,А;,¥>)=§(^,А*,¥') + Й;:п (24)

называется сплайн-всплесковым сжатием пространства 8(Х„, А*, <£>). В соответствии с равенством (24) для и £ §(Х„, А",,у>) имеем

и= £ Е ( Е ъйу+й')"]?™. ,

так что для чисел с,- = (/¿,и) получаем

с,- = Е ^¡р^+Ь,-, V.? е ,/,„,„_ь (25)

•€.7т.„-а

Пусть известны коэффициенты ^ в разложении элемента и £ §(А'„, А*, у>) по элементам базиса а именно, и = X] сзш£т-

jC.7rn.n-l

Формулы

г,= £ ч^с*, УгеЛ.,«-», (20)

i'eJ,„,„-l

Ьз=с1~ ( Р^'Чм')с«', 1, (27)

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

Введем вектор-столбцы а„ ^ (а_ш, а_,„+1, •. •, «п-2)7 , Ь„ = (¿-т, Ь_т+1, •. ■, Т \т ~ ~ ~

Оп-1; I сп — Vе-"" с-т+1> • ■ ■ 1 с11-1) ■

Рассмотрим пространство 6 М, всех числовых последовательностей,

представленных вектор-столбцами (1-т, 1-т+\, ■ ■ ■, ';)т, и линейный опе-

ратор из пространства С„ 1Ь„_1 в пространство Л„ =Г Ь„_2, определяемый матрицей Оп в нем. Ядро этого оператора представляет собой линейное пространство; обозначим его через 23„ = {Ь„ | Ьп = (Ь_,„, ¿-т+1> • • • > К-1)Т, П„Ь„ = 0}, т. е. В„ = кегЙ„.

Пусть 3"„ — прямое произведение пространств -Д.,, и Ъп : = Ап х т. е.

5„ е Л„, Ь„ е

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

э„: е„ V» ©„ ^ _ .

для которого

!-Л _ 5 н _ ( ^ „ \ 15„ = а„сп _

ьп) ~ с" ^ - жап)с" ^ \ь„ = (/ - г„ '

этот оператор называется оператором декомпозиции.

Пусть известны коэффициенты а,-, г £ Зт (П_2 н Ь;', г £ ^т,п— 1 в разложениях проекций элемента и £ А*, <^э) на пространства 8(ХП, А„, у>) и

йЛ„,„-г „,„-1

Найдем формулы для определения коэффициентов сГ^ для представления элемента и в виде следующей суммы и = упомянутые формулы

имеют вид (25) и называются формулами реконструкции. Оператор ОХп : Э"„ >-> С„, =Г , для которого

называется оператором реконструкции.

Теорема 16. Операторы, Т)п и взаимно обратны; они реализуют линейный изоморфизм пространств С„ и ?„.

Рассмотрим сплайп-всилесковое уточнение па интервале. Согласно калибровочным соотношениям (15) справедливо вложение пространств §(Х, А',(р) С S(X,A ,<р). Используя систему функционалов {fj} для построения оператора проектирования пространства §(Х, A ,ip) на подпространство §(Х, А*,у>) находим следующее представление

называемое сплайн-всплесковым уточнением пространства А , <р), IV — пространство всплесков, которое натянуто па Д,-снлайн, соответствующий добавленному (к сетке X) узлу. Согласно калибровочным соотношениям (17) справедливо вложение пространств §(Х„,А^,¥>) С §(Х„, Ап,1р), откуда находим представление

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

Далее в данной главе для последовательности вложенных сеток рассматриваются варианты систем вложенных пространств Д^-сплайпов (телескопы-ческие системы пространств), для которых получено разложение в прямую сумму всплесковых пространств, приведены соответствующие формулы декомпозиции и реконструкции для сплайнов порядка то = 0,1,2,3.

В пятой главе рассматриваются вопросы аппроксимации минимальными сплайнами максимальной гладкости. Пусть дана функция и е Ст+1(а, /3). Рассмотрим сплайн

п

i

где (/3-,!|) — некоторые линейные функционалы над пространством Ст+1(а, /3), которые в этом случае будем называть аппроксимационными. Введем обозначения е"= (0,..., О,1)т,

u(t) MoW [v»]l (0 ••• Mm(t)

«'(О M'oW MiW ••• W,n(t)

u"(t) MSW MiW ... им

«(m)M Mim)(0 ••• [#w

„<•»«)(«) Mim+l)(o •■•

rm + 1

Теорема 17. Если и 6 Ст+1(а,(3), t G то справедливо представ-

ление

к

Uft(t) -«(*)= X] <Л. ^mW,

j=k—in

где символ • означает переменную, по которой вычисляются функционалы fj.

Аппроксимация (28) при t е (х/,, xk+i) обладает свойством точности на функциях и е {[vL | -5 = 0,1,-.- ,m}, т. е.

uh{t)=u{t) при и G {[у]> | s = 0,1,... , т}.

Далее в главе приводятся результаты численных экспериментов по аппроксимации сплайнами порядка т = 0,1,2,3. Аппроксимация (28) рассматривалась на отрезке [а, Ь] для сеток вида Хп '= {xj = а + j(b — а)/п, j = 0,..., п}, и искалась экспериментальная погрешность приближения Е"1 = max lu^fi) —u(t)\

t£[a,b]

иа вспомогательной более мелкой сетке. В качестве набора тестовых функций использовались, например, функция Рупге 1+25ta и некоторые другие суперпозиции элементарных функций. В качестве порождающих вектор-фупкций выбирались, например, вектор-функция ip(t) = (1, sh t, ch t)T и многие другие варианты. Построенные аппроксимации обладают свойством точности на компонентах вектор-функции ip.

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

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

Рассмотрим сплайп-всплеековос сжатие и уточнение с соответствующими формулами декомпозиции и реконструкции. Для удобства одновременного рассмотрения упомянутых выше объектов введем единые обозначения а = (..., а_ь ао, «1,.. ,)Т либо (... , a_i, а0, ai,.. .)т, b =f (..., , bo, b\, ■ ■ ■)' либо (... ,b~i, bo,

.. (. .. .c-i.^j.ci,.. .)т либо (... ,c_i,c0,ci,.. .)т,ф '= ф либо ф,Д '=

£2 либо Д, соответственно.

Для векторов a,b,c и матриц ф,£} справедливы формулы декомпозиции

а = Ос, b = с — фг О с, (29)

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

с = ф7 а + Ь. (30)

Вектор с называется исходным потоком, вектор а — основным потоком, вектор b — всплесковым потоком.

Рассмотрим дна экземпляра введенного ранее пространства L, обозначая их через Л и С. Элементами пространства А являются векторы а = (..., a_i, во, а\, .. ,)т, а элементами пространства С являются векторы с = (..., со, с\, .. ,)т. Матрицы ф и £2 будем рассматривать как линейные операторы, действующие из пространства С в пространство А. Упомянутые линейные операторы будем обозначать теми же символами ф,£! £ [С >—► А]. Оператор фт, порождаемый транспонированием матрицы ф, будем рассматривать как оператор, действующий из пространства А в пространство С : фг £ [А \—> С]. Пространство С называется пространством, исходных потоков.

Рассмотрим формулы декомпозиции (29) и реконструкции (30) при а £ Л, с, b £ е. Обозначим через /д и I<¡ тождественные операторы в пространствах Л и С соответственно. Ввиду равенств (21) справедливо соотношение £3фт = 1л и, следовательно, верно равенство £Jb = 0. Таким образом, вектор b £ kerO.

Рассмотрим подпространство S пространства С, определяемое равенством S =г {а | а = фга' Va' £ Л}, и положим В = kcrO.

Теорема 18. Оператор ф7', рассматриваемый в паре пространств А и S, фг : [Л i—» S], является изоморфизмом от,их пространств. Обратным оператором слуо/сит сужение оператора £¡ на подпространство S :

окНФТ1-

Теорема 19. Пространство С может быть представлено е виде прямой суммы

e = s + B.

Оператор SK =f фт£2 проектирует пространство С на подпространство S, а оператор /е — проектирует, пространство С на подпространство Ъ.

Теорема 20. Если Su®— гильбертовы пространства со скалярными произведениями (si,s2)s и (bi,b2)s соответственно, то относительно скалярного произведения, в пространстве 6, вводимого для любых элементов сьс2 £ fe по формуле

(сьс2)е d=* (s1,s2)s + (bi, b2)s, s¡ "=' Эта,, Ь, = (Ie - i = 1,2,

линейный оператор (фг)+ £ [£ 1—> С], задаваемый соотношением

я,вляет.ся пеевдообратнъш оператором.

Норму, порождаемую скалярным произведением в пространстве С, обозначим через ||с[|'= yj(с, c)g, с £ е.

Следствие 4. Уравнение

фга = с0,

рассматриваемое при фиксированном с0 £ С относительно а £ Л, разрешимо при Со £ 2, а при са $ В это уравнение не имеет решения,. Вектор

a,(=f (фт)+Со может рассматриваться как «наилучшее обобщенное решение» уравнения в том смысле, что

||фта. - с0|| ^ ||фта - Со|| Vag-A, причем равенство достигается лишь при а = а».

Оценим число арифметических операций в формулах декомпозиции (29) и реконструкции (30) без учета числа операции необходимых при вычислениях элементов матриц ф и Q. Оценка этого количества может быть получена при конкретных вариантах задания порождающей вектор-фупкции <р.

Теорема 21. При декомпозиции для отыскания каждого элемента основного потока требуется не более т мультипликативных и не более т — 1 аддитивных операций, а для отыскания всплескового потока дополнительно требуется не более 2 мультипликативных и не более 2 аддитивных операций. Для определения каждого элемента реконструируемого исходного потока требуется не более 2 мультипликативных и не более 2 аддитивных операций.

def

Следствие 5. Если пространства Л, С — конечномерны и N = dim Л, М = dim С — их размерности, то при декомпозиции для отыскания основного потока требуется не более Nm мультипликативных и не более N(m — 1) аддитивных операций, а для отыскания всплескового потока дополнительно требуется не более 2М мультипликативных и не более 2М аддитивных операций. Для определения реконструируемого исходного потока требуется не более 2М мультипликативных и не более 2М аддитивных операций.

Для г, j € Z введем обозначения

{i I р. . ф 0}, Q(i) =Г {j | qij ф 0},

Р =fsup У] IPijl, Q =f sup V |q;j|. 'ez iep«> ,ez ieg«>

Пусть pj — число ненулевых элементов в j-й строке матрицы ф7, а ® — число ненулевых элементов в г-й строке матрицы Д. Ясно, что для чисел pj и qi справедливы равенства;^- = \P^\,qi = |<3'''|-

Будем считать, что пространства А и С сужены так, что их элементы имеют

конечные нормы ЦаЦоо^ sup|[a];|, ЦсЦ«,^ sup |[с]j| соответственно, iez j€Z

Теорема 22. При декомпозиции для векторов а и Ь справедливы оценки INloo^ QlHIoc, ||ЬЦОТ (1 -+- QP)

а при реконструкции верно неравенство

||с||оо < РЦаЦоо + ЦЬЦоо .

Далее в главе даны способы распараллеливания всплесковых разложений. Приведены параллельные формы для вычисления формул декомпозиции и реконструкции. Представлены результаты применения алгоритмов декомпозиции и реконструкции к сжатию и восстановлению модельных числовых потоков, в том число и изображений. Приводятся результаты численного сравнения сплайн-всплескового алгоритма сжатия (па неравномерной сетке) и алгоритмов сжатия, использующих различные известные всплески (па равномерной сетке). Упомянутые методы сжатия применялись к набору одномерных сигналов, генерируемых модельными функциями u(t). В качество критерия сравнения методов была взята оценка погрешности приближения Е = max \uc(t) — ?/.(i)|, где v.c — зиачс-

иия сжатой функции в узлах исходной сетки. Для сжатия сигнала известными всплесками использовался пакет Wavelet Toolbox системы MATLAB, в котором, в частности, реализован всплеск Хаара (liaar), всплески Добенш (db2-db5), кои-флетьг (coifl-coif3), биортогоналытые всплески (bior2.2, bior3.1-bior3.5). Например, для сигнала, генерируемого модельной функцией u(t) = sin(301) на отрезке [а, Ь] = [0,1] с сеткой Хп,п = 1000, перечисленные всплески заметно уступают сплайп-всплссковому сжатию Д^-сплайпами, ip(t) = (l,i,i2)T, при сжатии данного сигнала в 20 и, особенно, в 100 раз. Сплайи-всплссковый метод сжатия па неравномерной секте также показал лучшие результаты при большом сжатии (в 100 и более раз) и во всех других рассмотренных случаях.

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

Программный комплекс состоит из отдельных модулей (функциональных блоков), написанных с использованием языка программирования С* и системы компьютерной математики Maple; дадим их краткое описание.

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

Второй блок (InpntFlowGenerator) выполняет генерацию исходного потока при помощи чисел Cj '= (fj,u), где и — функция, задаваемая либо некоторой модельной функцией, либо массивом отсчетов значений сигнала. Аналогично интерполяционной задаче (18) ищется соответствующее решение (19).

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

числового потока. Далее по формулам декомпозиции (20)-(27) получается основной и всплесковый потоки.

В четвертом блоке (Restorer) по основному потоку строится сплайн, который приближенно восстанавливает исходный поток. При этом происходит «восстановление с потерей информации».

• В пятом блоке (Reconstructor) по основному и всплесковому потокам, используя формулы реконструкции (25), строится сплайн, который полностью реконструирует исходный поток.

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

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

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

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

[1] Макаров А. А. Об одном алгебраическом тождестве в теории В^-сплайиов второго порядка // Вести. С.-Петерб. ун-та. Сер. 1. 2007. Вып. 1. С. 96-98. (Vestuik St. Petersburg University: Mathematics, 40 (2007), но. 1, 85-88.)

[2] Макаров А. А. О распараллеливании вэйвлетиых методов сжатия информации // Вести. С.-Петерб. ун-та. Сер. 10. 2007. Вып. 4. С. 45-49.

[3] Макаров А. А. Нормализованные тригонометрические сплайны лаг-ранжева типа // Вести. С.-Петерб. ун-та. Сер. 1. 2008. Вып. 3. С. 81-87. (Vestuik St. Petersburg University: Mathematics, 41 (2008), no. 3, 266-272.)

[4j Макаров А. А. О вэйвлетном разложении пространств сплайнов первого порядка // Проблемы матем. анализа. 2008. Вып. 38. С. 47-G0. (J. Math. Sci. 156 (2009), no. 4, 617-631.)

[5] Макаров А. А. Моделирование калибровочных соотношений для неполи-помиальных сплайнов // Вычисл. технологии. 2008. Т. 13. Спец. вып. 4. С. 94-100.

[6] Макаров А. А. Один вариант сплайн-вэйвлетного разложения пространств

i В-сплайнов // Вестн. С.-Петерб. ун-та. Сер. 10. 2009. Выи. 2. С. 59-71.

[7] Макаров А. А. О построении сплайнов максимальной гладкости // Проблемы матем. анализа. 2011. Выи. 60. С. 25-38. (J. Math. Sci. 178 (2011), no. G, 589-604.)

[8] Макаров А. А. Матрицы реконструкции и калибровочные соотношения для минимальных сплайнов // Проблемы матем. анализа. 2011. Вып. 60. С. 30-52. (J. Math. Sei. 178 (2011), no. 6, 605-621.)

[9] Макаров А. А. Матрицы реконструкции и декомпозиции для линейных сплайнов // Труды СПИИРАН. 2011. Вып. 18. С. 215-236.

[10] Макаров А. А. Алгоритмы вэйвлетпого уточнения пространств сплайнов первого порядка // Труды СПИИРАН. 2011. Вып. 19. С. 203-220.

[11] Макаров А. А. Матрицы добавления и удаления узлов для нсполиноми-альпых сплайнов // Вычислительные методы и программирование. 2012. Т. 13. С. 74-86.

[12] Демьянович 10. К., Макаров А. А. Калибровочные соотношения для иепо-линомиальиых сплайнов // Проблемы матем. анализа. 2006. Вып. 34. С. 39-54. (J. Math. Sei. 142 (2007), по. 1, 1769-1787.)

[13] Демьянович Ю. К., Косогоров О. М., Макаров А. А. Возможности распараллеливания вэйвлетпо-сплайпового сжатия па неравномерной сетке // Высокопроизводительные параллельные вычисления на кластерных системах. Материалы Седьмой Международной конференции-семинара. — Н. Новгород: Изд-во ННГУ, 2007. С. 381-384.

[14] Макаров A.A. Сплайн-вэйвлстная модель аппроксимации на неравномерной сетке // Космос, астрономия и программирование (Лавровские чтения): Тезисы докладов междунар. науч. конференции, С.-Петербург, 20-22 мая 2008 г. - СПб.: Изд-во С.-Петерб. ун-та, 2008. С. 216-221.

[15] Макаров А. А. Минимальные тригонометрические сплайны нулевой высоты // Методы вычислений. Выи. 22. Сб. / Под ред. В. М. Рябова. — СПб.: Изд-во С.-Петерб. ун-та, 2008. С. 82-98.

[16] Косогоров О. М., Макаров А. А. О сплайи-вэйвлетпом сжатии па неравномерной сетке // Питания оптимизацп обчислснь (ПОО-XXXV): Прайд М1жнародного симпозиуму, смт. Кацивел], Украша, 24-29 всросня 2009 р. — Кшв: 1пститут мберпетнки ÎMeni В. М. Глутпкова, 2009. Т. 1. С. 340-345.

[17] Kosogorov О. М., Makarov A. A. Spline wavelet decomposition and parallel compression // Zbornik radova konfcrcncije MIT 2009. University of Pristina. Bcograil, 2010. P. 202-205.

[18] Макаров А. А. Кусочно-пспрсрывиыс сплайн-вэйвлсты на неравномерной сетке // Труды СПИИРАН. 2010. Вып. 14. С. 103-131.

[19] Макаров А. А. Сплайн-вэйвлетные разложения на неравномерной сетке. Некоторые варианты построения. Lambert Academic Publishing, 2010. 130 с.

[20] Макаров А. А. Сплайн-вейвлетное сжатие на отрезке // Семинар «DHA k CAGD». Избранные доклады. 12 ноября 2011 г. (http ://dha.spb.ru/reps11.shtml#l112)

Подписано к печати 22.02.12. Формат 60x84 'А . Бумага офсетная. Гарнитура Тайме. Печать цифровая. Печ. л. 2,00. Тираж 100 экз. Заказ 5385.

Отпечатано в Отделе оперативной полиграфии химического факультета СПбГУ 198504, Санкт-Петербург, Старый Петергоф, Университетский пр., 26 Тел.'. (812) 428-4043, 428-6919

Введение

1 Пространства минимальных сплайнов

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

1.2 Пространства минимальных сплайнов лагранжева типа.

1.3 Пространства минимальных сплайнов максимальной гладкости

1.4 О представлении элементарных симметрических многочленов

1.5 О представлении сплайнов произвольного порядка.

1.6 Сплайны порядка m = 0.1. 2, 3.

1.7 Конечномерные пространства сплайнов.

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

2.1 Калибровочные соотношения и матрицы реконструкции для сплайнов произвольного порядка.

2.2 Матрицы реконструкции в частных случаях.

2.2.1 Сплайны нулевого порядка.

2.2.2 Сплайны первого порядка.

2.2.3 Сплайны второго порядка.

2.2.4 Сплайны третьего порядка.

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

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

3.2 Матрицы декомпозиции в частных случаях.

3.2.1 Сплайны нулевого порядка.

3.2.2 Сплайны первого порядка.

3.2.3 Сплайны второго порядка.

3.2.4 Сплайны третьего порядка.

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

4.1 Всплесковое сжатие пространств сплайнов.

4.2 Всплесковое уточнение пространств сплайнов.

4.3 О вариантах телескопических систем и их всплесковых разложениях

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

4.4.1 Сплайны нулевого порядка.

4.4.2 Сплайны первого порядка.

4.4.3 Сплайны второго порядка.

4.4.4 Сплайны третьего порядка.

5 Аппроксимация минимальными сплайнами

5.1 Представление остатка приближения и реализация точности аппроксимации.

5.2 О другом представлении остатка приближения.

5.3 Численные эксперименты по аппроксимации.

5.4 О порядке малости всплесковой составляющей.

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

6 Всплесковые разложения пространства потоков

6.1 Всплесковое разложение пространства исходных потоков

6.2 О количестве арифметических операций.

6.3 Устойчивость вычислений при декомпозиции и реконструкции

6.4 О распараллеливании всплесковых разложений.

6.5 Моделирование потоков данных. Сжатие, восстановление и реконструкция

6.6 Сравнение аппроксимации и сжатия числовых потоков.

6.7 Сжатие, восстановление и реконструкция изображений.

7 Программный комплекс

7.1 О среде разработки

7.2 Компоненты комплекса.

7.3 Ключевые моменты реализации

Объёмы информационных потоков постоянно увеличиваются, соответственно растут и объёмы числовой обработки этих потоков. Современные потоки информации в процессе обработки, хранения и передачи имеют цифровую форму: чаще всего это последовательности (массивы) нулей и единиц огромной длины. Такие последовательности можно быстро обрабатывать лишь в случае наличия колоссальных компьютерных ресурсов, обладающих быстродействием, огромной памятью, мощными каналами связи. Задача сокращения объёмов цифровой информации за счёт отбрасывания несущественных составляющих чрезвычайно актуальна, причём степень важности эффективного решения этой задачи постоянно возрастает. Ввиду этого требуется разрабатывать эффективные алгоритмы сжатия сигналов и передачи информации по каналам связи с ограниченной пропускной способностью. Под эффективностью понимается разложение потока информации на составляющие с минимальными затратами ресурсов ЭВМ (памяти и времени обработки). С другой стороны, часто возникают задачи уточнения полученного решения за счёт измельчения расчётных сеток, при этом требуется разрабатывать эффективные алгоритмы уточнения потоков данных. Сплайны и всплески1 широко применяются при решении упомянутой задачи, что подтверждается большим числом приложений в различных научных и технических областях, например, в вычислительной математике, геометрическом моделировании, медицине, космической технике, астрономии, геофизике, биологии, нанотехнологических разработках, экономике и т. д.

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

Можно считать, что первое направление берёт своё начало от работ Л. Эйлера, т. к. ломанную Эйлера можно рассматривать как простейшую сплайно

1 Математики чаще используют термин «всплеск», инженеры — «вэйвлст» или «всйвлст». вую аппроксимацию. В 1926 году В. Дженкинс [247] фактически рассматривал сплайны, когда исследовал кусочно-полиномиальные функции в теории оскуляторной интерполяции; в 1944 году Т. Гревилл [239] систематизировал подход Дженкинса. Изначально термин «сплайн» (англ. spline) использовался для названия гибкой линейки, применявшейся для проведения гладких кривых через заданные точки. Математика получила этот термин в 1946 году благодаря работам И. Шёнберга [290], в которых было введено понятие сплайна как кусочно-полиномиальной функции. Ю. С. Завьялов предложил их называть «многозвенниками» [83], однако такое название не прижилось. Здесь исходным моментом является решение какой-либо задачи интерполяции (задачи Лагранжа, Эрмита или Эрмита-Биркгофа) в классе функций с «кусочными» свойствами с определённой гладкостью в узлах рассматриваемой сетки (см. [84, 115, 157, 192, 280, 291, 292]). Принципиальным достижением этой теории стало построение В-сплайнов (базисных сплайнов), которые при заданной гладкости имеют минимальный носитель. Это обеспечивает при введении новых узлов интерполяции лишь локальное изменение интерполирующего сплайна. Аппроксимационные свойства и вычислительная простота получаемых сплайнов всякий раз исследуются дополнительно. Сюда относятся современные исследования по обобщённым сплайнам, так называемым ЕСТ-В-сплайнам (см., например, [192, 280]); в этих работах для построения сплайнов на сеточных промежутках используются различные ЕСТ-системы, которые при определённых условиях удаётся гладко «склеить» в узлах.

В дополнение к описанию первого направления отметим, что общая теория сплайнов базируется на двух основных подходах: алгебраическом и вариационном. В алгебраическом подходе сплайны понимаются как гладкие кусочные функции (подробнее см. монографии [35, 84, 157]). Сюда относится и теория L-сплайнов не являющаяся ни классической, ни наиболее общей [22]. Обнаружение в 1957 году Дж. Холладеем [244] глубокой связи между сплайнами Шёнберга и многоточечными вариационными задачами дало начало вариационному подходу (см., например, монографии [23, 105]). В дальнейшем выяснилось, что вариационный подход открывает широкие возможности для обобщения понятия сплайна. Это привело в 1965 году к введению М. Аттья [184] общего определения сплайна как элемента гильбертова пространства, минимизирующего определённый функционал. Заметим, что похожие результаты неявно содержались в ином виде в статье М. Голомба и X. Вайнбергера [238] в 1958 году. Затем в 1968 году П. М. Анселон и П.-Ж. Лоран предложили общий алгоритм построения таких сплайнов. Иногда отдельно выделяют подход [179], связанный с определением сплайна как решения дифференциальных многоточечных краевых задач. Существует большое количество публикаций, посвященных как теоретическим исследованиям, так и практическому применению сплайнов (см. [1, 21, 91, 292] и библиографию там). Для разработки экономичных методов используют локальные функции с минимальным носителем (см. [35, 37, 149]). Отметим недавно вышедшие по сплайнам монографии Б. И. Квасова [91], А. П. Колесникова [94], М.-Дж. Лай и Л. Л. Шумейкера [255], А. И. Роженко [148], С. Ф. Свиньина [150|, Л. Л. Шумейкера [292]. Упомянем также работы О. Л. Виноградова и В. В. Жука [25, 26], Ю. С. Волкова [29], О. Давыдова и Л. Л. Шумейкера [219], Ю. С. Волкова, В. В. Богданова, В. Л. Мирошниченко и В. Т. Шевалдина [30],

B. П. Заставного и Р. М. Тригуба [85], В. Н. Малозёмова и Н. В. Чашникова [120, 121], В. Н. Малозёмова и А. Б. Певного [116], Ю. Н. Субботина [163, 164], Ю. Н. Субботина и С. А. Теляковского [165], А. Ю. Шадрина [293].

Второе направление опирается на аппроксимационные свойства получаемых сплайнов, где определение базисных функций связано с решением ап-проксимационных соотношений, рассматриваемых как система уравнений. Эти исследования появились в связи с теорией метода конечных элементов. Такой подход применялся Дж. Гоэлом [237], Дж. Фиксом и Дж. Стрэн-гом [300]. В 1973 году С. Г. Михлиным и Ю. К. Демьяновичем [69] предложен подход (ориентированный на построение простейших аппроксимаци-онных формул) к построению полиномиальных сплайнов, удовлетворяющих аппроксимационпым соотношениям и имеющих заданную гладкость. При этом сначала минимизируется кратность накрытия (так называется минимальная кратность перекрытия носителей базисных функций) базисных сплайнов, а затем степень сплайнов. Построенные таким образом функции называются минимальными сплайнами для данных аппроксимационных соотношений и для заданной гладкости. Ввиду важности этих соотношений

C. Г. Михлин [123] называл их фундаментальными. Если воспользоваться аппроксимационными соотношениями интерполяционного характера, то получатся аппроксимации, точные на полиномах определённой степени (показатель этой степени называется порядком точности). Отсюда можно найти минимальные сплайны с локальным интерполяционным базисом. Весьма важной характеристикой аппроксимации является число входящих в неё производных приближаемой функции. Это число называется высотой аппроксимации. Понятие высоты введено С. Г. Михлиным [123]. Аппроксимирующий сплайн нулевой высоты использует значения приближаемой функции, но не использует её производных; такой сплайн называется лаграпэюе-вым. Аппроксимирующий сплайн, использующий последовательные г-е производные указанной функции (г = 0,1,.,^, где Н Е М) называется эрмитовым или сплайном высоты К. Обобщению аппроксимационных соотношений и развитию на их основе общей теории минимальных сплайнов посвящены работы Ю. К. Демьяновича и его учеников, в которых построенные аппроксимации обладают свойством точности на степенях заданной произвольной достаточно гладкой функции. В данной работе найдено простое представление определяющей цепочки векторов для построения минимальных сплайнов лагранжева типа максимальной гладкости произвольного порядка, указан новый алгоритм построения таких сплайнов, установлена связь этого алгоритма с алгоритмом построения элементарных симметрических многочленов. При таком подходе интерполяционные свойства и алгоритмы минимизации вычислительной сложности (вложенность пространств и всплесковое представление цепочки вложенных пространств) приходится устанавливать дополнительно. Выбор порождающей (т + 1)-компонентной вектор-функции заданной на интервале (а.р), определяет семейства конечномерных пространств на элементарных сеточных интервалах рассматриваемой (конечной или бесконечной) сетки X = X С а выбор цепочки А, состоящей из векторов со свойством полноты, приводит к пространству (А. </?)-сплайнов. Условия гладкости эквивалентны определённым алгебраическим соотношениям между значениями (и её производных) в узлах сетки и векторами цепочки А. Требование максимальной гладкости сплайнов (при выбранной вектор-функции </?(£) с отличным от нуля вронскианом из её компонент) однозначно (с точностью до постоянных отличных от нуля множителей) определяет цепочку А; при этом однозначно определяется также пространство (А, (¿?)-сплайнов, которое в этом случае называется пространством В^-сплайиов. Заметим также, что пространства ЕСТ

В-сплайнов находятся среди пространств (А, у?)-сплайнов; они получаются, если в качестве компонент вектор-функции ip(t) при t G (xk, Xk+i) взять (возможно, различные) ЕСТ-системы (вронскиан ЕСТ-системы всегда отличен от нуля, что важно для построения Д^-сплайнов, являющихся в этом случае Е'СТ-В-сплайнами максимальной гладкости). Отметим недавно вышедшие монографии И. Г. Буровой и Ю. К. Демьяновича [14, 15], Ю. К. Демьяновича [38, 43], А. А. Макарова [334]. Упомянем также работы Ю. К. Демьяновича [49, 54], И. Г. Буровой и Ю. К. Демьяновича [16], И. Г. Буровой и А. Ф. Дёминой, Т. О. Евдокимовой, В. А. Тимофеева, И. Р. Хассан [13, 17-20], Ю. К. Демьяновича и О. Н. Иванцовой, О. М. Косогорова, А. А. Макарова [61, 63, 319], А. А. Макарова [325, 329, 335].

Третье направление относится к теории всплесков, в которой выделяют два раздела, в каждом из которых вводится объект, называемый всплеск. Вообще говоря, эти два объекта близки, но неэквивалентны. Большинство существующих всплесков являются модификациями этих двух объектов. В первом разделе рассматривается произвольная функция ф, чьи сдвиги (translations) и сжатия/растяжения (contractions/dilations) образуют систему представления в каком-либо смысле. Например, если функция ф £ L2(R1), то рассматривают систему функций образующую ортонормированный базис пространства Ь2(Ж.1). Тогда любая функция / 6 Ь2(М1) может быть представлена в виде ряда где через (/, д) обозначено скалярное произведение функций f.g Е L2(RX) ipj,k(x) = 2J/2 ф(2 Зх-к), J., к 6 Z, 00 +оо

1) J оо а черта над функцией означает операцию комплексного сопряжения.

Функция ф называется всплеском. Такой всплеск также называют базовым, образующим или материнским. Система функций называется системой всплесков, ряды из представления (1) называются всплеск-рядами.

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

Во втором разделе теории всплесков свойства исследуемой функции / (Е 1/2(К1) изучаются при помощи функции ф, задающей ядро фа\х) М |а|-1/2ф ) , а,ъ е Ж1, а ф 0, (2) интегрального преобразования оо }{х)ф^{х)дх. (3)

Функция ф £ Ь2(Ш}), удовлетворяющая условию допустимости

00 ^

Щ^сЬк+оо, (4)

7 и; где через ф обозначено преобразование Фурье функции ф, называется всплеском в пространстве Ь2(Ш}). Такой всплеск также называют базовым, образующим или материнским. Выполнение условия допустимости (4) требуется для нахождения формулы обращения преобразования (3). Если ф — базовый всплеск, то для любых /. д € 1/2(М1) справедливо равенство оо +00

И^/)(а, Ъ) ЩЩЪ) ^ = (/, д), а оо —оо более того, для любой точки х. в которой функция / непрерывна, верна формула оо +оо

1 [ , ч , „ А, ч да дЬ т ь)фа-\х) (5) оо —ос

Преобразование (3) называется непрерывным (или интегральным) всплеск-преобразованием, преобразование (5) называется обратным непрерывным (или обратным интегральным) всплеск-преобразованием.

Заметим, что если функция ф е Ь (М ), то её преобразование Фурье ф непрерывно; следовательно, неравенство (4) выполняется тогда, когда

Ясно, что непрерывное всплеск-преобразование содержит в себе избыточную информацию. С целью создания эффективных алгоритмов вместо восстановления функции / по всем значениям (\¥-ф/)(а,Ь), а.Ъ £ К1, а ^ О, часто рассматривают только дискретные значения переменных а и Ь. Пусть, например, функции фа'Ь при значениях а = 2= 2/с, £ Ъ, образуют ортонормированный базис пространства Ь2(К1). Тогда формула (3) превращается в формулу вычисления коэффициентов разложения по данному базису и для восстановления функции / вместо интеграла (5) используется ряд (1). Таким образом, в рассмотренном частном случае функция ф является всплеском с точки зрения любого из двух упомянутых разделов теории всплесков. Однако в общем случае не требуется, чтобы функции фа'Ь образовывали ортонормированный базис пространства L^IR1). К тому же из непрерывного

ТА т—г ТТ /"Л л Т Г гт ТЛ А /~\ ^ГЛ П П А Г> Л ТТТТ ГТ ТТЛ Т"> П Л П "Г Л -Г /ЛЛТГ Т Т /~\ ТТ Л ТП TYTT ТГПТ 1-Л Г» О ТТ Тг АТТТТ<-\ TY Л ^ Л» г—ч * -г /1т г

D^iiJiC^tV-ПС DV^Ci /j,ci iviuyrvriu uujiJHmid рСЮЛиУГЧ.СГ1У1С ни исизииу всплесков. Оно чаще используется для решения задач, в которых нет существенных ограничений на производительность вычислительных систем и не требуется проводить вычисления в реальном масштабе времени.

Используя методы разложения по базисам всплесков удаётся разработать эффективные алгоритмы цифровой обработки сигналов. В основе этих методов лежит вычислительная простота, отражением чего является масштабирующее уравнение (его также называют кратномасштабным), в английской литературе используются термины: refinement equation, dilation equation, two-scale difference equation (см. [43, 72, 109, 133, 175]). Исследование последнего приводит к вложенности получаемых пространств и к всплесковому представф( 0) оо лению соответствующей цепочки вложенных пространств (это ведёт к минимизации вычислительной сложности); остальные из перечисленных выше (в первом и втором направлениях) свойств с большим или меньшим успехом исследуются дополнительно (см., например, [109]). Теория всплесков появилась несколько десятилетий назад и завоевала прочные позиции в математике и её приложениях. Основной результат теории всплесков заключается в составлении эффективных алгоритмов обработки больших потоков информации или цифровых сигналов. Идея такой обработки состоит в прореживании «по времени» или «по частоте» поступающего цифрового сигнала, что приводит к его сжатию. В данном случае под эффективностью понимается экономное с точки зрения экономии ресурсов ЭВМ (памяти и времени обработки) разложение потока информации на составляющие таким образом, чтобы можно было выделить основной информационный поток, уточняющий информационный поток и информационный поток с несущественной информацией. Как правило, основной информационный поток (его также называют масштабирующим потоком) значительно менее плотный, чем исходный поток информации, поэтому его можно передать быстро, и при этом не требуется использовать широкополосные линии связи. Уточняющий информационный поток (его также называют всплесковым потоком или детализирующим) не во всех случаях необходим, его можно передавать фрагментарно в зависимости от потребностей. Наконец, поток с несущественной информацией вообще может быть отброшен, тогда исходный поток должен однозначно восстанавливаться по основному и всп л вековому потокам. Естественный вопрос о разделении информации на основную, уточняющую и несущественную выходит за рамки математических исследований и должен решаться в каждом отдельном случае специалистом данной предметной области. Для более наглядной иллюстрации идеи всплеск-преобразования рассмотрим числовой поток, кодирующий некоторое изображение, выводимое на экран компьютера (или цифрового телевизора). Предположим, что экран представляет собой прямоугольную матрицу из большого числа пикселей — маленьких прямоугольников (наименьших логических элементов двумерного цифрового изображения), нанесенных на прозрачную поверхность (стекло), которые светятся под воздействием попадающих на них электронов, причём для такого свечения имеется фиксированное число градаций яркости. Известно, что человеческое зрение более восприимчиво к уровню яркости, чем к цвету, поэтому для простоты иллюстрации рассмотрим известный пример [71] монохромного изображения (т. е. одноцветного изображения на чёрно-белом экране). Ясно, что рассмотрение монохромного изображения не уменьшает общности. Например, в цветовой модели RGB цветное изображение может быть представлено в виде трёх потоков чисел, каждый из которых может обрабатываться самостоятельно; аналогичные представления получаются и в других моделях. Каждому пикселю предписывается определённая яркость, выражаемая некоторым числом; обозначим это число для j-ro пикселя через сг Обычно пиксели перенумерованы последовательно по строкам, которые предварительно выстроены одна за другой в прямую линию (построчная развёртка); таким образом, пиксели приобретают номера j = 0,1, 2. TV — 1, где N = М х К, М — число строк рассматриваемой матрицы, К — число её столбцов. Для определённости будем считать N чётным; пусть N = 2п, где п Е N. Таким образом, кодировка изображения производится с помощью числового потока

Со-, Cl, с2; с3, С4, С5, С6. С7, . . . , С2п1. (6)

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

Cl, с3, с5. с7, ., с2п1. (7)

Такое преобразование называется прореживанием (upsampling — разрежение или разрежающая выборка) исходного числового потока. Вместо потока (6) передают в два раза более короткий поток (7); приёмное устройство расширяет полученный числовой поток (7) дублированием принятых значений так, чтобы в результате на местах с чётным и со следующим нечётным номером находились одинаковые числа. В результате на экране воспроизводится изображение, полученное с помощью числового потока вида

С1, СЬ с3, с3, с5, с5., с2п-1, с2«-1. (8)

Тем самым «восстановление» (8) исходного потока (6) производится с погрешностью, причём информация теряется необратимым образом (т. е. без передачи дополнительной информации приёмное устройство, вообще говоря, не в состоянии восстановить поток (6)). Такой приём, называемый сгущением (сЬ'шгзатрНг^), оправдан, если полученное изображение мало отличается от исходного.

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

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

С2] + V

9) ь = % - С23+1 01.2п~1-1. т>ем}\т. р .

Из соотношений (9) ясно, что р(а3 + Ъ3) с2з 2 р(аі — ЬІ) і

С2І+1 = % , 3 =0,1,.,2я-1-!.

10)

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

Соотношения (9) и (10) определяют простейшее всплеск-преобразование, которое при р — 2 называется преобразованием Хаара (прямое и обратное преобразование Хаара, соответственно).

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

Поток чисел а0, аь а2. а4, а5, а6,., а2п- 1х (11) называется основным, а поток чисел

Ьо, к, Ь2, 63, Ь4, Ь5, 6б,., Ь2п- 1х (12) называется всплесковым. потоком.

Полученный основной поток (11) можно рассматривать как сжатие исходного потока (6), а поток (12) как поправку к основному потоку, позволяющую восстановить исходный поток.

Если поток (11) всё ещё велик для передачи, то аналогичной процедурой его расщепляют на два потока: поток, являющийся основным для потока (11) (его называют нулевым приблиоюением к исходному потоку (6) или нулевым потоком) и соответствующий всплесковый поток, который называют нулевой поправкой к нулевому потоку или нулевым всплесковым потоком; в этом случае поток (12) называют первой поправкой или первым всплесковым потоком.

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

А-,+1) (А-/+1) „(*-' + !) к-г) 2] + 2у+1 Ак-г) % ~ %+1

7 ' 1 ~~ '

V Р j = 0,1,.,2п"г-1, 1 = 1 .,.,к, а формулы (10) примут следующий вид

11+1) р(а'*-° + (1,+1) Р(а\к~'] а2з - 2 2

3 = 0,1,. ,2п~г - 1, г = 1,. ,к.

Известно, что универсальным способом исследования математических моделей является использование численных методов, реализованных с использованием современной вычислительной техники. Теория аппроксимации функций широко используется в математическом моделировании. В простейшем случае исходный сигнал отождествляется с функцией, заданной на интервале (а, (3) вещественной оси. Для компьютерной обработки используется дискретный сигнал, представляемый сеточной функцией, определяемой как значения исходной функции (или результатов её сглаживания) в узлах некоторой сетки. Построение сеточной функции позволяет приближать исходную функцию с помощью того или иного аппарата аппроксимации или интерполяции. Далее линейное пространство таких приближений представляется в виде прямой суммы пространств: основного (масштабирующего) и всплескового (уточняющего). Часто основное пространство связывают с сеткой, получающейся выбрасыванием узлов из исходной сетки, а подпространство всплесков определяют операцией проектирования исходного пространства на основное. Таким образом, порождается разложение упомянутого приближения на основную и всплесковую составляющие. Особое внимание здесь уделяют вложенности основного пространства в исходное и заданию операции проектирования исходного пространства на основное. Представления элементов этого разложения в базисах рассматриваемых пространств порождают соответствующие соотношения между коэффициентами этих представлений. Соотношения, которые позволяют перейти от коэффициентов базиса исходного пространства к коэффициентам базиса основного и всплескового пространств, называются формулами декомпозиции (их также называют формулами разложения или анализа), а соотношения, дающие обратный переход, называются формулами реконструкции (их также называют формулами восстановления или синтеза). Затем каждое из подпространств иногда также разлагают в прямую сумму некоторых подпространств, возможно, продолжая этот процесс дальше и получая в результате соответствующие всплеск-пакеты. Важнейшими вопросами, которые волнуют исследователей, являются: вычислительная сложность (объём используемых ресурсов вычислительной системы: памяти, каналов передачи результатов, времени счёта), свойства гладкости и устойчивости решения интересующих задач, аппроксимационные и интерполяционные свойства, а также ряд других свойств: компактность носителя базисных функций, скорость их убывания на бесконечности в случае некомпактного носителя и т. д. Если в качестве аппарата приближения использовать сплайны и если при этом удаётся установить вложенность пространств сплайнов на последовательности измельчающихся/укрупняющихся сеток и представить цепочку вложенных пространств в виде прямой суммы всплес-ковых пространств, а также реализовать базисные функции с минимальной длиной носителя, то вычислительная сложность оказывается приемлемой, причём это ведёт к всплесковому разложению потока информации и существенно экономит ресурсы вычислительных систем. В результате исходный поток информации удаётся разложить на составляющие так, что можно выделить основной и уточняющий информационные потоки. Это приводит к сжатию поступающего цифрового сигнала и к возможности быстрой передачи основного потока и фрагментарной передаче уточняющего потока в зависимости от потребностей. Роль теории всплесков при математическом моделировании заключается в предоставлении предметному специалисту достаточно широкого набора средств, из которых он может выбрать именно то средство, которое ему подходит для обработки (для разложения на составляющие) интересующего его потока информации (цифрового сигнала). В теории всплесков упомянутыми средствами являются наборы вложенных (основных) пространств функций и их представлений в виде прямой (а иногда и ортогональной) суммы всплесковых пространств. Построению и изучению свойств базисов основных пространств и базисов всплесков посвящено большое количество работ (см. [43, 72, 109, 133, 175] и библиографию в них). Продолжая иллюстрацию идеи всплеск-преобразования, представим преобразование (10) в матричной форме со N

Сі I о 0 о о о

2 о 2 и о 1 о

0 0 0 V о о о о о о о р 2 р 2 р 2 0 0 . о\

Р 2 0 0 . 0

0 V 2 0 . 0

0 р 2 0 . 0 о о о о о о р 2

2 /

2 / ао N

0,2^-1 —1 ь0

13)

Обозначая через Я квадратную матрицу в соотношении (13) и вводя векторы а = (ао, аь ., а2п-іі)і, Ь = (60, 6Ь ., Ь^-і^і)1, Т сіе£ с = (с0, Сі, . . . ,С2пі) , а также блочную одностолбцовую матрицу , перепишем равенство (13) в виде с = Я

14)

Схема перехода от потоков (11) и (12) к потоку (6) называется рекон-струщией, соотношения (10) (а также (13) и (14)) называются формулами реконструкции, матрица Я называется матрицей реконструкции.

Формулы, позволяющие по исходному числовому потоку (6) получить основной поток (11) и всплесковый поток (12), называются формулами декомтогда формулы депозиции. Для того, чтобы получить формулы декомпозиции, достаточно обратить матрицу Я. в соотношении (14). Пусть В ^ композиции имеют вид я. \ В с.

15) где В

Другая запись формул декомпозиции даётся соотношениями (9). Матрица В называется матрицей декомпозиции.

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

Из сказанного следует, что разложение исходного числового потока (представляющего собой последовательность {с^}) на основной и всплесковый потоки является вариантом фильтрации потока (подробнее о всплесках и фильтрах см. [299]): таким образом, можно говорить о всплеск-фильтре: основной поток (последовательность {%}) — результат фильтрации низкочастотным фильтром, а всплесковый поток (последовательность {6?}) — результат фильтрации высокочастотным фильтром (эти фильтры определяются формулами (9)). В случае наличия системы вложенных пространств с Уі+\ можно ввести пространства \Уі С Уі+і так, что рассматриваемое разложение можно трактовать как результат представления исходного пространства 1 в виде прямой суммы основного Уг и всплескового пространств с переходом между коэффициентами базисов пространств по формулам декомпозиции (15) и реконструкции (14).

Дадим краткий исторический обзор развития теории всплесков. В настоящий момент библиография насчитывает тысячи работ, естественно, в подобном обзоре нет возможности охватить большинство из них. Например, обзор [285] содержит более одной тысячи статей о теории всплесков и её различных приложениях. Книга «Фундаментальные работы по теории всплесков» [235] содержит репринты 37 статей, с которых, по мнению составителей, началось развитие теории всплесков. Далее будут упомянуты работы, соответствующие интересам автора.

При цифровой обработке стационарных сигналов (т. е. сигналов, чьи свойства стационарно изменяются инвариантными во времени и пространстве операторами) традиционно применяется преобразование Фурье, история которого начинается с мемуаров Ж. Б. Ж. Фурье 1807 года, утверждавшего, что любая 27г-периодическая функция / разлагается в ряд, называемый рядом Фурье,

Vj+i = Vi + Wi

16) к= 1 где коэффициенты Фурье вычисляются по формулам

7Г а/с = — / f(x) cos kx dx, k Є Ъ к J 7Г

7Г

Ъь = — / /(.т) эт. кх (1х: кЕ тг 7

N.

Отметим, что когда Фурье анонсировал свои результаты не было сформировано ни современного понятия функции, ни понятия интеграла (Рима-на), ни теории множеств (Кантора), появившиеся в связи с исследованием тригонометрических рядов. Однако неверно, что, составив ряд Фурье произвольно заданной функции /, мы получаем её разложение. В 1873 году П. Дю Буа Реймонд [227] построил пример функции / Е С2ж. ряд Фурье которой расходится в отдельных точках. В 1905 году А. Л. Лебег [260] указал функцию / £ С27Г, ряд Фурье которой сходится к / всюду, но неравномерно. В 1923 году А. Н. Колмогоров [251] построил функцию / £ 1/2?г, ряд Фурье которой расходится почти всюду, а в 1926 году [252] функцию / € £27Г. ряд Фурье которой расходится всюду. М. Рисс [288] установил, что для функции / £ Ь^ при 1 < р < оо её ряд Фурье сходится к ней в пространстве Ь^', вообще говоря, для р = 1,р = оо это неверно. Позже оказалось, что пример Колмогорова нельзя усилить. В 1966 году Л. Карлесон [199] доказал, что для любой функции / Е 1/2тг РЯД ФуРье сходится почти всюду. Р. А. Хант [245] распространил результат Карлесона на функции из пространства Ь^, р > 1. Подробнее о тригонометрических рядах Фурье см. [82].

Для представления аналогового сигнала конечной энергии используется функция / Е Ь2(М}), преобразование Фурье которой оо \ Т-Г (•/ \ / \ —г:гы I J ] ах оо дает спектральную информацию о сигнале (представление о частотной характеристике /), при этом не отражается информация о временной локализации (изменении частотных характеристик по времени х). С практической точки зрения преобразование Фурье имеет ряд недостатков. Во-первых, для получения преобразования Фурье на одной частоте необходимо знать функцию / полностью на всей вещественной оси (т. е. должно быть известно будущее поведение сигнала). Во-вторых, изменение функции / приводит к изменению всего спектра. Временная локализации может быть получена за счёт умножения функции / на подходящую функцию-окно. В результате вводится оконное или кратковременное преобразование Фурье функции / (с окном ш), определяемое формулой оо

ТАПх)}(и,Ь) = I ¡(х)е-гхшъ(х-Ъ) йх. оо

Оконное преобразование Фурье зависит от времени и даёт частотно-временное описание сигнала. Однако, в результате использования фиксированной функции-окна, оконное преобразование Фурье не может быть адаптировано к локальным свойствам сигнала ввиду того, что ширина окна постоянна. Таким образом, для представления нестационарного сигнала преобразования Фурье являются неподходящим инструментом. Отметим также наличие эффекта Гиббса, возникающего при разложении разрывных функций в ряд Фурье. Теория всплесков — один из важных примеров требуемой в этом случае техники. Ширина во времени функции фа,ь (см. определение (2)) соответствует частоте; высокочастотные функции фа'Ь — узкие, низкочастотные — широкие. При этом, согласно принципу неопределённости Гейзенберга, площадь частотно-временного окна остаётся постоянной. Характеристикой частотно-временной локализации является константа неопределённости. О константах неопределённости см. также работы И. Я. Новикова, Е. А. Лебедевой, В. Ю. Протасова [101, 128, 129, 259]. Частотно-временное окно непрерывного всплеск-преобразования (3) автоматически сужается при изучении высокочастотных изменений (при малом значении параметра а) и расширяется при изучении низкочастотных изменений (при большом значении параметра а).

Изучение А. Хааром частных сумм ряда Фурье по системе Хаара привело к построению первого всплеска2. В 1909 году А. Хаар [241] построил ортонор-мированную систему функций с компактным носителем, образующую базис в пространстве Ь2[0.1], и первый простейший ортонормированный всплеск 1, х Е [0, 1/2), фн(х) =1-1, хе [1/2,1), [ 0, иначе,

2В монографии [158] указывается, что истоки всплесков восходят к работе К. Вейерштрасса [31X], который в 1873 году описал семейство фрактальных, всюду непрерывных и нигде не дифференцируемых функций, построенных масштабированием заданной базисной функции. названный всплеском Хаара. Для некоторых приложений используется очень похожий на всплеск Хаара, но симметричный всплеск, называемый французская шляпа (ШАТ-всплеск). Систематическое изучение системы Хаара в России было начато П. Л. Ульяновым [170]. Для устранения недостатков системы Хаара в 1910 году Г. Фабером [230] и в 1927 году Ю. Шаудером [295] была построена система Фабера-Шаудера, которая получается интегрированием функции Хаара. Перенося ряд (1) на отрезок [0,1] получаем разложение функции / Е Ь2[0,1] в ряд Хаара оо 2^-1 .7=0 к=0 где

СО = (/, л = (/,<*), я/ \ def г хе [0, 1),

Ч> (х) = Х[од) = <

I 0, иначе.

Функция (рн является масштабирующей функцией для кратномасштаб-ного анализа Хаара. Рассматриваемое разложение можно трактовать как результат представления исходного пространства Ь2[0,1] в виде ортогональной суммы основного пространства Уо и всплесковых пространств : оо

Ь2[0,1] = Уо 8 0^-. з=о

Недостатки ряда Фурье (17) по сравнению с рядом Хаара (18) аналогичны упомянутым выше недостаткам преобразования Фурье. Во-первых, ряд Хаара хорошо локализован. Для рассмотрения функции / на подинтерва-ле [а.Ь] требуются только индексы ] и к в разложении (18), для которых Биррт/;^,. = пересекается с отрезком [а.Ь], в отличии от разложения (17), в котором требуются все коэффициенты. Во-вторых, ряд Хаара хорошо масштабирован. Частичная сумма ряда Хаара по = 0.1,. ,п является приближением исходной функции с точностью до масштаба 2-п-1. Свойства локализованности и масштабируемости являются характерными для всех всплесковых разложений (подробнее см. [132]).

Базис всплесков, построенный по sinc-функции (такие всплески называются всплесками Шеннона) аналогичен базису, построенному из теоремы выборки Уиттекера-Котельникова-Шеннона, доказанной в 1915 году Э. Т. Уит-текером [312], в 1933 году В. А. Котельниковым [96], в 1949 году К. Шенноном [294]. Вероятно, опубликованная ими интерполяционная формула уже была известна и ранее, например, С. Д. Пуассону, О. JI. Коши и Э. Борелю.

В 1917 году И. Радон [286] предложил метод восстановления (реконструкции) многомерных функций rio их интегральным характеристикам, лежащий в основе компьютерной томографии. Развитие его идей привело к появлению кратномасштабных интегральных преобразований, в которых в дополнение к всплесковым параметрам сдвига b и масштаба а (сжатия или растяжения) добавляется третий параметр ориентации — угол в. Такие преобразования используются для обработки изображений, которые имеют участки, ограниченные непрерывными кривыми. Свойства интегрируемой функции f(x,y) изучаются при помощи всплеска ф £ L2(M1), задающего ядро

Ч def , , i /9 , / £ cos 9 + у sin 9 — b\ , , л

Фа,ьА*>У) = Н f Ф (-f-j , а,6 G R , a 0. 0 € [0, 2тт). интегрального преобразования 00 +оо iVf)(a,M)= J J 1(х.,у)фаАв(х,у) dxdy. (19) oo —oo

Функция фпь.в-, введённая в работе Э. Кандеса и Д. Л. Донохо [197], называется риджлетом (ridgelet), преобразование (19) называется непрерывным (или интегральным) риджлет-преобразованием. Последовательное применение двумерного непрерывного всплеск-преобразования, и затем на каждом фиксированном масштабе применение непрерывного риджлет-преобра-зования приводят к кёрвлет-преобразованию (curvelet transform) [198]. Отметим также появление бимлетов (beamlet) [226], бандлетов (bandlet) [258], брашлетоь (brushlet) [206], дирекшионлетов (directionlet) [306], контурлетов (contourlet) [224], нидлетов (needlets) [248], ширлетов (shearlet) [254].

В 1928 году Ф. Франклин [233] построил ортонормированную систему функций, образующую базис в пространстве С[0,1]. Система Хаара и система Франклина на отрезке [0,1] одни из наиболее важных ортогональных систем (подробнее см. [90]). Для системы Хаара переход от отрезка [0,1] к вещественной оси R1 очевиден, для системы Франклина этот переход был сделан в 1981 году Я.-О. Стрёмбергом [301], который, модифицируя систему Франклина, на основе сплайнов построил ортонормированную систему (безусловные базисы пространств Харди) непрерывных всплесков (называемых всплесками Стрёмберга) с экспоненциальным убыванием на бесконечности. В работе [277] всплески Стрёмберга вычислены в образах Фурье. Экспоненциальное убывание системы Франклина на бесконечности показано 3. Чи-сельским [202, 203]. Хотя сама система Франклина не является всплеском, функции её образующие асимптотически сколь угодно близки к всплескам Стрёмберга. Отметим также, что существуют всплески, называемые всплесками Франклина (подробнее см. [243]).

В 1930 году Н. Н. Лузин [267] анализировал и синтезировал функции из пространств Харди при помощи интегрального представления, которому можно придать всплесковый вид.

В 1931 году Дж. Литтлвуд и Р. Пэли [263] разработали способ получения информации о функциях, которую не давало разложение функций в ряд Фурье; если в рамках кратномасштабного анализа в качестве масштабирующей функции взять sine-функцию, то кратномасштабное разложение пространства L2(R1) есть двоичное разложение Литтлвуда-Пэли, поэтому всплеск Шеннона иногда называют всплеском Литтлвуда-Пэли (LP-всплеском).

В 1940 году Н. Рикер [287] ввел термин «всплеск» в сейсмологии для описания процесса возмущения от сильного сейсмического импульса или заряда взрывчатого вещества. В русскоязычной математической литературе используется термин «всплеск», предложенный К. И. Осколковым в качестве эквивалента терминам «вэйвлет», «вейвлет», «онделетт» (англ. wavelet, фр. ondelette), что переводится как маленькая (имеется ввиду по продолжительности) волна (т. е. локальная функция); также встречается употребление терминов: «волнушка», «волночка», «волнолет», «Ж-система», «волновой пакет».

В 1946 году Д. Габор [236] описал неортогональный базис всплесков (такие всплески называются всплесками Габора) с неограниченным носителем, построенный по функциям Гаусса \ с^ 1 г,

9а{х) = —е 1«, а > 0. 'тта

Преобразованием Габора функции / £ Ь2(К1) называется преобразование оо = I 1(х)е-гхшда(х - Ъ) ёх.

-оо

Преобразование Габора имеет наименьшее частотно-временное окно, ширина которого постоянна на всех частотах.

В 1948 году Дж. Билль [308] предложил анализировать частотно-временные свойства сигналов при помощи плотности энергии. Такое распределение, называемое распределением Вигнера-Билля, уже рассматривалось в 1932 году Е. П. Вигнером [313] в связи с задачами квантовой механики. Применение распределений Вигнера-Вилля ограничено, ввиду наличия интерференционных членов, при удалении которых теряется разрешение.

В 1964 году А. Кальдерон [196] изучал сингулярные интегральные операторы (впоследствии развитая теория сейчас называется теорией операторов Кальдерона-Зигмунда (подробнее см. [207])); к его работе восходит разработанная в теории всплесков техника, основанная на использовании сдвигов и сжатий (растяжений) заданной функции.

В 1967-1972 годах Ю. Н. Субботин [160-162] на основе полиномиальных сплайнов построил базис пространств гладких периодических функций, являющийся системой интерполяционных периодических всплесков, вместе с системой вложенных подпространств; результаты легко переносятся на пространства функций, равномерно непрерывных вместе с соответствующими производными на всей оси [167]. Отметим более поздние статьи Ю. Н. Субботина и Н. И. Черных [166-168].

В 1971 году В. Л. Рвачёв и В. А. Рвачёв [147] описали семейство атомарных функций, которые порождают всплески [97], ими изучались разностные уравнения (фактически аналоги масштабирующих уравнений), имеющие решения с компактным носителем. Последующее развитие отражено в работах В. Ф. Кравченко, В. Л. Рвачёва, В. И. Пустовойта [34, 97-100].

Базисы всплесков широко применяются для конструктивного описания различных функциональных пространств и построения в них безусловных базисов. Известно [169], что описание многих из пространств Бесова и Ли-зоркина-Трибеля не сводится к описанию ни во временной, ни в частотной областях. Один из подходов к описанию таких пространств опирается на идею атомарного разлоэ/сения, идущую от работ Ч. Феффермана, Е. М. Стейна [231] (1972 г.) и Р. Койфмана, Г. Вейса [208] (1977 г.). В работе [208] доказано, что любая функция из пространства Харди Н1 разложима в сумму атомов. Однако теоремы о разложении гарантируют лишь существование и не описывают способа получения разложения. Базисы всплесков позволили производить такие разложения. О всплесковом разложении функций из пространства Я1 и связи с атомарным разложением Койфмана-Вейса подробнее см. в монографии [278]. О связи интегрального представления Лузина, тождества Кальдерона, переоткрытого в работах А. Гроссмана и Ж. Морле, и атомарных разложениях см. в [132, 246]. В 1977 году X. Трибель [305] рассматривал бесконечно дифференцируемые всплески (безусловные базисы пространств Бесова), убывающие на бесконечности как \/х. Системы всплесков в различных пространствах рассматривались также в работах П. Я. Лизоркина [104], Д. Г. Орловского [136], С. В. Бочкарёва [12]. Используя базисы всплесков удалось впервые построить безусловные базисы некоторых пространств. Важно также применение безусловных базисов в прикладных задачах, т. к. не нужно следить за тем какие слагаемые из представления в виде ряда отбрасываются. И. Мейер [278] доказал, что если всплеск-функция имеет определённую гладкость, то ортогональные системы всплесков являются безусловными базисами в пространствах ^(М1). 1 < р < оо. В работе П. Войтащика [314] вместо предположения гладкости требуется некоторый порядок убывания всплеск-функции. Отметим также работы М. 3. Берколайко и И. Я. Новикова [8, 127], Д. Оффина и К. И. Осколкова [281], Р. А. Лоренца и А. А. Саакяна [266], М. А. Скопиной [151], К. Вожняковского [315]. Подробнее см. монографию [133].

В 1980 году Д. Марр [274] при изучении информационной теории зрения для обнаружения изменения яркости в качестве фильтра использовал функции, построенные применением оператора Лапласса к функции Гаусса. Вещественные базисы всплесков, построенные на основе производных функции Гаусса называют всплесками Марра, в частности, первая производная функции Гаусса называется WAVE-всплеском, вторая производная, взятая с обратным знаком, называется мексиканская шляпа (МНАТ-всплеск) или сомбреро, на основе функции Гаусса также строится DOG-всплеск (difference of gaussians, разность гауссианов).

В 1982 году Ж. Морле [279] с коллегами применили функции, определённые Д. Табором, к моделированию сейсмических импульсов в нефтеразведке. А. Гроссман интерпретировал всплески Морле как когерентные состояния в квантовой механике и обосновал алгоритм восстановления (реконструкции).

В 1984 году А. Гроссман и Ж. Морле [240J ввели понятие интегрального всплеск-преобразования и установили как анализировать произвольные сигналы, масштабируя (сжимая или растягивая) и сдвигая порождающий всплеск (называемый материнский всплеск); построенный в работе комплексный всплеск (называемый всплеском Морле) — это гармоническая функция, модулированная функцией Гаусса. В этом же году Т. Паул построил комплексный всплеск (называемый всплеском Паула) часто применяемый в квантовой механике.

В 1985 году И. Мейер [275] построил семейство ортонормированных базисов всплесков (названных всплесками Мейера), порождённых бесконечно дифференцируемыми функциями; затем П. Ж. Лемарье и И. Мейер [262] распространили результаты на пространство Rn.

Статья 1986 года И. Мейера [276] и диссертация 1988 года С. Малла [270] привели к появлению теории, названной кратномасштабным анализом (multiresolution analysis). Последовательность подпространств {Vj}jez из L2(M1) называется кратномасштабным анализом (КМА), если выполнены следующие условия:

1. У)С Vj+1 VjeZ,

2. \jVj плотно в L2(R1), j€Z я f a V. f(1.) С Т/

J - 'J " M"/ "J + l;

4. Существует масштабирующая функция </? e Vо такая, что множество функций {(/?(■ — k)}fcGz образует ортонормированный базис в Vq.

Из условий 3 и 4 КМА вытекают следующие свойства:

1. Для функции (р G Vj множество функций {(/?(• — k)}k£z образует орто-нормированный базис в Vr

2. Пространство Vo инвариантно относительно целочисленных сдвигов, т. е. если / G И,, то /(• - к) G Vo VA: G Z.

3- П V3 = {0}. jez

KMA позволяет построить ортонормированный базис всплесков {i/jjk}j,k€Z в пространстве L2(R1). В работах [271-273] С. Малла разработал алгоритмы декомпозиции и реконструкции, использующие системы вложенных пространств, используя ортогональное разложение (16), в котором знак прямой суммы + следует заменить на знак ортогональной суммы 0. В работе [272] С. Малла использовал кратномасштабный анализ как одну из форм пирамидальных алгоритмов (pyramidal algorithms), введённых в 1983 году П. Дж. Бартом и Э. X. Адельсоном [195] и применяемых в обработке изображений, и разложение сигнала по поддиапазонам (subband decomposition) при помощи квадратурных зеркальных фильтров (quadrature mirror filters), введённых в 1976 году А. Круазье, Д. Эстебаном, С. Галандом [209] и применяемых в анализе сигналов.

Отметим также, что существуют всплески не порожденные КМА. Пример такого всплеска установлен Ж.-Л. Журне [271]. Обратное верно всегда [132].

В 1987-1988 годах Г. Баттл [187] и П. Ж. Лемарье [261], используя полиномиальные .B-сплайны, в рамках кратномасштабного анализа независимо построили ортогональные всплески с экспоненциальным убыванием на бесконечности (называемые всплесками Баттла-Лемарье), близкие к всплескам Стрёмберга. Известно [124], что к всплескам Баттл а-Лемарье приводят также полиномы Жамалова [154].

В 1988 году И. Добеши [211], основываясь на структуре кратномасштабного анализа, построила ортонормальные всплески (называемые всплесками Добеши) любого конечного порядка гладкости с компактным носителем. Предложенный И. Добеши новый способ построения кратномасштабного анализа основан на определении коэффициентов масштабирующего уравнения относительно функции (f ф) = ^Ку(2х-п), (20) neZ или эквивалентного уравнения, записанного в образах Фурье, ф{ш) = то{ш/2) (р(ш/2), где т0(и) = ^ Ке~гпш/2, пеЪ по решению которого строится всплеск ф. Так в теорию всплесков вошли масштабирующие уравнения, которые были исследованы в работах И. Добеши и Дж. Лагариса [215, 216]. Функция (р называется масштабирующей функцией (scaling или refinable) или отцовским всплеском.

Таким образом был предложен общий подход к построению систем всплесков, основанный либо на построении системы вложенных пространств {Vj}j^z и масштабирующей функции ip Е Vq, либо на выборе масштабирующей функции </?. удовлетворяющей масштабирующему уравнению, и построении пространства Vo из функций (/?(• — к), и дальнейшем построении остальных пространств Vj. Затем началось колоссальное развитие теории всплесков.

Ортонормированные базисы всплесков с компактным носителем несимметричны по сравнению с всплесками с бесконечными носителями. Например, всплески Добеши очень асимметричны. Для получения симметричного или асимметричного всплеска соответствующий фильтр должен быть симметричен или асимметричен относительно центра своего носителя. Всплески, получаемые симметризацией всплесков Добеши, называются симмлетами [109]. Заметим, что всплески Добеши малых порядков и соответствующие им симмлеты совпадают, различия наблюдаются начиная с четвертого порядка.

Для применения в численном анализе [190] использовался ортонормиро-ванный базис всплесков, в котором нулевые моменты имеет и сам всплеск, и масштабирующая функция. Такие всплески называются койфлетами [212].

Ортогональность базиса всплесков является достаточно сильным ограничением. Условие 4 в определении КМ А может быть заменено на формально более слабое условие: множество функций {</?(• — k)}kez образует базис Рисса в пространстве Vq. (Известно [271], что такой базис всегда может быть заменён на ортонормированный.) Тогда систему вложенных пространств можно разложить в прямую сумму (16) и построить неортогопалъный базис всплесков, который будет являться базисом Рисса.

При разложении функции по неортогональному базису всплесков для вычисления коэффициентов разложения требуется найти двойственный (дуальный) базис, который биортогонален исходному. Такие всплески называются биортогональными. Первый пример биортогональных всплесков построен Ф. Чамичаном [304]. В работах А. Коэна, И. Добеши, Ж. Фово [204, 205] пара биортогональных систем всплесков порождается парой КМА. Ряд аналогичных примеров получен в работе М. Веттерли, С. Херли [307], в которой рассматривается подход с точки зрения набора фильтров. Заметим, что в отличие от ортогональных всплесков с компактным носителем (за исключением всплеска Хаара) можно построить гладкие биортогональные всплески с компактным носителем, которые либо симметричны, либо асимметричны. Ортонормированные всплески являются частным случаем биортогональных всплесков, т. к. ортонормированный базис биортогонален самому себе.

Еще одним частным случаем биортогональных всплесков являются полуортогональные всплески, при построении которых систему вложенных пространств разлагают в ортогональную сумму (16) и строят неортогональный базис всплесков. При этом подходе, рассмотренным П. Ошером [185] и Ч. Чуй, Дж. Вонгом [200, 201], двойственные системы всплесков порождаются одним КМА. Так, например, при построении КМА на основе полиномиальных В-сплайнов сдвиги масштабирующих функций не образуют ортонормированный базис в пространстве Vo- После ортогонализации полиномиальных В-сплайнов получаются ортогональные всплески Баттла-Лемарье с некомпактным носителем. Однако, если систему вложенных пространств разложить в ортогональную сумму и построить неортогональный базис всплесков, то получатся В-силайн-всплески с компактным носителем.

Обобщением базиса Рисса является понятие фрейма, введённое в 1952 году Р. Дж. Даффином и А. С. Шеффером [228]. Фрейм (frame) или каркас — это любая система векторов (избыточная система векторов, т. е. не обладающая свойством минимальности), содержащая базис. Особый интерес представляют жёсткие (tight) фреймы [217] — фреймы, границы которых совпадают. Жёсткие фреймы с единичными границами называют ортоподоб-ными системами. Если ортоподобная система образует базис, то этот базис является ортонормированным. Системы всплесков, являющиеся системами фреймов, называют фреймами всплесков или фреймлетами (framelets) [289]. Практический интерес вызывают также фреймоподобные системы всплесков [186, 229, 242, 253]. Упомянем также работы [88, 89, 152, 191, 257, 284].

Вообще говоря, в масштабирующем уравнении (20) вместо параметра масштабирования 2 можно использовать любое целое и даже рациональное число (подробнее см. монографии [72,153] и цитируемую там литературу). При этом одной масштабирующей функции будут соответствовать несколько всплесков. Такие всплески возникают при анализе временных рядов. Большой интерес масштабирующие уравнения представляют для задач автоматизированного геометрического проектирования (CAGD), связанных с построением уточняющих схем (subdivision scheme).

Таким образом, в случае, когда (а,/3) = R1. а сетка — равномерная, удаётся применить мощный аппарат гармонического анализа (в пространстве функций L2(M}) и пространстве последовательностей /2; здесь используются различные варианты преобразований Фурье (дискретного и непрерывного). В 1992 году Д. JI. Донохо [225], не используя преобразование Фурье в качестве инструмента построения всплесков, построил всплески, являющиеся частным случаем лифтинговой схемы, предложенной в 1994 году В. Свел-денсом [302]. Лифтииговая схема (lifting scheme) или схема улучшения — это способ построения новых базисов всплесков, не основывающийся на преобразовании Фурье, который применяется для улучшения свойств всплесков. При помощи управляющей функции и всплескового потока лифтинговая схема изменяет («поднимает») основной поток (низкочастотную составляющую сигнала), причём все вычисления проводятся «на месте» (т. е. в одном массиве). Отметим, что наиболее существенным ограничением лифтинговой схемы является невозможность выбора произвольного масштаба, на котором выполнялась бы декомпозиция сигнала. Ввиду того, что лифтинговая схема не основывается на преобразовании Фурье, имеется возможность строить базисы всплесков по неинвариантным относительно сдвига областям и использовать неравномерные сетки |137, 213, 214, 232, 303]. Однако, в этом случае, ускользает возможность эффективно отслеживать порядок аппроксимации.

В 1997 году Ю. К. Демьянович [39, 41, 43] предложил всплесковую схему — другой способ построения новых базисов всплесков, не основывающийся на преобразовании Фурье. Ввиду того, что требование вложенности пространств на двукратно измельчающейся бесконечной сетке на вещественной оси приводит к масштабирующему уравнению (20), решение которого в ряде случаев затруднительно, было предложено заменить требования ортогональности всплескового базиса на процедуру построения биортогональной (к всплесковому базису) системы функционалов и заменить масштабирующую функцию (удовлетворяющую масштабирующему уравнению) на последовательность функций (удовлетворяющих калибровочным соотношениям). Термин «калибровочные соотношения» стал использоваться и другими авторами [110, 176]. Заметим, что если здесь в качестве масштабирующей функции выбрать полиномиальные В-сплайны первой степени (функции Куранта), то лифтинговая схема и всплесковая схема приведут к построению ленивых всплесков, являющимися подмножеством масштабирующих функций. Сплайны и всплески тесно связаны между собой: каждая цепочка вложенных пространств минимальных сплайнов порождает всплесковое разложение. Поскольку мощность множества упомянутых цепочек — континуум, то такова же мощность множества предлагаемых всплесковых разложений. Удивительно, что все они находят простую реализацию в виде явно выписываемых формул декомпозиции и реконструкции. Кроме того, эти всплесковые разложения наследуют хорошо исследованные асимптотически оптимальные (по Ы-поперечнику) аппроксимацинные свойства сплайнов. Всплесковую схему удалось применить и в случае неравномерной сетки, однако формулы несколько усложняются (они зависят и от рассматриваемой сетки [42]).

Некоторой последовательностью всплеск-функций также порождаются системы нестационарных всплесков или почти-всплесков (ргстаьеШз), введённые независимо М. 3. Берколайко, И. Я. Новиковым [7] и К. Де Бором, Р. ДеВором, А. Роном [220]. Здесь есть результаты, полученные для неравномерной сетки [193, 194]. Имеется также возможность рассматривать вместо всплеск-функции вектор-функцию — мультивсплеск (тиШтаьеЫ) [130, 234].

Во многих приложениях приходится рассматривать интервал (а. 3) С К1, поэтому необходимо строить теорию всплесков на интервале. Это вызывает значительные трудности, т. к. приходится учитывать краевые эффекты. Одним из способов построения являются периодические всплески, основанные либо на периодизации непериодических КМА [72, 278], либо на введении определения периодических КМА (ПКМА). В. А. Жёлудев [77] изучал ПКМА на базе периодических сплайнов. А. П. Петухов [141, 142] рассматривал ПКМА в банаховых пространствах из достаточно широкого класса. Более общее определение ПКМА предложено М. А. Скопиной [108, 297].

В России теорией всплесков одним из первых заинтересовался Е. М. Дынь-кин, опубликовавший в 1989 году статью [74], содержащую обзорные результаты по теории всплесков, и в 1991 году перевод рецензии П.-Ж. Лемарье [103] на монографию И. Мейера [278]. Большое внимание теории всплесков и её популяризации уделял С. Б. Стечкин, выступивший в 1993 году с обзорными докладами на конференциях в Воронеже и Днепропетровске, и опубликовавший совместно с И. Я. Новиковым обзорные статьи [131, 132]. Отметим также обзоры H. М. Астафьевой [5], И. М. Дрёмина, О. В. Иванова, В. А. Нечитай-ло [73], А. В. Переберина [139]. На русском языке опубликован ряд монографий, содержащих изложение различных аспектов теории всплесков. Среди них книги И. Добеши [72], Ч. К. Чуй [175], С. Малла [109], А. П. Петухова [143], Б. С. Кашина и А. А. Саакяна [90], В. И. Бердышева и Л. В. Петрак [6], Л. В. Новикова [134], В. В. Витязева [27], В. И. Воробьёва и В. Г. Грибу-нина [31], Э. Столница, Т. ДеРоуза и Д. Салезина [158], Ю. К. Демьяновича [43], В. Н. Малозёмова и С. М. Машарского [114], А. А. Короновского и

A. Е. Храмова [95], В. П. Дьяконова [75], К. Блаттера [10], И. Я. Новикова,

B. Ю. Протасова и М. А. Скопиной [133], В. Ф. Кравченко и В. Л. Рвачёва [97], Ю. К. Демьяновича и В. А. Ходаковского [71], М. Фрейзера [174], Н. К. Смо-ленцева [153] и др. Следует отметить, что перевод книг [109, 174, 175] на русский язык выполнен Я. М. Жилейкиным.

В 1998 году в Санкт-Петербурге совместно с городским семинаром по конструктивной теории функций организован семинар «Всплески и их приложения», руководители семинара: проф. Ю. К. Демьянович (СПбГУ), проф. В. Н. Малозёмов (СПбГУ), проф. А. П. Петухов (СПбГТУ), проф. М. А. Ско-пина (СПбГУ), сайт семинара: www.math.spbu.ru/ru/Archive/dmp/. Из его секции «Дискретный гармонический анализ» в 2004 году был организован семинар «Дискретный гармонический анализ и геометрическое моделирование» (рук. проф. В. Н. Малозёмов, сайт семинара: http://dha.spb.ru), основные итоги работы за 2004-2008 годы опубликованы в книге [122]. Большое внимание на семинаре уделяется теории всплесков, рассматриваемой с точки зрения дискретного гармонического анализа; подробнее см. работы В. Н. Ма-лозёмова, А. Б. Певного, В. А. Жёлудева, С. М. Машарского, А. А. Третьякова, В. А. Кирушева, Н. А. Соловьёвой [78-80, 92, 111-114, 117, 119, 138, 155].

В 2002 году С. В. Козырев [250] нашёл ортонормированные р-адические базисы всплесков, являющиеся аналогами базисов Хаара. Интерес к р-ади-ческим всплескам возник в связи с задачами р-адической математической физики. Подробнее см. работы С. Альбеверио, Дж. Дж. Бенедетто, P. JI. Бе-недетто, С. А. Евдокимова, В. Ч. Ленга, Т. П. Лукашенко, С. Ф. Лукомско-го, В. Ю. Протасова, М. А. Скопиной, Ю. А. Фаркова, А. Ю. Хренникова,

B. М. Шелковича [76, 106, 107, 145, 146, 171-173, 180, 188, 249, 256].

Упомянем также связанные с использованием теории всплесков работы отечественных учёных: И. А. Блатова [9], Я. М. Жилейкина [24, 81], С. В. Ко-нягина и В. Н. Темлякова [223], Е. В. Мищенко [125], Л. В. Новикова [135],

C. В. Умняшкина [2], Б. М. Шумилова [178].

Многие практические приложения требуют рассматривать ограниченный интервал вещественной оси и неравномерную сетку. Например, при обработке неоднородных цифровых потоков с резко меняющимися характеристиками (со сменой плавного поведения на скачкообразное и наоборот) или имеющих сингулярности целесообразно использовать адаптивную неравномерную сетку, учитывающую особенности обрабатываемого потока. Применение неравномерной сетки позволяет улучшить приближение функций без усложнения вычислений. Более того, для улучшения приближения могут понадобиться различные степени измельчения сетки в разных частях рассматриваемого промежутка. Имеется много работ, относящихся к всплесковым разложениям на равномерной сетке. Всплесковые аппроксимации на неравномерных сетках исследованы значительно меньше. Это связано с тем, что обычно применяемое на равномерной сетке преобразование Фурье в условиях неравномерной сетки использовать затруднительно. В некоторых случаях удаётся использовать неравномерную сетку. Как правило, в таких исследованиях строятся всплесковые разложения хорошо изученных пространств полиномиальных B-сплайнов, при этом на рассматриваемые сетки и на способы измельчения/укрупнения сеток накладываются значительные ограничения. Имеется небольшое количество публикаций, посвящённых таким построениям. Работы М. Д. Бухманна и Ч. А. Мичелли [193, 194], П. Освальда [282] относятся к построению систем нестационарных всплесков. Биортогональные всплески рассмотрены в работе Р. Стивенсона [298]. Всгшесковому разложению пространств сплайнов посвящены работы В. Дахмена и Ч. А. Мичелли [210], Ю. К. Демьяновича [42, 44], Т. Лише, К. Моркена, Е. Куака и Ф. Пелоси [268, 269], У. Лиу [264], Е. Е. Тыртышникова, Дж. М. Форда и И. В. Оселедца [137, 232]. Лифтинговая схема использовалась в работах И. Добеши, И. Гуськова, П. Шрёдера и В. Свелденса [213, 214], Ч. Бернарда и И. Ле Пен-нека [189], а также в упомянутых выше работах [137, 232, 282]. В работах А. Альдруби, К. Кабрелли и У. Молтер [181, 182], У. Лиу и Г. Г. Вальтера [265] строятся фреймы всплесков. Пространства мультивсплесков рассматривались в работах Ч. Жао и П. Жао [317], Л. Жанвея, X. Гуена и В. Гуочанга [316].

Предложенный Ю. К. Демьяновичем подход (всплесковую схему [43]) к построению всплесков на равномерной сетке удалось обобщить на случай неравномерной сетки для полиномиальных сплайнов, а затем и на случай неполиномиальных сплайнов. Оказалось, что использование биортогональ-ной системы функционалов позволяет построить всплесковые разложения и при произвольном способе измельчения/укрупнения сетки (это ведёт к упрощениям и в случае равномерной сетки). Весьма эффективными и простыми оказываются построения в пространствах минимальных сплайнов (вообще говоря, неполиномиальных), ибо конструируемые всплесковые пространства получают прекрасные аппроксимационные свойства (асимптотически оптимальные по поперечнику стандартных компактов). Поскольку эти построения локальны и справедливы для неравномерной сетки, их можно эффективно использовать в случае, когда имеются особенности у приближаемой функции или у её производных. Трудности, связанные с конечностью числа элементов обрабатываемой информации преодолеваются использованием упомянутых выше свойств локальности. Некоторые варианты всплеско-вых разложений пространств минимальных сплайнов лагранжева типа рассматривались в работах Ю. К. Демьяновича, М. В. С. Габра, А. В. Зимина, О. Н. Иванцовой, А. Б. Левиной, А. А. Макарова, А. В. Нездеровой [41, 45-47, 56, 62, 68, 70, 86, 321, 323, 326, 330]. Варианты всплесковых разложений пространств минимальных сплайнов эрмитова типа рассматривались в работах Ю. К. Демьяновича, А. В. Зимина, Т. Н. Б. Ле [58, 67]. Всплески на многообразиях рассматривались в работах Ю. К. Демьяновича [48, 53, 55, 221], Ю. К. Демьяновича и А. В. Зимина [59]. Построению симплициальных подразделений двумерных и трехмерных областей и рассмотрению соответствующих всплесковых разложений на двумерных сетках посвящены работы Е. П. Арсентьевой и Ю. К. Демьяновича [3, 4]. В упомянутых работах рассматривались сплайны на открытом интервале (а, определяемые бесконечной сеткой и вектор-функцией, заданной на интервале (а, /3). Бесконечность рассматриваемой сетки (а значит, и числового потока) облегчает теоретические исследования, однако на практике приходится иметь дело с конечными потоками. Соответственно и получаемые пространства сплайнов были бесконечномерны, что не всегда удобно для численной реализации. В работе Ю. К. Демьяновича и А. В. Зимина [57] рассмотрено всплесковое разложение пространств периодических В-сплайнов. В работах Ю. К. Демьяновича и О. М. Косогорова [66], Н. А. Лебединской и Д. М. Лебединского [102] рассмотрены всплесковые разложения некоторых конечных пространств сплайнов второго порядка на укрупняющихся сетках.

В данной работе для конечномерных пространств сплайнов произвольного порядка получено сплайн-всплесковое разложение для измельчающихся и укрупняющихся сеток на отрезке [а, Ь] с помощью сужения рассматриваемых функций с интервала (ос,/3) на отрезок [а. Ь] С (а,/3). В результате сплайн-всплескового разложения получаются достаточно простые формулы декомпозиции и реконструкции, определяемые используемыми конечными неравномерными сетками, причём базисные всплески имеют простое аналитическое представление и компактный носитель. Это позволяет производить сжатие, уточнение и восстановление потоков числовой информации с применением адаптивных сеток, приспосабливая последние к аппроксимации быстро меняющихся числовых потоков и существенно улучшая приближение функций, имеющих те или иные точечные особенности.

Конечно, получаемые в этих трёх направлениях развития теории обработки потоков данных классы сплайнов имеют непустое пересечение. В нём, в частности, лежат давно известные полиномиальные В-сплайны, что подчёркивает глубокую связь подходов Шёнберга и Михлина-Демьяновича. Сплайны В. С. Рябенького [149] представляют собой минимальные лагранжевы сплайны, порядки гладкости и точности которых совпадают. Классические эрмитовы сплайны являются частным случаем минимальных эрмитовых сплайнов. Известные квадратичные и кубические непрерывные конечноэле-ментные аппроксимации [159] оказываются в классе минимальных сплайнов. Кусочно-полиномиальные функции Дженкинса, известные в теории оскуляторной интерполяции, являются частными случаями минимальных сплайнов [36]. Минимальные сплайны включают также ЕСТ-В-сплайны, которые активно изучаются рядом авторов (см. [192, 280, 292]). Непусто также пересечение с B-L-сплайнами [176], [МТ-В-сплайнами [310], NUAT-В-сплайнами [309] и GB-сплайнами [91], используемыми в геометрическом моделировании.

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

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

В 1973 году С. Г. Михлиным и Ю. К. Демьяновичем предложен подход (ориентированный на построение простейших аппроксимационных формул) к построению полиномиальных сплайнов, удовлетворяющих аппроксимаци-онным соотношениям и имеющих заданную гладкость. При этом сначала минимизируется кратность накрытия (так называется минимальная кратность перекрытия носителей базисных функций) базисных сплайнов, а затем степень сплайнов. Построенные таким образом функции называются минимальными сплайнами для данных аппроксимационных соотношений и для заданной гладкости. Ввиду важности этих соотношений С. Г. Михлин называл их фундаментальными. Если воспользоваться аппроксимационными соотношениями интерполяционного характера, то получатся аппроксимации, точные на полиномах определённой степени (показатель этой степени называется порядком точности). Отсюда можно найти минимальные сплайны с локальным интерполяционным базисом. Весьма важной характеристикой аппроксимации является число входящих в неё производных приближаемой функции. Это число называется высотой аппроксимации. Аппроксимирующий сплайн нулевой высоты использует значения приближаемой функции, но не использует её производных; такой сплайн называется лагранжевым. Аппроксимирующий сплайн, использующий последовательные г-е производные указанной функции (г = 0.1., /г, где /1 6 М) называется эрмитовым или сплайном высоты К. Обобщению аппроксимационных соотношений и развитию на их основе общей теории минимальных сплайнов посвящены работы Ю. К. Демьяновича, И. Г. Буровой и их учеников.

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

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

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

В случае когда (а,/5) = К1, а сетка — равномерная, удаётся применить мощный аппарат гармонического анализа (в пространстве функций Ь2(МХ) и пространстве последовательностей 12); здесь используются различные варианты преобразований Фурье (дискретного и непрерывного). Этому случаю посвящено большое количество исследований. В этом направлении была предложена (И. Мейер, С. Малла, И. Добеши) общая теория построения систем всплесков, названная кратномасштабным анализом (КМА).

В дальнейшем появились способы построения базисов всплесков, не основывающиеся на преобразовании Фурье. Например, лифтинговая схема (Д. Донохо, В. Свелденс) — это способ построения базисов всплесков, который применяется для улучшения свойств всплесков. При помощи управляющей функции и всплескового потока лифтинговая схема изменяет («поднимает») основной поток (низкочастотную составляющую сигнала), причём все вычисления проводятся «на месте» (т. е. в одном массиве). Еще один способ построения новых базисов всплесков — это всплесковая схема (Ю. К. Демьянович). Ввиду того, что требование вложенности пространств на двукратно измельчающейся бесконечной сетке на вещественной оси приводит к масштабирующему уравнению, решение которого в ряде случаев затруднительно, было предложено заменить требования ортогональности всплескового базиса на процедуру построения биортогональной (к всплесковому базису) системы функционалов и заменить масштабирующую функцию (удовлетворяющую масштабирующему уравнению) на последовательность функций (удовлетворяющих калибровочным соотношениям).

Некоторой последовательностью всплеск-функций также порождаются системы нестационарных всплесков (М. 3. Берколайко, И. Я. Новиков) или почти-всплесков (К. Де Бор, Р. ДеВор, А. Рон). Имеется также возможность использовать вместо всплеск-функции вектор-функцию — мультивсплеск.

Во многих приложениях приходится рассматривать интервал (а. ¡3) с М1, поэтому необходимо строить теорию всплесков на интервале. Это вызывает значительные трудности, т. к. приходится учитывать краевые эффекты. Одним из способов построения являются периодические всплески, основанные либо на периодизации непериодических КМА (И. Мейер, И. Добеши), либо на введении определения периодических КМА (В. А. Жёлудев, А. П. Петухов, М. А. Скопина).

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

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

В данной работе для конечномерных пространств сплайнов произвольного порядка получено сгшайн-всплесковое разложение для измельчающихся и укрупняющихся сеток на отрезке [а, Ь] с помощью сужения рассматриваемых функций с интервала (а,/3) на отрезок [а.Ь] С (ос,/3). В результате сплайн-всплескового разложения получаются достаточно простые формулы декомпозиции и реконструкции, определяемые используемыми конечными неравномерными сетками, причём базисные всплески имеют простое аналитическое представление и компактный носитель. Это позволяет производить сжатие, уточнение и восстановление потоков числовой информации с применением адаптивных сеток, приспосабливая последние к аппроксимации быстро меняющихся числовых потоков и существенно улучшая приближение функций, имеющих те или иные точечные особенности.

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

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

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

Основные результаты и научная новизна. Основные результаты, полученные в диссертации, являются новыми. Дадим их краткое описание.

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

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

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

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

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

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

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

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

Апробация работы. Основные результаты были доложены на следующих конференциях и семинарах: семинар кафедры параллельных алгоритмов математико-механического факультета Санкт-Петербургского государственного университета (рук. проф. Ю. К. Демьянович); семинар кафедры вычислительной математики математико-механического факультета Санкт-Петербургского государственного университета (рук. проф. В. М. Рябов); семинар «Дискретный гармонический анализ и геометрическое моделирование» (рук. проф. В. Н. Малозёмов); объединенный семинар кафедр высшей математики и прикладной математики и информатики Санкт-Петербургского государственного архитектурно-строительного университета (рук. проф. Б. Г. Вагер); Международная конференция «Высокопроизводительные параллельные вычисления на кластерных системах», С.-Петербург (2006), Н. Новгород (2007), Казань (2008); 12th International Conference in Approximation Theory, San Antonio, Texas, USA, 2007; Международный конгресс «Нелинейный динамический анализ — 2007», посвященный 150-летию со дня рождения акад. A.M. Ляпунова, С.-Петербург, 2007; Всероссийская конференция по вычислительной математике «КВМ-2007», Академгородок, Новосибирск, 2007; Leonhard Euler Congress, Third International Workshop on Reliable Methods of Mathematical Modeling, St. Petersburg, 2007; Международная научная конференция «Космос, астрономия и программирование (Лавровские чтения)», посвященная 85-летию со дня рождения чл.-корр. РАН С. С. Лаврова, С.-Петербург, 2008; International conference «Harmonic analysis and approximations, IV», dedicated to 80th anniversary of academician A. A. Talalian, Tsaghkadzor, Armenia, 2008; International conference «Wavelets and applications», St. Petersburg, 2009; International conference «Mathematical and Information technologies MIT 2009», Ko-paonik, Serbia, Budva, Montenegro, 2009; Міжнародній симпозіум «Питання оптимизаціі обчислень», смт. Кацивелі, Украіна, 2009, 2011; Международная конференция «Теория приближений», С.-Петербург, 2010; Международная научная конференция «Современные проблемы анализа и преподавания математики», посвященная 105-летию акад. С. М. Никольского, Москва, 2010; I Jaen Conference on Approximation, Ubeda, Jaen, Spain, 2010; Международная конференция «Теория приближений», посвященная 90-летию со дня рождения С. Б. Стечкина, Москва, 2010; Российская конференция «Методы сплайн-функций», посвященная 80-летию со дня рождения Ю. С. Завьялова, Новосибирск, 2011; Международная конференция по Современному Анализу, Донецк, Украина, 2011; International Workshop on Wavelets, Frames and Applications, India, Delhi, 2011.

Публикации. Основные результаты опубликованы в 23 работах, включая статьи [320, 321, 325-327, 330, 335-338, 340], опубликованные в изданиях из «Перечня рецензируемых научных журналов», рекомендованных ВАК, а также монографию [334].

В работе [319] Ю. К. Демьяновичу принадлежит общая постановка задачи и указание на идею исследования, детальная реализация идеи принадлежит А. А. Макарову. В работе [324] Ю. К. Демьяновичу принадлежит общая постановка задачи, указание возможных приложений и модельных примеров, О. М. Косогоровым и А. А. Макаровым поставлены численные эксперименты и предложены различные варианты способов распараллеливания всплеско-вых разложений, нашедших дальнейшее отражение в самостоятельных статьях. В работах [331, 332] отражены результаты совместно поставленных численных экспериментов, выполненных под руководством А. А. Макарова.

Структура и объём работы. Диссертация объёмом 349 страниц состоит из введения, семи глав, заключения, двух приложений и списка литературы, а также 22 таблицы и 21 рисунка. Список литературы содержит 340 наименований.

Заключение

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

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

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

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

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

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

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

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

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

2. Александров А. А., Коплович Е. А., Умняшкин С. В. Алгоритм видеокомпрессии на основе дискретного вейвлет-преобразования с трехслойной схемой кодирования векторов движения // Известия вузов. Электроника. 2008. № 5. С. 69-73.

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

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

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

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

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

8. Берколайко М. 3., Новиков И. Я. Базисы всплесков и линейные операторы в анизотропных пространствах Лизоркина-Трибеля // Тр. МИАН. 1995. К0- 210. С. 5-30.

9. Блатов И. А., Китаева Е. В. О сочетании методов неполной факторизации и быстрого преобразования Фурье решения краевых задачдля уравнения Пуассона в областях с криволинейной границей // Ж. вычисл. матем. и матем. физ. 2003. Т. 43. № 5. С. 730-743.

10. Блаттер К. Вейвлет-анализ. Основы теории. М.: Техносфера, 2004. 280 с.

11. Болтянский В. Г., Виленкин Н. Я. Симметрия в алгебре. М: МЦ-НМО, 2002. 240 с.

12. Бочкарев С. В. Базисы в функциональных пространствах и система Франклина // Тр. МИАН. 1989. № 190. С. 22-39.

13. Бурова И. Г. Приближение минимальными сплайнами максимального и минимального дефекта // Вестн. С.-Петерб. ун-та. сер. 1. 2006. Вып. 1. С. 12-17.

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

15. Бурова И. Г., Демьянович Ю. К. Минимальные сплайны и их приложения. СПб.: Изд-во С.-Петерб. ун-та, 2010. 364 с.

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

17. Бурова И. Г., Демина А. Ф. О построении гладких интерполяционных сплайнов // Вестн. С.-Петерб. ун-та. сер. 1. 2007. Вып. 1. С. 75-81.

18. Бурова И. Г., Евдокимова Т. О. О гладких тригонометрических сплайнах второго порядка // Вестн. С.-Петерб. ун-та. сер. 1. 2004. Вып. 3. С. 11-16.

19. Бурова И. Г., Тимофеев В. А. Решение задачи Эрмита-Биркгофа с помощью минимальных неполиномиальных сплайнов // Вестн. С.-Петерб. ун-та. сер. 1. 2006. Вып. 3. С. 145-147.

20. Бурова И. Г., Хассан И. Р. Применение минимальных интероляци-онных сплайнов к решению задачи Коши // Вестн. С.-Петерб. ун-та. сер. 1. 2007. Вып. 4. С. 114-117.

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

22. Варга Р. Функциональный анализ и теория аппроксимации в численном анализе. М.: Мир, 1974. 124 с.

23. Василенко В. А. Сплайн-функции: теория, алгоритмы, программы. Новосибирск, 1983. 216 с.

24. Васильева Л. Г., Жилейкин Я. М., Осипик Ю. И. Преобразование Фурье и вейвлет-преобразование. Их свойства и применение // Вычислительные методы и программирование. 2002. Т. 3. С. 172-175.

25. Виноградов О. Л., Жук В. В. Точные неравенства типа Джексона для сплайновых аналогов операторов Ахиезера—Крейна—Фавара // Докл. РАН. 2003. Т. 393. № 2. С. 151-154.

26. Витязев В. В. Вейвлет-анализ временных рядов: Учеб. пособие. СПб.: Изд-во С.-Петерб. ун-та, 2001. 58 с.

27. Воеводин В. В., Воеводин Вл. В. Параллельные вычисления. СПб.: БХВ-Петербург, 2002. 608 с.

28. Волков Ю. С. Безусловная сходимость еще одной средней производной для интерполяционных сплайнов нечетной степени // Докл. РАН. 2005. Т. 401. № 5. С. 592-594.

29. Волков Ю. С., Богданов В. В., Мирошниченко В. Л., Шевалдин В. Т. Формосохраняющая интерполяция кубическими сплайнами // Матем. заметки. 2010. Т. 88. № 6. С. 836-844.

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

31. Габр M. В. С. О. Сплайн-вейвлетные разложения для тригонометрических сплайнов первого порядка / / Семинар «DHA & CAGD». Избранные доклады. 18 сентября 2010 г. (http ://dha.spb.ru/reps10.shtml#0918)

32. Гергель В. П. Теория и практика параллельных вычислений. М.: Интернет-Университет, Бином. Лаборатория знаний, 2007. 424 с.

33. Гуляев Ю. В., Кравченко В. Ф., Пустовойт В. И., Чуриков Д. В. Новый класс WA-систем функций Кравченко-Рвачева // Докл. РАН. 2007. Т. 413. № 3. С. 320-328.

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

35. Демьянович А. Ю., Малоземов В. Н. Функции Дженкинса и минимальные сплайны // Вестн. С.-Петерб. ун-та. сер. 1. 1998. Вып. 2. № 8. С. 38-43.

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

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

38. Демьянович Ю. К. О построении проекционных сплайнов и вейвле-тов // Вестн. С.-Петерб. ун-та. сер. 1. 1997. Вып. 1. № 1. С. 17-19.

39. Демьянович Ю. К. Компьютерная алгебра. Системы аналитических вычислений. СПб.: Изд-во С.-Петерб. ун-та, 1999. 103 с.

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

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

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

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

44. Демьянович Ю. К. Вложенные пространства тригонометрических сплайнов и их всплесковое разложение // Матем. заметки. 2005. Т. 78. № 5. С. 658-675.

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

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

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

48. Демьянович Ю. К. Минимальные сплайны и всплески // Вестн. С.-Петерб. ун-та. Сер. 1. 2008. Вып. 2. С. 8-22.

49. Демьянович Ю. К. Всплесковое разложение для функций на дифференцируемом многообразии // Вестн. С.-Петерб. ун-та. Сер. 1. 2008. Вып. 4. С. 7-15.

50. Демьянович Ю. К. Некоторые свойства Д^-сгшайнов // Проблемы матем. анализа. 2008. Вып. 38. С. 11-21.

51. Демьянович Ю. К. Об асимптотических разложениях координатных сплайнов // Зап. научн. семин. ПОМИ. 2008. Т. 359. С. 17-30.

52. Демьянович Ю. К. Вэйвлеты на многообразии // Докл. РАН. 2009. Т. 421. № 2. С. 156-160.

53. Демьянович Ю. К. Минимальные сплайны лагранжева типа // Проблемы матем. анализа. 2010. Вып. 50. С. 21-64.

54. Демьянович Ю. К. Вложенность пространств и вэйвлеты на многообразии // Зап. научн. сем. ПОМИ. 2010. Т. 382. С. 15-37.

55. Демьянович Ю. К., Габр М. B.C. Один вариант вэйвлетных разложений пространств полиномиальных сплайнов // Проблемы матем. анализа. 2010. Вып. 45. С. 53-68.

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

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

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

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

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

61. Демьянович Ю. К., Иванцова О. Н. Новые представления сплайн-вэйвлетных разложений // Проблемы матем. анализа. 2010. Вып. 46. С. 73-104.

62. Демьянович Ю. К., Косогоров О. М. Сплайны и биортогональные системы // Зап. научн. сем. ПОМП. 2009. Т. 367. С. 9-26.

63. Демьянович Ю. К., Косогоров О. М. Калибровочные соотношения для неполиномиальных сплайнов // Проблемы матем. анализа. 2009. Вып. 43. С. 51-67.

64. Демьянович Ю. К., Косогоров О. М. О вычислении матриц декомпозиции в сплайн-вэйвлетном разложении // Сб. Методы вычислений. 2010. Вып. 23. С. 73-98.

65. Демьянович Ю. К., Косогоров О. М. Сплайн-вэйвлетные разложения на открытом и замкнутом интервалах // Проблемы матем. анализа. 2009. Вып. 43. С. 69-86.

66. Демьянович Ю. К., Ле Т. Н. Б. Вэйвлетное разложение сплайнов эрмитова типа // Вестн. Санкт-Петерб. ун-та. Сер. 10. 2010. Вып. 2. С. 32-38.

67. Демьянович Ю. К., Левина А. Б. О вэйвлетных разложениях линейных пространств над произвольным полем и о некоторых приложениях // Матем. моделирование. 2008. Т. 20. № 11. С. 104-108.

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

69. Демьянович Ю. К., Нездерова А. В. Вложенность пространств Б^-сплайнов второго порядка // Мат. модели. Теория и приложения. Вып. 6. СПб.: ВВМ, 2005. С. 123-168. I

70. Демьянович Ю. К., Ходаковский В. А. Введение в теорию вэйвле-тов. СПб.: Изд-во ПГУПС, 2008. 51 с.

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

72. Дремин И. М., Иванов О. В., Нечитайло В. А. Вейвлеты и их применение // УФН. 2001. № 5. С. 465-501.

73. Дынькин Е. М. Методы теории сингулярных интегралов. II. Теория Литлвуда-Пэли и ее приложения // Коммутативный гармонический анализ—4, Итоги науки и техн. Сер. Соврем, пробл. мат. Фундам. направления, 42, ВИНИТИ, М., 1989. С. 105-198.

74. Дьяконов В. П. Вейвлеты. От теории к практике. М.: Солон-Пресс, 2004. 400 с.

75. Евдокимов С. А., Скопина М. А. 2-адические базисы всплесков // Тр. Ин-та математики и механики УрО РАН. Екатеринбург, 2009. Т. 15. № 1. С. 135-146.

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

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

78. Желудев В. А., Малоземов В. Н., Певный А. Б. Банки фильтров и фреймы в дискретном периодическом случае // Тр. С.-Петерб. матем. о-ва. 2008. Т. 14. С. 5-18.

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

80. Жилейкин Я. М., Осипик Ю. И. О погрешности и алгоритмах численной реализации непрерывных вейвлет-преобразований //Ж. вычисл. матем. и матем. физ. 2005. Т. 45. № 12. С. 2091-2101.

81. Жук В. В., Натансон Г. И. Тригонометрические ряды Фурье и элементы теории аппроксимации. JL: Изд-во Ленингр. ун-та, 1983. 188 с.

82. Завьялов Ю. С. Применение вычислительных систем для решения сложных задач проектирования в машиностроении // Вычислительные системы. Вып. 38. Новосибирск: ИМ СО АН СССР, 1970. С. 3-22.

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

84. Заставный В. П., Тригуб Р. М. Положительно определенные сплайны специального вида // Матем. сб. 2002. Т. 193. № 12. С. 41-68.

85. Зимин А. В. Вэйвлетная схема, основанная на сплайн-аппроксимации кубическими В-сплайнами на неравномерной сетке // Методы вычислений. 2008. Вып. 22. С. 64-76.

86. Плюшкина Н., Чобану М. К. Применение новых критериев оценки качества изображений после их сжатия с потерями // Современная электроника. 2007. № 3. С. 66-69.

87. Кашин Б. С., Куликова Т. Ю. Замечание об аппроксимационных свойствах фреймов общего вида /'/ Матем. заметки. 2002. Т. 72. № 2. С. 312-315.

88. Кашин Б. С., Куликова Т. Ю. Замечание об описании фреймов общего вида // Матем. заметки. 2002. Т. 72. № 6. С. 941-945.

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

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

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

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

93. Колесников А. П. Функциональные сплайны в топологических векторных пространствах. М.: Изд-во УРСС, 2008. 452 с.

94. Короновский А. А., Храмов А. Е. Непрерывный вейвлетный анализ и его приложения. М.: ФИЗМАТЛИТ, 2003. 176 с.

95. Кравченко В. Ф., Рвачев В. Л. Алгебра логики, атомарные функции и вейвлеты в физических приложениях. М.: ФИЗМАТЛИТ, 2006. 416 с.

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

97. Кравченко В. Ф., Пустовойт В. И. Новые ортогональные вейвлеты Кравчено // Докл. РАН. 2009. Т. 428. № 5. С. 601-607.

98. Кравченко В. Ф., Пустовойт В. И., Чуриков Д. В. Применение комплексных WA-систем функций Кравченко к обработке временных рядов // Докл. РАН. 2011. Т. 436. № 5. С. 615-622.

99. Лебедева Е. А., Протасов В. Ю. Всплески Мейера с наименьшей константой неопределенности // Матем. заметки. 2008. Т. 84. № 5. С. 732-740.

100. Лебединская Н. А., Лебединский Д. М. Многопоточный алгоритм сплайн-вейвлетного сжатия цифрового представления сигнала // Вестн. С.-Петерб. ун-та. сер. 10. 2008. Вып. 1. С. 95-100.

101. Лемарье П.-Ж. Meyer Y. «Ondelettes et opérateurs». Hermann, Paris, 1990, vol. I—III // Алгебра и анализ. 1991. T. 3. № 2. С. 253-264.

102. Лизоркин П. Я. О базисах и мультипликаторах в пространствах В£ в // Тр. МИАН. 1997. Т. 143. С. 88-104.

103. Лоран П.-Ж. Аппроксимация и оптимизация. М., 1975. 496 с.

104. Лукашенко Т. П. Всплески на топологических группах // Докл. РАН. 1993. Т. 332. № 1. С. 15-17.

105. Лукомский С. Ф. Кратномасштабный анализ на нульмерных группах и всплесковые базисы // Матем. сб. 2010. Т. 201. № 5. С. 41—64.

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

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

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

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

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

111. Малоземов В. Н., Машарский С. М. Основы дискретного гармонического анализа. Части 1-3. СПб.: НИИММ СПбГУ, 2003. 288 с.

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

113. Малоземов В. Н., Певный А. Б. Дискретные периодические сплайны и их вычислительные применения // Журн. вычисл. мат. и матем. физ. 1998. Т. 38. № 8. С. 1235-1246.

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

115. Малоземов В. Н., Сергеев А. Н. Аналитические основы теории полярных форм // Алгебра и анализ. 1998. Т. 10. № 6. С. 156-185.

116. Малоземов В. Н., Соловьева Н. А. Параметрические лифтинго-вые схемы вейвлетных разложений // Проблемы матем. анализа. 2009. Вып. 42. С. 15-41.

117. Малоземов В. Н., Чашников Н. В. Дискретные периодические сплайны с векторными коэффициентами и геометрическое моделирование // Докл. РАН. 2009. Т. 429. № 1. С. 19-21.

118. Малоземов В. Н., Чашников Н. В. Предельные теоремы теории дискретных периодических сплайнов // Докл. РАН. 2011. Т. 436. № 2. С. 168-169.

119. Избранные главы дискретного гармонического анализа и геометрического моделирования. Под редакцией проф. В. Н. Малозёмова. СПб.: СПбГУ, 2009. 584 с.

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

121. Мищенко Е. В. Об одном случае использования квадратурных формул Соболева в теории вейвлетов // Вестн. Новосиб. гос. ун-та. Серия: Математика, механика, информатика. 2008. Т. 8. Вып. 4. С. 49-59.

122. Мищенко Е. В. Получение полиномов специального вида и примеры их использования в теории степенных рядов и теории вейвлетов // Изв. вузов. Матем. 2011. № 1. С. 24-38.

123. Мысовских В. И. Системы компьютерной алгебры и символьные вычисления // Зап. научн. семин. ПОМИ. 2001. Т. 281. С. 227-236.

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

125. Новиков И. Я. Всплески с компактным носителем // Фундамент, и прикл. матем. 2001. Т. 7. № 4. С. 955-981.

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

127. Новиков И. Я., Северов П. Г. О мультивсплесковых преобразованиях // Вестн. Воронеж, гос. ун-та. Сер.: Физика. Математика. 2009. № 2. С. 96-100.

128. Новиков И. Я., Стечкин С. Б. Основные конструкции всплесков // Фундамент, и прикл. матем. 1997. Т. 3. № 4. С. 999-1028.

129. Новиков И. Я., Стечкин С. Б. Основы теории всплесков // УМН. 1998. Т. 53. № 6 (324). С. 53-128.

130. Новиков И. Я., Протасов В. Ю., Скопина М. А- Теория всплесков. М.: ФИЗМАТЛИТ, 2005. 616 с.

131. Новиков Л. В. Основы вейвлет анализа сигналов. СПб.: Изд-во ООО «МОДУС+», 1999. 152 с.

132. Новиков JI. В. Аппаратно-ориентированные вейвлеты и их применение в обработке экспериментальных данных // Приборы и техника эксперимента. 2005. № 6. С. 15-20.

133. Орловский Д. Г. О мультипликаторах в пространствах Вг)в // Anal. Math. 5 (1979), 207-218.

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

135. Певный А. Б. Кратномасштабный анализ в пространстве l2(Z) на основе дискретных сплайнов // Сиб. журн. вычисл. матем. 2004. Т. 7. № 3. С. 261-275.

136. Переберин А. В. О систематизации вейвлет-преобразований // Вычислительные методы и программирование. 2001. Т. 2. № 2. С. 133-158.

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

138. Петухов А. П. Периодические всплески // Матем. сб. 1997. Т. 188. № 10. С. 69-94.

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

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

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

142. Протасов В. Ю., Фарков Ю. А. Диадические вейвлеты и масштабирующие функции на полупрямой // Матем. сб. 2006. Т. 197. № 10. С. 129-160.

143. Протасов В. Ю. Аппроксимация диадическими всплесками // Матем. сб. 2007. Т. 198. № 11. С. 135-152.

144. Рвачев В. Л., Рвачев В. А. Об одной финитной функции // Докл. АН УССР. 1971. № 8. С. 705-707.

145. Роженко А. И. Абстрактная теория сплайнов. Новосибирск: НГУ, 1999. 175 с.

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

147. Свиньин С. Ф. Базисные сплайны в теории отсчетов сигналов. СПб.: Наука, 2003. 118 с.

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

149. Скопина М. А. Жесткие фреймы всплесков // Докл. РАН. 2008. Т. 419. № 1. С. 26-29.

150. Смоленцев Н. К. Вейвлет-анализ в MATLAB. М.: ДМК Пресс, 2010. 448 с.

151. Соболев С. Л. Введение в теорию кубатурных формул. М.: Наука, 1974. 808 с.

152. Соловьева Н. А. О жестких фреймах специального вида // Вестн. С.-Петерб. ун-та. сер. 1. 2009. Вып. 3. С. 79-85.

153. Спивак М. Математический анализ на многообразиях.: Пер. с англ. И. А. Березанского. СПб., 2005. 160 с.

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

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

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

157. Субботин Ю. Н. О кусочно-полиномиальной интерполяции // Мат. заметки. 1967. Т. 1. № 1. С. 63-70.

158. Субботин Ю. Н. О гладком базисе в С 0,27т] // Тр. центр, зонального объединения мат. кафедр. Калинин. 1970. Вып. 1. С. 141-144.

159. Субботин Ю. Н. Приближение сплайнами и гладкие базисы в С 0,2тт\ 11 Мат. заметки. 1972. Т. 12. № 1. С. 43-51.

160. Субботин Ю. Н. Формосохраняющая экспоненциальная аппроксимация // Изв. вузов. Матем. 2009. № 11. С. 53-60.

161. Субботин Ю. Н. Аппроксимации полиномиальными и тригонометрическими сплайнами третьего порядка, сохраняющие некоторые свойства аппроксимируемых функций // Тр. ИММ УрО РАН. 2007. Т. 13. № 2. С. 156-166.

162. Субботин Ю. Ы., Теляковский С. А. Приближение производных производными интерполяционных сплайнов // Тр. МИАН. 2003. Т. 243. С. 320-333.

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

164. Субботин Ю. Н., Черных Н. И. Интерполяционно-ортогональные системы всплесков // Тр. ИММ. 2008. Т. 14. № 3. С. 153-161.

165. Субботин Ю. Н., Черных Н. И. Гармонические всплески в краевых задачах для гармонических и бигармонических функций // Тр. ИММ УрО РАН. 2010. Т. 16. № 4. С. 281-296.

166. Трибель X. Теория функциональных пространств. М.: Мир. 1986. 448 с.

167. Ульянов П. JX. О рядах по системе Хаара // Матем. сб. 1964. Т. 63. № 3. С. 356-391.

168. Фарков Ю. А. Ортогональные вейвлеты с компактными носителями на локально компактных абелевых группах // Изв. РАН. Сер. матем. 2005. Т. 69. № 3. С. 193-220.

169. Фарков Ю. А. Биортогональные всплески на группах Виленкина // Тр. матем. ин-та им. В. А. Стеклова. 2009. Т. 265. С. 110-124.

170. Фарков Ю. А., Строганов С. А. О дискретных диадических вей-влетах для обработки изображений // Изв. вузов. Матем. 2011. № 7. С. 57-66.

171. Фрейзер М. Введение в вэйвлеты в свете линейной алгебры: Пер. с англ. Я. М. Жилейкина. М.: БИНОМ. Лаборатория знаний, 2008. 487 с.

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

173. Шевалдин В. Т. Калибровочные соотношения для B-L-сплайнов // Современные проблемы математики: тезисы 42-й Всероссийской молодежной школы-конференции. Екатеринбург: Институт математики и механики УрО РАН, 2011. С. 151-153.

174. Шилдт Г. С# 4.0: полное руководство. — М.: ООО «И.Д. Вильяме», 2011. 1056 с.

175. Шумилов Б. М. Алгоритм с расщеплением вейвлет-преобразования эрмитовых кубических сплайнов // Вестн. Томск, гос. ун-та. Математика и механика. 2010. № 4 (12). С. 45-55.

176. Яненко Н. Н., Квасов Б. И. Итерационный метод построения поликубических сплайн-функций // Докл. АН СССР. 1970. Т. 195. С 10551057.

177. Albeverio S., Evdokimov S., Skopina M. p-adic multiresolution analysis and wavelet frames //J. Fourier Anal. Appl., 16:5 (2010), 693714.

178. Aldroubi A., Cabrelli C., Molter U. Wavelets on Irregular Grids with Arbitrary Dilation Matrices, and Frame Atoms for L2(M.d) // Appl. Comput. Harmon. Anal., Special Issue on frames, pp. 119-140, 2004.

179. Aldroubi A., Cabrelli C., Molter U. How to construct wavelet frames on irregular grids and arbitrary dilations in ~Rd // AMS Contemporary Mathematics, Vol. 345 (2004) 1-9.

180. Anselone P. M., Laurent P. J. A general method for the construction of interpolating and smoothing spline functions // Numer. Math., 12 (1968), 66-82.

181. Atteia M. Généralization de la définition et des propriétés des «spline-fonctions» // C. R. Acad. Sci. Paris 260 (1965), 3550-3553.

182. Auscher P. Ondelettes fractales et application, Ph.D. Thesis, Université Paris, Dauphine, Paris, France, 1989.

183. Averbuch A. Z., Zheludev V.A., Cohen T. Interpolatory frames in signal space // IEEE Trans. Signal Proc. 54:6 (2006) 2126-2139.

184. Battle G. A block spin construction of ondelettes. Part I: Lemarié functions // Comm. Math. Phys. 110 (1987) 601-615.

185. Benedetto J. J., Benedetto R. L. A wavelet theory for local fields and related groups // J. Geom. Anal. 2004. Vol. 14. no. 3. P. 423-456.

186. Bernard Ch., Le Pennec E. Adaptation of regular grid filterings to irregular grids. Preprint of the CMAP. (2003) 1-10.

187. Beylkin G., Coifman R., Rokhlin V. Fast Wavelet Transforms and Numerical Algorithms /'/ Comm. Pure Appl. Math. 44 (1991), 141-183.

188. Bownik M. Tight frames of multidimensional wavelets //J. Fourier Anal. Appl. 3 (1997) 525-542.

189. Buchwald B., Miihlbach G. Construction of B-splines for generalized spline spaces from local ECT-systems// Journal of Computational and Applied Mathematics 159 (2003), 249-267.

190. Buhmann M. D. Multiquadratic prewavelets on nonequally spaced knots in one dimension // Math. Comput. 64 (1995), 1611-1625.

191. Buhmann M. D., Micchelli C. A. Spline prewavelets with non-uniform knots // Numer. Math. 61 (1992), 455-474.

192. Burt P. J., Adelson E. H. The Laplaeian pyramid as a compact image code // IEEE Trans. Coramun, 31(4), pp. 532-540, 1983.

193. Calderón A. P. Intermediate spaces and interpolation, the complex method // Studia Math. 24 (1964), 113-190.

194. Candés E. J., Donoho D. L. Ridgelets: a key to higher-dimensional intermittency? // Phil. Trans. R. Soc. Lond. A., pp. 2495-2509, 1999.

195. Carleson L. On the convergence and growth of partial sums of Fourier series // Acta Math., 116 (1966), 135-195.

196. Chui C. K., Wang J. Z. A cardinal spline approach to wavelets // Proc. Amer. Math. Soc., 113 (1991), 785-793.

197. Chui C. K., Wang J. Z. On compactly supported spline wavelets and a duality principle // Trans. Amer. Math. Soc., 330(2), 903-916, 1992.

198. Ciesielski Z. Properties of the orthonormal Franklin system // Stud. Math. 23 (1963), 141-157.

199. Ciesielski Z. Properties of the orthonormal Franklin system. II // Stud. Math. 27 (1966), 289-323.

200. Cohen A., Daubechies I. A stability criterion for biorthogonal wavelet bases and their related subband coding scheme // Duke Math. J., 68, 313-¿ÓD, lyyz.

201. Cohen A., Daubechies I., Feauveau J.C. Biorthogonal bases of compactly supported wavelets // Comm. Pure & Appl. Math., 45 (5), 485560, 1992.

202. Coifman R., Meyer F. G. Brushlets: a tool for directional image analysis and image compression // Appl. Comput. Harmon. Anal. 5 (1997), 147-187.

203. Coifman R., Meyer Y. Au delà des opérateurs pseudo-differentiels, S.M.F., Astérisque, 1978. 188 p.

204. Coifman R. R., Weiss G. Extension of Hardy spaces and their use in analysis // Bull. Amer. Math. Soc. 1977. V. 83. № 4. P. 569-645.

205. Croisier A., Esteban D., Galand C. Perfect channel splitting by use of interpolation / decimation /tree decomposition techniques // Int. Conf. on Info. Sciences and Systems, Patras, Greece, 1976. P. 443-446.

206. Dahmen W., Micchelli C. A. Banded matrices with banded inverses II: Locally finite decompositions of spline spaces // Constr. Approx., 9(2-3) : 263-281, 1993.

207. Daubechies I. Orthonormal bases of compactly supported wavelets // Comm. Pure and Appl. Math. 41 (1988), 909-996.

208. Daubechies I. Orthonormal bases of compactly supported wavelets, II. Variations on a theme // SIAM J. Math. Anal., 24 (2), pp. 499-519, 1993.

209. Daubechies I., Guskov I., Schroder P., Sweldens W. Wavelets on irregular point sets // Phil. Trans. Math., Physical, Engng. Sci. 357 (1999), 2397-2413.

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

211. Daubechies I., Lagarias J. Two-scale difference equations. I: Existence and global regularity of solutions // SIAM. J. Math. Anal. 22 (1991), 13881410.

212. Daubechies I., Lagarias J. Two-scale difference equations. II: Local regularity, infinite products of matrices and fractals // SIAM. J. Math. Anal. 23 (1992), 1031-1079.

213. Daubechies I., Grossman A., Meyer Y. Painless nonorthogonal expansions // J. Math. Phys. 1986. V. 27. P. 1271-1283.

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

215. Davydov O., Schumaker L. L. Interpolation and scattered data fitting on manifolds using projected Powell-Sabin splines // IMA J. Numer. Anal., 28 (2008), 785-805.

216. De Boor C., DeVore R., Ron A. On construction of multivariate (pre) wavelets // Constr. Approx. 1993, V. 9, P. 123-166.

217. Demjanovich Yu. K. Spline approximations on manifolds // Int. J. Wavelets Multiresolut. Inf. Process., 4 (2006), 383-403.

218. Dittmer A. Cross Product Identities in Arbitrary Dimension // Amer. Math. Mon., 101:9 (1994), 887-891.

219. DeVore R. A., Konyagin S. V., Temlyakov V. N. Hyperbolic Wavelet Approximation // Constr. Approx., 14 (1998), 1-26.

220. Do M. N., Vetterli M. Contourlets //In Beyond Wavelets, J. Stoeckler and G. V. Welland, eds., Academic Press, 2003.

221. Donoho D. L. Interpolating wavelet transforms. Preprint, Department of Statistics, Stanford University, 1992. 54 p.

222. Duffin R. J., Schaeffer A. C. A class of nonharmonic Fourier series // Trans. Amer. Math. Soc., 1952, V. 72, 341-366.

223. Ehler M. The multiresolution structure of pairs of dual wavelet frames for a pair of Sobolev spaces // Jaen J. Approx. 2 (2) (2010).

224. Faber G. Uber die Ortogonalen Functionen des Herrn Haar // Jahresber. Deutsch Math. Verein. 1910. V. 19. P. 104-112.

225. Fefferman C, Stein E. M. Hp spaces of several variables // Acta Math. 1972. V. 129. P. 137-193.

226. Ford J. M., Oseledets I. V., Tyrtyshnikov E. E. Matrix approximations and solvers using tensor products and non-standard wavelet transforms related to irregular grids // Rus. J. Numer. Anal, and Math. Modelling. 2004. V. 19. № 2. P. 185-204.

227. Franklin Ph. A set of continuous orthogonal functions // Math. Annalen 100 (1928), 522-529.

228. Fritz K. Wavelet and Multiwavelet. Chapman & Hall/CRC, 2004. 269 p.

229. Fundamental Papers in Wavelet Theory. Edited by C. Heil, D. F. Walnut. Princeton University Press, 2006. 878 p.

230. Gabor D. Theory of communications //J. IEE (London) 93 (1946), 429457.

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

232. Golomb M., Weinberger H. Optimal approximation and erros bounds // On Numerical Approximation (R. E. Langer, ed.), Univ. of Wisconsin Press, Madison, 1958, 117-190.

233. Greville T. N. E. The general theory of osculatory interpolation // Trans. Actuar. Soc. Amer., 1944, vol. 45, p. 202-265.

234. Grossman A., Morlet J. Decomposition of Hardy functions into square intergable wavelets of constant shape // SIAM J. Math. Anal. 15 (1984), 723-736.

235. Haar A. Zur Theorie der orthogonalen Funktionensysteme // Inauguraldissertation, Cottingen, 1909. (Math. Ann. 71:1 (1910), 3853.)

236. Han B., Shen Z. Dual wavelet frames and Riesz bases in Sobolev spaces // Constr. Approx. 29 (2009) 369-406.

237. Hernandez E., Weiss G. A first course on wavelets. CRC Press, Boca Raton, FL, 1996.

238. Holladay J. C. A smoothest curve approximation // Math. Tables Aids Comput., 1957, vol 11, № 60, p. 233-243.

239. Hunt R. A. On the convergence of Fourier series // Proc. of the Conference on Orthogonal Expansions and their Continuous Analogues (D. T. Haimo. ed.), Southern Illinois University Press, (1968), 235-255.

240. Jaffard S., Meyer Y., Ryan R. Wavelets: Tools for Science and Technology, SIAM (2001). 256 p.

241. Jenkins W. A. Osculatory Interpolation: New Derivation and Formulae // Record of the American Institute of Actuaries 15, pp. 87, (1926).

242. Kerkyacharian G., Kyriazis G., Le Pennec E., Petrushev P., Picard D. Inversion of noisy Radon transform by SVD based needlets // Appl. Comput. Harmon. Anal., 28(1):24—45, 2010.

243. Khrennikov A. Yu., Shelkovich V. M., Skopina M. A. p-Adic refinable functions and MRA-based wavelets // J. Approx. Theory, 161, (2009), 226-238.

244. Kozyrev S. V. Wavelet analysis as a p-adic spectral analysis // Izv. Akad. Nauk. Seria Math. 2002. Vol. 66, no. 2. P. 149—158.

245. Kolmogoroff A. N. Une série de Fourier-Lebesque divergente presque partout // Fund. Math., 4 (1923), 324-328.

246. Kolmogoroff A. N. Une série de Fourier-Lebesque divergente partout // C. R. Acad. Sci. Paris, 183 (1926), 1327-1329.

247. Krivoshein A., Skopina M. Approximation by frame-like wavelet systems // Appl. Comput. Harmon. Anal., 31:3 (2011), 410-428.

248. Labate D., Lim W., Kutyniok G., Weiss G. Sparse multidimensional representation using shearlets // Wavelets XI (San Diego, CA, 2005), 254262, SPIE Proc. 5914, SPIE, Bellingham, WA, 2005.

249. Lai M.-J., Schumaker L. L. Spline Functions on Triangulations. Cambridge University Press, Cambridge, 2007, 607 pp.

250. Lang W. Ch. Orthogonal wavelets on the Cantor dyadic group // SIAM J. Math. Anal., 27:1 (1996), 305-312.

251. Lawton W. Tight frames of compactly supported affine wavelets // J. Math. Phys. 31 (1990), 1898-1901.

252. Le Pennec E., Mallat S. Sparse geometrical image representation with bandelets, IEEE Transactions on Image Processing, (2004).

253. Lebedeva E. A. Quasispline wavelets and uncertainty constants // Applied and Computational Harmonic Analysis, 30:2 (2011), 214—230.

254. Lebesgue H. Recherches sur la convergence des series de Fourier // Math. Annalen,. 61 (1905), 251-280.

255. Lemarié P. G. Ondelettes a localisation exponentielle //J. Math. Pures et Appl., vol. 9, no. 67, 227-236, 1988.

256. Lemarié P. G., Meyer Y. Ondelettes et bases hilbertiennes // Rev. Math. Iber. 2 (1986), 1-18.

257. Littlewood J. E., Paley R. E. A. C. Theorems on Fourier series and power series // J. Lond. Math. Soc., 6 (1931), 230-233; Proc Lond. Math. Soc. 42 (1936), 52-89; 43, 105-126.

258. Liu Y. Irregular sampling for spline wavelet subspaces // IEEE Trans. Inform. Theory, vol. 42, pp. 623-627, Mar. 1996.

259. Liu Y., Walter G. G. Irregular sampling in wavelet subspaces //J. Fourier Anal. Appl., vol. 2, no. 2, pp. 181-189, 1995.

260. Lorentz R. A., Sahakian A. A. Orthogonal trigonometric Shauder bases of optimal degree for C(0.2tt) // J. Fourier Anal. Appl., 1:1 (1994), 103— 112.

261. Luzin N. N. Sur une propriété des fonctions a carré sommable // Bull. Calcutta math. Soc. 20 (1930), 139-154.

262. Lyche T., Morken K., Quak E. Theory and Algorithms for non-uniform spline wavelets // Multivariate Approximation and Applications, N. Dyn, D. Leviatan, D. Levin, and A. Pinkus, (eds), Cambridge University Press, 2001, 152-187.

263. Lyche T., Morken K., Pelosi F. Stable, linear spline wavelets on nonuniform knots with vanishing moments // CAGD, 26(2), 2009, 203-216.

264. Mallat S. Multiresolution representation and wavelets, Ph. D. Thesis, University of Pennsylvania, Philadelphia, PA, 1988.

265. Mallat S. Multiresolution approximations and wavelet orthogonal bases of L2(M) // Trans. Amer. Math. Soc., vol. 315, no. 1, 69-87, 1989.

266. Mallat S. A theory of multiresolution signal decomposition: The wavelet representation // IEEE Trans. Pattern Anal. Machine Intell. 11 (1989), 674693.

267. Mallat S. An efficient image representation for multiscale analysis // Proc. of Machine Vision Conference, Lake Taho. 1987.

268. Marr D., Hildreth E. Theory of edge detection // Proc. R. Soc. Lond. Series B, Biological Sciences, vol. 207, 187-217, Feb. 1980.

269. Meyer Y. Principe d'incertitude, bases hilbertiennes et algebres d'opérateurs // Séminaire Bourbaki. 1985-86. № 662. 1-15.

270. Meyer Y. Ondelettes et fonctions splines // Séminaire EDP, Ecole Polytech., Paris, Décembre 1986.

271. Meyer Y. Constructions de bases orthonormeés d'ondelettes // Rev. Mat. Iberoamer, 4:1 (1988), 31-39.

272. Meyer Y. Ondelettes et opérateurs. Paris: Herman, 1990.

273. Morlet J., Arens G., Fourgeau I., Giard G. Wave propagation and sampling theory // Geophysics, 47 (1982), 203-236.

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

275. Offin D., Oskolkov K. A note on orthonormal polynomial bases and wavelets // Constr. Approx., 9:1 (1993), 319-325.

276. Oswald P. Semiorthogonal linear prewavelets on irregular meshes //In Approximation and Probability, Banach Center Publ. vol. 72, Inst. Math. Polish Acad. Sei., 2006, 221-234.

277. Paul T. Functions analytic on the half-plane as quantum mechanical states // J. Math. Phys. 25:11 (1984) 3252-3262.

278. Petukhov A. Explicit construction of framelets // Appl. Comput. Harm. Anal. 11 (2001), 313-327.

279. Pittner S., Schneid J., Ueberhuber Ch. W. The Wavelet Literature Survey // Technical University Vienna, Wien, Austria, 1993.

280. Radon J. Uber die Bestimmung von Funktionen durch ihre Integralwerte längs gewisser Mannigfaltigkeiten // Ber. Verh. Sachs. Akad. Wiss. Leipzig, Math. Nat. kl. 69 (1917), 262-277.

281. Ricker N. The form and nature of seismic waves and the structure of seismograms // Geophysics, 1940, Vol. 5, № 4, 348-366.

282. Riesz M. Sur les fonctions conjuguées, Math. Zeit. vol. 27 (1927) pp. 218244.

283. Ron A., Shen Z. Affine systems in L2(Rd): the analysis of the analysis operator //J. Func. Anal. 1997. V. 148. P. 408-447.

284. Schoenberg I. J. Contributions to the problem of approximation of equidistant data by analytic functions // Quart. Appl. Math. 1946. Vol. 4. P. 45-99, 112-141.

285. Schumacker L. L. Spline Functions. Basic Theory. Waley Interscience.lOQI K/IQ ^1NCVV iUiiV. UUi. jj.

286. Schumaker L. L. Spline Functions: Basic Theory, 2nd Edition, Cambridge University Press, Cambridge, 2007, 600 pp.

287. Shadrin A. Yu. The Loo-norm of the Z/2-spline projector is bounded independently of the knot sequence: A proof of de Boor's conjecture // Acta Math. 2001. V. 187, N 1. P. 59-137.

288. Shannon C. E. Communication in the presence of noise // Proc. IRE, 37 (1949) 10-21.

289. Shauder J. Zur Theorir stetiger Abbildungen in Funktionalraumen // Math. Z. 1927. V. 26. P. 47-65.

290. Show R. Vector cross products in n dimensions // Int. J. Math. Educ. Sci. Technol., 18:6 (1987), 803-816.

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

292. Stevenson R. Locally supported piecewise polynomial biorthogonal wavelets on non-uniform meshes // Constr. Approx. 19 (2003), 477—508.

293. Strang G., Nguyen T. Wavelets and filter banks, Wellesley-Cambridge Press, 1996.

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

295. Sweldens W. The lifting scheme: A customdesign construction of biorthogonal wavelets. Tech. Rep. 1994:7, Industrial Mathematics Initiative, Department of Mathematics, University of South Carolina, 1994.

296. Sweldens W. The lifting scheme: A construction of second generation wavelets // SIAM J. Math. Anal., 29:2 (1997) 511-546.

297. Tchamitchian Ph. Biorthogonalité et theorie des operateurs // Revista Matematica Iberoamericana, v. 3. 163-189, 1987.

298. Triebel H. Multipliers and unconditional Schauder bases in Besov spaces // Stud. Math. 60 (1977), 145-156.

299. Velisavljevic V., Beferull-Lozano B., Vetterli M., Dragotti P. L.

300. Directionlets: Anisotropic multidirectional representation with separable filtering, IEEE Trans. Image Process. 15(7) (2006), 1916-1933.

301. Vetterli M., Her ley C. Wavelets and filter banks: theory and design // IEEE Trans, on Signal Proc, 40(9), 2207-2232, 1992.

302. Ville J. Theorie et applications de la notion de signal analytique // Cables et TYansm. 1948. Vol. 2A, №1. P. 61-74.

303. Wang G., Chen Q., Zhou M. NUAT B-spline curves // Computer Aided Geometric Design. 2004. Vol. 21, № 2. P. 193-205.

304. Wang G., Li Y. Optimal properties of the uniform algebraic trigonometric B-splines // Computer Aided Geometric Design. 2006. Vol. 23, № 2. P. 226238.

305. Weierstrass K. Mathematische Werke, volume II. Mayer & Muller, Berlin, 1895.

306. Whittaker E. T. On the functions which are represented by the expansion of interpolating theory // Proc. R. Soc. Edinburgh, 35 (1915) 181-194.

307. Wigner E. P. On the quantum correction for thermodynamic equilibrium // Phys. Rev. 1932. Vol. 40. P. 749-759.

308. Wojtaszczyk P. Wavelets as unconditional bases in Lp( R) //J. Fourier Anal. Appl. v. 5 n. 1 (1999) pp.73-85.

309. Wozniakowski K. On a orthonormal polynomial bases C—1,1] // Studia Math. 2001. V. 144. № 2. P. 181-196.

310. Zhanwei L., Guoen H., Guochang W. Regular and Irregular Sampling Theorem for Multiwavelet Subspaces // Mathematical Problems in Engineering Volume 2010 (2010), Article ID 757039, 18 pages.

311. Zhao С., Zhao P. Sampling theorem and irregular sampling theorem for multiwavelet subspaces // IEEE Trans. Signal Processing, vol. 53, no. 2, part 1, pp. 705-713, 2005.

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

313. Демьянович Ю. К., Макаров А. А. Калибровочные соотношения для неполиномиальных сплайнов // Проблемы матем. анализа. 2006. Вып. 34. С. 39-54. (J. Math. Sei. 142 (2007), no. 1, 1769-1787.)

314. Макаров А. А. Об одном алгебраическом тождестве в теории Д^-сплайнов второго порядка // Вестн. С.-Петерб. ун-та. Сер. 1. 2007. Вып. 1. С. 96-98. (Vestnik St. Petersburg University: Mathematics, 40 (2007), no. 1, 85-88.)

315. Макаров А. А. О распараллеливании вэйвлетных методов сжатия информации // Вестн. С.-Петерб. ун-та. Сер. 10. 2007. Вып. 4. С. 45-49.

316. Макаров А. А. Нормализованные тригонометрические сплайны лаг-ранжева типа // Вестн. С.-Петерб. ун-та. Сер. 1. 2008. Вып. 3. С. 81-87. (Vestnik St. Petersburg University: Mathematics, 41 (2008), no. 3, 266-272.)

317. Макаров А. А. О вэйвлетном разложении пространств сплайнов первого порядка // Проблемы матем. анализа. 2008. Вып. 38. С. 47-60. (J. Math. Sci. 156 (2009), no. 4, 617-631.)

318. Макаров А. А. Моделирование калибровочных соотношений для неполиномиальных сплайнов // Вычисл. технологии. 2008. Т. 13. Спец. вып. 4. С. 94-100.

319. Макаров А. А. Минимальные тригонометрические сплайны нулевой высоты // Методы вычислений. Вып. 22. Сб. / Под ред. В. М. Рябова. СПб.: Изд-во С.-Петерб. ун-та, 2008. С. 82-98.

320. Макаров А. А. Один вариант сплайн-вэйвлетного разложения пространств В-сплайнов // Вестн. С.-Петерб. ун-та. Сер. 10. 2009. Вып. 2. С. 59-71.

321. Kosogorov О. М., Makarov A. A. Spline wavelet decomposition andparallel compression // Zbornik radova konferencije MIT 2009. University of Pristina. Beograd, 2010. P. 202-205.

322. Макаров А. А. Кусочно-непрерывные сплайн-вэйвлеты на неравномерной сетке // Труды СПИИРАН. 2010. Вып. 14. С. 103-131.

323. Макаров А. А. Сплайн-вэйвлетные разложения на неравномерной сетке. Некоторые варианты построения. Lambert Academic Publishing, 2010. 130 с.

324. Макаров А. А. О построении сплайнов максимальной гладкости // Проблемы матем. анализа. 2011. Вып. 60. С. 25-38. (J. Math. Sci. 178 (2011), по. 6, 589-604.)

325. Макаров А. А. Матрицы реконструкции и калибровочные соотношения для минимальных сплайнов // Проблемы матем. анализа. 2011. Вып. 60. С. 39-52. (J. Math. Sci. 178 (2011), no. 6, 605-621.)

326. Макаров А. А. Матрицы реконструкции и декомпозиции для линейных сплайнов // Труды СПИИРАН. 2011. Вып. 18. С. 215-236.

327. Макаров А. А. Алгоритмы вэйвлетного уточнения пространств сплайнов первого порядка // Труды СПИИРАН. 2011. Вып. 19. С. 203-220.

328. Макаров А. А. Сплайн-вейвлетное сжатие на отрезке // Семинар «DHA h CAGD». Избранные доклады. 12 ноября 2011 г. (http://dha.spb.ru/reps11.shtml#l112)

329. Макаров А. А. Матрицы добавления и удаления узлов для неполиномиальных сплайнов // Вычислительные методы и программирование. 2012. Т. 13. С. 74-86.