Сплайн-всплески и их реализация

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

И. Г. Бурова, Ю. К. Демьянович,
Т. О. Евдокимова

СПЛАЙН-ВСПЛЕСКИ
И ИХ РЕАЛИЗАЦИЯ

Второе издание, стереотипное

ИЗДАТЕЛЬСТВО САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА

УДК 519.6
ББК 22.19
Б91

Р е ц е н з е н т ы:
д-р
физ.-мат.
наук, проф.
С. И. Репин
(С.-Петерб.
отд.
мат.
ин-та
им. В. А. Стеклова), д-р техн. наук, проф. В. А. Ходаковский (Петерб. гос.
ун-т путей сообщения Императора Александра I)

Б91
Бурова И. Г., Демьянович Ю. К., Евдокимова Т. О.
Сплайн-всплески и их реализация. 2-e изд., стер. — СПб.: Изд-во
С.-Петерб. ун-та, 2018. 414 с.

ISBN 978-5-288-05804-2

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

УДК 519.6

ББК 22.19

При оформлении обложки использованы материалы автора
projin/Shutterstock.com

ISBN 978-5-288-05804-2

©
Санкт-Петербургский
государственный
университет, 2017

©
И. Г. Бурова, Ю. К. Демьянович,
Т. О. Евдокимова, 2017

СОДЕРЖАНИЕ

ВВЕДЕНИЕ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
I. О подходах к обработке информационных потоков . . . . . . . . . . . . . . . . . . . —
II. Особенности всплесковой обработки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
III. Основная идея всплескового (вэйвлетного) разложения . . . . . . . . . . . . 12
IV. Потоки числовой информации, сигналы, сеточные функции . . . . . . . 15
V. Некоторые дополнения и описание структуры книги. . . . . . . . . . . . . . . . 17

1. АППРОКСИМАЦИЯ Bϕ-СПЛАЙНАМИ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .20
1.1. Пространства Bϕ-сплайнов. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .—
1.2. Биортогональная система функционалов. . . . . . . . . . . . . . . . . . . . . . . . . . .22
1.3. Об оценке погрешности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2. УСЛОВИЯ ВЛОЖЕННОСТИ МИНИМАЛЬНЫХ СПЛАЙНОВ
ВТОРОГО ПОРЯДКА . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.1. Предварительные сведения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .—
2.2. Пространство минимальных сплайнов на укрупненной сетке . . . . . . 28

3. БИОРТОГОНАЛЬНАЯ АППРОКСИМАЦИЯ СПЛАЙНАМИ . . . . . . . . . 31
3.1. Предварительные сведения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .—
3.2. Вспомогательные результаты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.3. Квадратичные сплайны и биортогональная система функционалов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.4. Нормализованные квадратичные сплайны. . . . . . . . . . . . . . . . . . . . . . . . . .36
3.5. Остаток биортогональной аппроксимации . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.6. Оценка аппроксимации дважды непрерывно дифференцируемых
функций. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .40
3.7. Некоторые вспомогательные утверждения . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.8. Интегральные представления компонент аппроксимации . . . . . . . . . . 43
3.9. Об оценках продолженного вронскиана w(x, y) . . . . . . . . . . . . . . . . . . . . 44

Содержание

4. БИОРТОГОНАЛЬНЫЕ СИСТЕМЫ И АППРОКСИМАЦИЯ . . . . . . . . . . 50
4.1. Биортогональность заданных функционалов к компонентам
вектор-функции ϕ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . —
4.2. Общий случай (небиортогональная система функционалов) . . . . . . . 52
4.3. О вариантах реализации системы функционалов, биортогональной
к заданной системе функций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

5. ЕДИНСТВЕННОСТЬ ПРОСТРАНСТВ ГЛАДКИХ СПЛАЙНОВ
И КАЛИБРОВОЧНЫЕ СООТНОШЕНИЯ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5.1. Пространства (X, A, ϕ)-сплайнов порядка m . . . . . . . . . . . . . . . . . . . . . . . 59
5.2. Непрерывность и непрерывная дифференцируемость
минимальных сплайнов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
5.3. Bϕ-сплайны порядка m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
5.4. Калибровочные соотношения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

6. О ПОЛОЖИТЕЛЬНОСТИ МИНИМАЛЬНЫХ
КООРДИНАТНЫХ СПЛАЙНОВ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
6.1. Предварительные сведения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .—
6.2. Общая схема построений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
6.3. Другое представление координатных сплайнов. . . . . . . . . . . . . . . . . . . . .77
6.4. Вспомогательные утверждения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
6.5. Полнота и позитивность цепочки векторов . . . . . . . . . . . . . . . . . . . . . . . . . 85
6.6. Критерий положительности координатных сплайнов. . . . . . . . . . . . . . .90
6.7. Экспоненциальные непрерывно дифференцируемые сплайны. . . . . .93
6.8. Гиперболические непрерывно дифференцируемые сплайны. . . . . . . .97
6.9. Дробно-рациональные непрерывно дифференцируемые сплайны . . 99

7. АППРОКСИМАЦИЯ СПЛАЙНАМИ ЭРМИТОВА ТИПА . . . . . . . . . . . . 104
7.1. О представлении остатка аппроксимации . . . . . . . . . . . . . . . . . . . . . . . . . . . —
7.2. Сплайны эрмитова типа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
7.3. Некоторые вспомогательные утверждения . . . . . . . . . . . . . . . . . . . . . . . . 107
7.4. Оценка погрешности аппроксимации . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110

8. СПЛАЙН-ВЭЙВЛЕТЫ ПРИ ОДНОКРАТНОМ ЛОКАЛЬНОМ
УКРУПНЕНИИ СЕТКИ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
8.1. Предварительные сведения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .—
8.2. Матрица вложения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
8.3. Матрица продолжения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .121
8.4. Вэйвлетное разложение. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .126

Содержание
5

8.5. Интерференция при локальном укрупнении сетки . . . . . . . . . . . . . . . . 131
8.6. Об аппроксимационных свойствах вэйвлетного потока. . . . . . . . . . . .132

9. СПЛАЙН-ВСПЛЕСКИ ВТОРОГО ПОРЯДКА . . . . . . . . . . . . . . . . . . . . . . . . 134
9.1. Предварительные замечания . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . —
9.2. Вспомогательные результаты. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .135
9.3. Пространство Bϕ-сплайнов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
9.4. Пространство Bϕ-сплайнов на укрупненной сетке. . . . . . . . . . . . . . . . .141
9.5. Калибровочные соотношения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
9.6. Всплесковое разложение. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .146

10. СПЛАЙН-ВСПЛЕСКОВАЯ ДЕКОМПОЗИЦИЯ НА ОТРЕЗКЕ . . . . . 150
10.1. Сплайны на отрезке. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .—
10.2. Матрица продолжения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
10.3. Сплайн-всплесковое представление пространства S∗
N . . . . . . . . . . . . 155
10.4. Вариант сплайн-всплескового разложения . . . . . . . . . . . . . . . . . . . . . . . 157
10.5. Изменение порядка элементарных операций . . . . . . . . . . . . . . . . . . . . . 162

11. НЕГЛАДКИЕ СПЛАЙН-ВЭЙВЛЕТНЫЕ РАЗЛОЖЕНИЯ
И ИХ СВОЙСТВА. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .168
11.1. Предварительные обозначения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .—
11.2. Биортогональная система функционалов . . . . . . . . . . . . . . . . . . . . . . . . 170
11.3. Укрупнение сетки и калибровочные соотношения. . . . . . . . . . . . . . . .177
11.4. Некоторые свойства биортогональной системы . . . . . . . . . . . . . . . . . . 181
11.5. Вэйвлетное разложение. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .184
11.6. Операторы декомпозиции и реконструкции . . . . . . . . . . . . . . . . . . . . . . 187
11.7. Коммутативность операторов декомпозиции . . . . . . . . . . . . . . . . . . . . . 190

12. СТРУКТУРА ОПЕРАТОРОВ ГНЕЗДОВОГО
СПЛАЙН-ВЭЙВЛЕТНОГО РАЗЛОЖЕНИЯ . . . . . . . . . . . . . . . . . . . . . . . . . 197
12.1. Предварительные сведения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . —
12.2. Удаление совокупности последовательных узлов
(удаление гнезда) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
12.3. Вложенность пространств . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
12.4. Свойства биортогональной системы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
12.5. Реконструкция и декомпозиция . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
12.6. О представлениях вэйвлетного разложения . . . . . . . . . . . . . . . . . . . . . . 210
12.7. Матричное представление оператора декомпозиции . . . . . . . . . . . . . 212
12.8. Сплайн-вэйвлетное разложение пространств
непрерывных сплайнов. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .214

Содержание

12.9. Сплайн-вэйвлетное разложение пространств непрерывных
сплайнов первой степени на равномерной сетке . . . . . . . . . . . . . . . . . 215
12.10. О совокупностях гнезд . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216
12.11. Заключительные замечания . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219

13. ИНТЕРФЕРЕНЦИЯ В СПЛАЙН-ВЭЙВЛЕТНОМ
РАЗЛОЖЕНИИ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220
13.1. Предварительные сведения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . —
13.2. Матрица вложения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
13.3. Матрица продолжения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224
13.4. Об односторонней обратимости матриц QN{Γ} и PT
N{Γ} . . . . . . . . . .227
13.5. Сплайн-вэйвлетное разложение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
13.6. Интерференция в вэйвлетном потоке. . . . . . . . . . . . . . . . . . . . . . . . . . . . .229
13.7. Об аппроксимационных свойствах вэйвлетов. . . . . . . . . . . . . . . . . . . . .233

14. ВЭЙВЛЕТНОЕ РАЗЛОЖЕНИЕ
НА ГРЕБЕНЧАТОЙ СТРУКТУРЕ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
14.1. Предварительные сведения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . —
14.2. Матрица вложения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240
14.3. Матрица продолжения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246
14.4. Об односторонней обратимости матриц Q и PT . . . . . . . . . . . . . . . . . 251
14.5. Вэйвлетное разложение. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .253
14.6. Основной и вэйвлетный потоки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254
14.7. Интерференция на гребенчатой структуре . . . . . . . . . . . . . . . . . . . . . . . 260
14.8. Об аппроксимационных свойствах вэйвлетного потока . . . . . . . . . . 261

15. ОРТОГОНАЛЬНЫЙ БАЗИС ВСПЛЕСКОВЫХ ПОТОКОВ. . . . . . . . .263
15.1. Предварительные сведения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .264
15.1.1. Пространство сплайнов первого порядка . . . . . . . . . . . . . . . . . . . —
15.1.2. Непрерывные сплайны первой степени. . . . . . . . . . . . . . . . . . . .265
15.2. Двухинтервальная гребенчатая структура. . . . . . . . . . . . . . . . . . . . . . . . .—
15.3. Матрица вложения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267
15.3.1. Пространство CX и матрица вложения . . . . . . . . . . . . . . . . . . . . . —
15.3.2. Матрица вложения для сплайнов первой степени. . . . . . . . .269
15.4. Матрица продолжения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270
15.4.1. Матрица продолжения для сплайновых пространств
первого порядка. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .—
15.4.2. Матрица продолжения для сплайнов первой степени. . . . . . .—
15.5. Всплесковое разложение потоков. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .271
15.5.1. Оператор проектирования . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . —

Содержание
7

15.5.2. Ортогональный базис пространства всплесковых потоков
первого порядка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272
15.5.3. Ортогональный базис в случае всплесковых потоков
первой степени . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274
15.6. Базис всплесков . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275
15.6.1. Представления базисных всплесков. . . . . . . . . . . . . . . . . . . . . . . . .—
15.6.2. Базис всплесков первой степени. . . . . . . . . . . . . . . . . . . . . . . . . . .277
15.6.3. О связи с понятием интерференции . . . . . . . . . . . . . . . . . . . . . . . . —
15.7. Вычисление основного потока . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278
15.7.1. Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . —
15.7.2. Последовательные вычисления основного потока
в сплайн-всплесковом разложении первого порядка. . . . . . .279
15.7.3. Последовательные вычисления основного потока
в сплайн-всплесковом разложении первой степени . . . . . . . . 280
15.7.4. Параллельные вычисления основного потока
в сплайн-всплесковом разложении первого порядка. . . . . . .281
15.7.5. Упрощение ситуации при параллельном вычислении
основного потока в сплайн-всплесковом разложении
первой степени . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283
15.8. Вычисление всплескового потока. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .284
15.8.1. Применяемые формулы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . —
15.8.2. Последовательные вычисления всплескового потока
в сплайн-всплесковом разложении первого порядка. . . . . . .285
15.8.3. Параллельные вычисления всплескового потока . . . . . . . . . . 287

16. АДАПТИВНЫЕ СВОЙСТВА СПЛАЙН-ВСПЛЕСКОВОЙ
АППРОКСИМАЦИИ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290
16.1. Об основных результатах данного раздела . . . . . . . . . . . . . . . . . . . . . . . 291
16.2. Некоторые вспомогательные утверждения . . . . . . . . . . . . . . . . . . . . . . . 292
16.2.1. Сетка адаптивного типа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . —
16.2.2. Равномерная сетка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295
16.2.3. О числе узлов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296
16.3. Об оценках аппроксимации интерполяционными
кусочно-линейными сплайнами. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .297
16.4. О числе узлов при аппроксимации
кусочно-линейными сплайнами. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .299
16.5. О числе узлов равномерной сетки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300
16.6. О численной устойчивости сетки адаптивного типа. . . . . . . . . . . . . .303
16.7. Координатные сплайны первой степени . . . . . . . . . . . . . . . . . . . . . . . . . . 305

Содержание

16.8. Биортогональная система функционалов . . . . . . . . . . . . . . . . . . . . . . . . 306
16.9. Укрупнение сетки и калибровочные соотношения . . . . . . . . . . . . . . . . . —
16.10. Вэйвлетное разложение. Формулы декомпозиции . . . . . . . . . . . . . . . 309

17. АДАПТИВНАЯ СПЛАЙН-ВСПЛЕСКОВАЯ ОБРАБОТКА
ДИСКРЕТНОГО ПОТОКА . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314
17.1. Общая характеристика результатов данного раздела. . . . . . . . . . . . . .—
17.2. Сетка адаптивного типа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316
17.3. О построении сетки адаптивного типа . . . . . . . . . . . . . . . . . . . . . . . . . . . 318
17.4. Псевдоравномерная сетка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320
17.5. Относительное количество узлов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321
17.6. Предельные соотношения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322
17.7. Аппроксимация дискретного потока. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .323
17.8. Еще один вариант аппроксимации дискретного потока . . . . . . . . . . 326
17.9. О числе узлов сетки адаптивного типа. . . . . . . . . . . . . . . . . . . . . . . . . . . 328
17.10. О числе узлов псевдоравномерной сетки . . . . . . . . . . . . . . . . . . . . . . . . 330
17.11. Сравнительная характеристика числа узлов
при одинаковой аппроксимации. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .331
17.12. Укрупнение сетки и калибровочные соотношения . . . . . . . . . . . . . . 332
17.13. Сплайн-вэйвлетное разложение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 336

18. РЕАЛИЗАЦИЯ СПЛАЙН-ВСПЛЕСКОВОГО РАЗЛОЖЕНИЯ
ПЕРВОГО ПОРЯДКА. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .341
18.1. О содержании и структуре данного раздела . . . . . . . . . . . . . . . . . . . . . 342
18.2. Первоначальные обозначения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345
18.3. Укрупнение сетки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346
18.4. Калибровочные соотношения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .348
18.5. Матрица сужения и ее свойства . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351
18.6. Дискретное сплайн-всплесковое разложение . . . . . . . . . . . . . . . . . . . . . 354
18.7. Матрица продолжения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356
18.8. Потоки. Формулы декомпозиции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357
18.9. Иллюстративный пример всплескового разложения . . . . . . . . . . . . . 361
18.10. Континуальный образ дискретного всплескового разложения . . 365
18.11. Вычисление всплескового разложения . . . . . . . . . . . . . . . . . . . . . . . . . . 367

19. СПЛАЙН-ВСПЛЕСКОВОЕ УКРУПНЕНИЕ АППРОКСИМАЦИЙ
КУРАНТОВА ТИПА . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373
19.1. Некоторые обозначения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374
19.2. Вспомогательные утверждения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .375
19.3. Непрерывность функций курантова типа . . . . . . . . . . . . . . . . . . . . . . . . 380

Содержание
9

19.4. Укрупнение триангуляции. Калибровочные соотношения. . . . . . . .381
19.5. Вложенность пространств и всплесковое разложение . . . . . . . . . . . . 384
19.6. О матрицах всплескового разложения
пространств аппроксимаций курантова типа . . . . . . . . . . . . . . . . . . . . . 385
19.7. Триангуляция, допускающая локальное укрупнение . . . . . . . . . . . . . 387
19.8. Структура барицентрических звезд исходной триангуляции. . . . . 390
19.9. Структура барицентрических звезд локально укрупненной
триангуляции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391
19.10. Калибровочные соотношения для функций Куранта . . . . . . . . . . . 392
19.11. Биортогональная система и ее значения на базисных функциях
объемлющего пространства . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395
19.12. Общая структура всплескового разложения . . . . . . . . . . . . . . . . . . . . 397
19.13. Всплесковое разложение при локальном укрупнении
триангуляции. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .399
19.14. Структура локального укрупнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .400

ЗАКЛЮЧЕНИЕ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .404
1. Методы сплайт-всплесковых разложений . . . . . . . . . . . . . . . . . . . . . . . . . . .405
2. Нерешенные задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . —
3. Нерешенные проблемы и подходы к их решению . . . . . . . . . . . . . . . . . . .406

Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408

ВВЕДЕНИЕ

I. О подходах к обработке информационных потоков

Исследования в области обработки больших числовых массивов информации восходят к трем источникам, возникшим независимо друг от друга:
к классической теории сплайнов, к методу конечных элементов и к теории
вэйвлетов. В соответствии с этим можно выделить по крайней мере три направления развития теории обработки упомянутых массивов. Первое направление берет свое начало от работ Шонберга [110, 111]; здесь исходным моментом является решение какой-либо задачи интерполяции (задачи Лагранжа,
Эрмита или Эрмита-Биркгофа) в классе функций с «кусочными» свойствами и с определенной гладкостью в узлах рассматриваемой сетки (см. [10,
40–41, 44, 47–48, 52, 54, 56–57, 69, 98–102, 104–105, 110–111]). Заметим, что
если исходный массив числовой информации задан как сеточная функция
на мелкой сетке, то замена этой сеточной функции на результат решения
интерполяционной задачи для крупной сетки (являющейся подмножеством
мелкой сетки) может рассматриваться как сжатие исходного массива числовой информации. Аппроксимационные свойства и вычислительная простота
получаемых сплайнов всякий раз исследуются дополнительно. Сюда относятся современные исследования по обобщенным сплайнам (см., например, [10]),
так называемым ECT-B-сплайнам; в этих работах для построения сплайнов
на сеточных промежутках используются различные ECT-системы, которые
при определенных условиях удается гладко «склеить» в узлах.
Второе направление опирается на аппроксимационные свойства рассматриваемых функций, где определение базисных функций связано с решением
аппроксимационных соотношений, рассматриваемых как система уравнений
(эти исследования появились в связи с теорией метода конечных элементов, см. [1–9, 25, 27, 33–34, 59–68, 73–75, 79, 83, 88–92]); при таком подходе интерполяционные свойства и алгоритмы минимизации вычислительной
сложности (вложенность пространств и вэйвлетное представление цепочки
вложенных пространств) приходится устанавливать дополнительно. Выбор
порождающей m + 1-компонентной вектор-функции ϕ(t), заданной на ин

Введение
11

тервале (α, β), определяет семейства конечномерных пространств на элементарных сеточных интервалах рассматриваемой (конечной или бесконечной)
сетки X = {xj}, X ⊂ (α, β), а выбор цепочки A векторов со свойством полноты приводит к пространству (X, A, ϕ)-сплайнов. Условия гладкости эквивалентны определенным алгебраическим соотношениям между значениями
ϕ(t) (и ее производных) в узлах сетки и векторами цепочки A. Требование
максимальной гладкости сплайнов (при выбранной вектор-функции ϕ(t) с отличным от нуля вронскианом из ее компонент) однозначно (с точностью до
постоянных отличных от нуля множителей) определяет цепочку A; при этом
однозначно определяется также пространство (X, A, ϕ)-сплайнов, которое в
этом случае называется пространством Bϕ-сплайнов (см. [11–24, 26, 28–32,
35–38, 70–72, 76–82, 84–87, 93–97]).
Третье направление — теория вэйвлетов — в основу кладет вычислительную простоту, отражением чего является кратно-масштабное уравнение (см.
[45–46, 50–51, 55, 58, 103]); исследование последнего приводит в первую очередь ко вложенности получаемых пространств и к вэйвлетному представлению соответствующей цепочки вложенных пространств (это ведет к минимизации вычислительной сложности); остальные из перечисленных выше
свойств с б´ольшим или меньшим успехом исследуются дополнительно (см.,
например, [46]).

II. Особенности всплесковой обработки

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

Введение

быть отброшен. Конечно, вопрос о том, какая информация является основной, какая — уточняющей, а какая — несущественной, выходит за рамки математических исследований и должен решаться в каждом отдельном случае
специалистом предметной области.
Роль теории вэйвлетов (всплесков) состоит в том, что она дает предметному специалисту достаточно широкий арсенал средств, из которых он может
выбрать то средство, которое ему подходит для обработки (для разложения
на составляющие) интересующего его потока информации. Такими средствами в теории вэйвлетов являются наборы вложенных (основных) пространств
функций и их представлений в виде прямой (а иногда и ортогональной) суммы вэйвлетных пространств. Весьма важными являются базисы основных
пространств, а также базисы вэйвлетов (всплесков); построению и изучению
свойств таких базисов посвящено много работ.
Обращаясь к эффективным способам сжатия неоднородных потоков информации (имеющих сингулярности или быстро меняющиеся характеристики), следует отметить важность использования неравнометной сетки. В связи с этой проблемой отметим работы Добеши, Свелденса, И. В. Оселедса,
Е. Е. Тыртышникова [106–108].

III. Основная идея всплескового (вэйвлетного) разложения

Для более наглядной иллюстрации идеи вэйвлет-преобразования представим себе, что рассматриваемый числовой поток кодирует некоторое изображение, выводимое на экран компьютера (или цифрового телевизора). Предположим, что экран представляет собой прямоугольную матрицу из большого числа пикселей — маленьких прямоугольников, нанесенных на прозрачную
поверхность (стекло), которые светятся под воздействием попадающих на них
электронов, причем для такого свечения имеется фиксированное число градаций яркости. Для простоты рассматриваем лишь одноцветные изображения (черно-белый экран). Обычно пиксели перенумерованы последовательно
по строкам, которые предварительно выстроены одна за другой в прямую
линию; таким образом, пиксели приобретают номера 0, 1, 2, . . . , N − 1, где
N = M × K, где M число строк рассматриваемой матрицы, а K — число ее
столбцов. Для определенности будем считать N четным; пусть N = 2L, где
L — натуральное число. Каждому пикселю предписывается определенная яркость, выражаемая некоторым числом; обозначим это число для j-го пикселя
через cj. Таким образом, кодировка изображения производится с помощью
числового потока

c0, c1, c2, c3, c4, c5, c6, c7, . . . , c2L−1.
(III.1)

Введение
13

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

c1, c3, c5,
c7, . . . , c2L−1.
(III.2)

Такое преобразование называется прореживанием исходного числового потока (английский термин upsampling — разрежение или разрежающая выборка). Вместо потока (III.1) передают в два раза более короткий поток (III.2);
приемное устройство расширяет полученный числовой поток (III.2) дублированием принятых значений так, чтобы в результате на местах с четным и со
следующим нечетным номером находились одинаковые числа. В результате
на экране воспроизводится изображение, полученное с помощью числового
потока вида
c1, c1, c3, c3, c5, c5, c7, . . . , c2L−1, c2L−1.
(III.3)

Тем самым «восстановление» (III.3) исходного потока (III.1) производится
с погрешностью, причем информация теряется необратимым образом (т. е.
без передачи дополнительной информации приемное устройство, вообще говоря, не в состоянии восстановить поток (III.1)). Такой прием (английский
эквивалент downsampling — сгущение) оправдан, если полученное изображение мало отличается от исходного.
Недостатки описанного подхода состоят в следующем: 1) он применим
лишь к достаточно медленно менящемуся потоку; 2) отсутствует учет характеристик числового потока (в некоторых частях числовой поток может меняться очень медленно, и можно было бы выбрасывать много чисел подряд, а
в других частях при быстром изменении потока любые выбрасывания чисел
могут существенно испортить передаваемое изображение); 3) нет средств для
уточнения передаваемого потока.
Идея вэйвлетного подхода иллюстрируется следующим образом. Из числового потока (III.1) формируются два числовых потока:

aj = (c2j + c2j+1)/2,
bj = (c2j − c2j+1)/2,
где j = 0, 1, . . . , L − 1.
(III.4)

Нетрудно видеть, что

c2j = aj + bj,
c2j+1 = aj − bj,
j = 0, 1, . . . , L − 1.
(III.5)

Введение

Таким образом, если поток (III.1) заменить двумя потоками (III.4), то после
их передачи можно восстановить исходный поток (III.1), используя формулы
(III.5).
Возникает вопрос, в чем же польза от замены потока (III.1) на два потока
(III.4), если общее количество чисел в потоках (III.4) совпадает с количеством
чисел в (III.1). Для ответа на этот вопрос заметим, что если соседние числа в
(III.1) близки, то второй из потоков в (III.4) состоит из чисел, близких к нулю, так что может оказаться, что второй поток вообще не нужен и его можно
отбросить. Однако если некоторые фрагменты первого потока из (III.4) не
дают достаточной точности, то можно использовать соответствующие фрагменты (с теми же диапазонами индексов) второго потока и произвести расчеты по формулам (III.5); это приведет к точному восстановлению исходного
потока (III.1) на соответствующих участках (подобная технология передачи
используется, в частности, при передаче изображений в Интернете: сначала
появляются основные контуры изображения, позволяющие оценить его содержание и прервать передачу, если в ней нет необходимости, и лишь затем
происходит уточнение и окончательное завершение передачи изображения).
Поток чисел
a0, a1, a2, a3, a4, a5, a6, . . . , aL−1
(III.6)

называют основным, а поток чисел

b0, b1, b2, b3, b4, b5, b6, . . . , bL−1
(III.7)

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

Введение
15

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

IV. Потоки числовой информации, сигналы, сеточные функции

Числовой информационный поток часто появляется в результате обработки параметра какого-либо физического процесса, причем этот параметр
рассматривается как функция времени; такая обработка называется дискретизацией или оцифровкой. Простейший способ оцифровки — измерение значений упомянутого параметра в отдельные моменты времени. Эти моменты
времени образуют дискретное множество чисел, обычно называемое сеткой на
числовой оси (точки этого множества называются узлами сетки). Таким образом, каждому рассматриваемому моменту времени сопоставляется число —
значение этого параметра. Такое сопоставление называют цифровым сигналом или сеточной функцией.
Итак, пусть упомянутый выше физический параметр представлен функцией u(t), заданной на интервале (α, β) вещественной оси; дальше эту функцию называем первоначальной. Как сказано выше, для компьютерной обработки вводится сеточная функция v(t), определяемая с помощью значений
первоначальной функции (и, возможно, ее производных) в узлах некоторой
сетки (эту сеточную функцию и сетку назовем исходными). Использование
исходной сеточной функции позволяет построить приближение к первоначальной функции с помощью того или иного аппарата аппроксимации или
интерполяции.
Выбор способа уменьшения числового потока находится целиком в руках предметного специалиста (т. е. специалиста в той предметной области,
где приходится иметь дело с числовыми потоками): именно предметный специалист должен решить, какая информация настолько несущественна, что
ею можно пренебречь. В некоторых областях знаний для такого заключения
необходим переход к частотному представлению информации (в виде суммы
гармоник — синусов или косинусов с соответствующими коэффициентами);
такой переход, например, часто делают при обработке электронного кода видеоинформации. Для этого перехода используют преобразование Фурье или
ряд Фурье (или их дискретные аналоги), а интересующие предметного специалиста частоты выделяют с помощью так называемой оконной функции g(x);
по существу, g(x) — срезающая функция (т. е. функция, близкая к константе
на интересующем диапазоне частот и равная нулю вне этого диапазона), так

Введение

что нужные частоты выделяются умножением частотного представления на
эту функцию (иногда с дополнительным сдвигом аргумента).
Линейное пространство приближений (будем называть его аналогично
предыдущему исходным пространством) затем представляют в виде прямой
суммы пространств, одно из которых называют основным, а второе — вэйвлетным. Часто основное пространство связывают с сеткой, получающейся
выбрасыванием некоторой совокупности узлов из исходной сетки, а подпространство вэйвлетов определяют операцией проектирования исходного пространства на основное. Таким образом, порождается разложение упомянутого приближения на основную и вэйвлетную составляющие. Центральными
здесь оказываются два момента: вложенность основного пространства в исходное и задание операции проектирования исходного пространства на основное. Представления элементов этого разложения в базисах рассматриваемых
пространств порождают соответствующие соотношения между коэффициентами этих представлений. Соотношения, позволяющие перейти от коэффициентов базиса исходного пространства к коэффициентам базисов основного
и вэйвлетного пространств, называются формулами декомпозиции, а соотношения, дающие обратный переход, — формулами реконструкции.
Каждое из упомянутых выше подпространств иногда также разлагают
в прямую сумму некоторых подпространств и, возможно, продолжают этот
процесс дальше; разложения подобного рода, как было отмечено ранее, называются вэйвлет-пакетами.
Важнейшими вопросами, которые волнуют исследователей, являются вычислительная сложность (объем используемых ресурсов вычислительной системы: памяти, каналов передачи результатов, времени счета), свойства гладкости и устойчивости решения интересующих задач, аппроксимационные и
интерполяционные свойства, а также ряд других свойств (компактность носителя базисных функций, скорость их убывания на бесконечности — в случае
некомпактного носителя и т. д.)
В случае когда (α, β) = R1, а сетка — равномерная, удается применить
мощный аппарат гармонического анализа (в пространстве функций L2(R1)
и в пространстве последовательностей l2); этому случаю посвящено большое
количество исследований (см., например, [46, 55] и имеющуюся там библиографию). Для цифровых потоков с резко меняющимися характеристиками
(со сменой плавного поведения на скачкообразное и наоборот) весьма важно
использовать неравномерную сетку, приспосабливаемую к обрабатываемому
потоку. В случае неравномерной сетки и для случая, когда (α, β) не совпадает с вещественной осью, работ немного (см. [58, 103]); непосредственное
применение гармонического анализа в этих случаях затруднительно.

Введение
17

V. Некоторые дополнения и описание структуры книги

Новый подход к построению теории всплесков (вэйвлетов), развиваемый
с 2000 года, сначала нашел свое отражение в небольшой монографии
Ю. К. Демьяновича [12]. Дальнейшие результаты в этом направлении содержатся в монографии [38].
Данная монография в основном содержит результаты исследований авторов начиная с 2013 года и в определенном смысле является продолжением
предыдущих работ. Сразу же отметим, что тем не менее изложение не опирается на предыдущие результаты; более того, многие из разделов содержат
удобное для читателей повторение обозначений и необходимых для понимания сведений, так что могут читаться самостоятельно.
Дадим краткое описание разделов.
Первый раздел посвящен представлению остатка аппроксимации Bϕсплайнами первого порядка. Найдены константы в оценках погрешности аппроксимации как самих функций, так и их производных. Упомянутые оценки
точны на компонентах порождающей вектор-функции ϕ(t).
Во втором разделе рассматриваются условия вложенности минимальных
Bϕ-сплайнов второго порядка.
В третьем разделе установлены двусторонние границы биортогональной
аппроксимации
дважды
непрерывно
дифференцируемых
функций
Bϕсплайнами второго порядка. Получено интегральное представление остатка
биортогональной аппроксимации квадратичными сплайнами. На основе этих
результатов найдены оценки погрешности в некоторых задачах аппроксимации и интерполяции лагранжева типа. Упомянутые оценки достигаются в
полиномиальном случае.
Четвертый раздел содержит другие подходы к аппроксимации, в частности рассмотрена биортогональная аппроксимация и представлены некоторые
способы построения биортогональных систем функционалов.
В пятом разделе установлены необходимые и достаточные условия существования и гладкости пространств (вообще говоря, неполиномиальных)
сплайнов и доказано, что во множестве таких пространств порядка m существует единственное (при фиксированной сетке) пространство класса Cm−1

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