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

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

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

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

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

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

УДК 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), заданной на ин