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

УНИВЕРСИТЕТ

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

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

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

И ЕЕ ПРИЛОЖЕНИЯ

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

и комплексы программ

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

АВТОРЕФЕРАТ

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

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

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

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

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

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

доктор физико-математических наук, доцент Волков Юрий Степанович (Институт математики им. С. Л. Соболева СО РАН) доктор физико-математических наук Новиков Лев Васильевич (Институт аналитического приборостроения РАН) доктор физико-математических наук, профессор Скопина Мария Александровна (Санкт-Петербургский государственный университет)

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

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

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

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

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

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

Изучение А. Хааром частных сумм ряда Фурье привело к построению первого всплеска. Развитие теории всплесков осуществляли следующие ученые:

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

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

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

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

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

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

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

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

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

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

Пространства мультивсплесков рассматривались в работах Ч. Жао и П. Жао, Л. Жанвея, Х. Гуена и В. Гуочанга.

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

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

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

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

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

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

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

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

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

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

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

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

5. Для функций из пространства C m+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», Kopaonik, Serbia, Budva, Montenegro, 2009; Мiжнароднiй симпозiум «Питання оптимизацii обчислень», смт. Кацивелi, Украiна, 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а), грантом Президента РФ (МК-5219.2011.1), грантом АВЦП «Развитие научного потенциала высшей школы» (проект № 2.1.2/10824), грантом Санкт-Петербурга в сфере научной и научно-технической деятельности (проект № 361/09), грантами молодым ученым, молодым кандидатам наук вузов и академических институтов, расположенных на территории Санкт-Петербурга (проекты № 26.05/151/27, № 236/14.11.11), а также отмечены дипломом победителя (1 место) XII конкурса бизнес-идей, научно-технических разработок и научноисследовательских проектов «Молодые. Дерзкие. Перспективные», проводимого Комитетом по науке и высшей школе Правительства Санкт-Петербурга.

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

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

В первой главе рассматриваются сплайны произвольного порядка, имеющие минимальный носитель. Пусть N — множество натуральных чисел, Z — множество целых чисел, Z+ = {j | j 0, j Z}, R1 — множество вещественных чисел. Пусть m Z+. Векторное (линейное) пространство (m + 1)мерных вектор-столбцов обозначим через Rm+1, причем векторы в нем будем отождествлять с одностолбцовыми матрицами и применять к ним обычные матричные операции; в частности, для двух векторов a, b Rm+1 выражение (a, b)Rm+1 = aT b = [a]i [b]i представляет собой евклидово скалярное произвеi= дение этих векторов, где T — операция транспонирования, а компоненты векторов обозначаются квадратными скобками и снабжаются индексами 0, 1,..., m, например, a = ([a]0, [a]1,..., [a]m )T. Квадратная матрица, столбцами которой являются векторы a0, a1,..., am Rm+1 (в указанном порядке), обозначается символом (a0, a1,..., am ), а выражение det(a0, a1,..., am ) обозначает ее определитель.

Упорядоченное множество A = {aj }jZ векторов aj Rm+1 будем называть цепочкой векторов. Цепочка A называется полной цепочкой векторов, если det(ajm, ajm+1,..., aj ) = 0 для всех j Z. Совокупность всех полных цепочек будем обозначать через A.

Множество всех функций непрерывных на интервале (, ) обозначим чеdef рез C(, ). Для любого числа S Z+ введем обозначение C S (, ) = {u | u(i) C(, ) i = 0, 1, 2,..., S}, полагая C 0 (, ) = C(, ). Если компоненты векторфункции u Rm+1 непрерывно дифференцируемы S раз на интервале (, ), то будем писать u CS (, ). Аналогичные обозначения C S [a, b] и CS [a, b] будем использовать для соответствующих пространств на отрезке [a, b].

На интервале (, ) R1 рассмотрим сетку X = {xj }jZ, где = lim xj, = lim xj (случаи =, = + не исключаются).

Введем обозначения M = свойством локальной квазиравномерности и положим hX = sup (xj+1 xj ).

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

Если цепочка векторов A = {aj } полная, то из условий однозначно определяются функции j (t), t M, j Z. Ясно, что supp j (t) Sj. По формулам Крамера из системы линейных алгебраических уравнений (2) находим где символьная запись j означает, что определитель в числителе получается из определителя в знаменателе заменой столбца aj на столбец (t) (с сохранением прежнего порядка следования столбцов).

Линейная оболочка функций {j }jZ называется пространством минимальных (A, )-сплайнов m-го порядка или пространством минимальных сплайнов лагранжева типа (нулевой высоты) на сетке X и обозначается через Рассматриваемые бесконечные ряды вида фиксированном t (, ) содержат не более m + 1 слагаемых, поэтому при любой последовательности {cj }jZ упомянутый ряд сходится (в смысле поточечной сходимости). Здесь и далее отсутствие пределов суммирования у знака суммы означает суммирование по всем целым числам.

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

В дальнейшем для вектор-функции CS (, ), S Z+, положим Теорема 1. Пусть S Z+, CS (, ), A A. Для того, чтобы проS) изводные j (t) функций j (t), t M, j Z, могли быть продолжены до функций, непрерывных на интервале (, ), необходимо и достаточно, чтобы Следствие 1. Пусть Cm1 (, ), A A. Для того, чтобы все функции j (t), t M, j Z, могли быть продолжены до функций класса C m1 (, ), необходимо и достаточно, чтобы выполнялись соотношения для всех z, z0, z1,..., zm1 Rm+1. Вектор-функцию (z0, z1,..., zm1 ) называют m-местным векторным произведением в пространстве Rm+1 и обозначают При Cm1 (, ) рассмотрим векторы, определяемые формулой линейно независимые при любом k Z, то для того, чтобы функции j (t), t M, j Z, могли быть продолжены до функций класса C m1 (, ), необходимо и достаточно, чтобы выполнялись соотношения Пусть Cm (, ). Введем следующее обозначение для вронскиана Определим цепочку векторов A = {a } формулой В приложении 1 изучены свойства цепочки A, в частности, доказано, что вектору a можно придать вид следующего символического определителя Теорема 3. Пусть Cm (, ). Если выполнено условие и сетка X X (K0,, ) для некоторого K0 1, то при достаточно малом hX пространство S(X, A, ) лежит в пространстве C m1 (, ).

Замечание 1. Если на интервале (, ) компоненты вектор-функции образуют фундаментальную систему решений дифференциального уравнения вида u(m+1) + p1 (t)u(m) +... + pm+1 (t)u = 0 с непрерывными коэффициентами, то условие (7) выполнено.

Следствие 2. В условиях теоремы 3 цепочка векторов {dj }jZ является полной, при этом справедливы соотношения Пространство S(X, A, ) называется пространством минимальных B сплайнов m-го порядка на сетке X. Сами сплайны будем называть минимальными сплайнами максимальной гладкости.

Теорема 4. Пусть [(t)]0 1 для всех t (, ). Если цепочку векторов N def A = {aN } определить формулой то справедливо тождество Пространство S(X, AN, ) называется пространством нормализованных B сплайнов m-го порядка на сетке X.

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

Теорема 5. Сплайн j,m (t) определяется узлами своего носителя xj, xj+1,..., xj+m+1 и векторами Приведем примеры сплайнов порядка m = 0, 1, 2, 3. Рассмотрим измеримую функцию : (, ) R1 отличную от нуля почти всюду на интервале (, ).

Сплайнами нулевого порядка называются функции j,0 (t), j Z, удовлетворяB ющие условиям Сплайны j,0 (t), получаемые для порождающей функции C 1 (, ), (t) = 0 для всех t (, ) по формуле (8), называются кусочно-непрерывными сплайнами на сетке X, при этом j,0 (t) C 1 (, ).

Для m = 1 формулы (5) и (6), использующие m-местное векторное произвеdef дение (4), для всех j Z принимают вид dT x det(j, x), x R2, и a = j+1.

Сплайны j,1 C(, ) и справедливы формулы При m = 2 сплайны j,2 C 1 (, ) и справедливы формулы При m = 3 сплайны j,3 C 2 (, ) и справедливы Примеры полиномиальных и неполиномиальных сплайнов, построенных для различных порождающих вектор-функций, приведены в Приложении 2. При (t) = (1, t, t2,..., tm )T сплайны j,m (t) совпадают с известными полиномиальB ными B-сплайнами m-ой степени.

Рассмотрим конечномерные пространства сплайнов на отрезке [a, b] (, ).

Введем обозначения из полной бесконечной цепочки A A выделим конечную цепочку A, n Для измеримого (по Лебегу) множества M R1 обозначим через mes (M) его лебегову меру. Пусть система {gj } состоит из функций gj (t), заданных почти везде на интервале (, ), и [a, b] (, ). Система функций {gj | mes (supp gj (a, b)) > 0} называется сужением системы {gj } на отрезок [a, b].

Сузим все функции пространства S(X, A, ) на множество [a, b]. Совокупность этих сужений представляет собой конечномерное линейное пространство S(Xn, A, ) = u | u(t) = Теорема 6. Функция un (t) = стве S(Xn, A, ) и полностью определяется набором узлов {xj }jJm,m+n, наn бором векторов {j }jJm,m+n, S = 0, 1,..., m 1, и набором коэффициентов {cj }jJm,n1.

Следствие 3. Сужения функций j,m образуют линейно независимую систему на отрезке [a, b], причем dim S(Xn, A, ) = n + m.

Во второй главе рассматривается укрупнение и измельчение исходной сетки (бесконечной и конечной). Глава посвящена калибровочным соотношениям и построению соответствующих матриц реконструкции, откуда следует вложенность пространств B -сплайнов, построенных на различных сетках. На сетке X X (K0,, ), полученной из сетки X X (K0,, ) удалением одного узла, строятся сплайны i,m. Устанавливаются калибровочные соотношения (обобB щающие масштабирующее уравнение), выражающие сплайны i,m (на сетке X) в виде линейной комбинации сплайнов j,m. Последовательное удаление узлов позволяет рассмотреть любую пару сеток X X и утверждать, что справедливо вложение пространств S(X, A, ) S(X, A, ).

Ввиду теоремы 5 существует функция X, (t, g0, g1,..., gm+1 ), зависящая от вещественной переменной t (, ) и векторов g0, g1,..., gm+1 Rm+1, такая, что Из исходной сетки X для фиксированного k Z удалим один узел xk+1 и на полученной таким образом укрупненной (разреженной) сетке X рассмотрим сплайны j,m (t), j Z.

Пусть = xk+1, а xj – узлы вновь полученной сетки X = {xj | j Z} :

Условимся ставить волну сверху над обозначениями всех ранее введенных объектов, определяемых новой сеткой X. В частности, положим Функции j,m (t) можно отыскать по формуле (3), заменив узлы исходной сетки xj на узлы xj, j Z, при этом j,m (t) = X, (t, dj, dj+1,..., dj+m+1 ).

Введем два множества пар индексов (i, j), полагая Для формулировки следующей теоремы необходимо рассмотреть систему линейных алгебраических уравнений (с неособенной матрицей системы) отноB сительно функций j,m, которые в этой ситуации будем считать неизвестными, Теорема 7. Любую функцию i,m, i Z можно представить в виде конечB ной линейной комбинации функций j,m, j Z, где коэффициенты pi,j определяются следующей формулой Соотношения (11) называются калибровочными соотношениями. Дадим их матричное представление. Введем бесконечномерные вектор-столбцы, компонентами которых являются функции j,m (t) и j,m (t), j Z:

Соотношения (11) представимы в виде где P — бесконечная матрица вида P = (pi,j )i,jZ, элементы которой задаются формулой (12). Матрица P называется матрицей укрупняющей (разрежающей) реконструкции или матрицей удаления узла на интервале (, ).

Замечание 2. Матрицу P можно представить в виде Аналогичным образом рассматривается измельченная (уточненная или сгущенная) сетка X X (K0,, ), полученная из сетки X добавлением одного нового узла (xk, xk+1 ). Будем надчеркивать обозначения всех ранее введенных объектов, определяемых сеткой X = {xj | j Z}:

На сетке X строятся сплайны B и устанавливаются калибровочные соотj,m ношения, выражающие сплайны i,m (на сетке X) в виде линейной комбинации сплайнов B. Введем бесконечномерный вектор-столбец B (t), компонентами которого являются функции B (t), j Z:

Тогда калибровочные соотношения представимы в виде где P = (pi,j )i,jZ — матрица измельчающей (уточняющей или сгущающей) реконструкции или матрица добавления узла на интервале (, ).

Последовательное добавление узлов позволяет рассмотреть любую пару сеток X X, и утверждать, что справедливо вложение пространств S(X, A, ) S(X, A, ).

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

Предполагая, что k {0, 1,..., n 2}, удалим узел xk+1 из сетки Xn ; в результате получим укрупненную сетку где узлы xi, i = m,..., n + m 1, определяются формулами (9). Для k {0, 1,..., n 1} добавим узел (xk, xk+1 ) к сетке Xn ; в результате получим измельченную сетку где узлы xi, i = m,..., n + m + 1, определяются формулами (14).

Введем конечномерные вектор-функции Ввиду равенства (13) в конечномерном случае калибровочные соотношения для k {0, 1,..., n 2} могут быть записаны в виде где Pn — прямоугольная числовая матрица размера (n + m 1) (n + m), называемая матрицей укрупняющей (разрежающей) реконструкции на отрезке [a, b].

Ввиду равенства (15) в конечномерном случае калибровочные соотношения для k {0, 1,..., n 1} могут быть записаны в виде где Pn — прямоугольная числовая матрица размера (n+m)(n+m+1), называемая матрицей измельчающей (уточняющей или сгущающей) реконструкции на отрезке [a, b].

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

Третья глава посвящена построению систем функционалов, биортогональных системам минимальных сплайнов, и нахождению соответствующих матриц декомпозиции. Рассмотрим некоторое линейное пространство U над полем вещественных чисел и сопряженное ему пространство U линейных функционалов f над пространством U. Значение функционала f на элементе u U обозначим через f, u. Введем линейное пространство Cc, d, состоящее из функций u(t) пространства C(c, d), которые имеют следующие конечные пределы lim u(t) и lim u(t). Введем также пространства td Символом (CS ) обозначается пространство, сопряженное к пространству CS. При CS (, ) пространства S(X, A, ) лежат в пространстве CS.

Для функционала f (CS ) будем писать supp f [c, d], если значение f, u определяется значениями функции u CS на интервале (c, d).

Теорема 8. Пусть CS (, ), A A и для каждого фиксированного k Z определен вектор fk = ([fk ]0, [fk ]1,..., [fk ]m )T, компонентами которого являются функционалы [fk ]i (CS ), i = 0, 1,..., m, такие, что supp [fk ]i [xk, xk+1 ]. Пусть матрица fk T со столбцами вида неособенная. Тогда при каждом фиксированном числе r {0, 1,..., m} система {gk }kZ функционалов [gk ]r (CS ), определяемых равенствами представляет собой продолжение на CS системы функционалов, биортогоX нальной системе минимальных (A, )-сплайнов {k }k Z, т. е.

где k,k — символ Кронекера. При этом supp [gk ]r [xkr+m1, xkr+m ].

Пусть {fj }jZ такая система функционалов, что supp fj [xj, xj+1 ].

Теорема 9. Для того, чтобы система функционалов {fj }jZ была биортогональна системе минимальных (A, )-сплайнов {j }j Z, необходимо и достаточно, чтобы смотрим интерполяционную задачу где {vj }jZ — заданная последовательность чисел (бесконечная в обе стороны).

Теорема 10. В пространстве S(X, A, ) существует единственное решение задачи (18), и это решение дается формулой Рассмотрим систему функционалов {fi }iZ биортогональную системе функций {j,m }jZ. Вычислим значения функционалов fi на функциях j,m (t). Пусть далее Введем два множества пар индексов (i, j), полагая Теорема 11. Для i, j, k Z справедливы равенства qi,j = Матрица Q = (qi,j )i,jZ, элементы которой задаются формулами (20), называется матрицей укрупняющей (разрежающей) декомпозиции на интервале (, ).

Замечание 3. Матрицу Q можно представить в виде Пусть qi,j = fi, B для всех i, j Z. Матрица Q = (qi,j )i,jZ называетj,m ся матрицей измельчающей (уточняющей или сгущающей) декомпозиции на интервале (, ).

Теорема 12. Матрицы Q и Q являются левыми обратными к матрицам P и P соответственно, т. е.

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

Пусть далее система функционалов {f j }jZ биортогональна системе функций { B,m }j Z.

Замечание 4. Справедливы равенства Рассмотрим представление матриц декомпозиции на отрезке [a, b]. Выделим из множества функционалов {fj }jZ конечный набор из n+m функционалов, из множества функционалов {fj }jZ конечный набор из n+m1 функционалов, из множества функционалов {f j }jZ конечный набор из n + m + 1 функционалов.

Теорема 13. Для систем функционалов {fi }iJm,n1, {fj }jJm,n2 и {f l }lJm,n справедливы равенства причем supp fi [a, b], supp fj [a, b], supp f l [a, b].

Прямоугольная матрица Qn = (qi,j ), i Jm,n2, j Jm,n1, размера (n + m 1) (n + m) называется матрицей укрупняющей (разрежающей) декомпозиции на отрезке [a, b], а прямоугольная матрица Qn = (qi,j ), i Jm,n1, j Jm,n, размера (n + m) (n + m + 1) называется матрицей измельчающей (уточняющей) декомпозиции на отрезке [a, b].

Теорема 14. Для матриц Pn и Qn, Pn и Qn справедливы соотношения где In+m1, In+m — единичные квадратные матрицы порядка n + m 1 и n + m соответственно.

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

Четвертая глава посвящена построению всплесковых разложений пространств сплайнов. Рассмотрим сплайн-всплесковое сжатие на интервале. Согласно калибровочным соотношениям (11) справедливо вложение пространств Рассмотрим оператор P проектирования пространства S(X, A, ) на подпространство S(X, A, ), задаваемый формулой и введем оператор Q = I P, где I — тождественный оператор.

Пространство W = Q S(X, A, ) называется пространством всплесков, а прямое разложение называется сплайн-всплесковым сжатием пространства S(X, A, ).

В соответствии с равенством (22) для u S(X, A, ) имеем так что для чисел cj = fj, u получаем Пусть известны коэффициенты cj в разложении элемента u S(X, A, ) по элементам базиса j,m, а именно, u = cj j,m.

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

Введем вектор-столбцы a = (..., a1, a0, a1,...)T, b = (..., b1, b0, b1,...)T, c = (..., c1, c0, c1,...)T, и перепишем формулы декомпозиции в матричном виде Применяя к предыдущему равенству матрицу Q и используя формулу (21), получаем равенство Q b = 0, откуда следует, что вектор b содержится в ядре оператора Q : b ker Q.

Рассмотрим пространство L всех числовых последовательностей, представdef ленных вектор-столбцами l = (..., l1, l0, l1,...)T, и линейный оператор, определяемый матрицей Q в нем (это определение корректно, ибо упомянутая матрица имеет конечное число ненулевых элементов в каждой строке). Ядро этого оператора представляет собой линейное пространство; обозначим его через Рассмотрим еще два экземпляра пространства L, обозначая их через A и C.

Элементами пространства A являются векторы a, а элементами пространства C являются векторы c. Пусть F — прямое произведение пространств A и B:

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

Пусть теперь известны коэффициенты ai и bi в разложениях проекций элемента u S(X, A, ) на пространства S(X, A, ) и W :

Найдем формулы для определения коэффициентов cj для представления элемента u в виде суммы u = cj j,m ; упомянутые формулы имеют вид (23) и называются формулами реконструкции.

Оператор R : F C, R = P I, для которого называется оператором реконструкции.

Теорема 15. Операторы D и R взаимно обратны; они реализуют линейный изоморфизм пространств C и F.

Рассмотрим сплайн-всплесковое сжатие на отрезке. Согласно калибровочным соотношениям (16) справедливо вложение пространств Рассмотрим оператор Pn проектирования пространства S(Xn, A, ) на подn пространство S(Xn, An, ), задаваемый формулой и введем оператор Qn = I Pn, где I — тождественный в S(Xn, A, ) оператор.

Пространство Wn = Qn S(Xn, An, ) называется пространством всплесков, а прямое разложение называется сплайн-всплесковым сжатием пространства S(Xn, A, ). n В соответствии с равенством (24) для u S(Xn, A, ) имеем так что для чисел cj = fj, u получаем Пусть известны коэффициенты cj в разложении элемента u S(Xn, A, ) по элементам базиса j,m, а именно, u = cj j,m.

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

Введем вектор-столбцы an = (am, am+1,..., an2 )T, bn = (bm, bm+1,..., bn1 )T, cn = (cm, cm+1,..., cn1 )T.

Рассмотрим пространство Li, i N, всех числовых последовательностей, ратор из пространства Cn = Ln1 в пространство An = Ln2, определяемый матрицей Qn в нем. Ядро этого оператора представляет собой линейное пространство; обозначим его через Bn = {bn | bn = (bm, bm+1,..., bn1 )T, Qn bn = 0}, т. е. Bn = ker Qn.

Пусть Fn — прямое произведение пространств An и Bn : Fn = An Bn, т. е.

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

Пусть известны коэффициенты ai, i Jm,n2 и bi, i Jm,n1 в разложениях проекций элемента u S(Xn, A, ) на пространства S(Xn, An, ) и Wn :

Найдем формулы для определения коэффициентов cj для представления элемента u в виде следующей суммы u = cj j,m ; упомянутые формулы имеют вид (25) и называются формулами реконструкции.

Оператор Rn : Fn Cn, Rn = PT I, для которого называется оператором реконструкции.

Теорема 16. Операторы Dn и Rn взаимно обратны; они реализуют линейный изоморфизм пространств Cn и Fn.

Рассмотрим сплайн-всплесковое уточнение на интервале. Согласно калибровочным соотношениям (15) справедливо вложение пространств S(X, A, ) S(X, A, ). Используя систему функционалов {fj } для построения оператора проектирования пространства S(X, A, ) на подпространство S(X, A, ) находим следующее представление называемое сплайн-всплесковым уточнением пространства S(X, A, ), W — пространство всплесков, которое натянуто на B -сплайн, соответствующий добавленному (к сетке X) узлу. Согласно калибровочным соотношениям (17) справедливо вложение пространств S(Xn, A, ) S(X n, An, ), откуда находим представление называемое сплайн-всплесковым уточнением пространства S(X n, An, ), W n — пространство всплесков. Для сплайн-всплескового уточнения на интервале и отрезке построены операторы декомпозиции и реконструкции, найдены формулы декомпозиции и реконструкции. Соответствующие коэффициенты в них обозначаются через векторы a = (..., a1, a0, a1,...)T, b = (..., b1, b0, b1,...)T, Далее в данной главе для последовательности вложенных сеток рассматриваются варианты систем вложенных пространств B -сплайнов (телескопические системы пространств), для которых получено разложение в прямую сумму всплесковых пространств, приведены соответствующие формулы декомпозиции и реконструкции для сплайнов порядка m = 0, 1, 2, 3.

В пятой главе рассматриваются вопросы аппроксимации минимальными сплайнами максимальной гладкости. Пусть дана функция u C m+1 (, ). Рассмотрим сплайн где fj, u — некоторые линейные функционалы над пространством C m+1 (, ), которые в этом случае будем называть аппроксимационными.

Введем обозначения e = (0,..., 0, 1)T, Теорема 17. Если u C m+1 (, ), t (xk, xk+1 ), то справедливо представление где символ · означает переменную, по которой вычисляются функционалы fj.

Аппроксимация (28) при t (xk, xk+1 ) обладает свойством точности на функциях u []s | s = 0, 1,..., m, т. е.

Далее в главе приводятся результаты численных экспериментов по аппроксимации сплайнами порядка m = 0, 1, 2, 3. Аппроксимация (28) рассматриваdef лась на отрезке [a, b] для сеток вида Xn = {xj = a + j(b a)/n, j = 0,..., n}, и искалась экспериментальная погрешность приближения E m = max |uh (t)u(t)| на вспомогательной более мелкой сетке. В качестве набора тестовых функций использовались, например, функция Рунге 1+25 t2 и некоторые другие суперпозиции элементарных функций. В качестве порождающих вектор-функций выбирались, например, вектор-функция (t) = (1, sh t, ch t)T и многие другие варианты. Построенные аппроксимации обладают свойством точности на компонентах вектор-функции.

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

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

Рассмотрим сплайн-всплесковое сжатие и уточнение с соответствующими формулами декомпозиции и реконструкции. Для удобства одновременного расdef смотрения упомянутых выше объектов введем единые обозначения a = (..., a1, Q либо Q, соответственно.

Для векторов a, b, c и матриц P, Q справедливы формулы декомпозиции и формулы реконструкции Вектор c называется исходным потоком, вектор a — основным потоком, вектор b — всплесковым потоком.

Рассмотрим два экземпляра введенного ранее пространства L, обозначая их через A и C. Элементами пространства A являются векторы a = (..., a1, a0, a1,...)T, а элементами пространства C являются векторы c = (..., c1, c0, c1,...)T.

Матрицы P и Q будем рассматривать как линейные операторы, действующие из пространства C в пространство A. Упомянутые линейные операторы будем обозначать теми же символами P, Q [C A]. Оператор PT, порождаемый транспонированием матрицы P, будем рассматривать как оператор, действующий из пространства A в пространство C : PT [A C]. Пространство C называется пространством исходных потоков.

Рассмотрим формулы декомпозиции (29) и реконструкции (30) при a A, c, b C. Обозначим через IA и IC тождественные операторы в пространствах A и C соответственно. Ввиду равенств (21) справедливо соотношение Q PT = IA и, следовательно, верно равенство Q b = 0. Таким образом, вектор b ker Q.

Рассмотрим подпространство S пространства C, определяемое равенством Теорема 18. Оператор PT, рассматриваемый в паре пространств A и S, PT : [A S], является изоморфизмом этих пространств. Обратным оператором служит сужение оператора Q на подпространство S :

Теорема 19. Пространство C может быть представлено в виде прямой суммы Оператор R = PT Q проектирует пространство C на подпространство S, а оператор IC R проектирует пространство C на подпространство B.

Теорема 20. Если S и B — гильбертовы пространства со скалярными произведениями (s1, s2 )S и (b1, b2 )B соответственно, то относительно скалярного произведения в пространстве C, вводимого для любых элементов c1, c2 C по формуле линейный оператор PT [C C], задаваемый соотношением является псевдообратным оператором.

Норму, порождаемую скалярным произведением в пространстве C, обознаdef чим через c = (c, c)C, c C.

Следствие 4. Уравнение рассматриваемое при фиксированном c0 C относительно a A, разрешимо при c0 B, а при c0 B это уравнение не имеет решения. Вектор a = PT c0 может рассматриваться как «наилучшее обобщенное решение»

уравнения в том смысле, что причем равенство достигается лишь при a = a.

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

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

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

Для i, j Z введем обозначения Пусть pj — число ненулевых элементов в j-й строке матрицы PT, а qi — число ненулевых элементов в i-й строке матрицы Q. Ясно, что для чисел pj и qi справедливы равенства pj = |P (j) |, qi = |Q(i) |.

Будем считать, что пространства A и C сужены так, что их элементы имеют конечные нормы a = sup |[a]i |, c = sup |[c]j | соответственно.

Теорема 22. При декомпозиции для векторов a и b справедливы оценки а при реконструкции верно неравенство Далее в главе даны способы распараллеливания всплесковых разложений.

Приведены параллельные формы для вычисления формул декомпозиции и реконструкции. Представлены результаты применения алгоритмов декомпозиции и реконструкции к сжатию и восстановлению модельных числовых потоков, в том числе и изображений. Приводятся результаты численного сравнения сплайнвсплескового алгоритма сжатия (на неравномерной сетке) и алгоритмов сжатия, использующих различные известные всплески (на равномерной сетке). Упомянутые методы сжатия применялись к набору одномерных сигналов, генерируемых модельными функциями u(t). В качестве критерия сравнения методов была взята оценка погрешности приближения E = max |uc (t) u(t)|, где uc — значеt[a,b] ния сжатой функции в узлах исходной сетки. Для сжатия сигнала известными всплесками использовался пакет Wavelet Toolbox системы MATLAB, в котором, в частности, реализован всплеск Хаара (haar), всплески Добеши (db2–db5), коифлеты (coif1–coif3), биортогональные всплески (bior2.2, bior3.1–bior3.5). Например, для сигнала, генерируемого модельной функцией u(t) = sin(30 t) на отрезке [a, b] = [0, 1] c сеткой Xn, n = 1000, перечисленные всплески заметно уступают сплайн-всплесковому сжатию B -сплайнами, (t) = (1, t, t2 )T, при сжатии данного сигнала в 20 и, особенно, в 100 раз. Сплайн-всплесковый метод сжатия на неравномерной секте также показал лучшие результаты при большом сжатии (в 100 и более раз) и во всех других рассмотренных случаях.

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

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

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

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

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

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

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

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

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

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

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

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

(Vestnik St. Petersburg University: Mathematics, 40 (2007), no. 1, 85–88.) [2] Макаров А. А. О распараллеливании вэйвлетных методов сжатия информации // Вестн. С.-Петерб. ун-та. Сер. 10. 2007. Вып. 4. С. 45–49.

[3] Макаров А. А. Нормализованные тригонометрические сплайны лагранжева типа // Вестн. С.-Петерб. ун-та. Сер. 1. 2008. Вып. 3. С. 81–87.

(Vestnik St. Petersburg University: Mathematics, 41 (2008), no. 3, 266–272.) [4] Макаров А. А. О вэйвлетном разложении пространств сплайнов первого порядка // Проблемы матем. анализа. 2008. Вып. 38. С. 47–60. (J. Math.

Sci. 156 (2009), no. 4, 617—631.) [5] Макаров А. А. Моделирование калибровочных соотношений для неполиномиальных сплайнов // Вычисл. технологии. 2008. Т. 13. Спец. вып. 4.

[6] Макаров А. А. Один вариант сплайн-вэйвлетного разложения пространств B-сплайнов // Вестн. С.-Петерб. ун-та. Сер. 10. 2009. Вып. 2. С. 59–71.

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

С. 39–52. (J. Math. Sci. 178 (2011), no. 6, 605–621.) [9] Макаров А. А. Матрицы реконструкции и декомпозиции для линейных сплайнов // Труды СПИИРАН. 2011. Вып. 18. С. 215–236.

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

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

[12] Демьянович Ю. К., Макаров А. А. Калибровочные соотношения для неполиномиальных сплайнов // Проблемы матем. анализа. 2006. Вып. 34.

С. 39–54. (J. Math. Sci. 142 (2007), no. 1, 1769–1787.) [13] Демьянович Ю. К., Косогоров О. М., Макаров А. А. Возможности распараллеливания вэйвлетно-сплайнового сжатия на неравномерной сетке // Высокопроизводительные параллельные вычисления на кластерных системах. Материалы Седьмой Международной конференции-семинара. — Н. Новгород: Изд-во ННГУ, 2007. С. 381–384.

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

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

Изд-во С.-Петерб. ун-та, 2008. С. 82–98.

[16] Косогоров О. М., Макаров А. А. О сплайн-вэйвлетном сжатии на неравномерной сетке // Питання оптимизацii обчислень (ПОО-XXXV): Працi мiжнародного симпозiуму, смт. Кацивелi, Украiна, 24–29 вересня 2009 р.

— Киiв: Iнститут кiбернетики iменi В. М. Глушкова, 2009. Т. 1. С. 340–345.

[17] Kosogorov O. M., Makarov A. A. Spline wavelet decomposition and parallel compression // Zbornik radova konferencije MIT 2009. University of Pristina.

Beograd, 2010. P. 202–205.

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

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

[20] Макаров А. А. Сплайн-вейвлетное сжатие на отрезке // Семинар «DHA & CAGD». Избранные доклады. 12 ноября 2011 г.

(http://dha.spb.ru/reps11.shtml#1112)