Вопросы теории и вычислительные применения сплайнов и вейвлетов тема диссертации и автореферата по ВАК РФ 01.01.07, доктор физико-математических наук Певный, Александр Борисович

• Певный, Александр Борисович
• доктор физико-математических наук
• 2002

Оглавление диссертации доктор физико-математических наук Певный, Александр Борисович

Введение

Глава 1. Дискретные непериодические сплайны.

§ 1. Дискретные В-сплайны

§ 2. Дискретные сплайны и интерполяция по равноотстоящим узлам.

§ 3. ТВ-сплайны и двойственные к ним сплайны.б'

§ 4. Основы сплайн-вейвлетного анализа.

§ 5. Декомпозиция и реконструкция сигналов.

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

§ 1. Вспомогательные сведения о дискретных сплайнах.9'

§ 2. Лифтинговый алгоритм декомпозиции и реконструкции сигналов.

§ 3. Рекурсивная реализация лифтингового алгоритма.

§ 4. Вычисление вейвлетов ф1 и <р

§ 5. Многоуровневое вейвлетное преобразование.

§ 6. Ортогональность сдвигов ф1 и <рг

§ 7. Вейвлетное преобразование Баттерворта для конечных сигналов

§ 8. Тензорное произведение базисов.

§ 9. Вейвлетное преобразование Баттерворта для изображений.

Глава 3. Дискретные периодические сплайны: сверточная природа и приложения.1с

§ 1. Рекуррентное определение дискретных периодических В-сплайнов.

§ 2. ДПФ и интерполяция дискретными сплайнами.

§ 3. Некоторые вспомогательные соотношения

§ 4. Решение задачи сглаживания дискретных данных

§ 5. Решение задачи о бесконечной цилиндрической оболочке

§ 6. Ортогональный базис в пространстве дискретных периодических сплайнов.

§ 7. ТВ-сплайны и самодвойственный вейвлет

Глава 4. Лифтинговые схемы для вейвлетного преобразования дискретных периодических сигналов.

§ 1. Биортогональные вейвлетные схемы.

§ 2. Лифтинговый алгоритм получения коэффициентов разложения в интерполяционном случае.

§ 3. Вейвлетное разложение пространства сигналов.

§ 4. Биортогональная вейвлетная схема, основанная на интерполяции дискретными сплайнами.

§ 5. Алгоритм декомпозиции сигналов, основанный на рекурсивных фильтрах.

Глава 5. Натуральные сплайны многих переменных.

§ 1. Общая задача о натуральных сплайнах.

§ 2. Задача оптимального восстановления функционала на классе элементов.

§ 3. Сплайновые алгоритмы, их оптимальность и центральность.

§ 4. Фундаментальное решение полигармонического уравнения и теорема С.Л. Соболева о плотности финитных функций

§ 5. Натуральные сплайны, заданные на всем пространстве

§ 6. Сглаживание данных при помощи натуральных сплайнов

§ 7. Численные методы решения задачи сглаживания.

§ 8. Степенные сплайны.

§ 9. Логарифмические сплайны.

§ 10. Сферические натуральные сплайны.

Введение диссертации (часть автореферата) на тему «Вопросы теории и вычислительные применения сплайнов и вейвлетов»

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

Вейвлетный анализ сигналов лежит на пересечении чистой математики, вычислительной математики, цифровой обработки сигналов и изображений. Он находит все более широкое применение в различных областях науки, так как дает более подробную информацию о сигнале или изображении, чем обычный анализ Фурье. Такую мысль высказывают многие авторы обобщающих работ по вейвлетам (Н.М. Астафьева [1], И.Я. Новиков, С.Б. Стечкин [64, 65], А.П.Петухов [79]).

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

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

Назовем имена математиков внесших существенный вклад на предшествующих этапах развития теории сплайнов и вейвлетов. Развитию теории полиномиальных сплайнов и их популяризации содействовали труды И. Шенберга [126, 127, 128], С.Б. Стечкина, Ю.Н. Субботина [89], Ю.С. Завьялова, Б.И. Квасова, B.JI. Мирошниченко [35], В.Н. Малоземова [52].

Задаче сглаживания сплайнами посвящены работы К. Райнша [123, 124], Ю.Е. Воскобойникова, Н.Г. Преображенского, А.И. Се-дельникова [20], В.В. Вершинина, Ю.С. Завьялова, H.H. Павлова [15], В.Н. Малоземова [54].

1)т-сплайны и сплайны в гильбертовом пространстве исследовались в работах Ж. Дюшона, Т. Гудмана, Р. Франке, П.-Ж. Лорана, 5

В.А. Василенко, А.И. Роженко, В.Т. Шевалдина [144, 145, 151, 147, 148, 150, 12, 84] и других авторов.

Родственные вопросы, связанные с интерполяцией радиальными базисными функциями, рассматривали И. Шенберг [160], Ч. Мичелли [156, 157], Р. Шабак [159] и другие.

Отправной точкой в систематическом изучении базисов всплесков считается работа С. Маллата(1989). Базисам всплесков (вейвлет-ным базисам) уделено значительное внимание в работах И. Добеши [25, 111], Ч. Чуй [101], И.Я. Новикова, С.Б. Стечкина [64, 65], А.П. Петухова [82, 80, 81, 79, 78], М.А. Скопиной [85, 131], В.А. Желудева [28, 29, 30, 138, 139, 140, 141], В.Н. Малоземова, С.М. Машарского,

A.А. Третьякова [48, 49, 50, 51, 55, 57, 58, 59, 60, 61] и других авторов. Задачам сжатия информации посвящена обширная литература.

Упомянем только работы Г. Белкина, Р. Койфмана, В. Рохлина [106],

B.И. Бердышева [6], А.П. Петухова [78], C.B. Умняшкина [98], А. Сайда, В. Перлмана [125].

Следует отметить, что наибольшее влияние на работы автора оказали труды В.А. Желудева, В.Н. Малоземова, А.П. Петухова. Конкретные ссылки на их труды и предшествующие работы других авторов содержатся далее в обзоре работы по главам и во введениях к главам 1-5.

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

В главе 1 параграфы 1-3 являются вводными. В них рассматриваются дискретные непериодические сплайны S(j) с равноотстоящими узлами, где j пробегает множество целых чисел Z. На этот дискретный случай переносятся результаты для сплайнов и вейвлетов вещественного аргумента х, полученные ранее Ю.Н. Субботиным, В.А. Желудевым, Ч. Чуй, И. Добеши. В частности исследована разрешимость интерполяционной задачи для дискретных сплайнов по бесконечной системе равноотстоящих узлов, изложена теория ТВ-сплайнов и двойственных к ним сплайнов.

В §1 дается определение В-сплайна Вр порядка р, описываются его свойства. Дискретным сплайном S(j) называется линейная ком6 бинация сдвигов В-сплайна.

Дискретные В-сплайны Вр определяются естественным образом. В-сплайн первого порядка В\{1) ("ступенька") имеет вид

BiU) =

1, j € 0 : п - 1, О, при остальных j е Z. i) п

Здесь 0 : п — 1 — множество целых чисел {0,1,., п — 1}, фиксированное натуральное число.

Используем рекуррентное определение Вг = В\ * Д.1, г € 2 : р, или

71 — 1

A-ü) = J2 -к), je z, Г = 2 к=О

Такое естественное определение (аналогичное непрерывному случаю) не могло пройти мимо внимания математикрв. И действительно оно нашлось в работе японских математиков [115], а затем в [121].

В-сплайн Bp(j) положителен только на целочисленном промежутке 0 : р(п — 1), симметричен относительно! середины этого промежутка и принимает только целые неотрицательные значения. ле выявления кусочно ая теорема принадле

Слово 'сплайн' становится оправданным пос - полиномиальной структуры Bp(j). Следующ жит В.А. Желудеву.

Теорема 1. В-сплайн Вр есть кусочно-полиномиалъная функция степени р — 1: вР(з) р

-i—¿(-irCJ(iH-l-m) r=0

P-I) + )

2) где через будем обозначать усеченный факториальный полином

P-1) í j{j+l).(j+p-2), je 1: оо,

J+ =

О, j < о, j е z

Дискретный В-сплайн Bp(j) не является следом непрерывного В-сплайна на сетке, но если Bp(j) соответствующим образом масштабировать, то в пределе при п —> оо получим непрерывный В-сплайн (см. п. 1.2).

В п. 1.3 предполагается, что число v — р{п — 1)/2 является целым (точка v — это середина носителя В-сплайна Вр). Положим bp(k) = вр(р + кп). Заметим, что Ьр(-к) = Ьр(к) и Ър(к) отлично от нуля, если

1*1 ^ ;= И = р(п-1) 2 п Здесь [а] означает целую часть а.

Четный тригонометрический полином м

ТРА*)= Ьр(кукх = Ьр(0) + 2^Ьр(к)со8кх к=~1Х

3) к=1 называется полиномом Эйлера-Фробениуса (такой термин используется в непрерывном случае - см. [128]). С помощью дискретного преобразования Фурье получена явная формула для значений ТРуП на сетке х = 2-7Г 1/т, I £ 0 : т:

Т,

2тгГ

171 р

V эт к=0 \ тп

Заменяя 2-к1/т на ж, получаем

К х ' п\ 2/ ^ \ тп^

4) л . эт 0 ¿=0 V 2 71

5)

Поскольку (4) выполнено на сетке любой густоты (ш - любое натуральное число), то (5) выполнено для всех х е (0,2тг). Формула (5) аналогична формуле для непрерывного полинома Эйлера-Фробениуса (см. [101], формула (6.4.1)). В дискретном случае в знаменателе формулы (5) появляется синус, и это указывает на качественное отличие Тр,п{х) от непрерывного полинома Эйлера-Фробениуса.

Доказана теорема 1.2 о положительности ТР:П(х) при всех х:

Тр,п(х) > 0.

При р четном это сразу следует из (5) (все слагаемые положительны), а при нечетном р сумма (5) содержит отрицательные слагаемые, эта сложность преодолевается с помощью леммы 1.4, доказанной В.А. Желудевым.

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

00 Е с(оад-гп),

6) 8 где коэффициенты {с(к)} имеют не более чем степенной рост при \к\ -»■ оо, т.е. существуют М, 5 такие, что |с(&)| < М(1+\к\У, к е 1. Тогда и сам сплайн 5(7) имеет не более чем степенной рост при \з\ —^ оо. Традиция рассматривать сплайны с таким ростом на бесконечности идет от Шенберга [128], хотя и не имеет практического значения. Множество всех сплайнов порядка р обозначим УР)П.

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

X)

Яр,п(*>з)= Е ^1хВР{з~1п). (7) = — 00

При каждом з Е Ъ в сумме (7) конечное число слагаемых, поэтому при фиксированном ] функция Ер^п(х,]) является тригонометрическим полиномом от х. При каждом фиксированном х функция Ер,п{%13) является дискретным сплайном (принадлежит пространству VР}П). Аналогичные сплайны непрерывного аргумента рассматривались И. Шенбергом в [128], с. 17.

Сплайн (6) представляется в виде з еж, (8) где распределение С по коэффициентам (с(/)} сплайна восстанавливается по формуле

00

С{х) = £ с(/)еЛ (9) = — 00

Наиболее важным является случай, когда последовательность с € £2(ъ). Тогда ряд (9) определяет элемент С из Ь2(0,27т). И обратно, если С 6 Ь2(0,27г), то последовательность с принадлежит В этом случае формула (8) переписывается в интегральном виде

Случай, когда с £ 12{ъ) или, что то же самое, С 6 Ь2(0, 27т), будем в дальнейшем называть квадратично суммируемым случаем.

Далее в §2 рассматривается задача интерполяции по равноотстоящим узлам. Дана последовательность г = }£100. Требуется 9 найти сплайн Я <Е УР)П такой, что

Б{у + кп) = х{к), ^ € (10)

Здесь, как и выше ^ = р(п — 1)/2 — целое число.

Условия разрешимости такой задачи в непрерывном случае впервые получены Ю.Н. Субботиным [90] и позднее И. Шенбергом [128]. Систему уравнений (10) можно записать в сверточном виде с * Ьр)(к) = г(к), к£Ъ. (11)

Введем функцию У(х) = 1/Тр(х). Ввиду доказанной положительности Тр(х) это бесконечно дифференцируемая 27г-периодическая функция. Она разлагается в ряд Фурье

00

У(х) = ь(к)е{кх. (12) к=—оо

Коэффициенты ю(к) при к —»• оо убывают быстрее любой степени

Коэффициенты с(1), являющиеся коэффициентами интерполяционного сплайна находятся по формулам 00 00 с(0 = *(РМ* -р)= $3 ~ <гМ<Л I е г, (13) р=—оо #=-00 при условии, что ряды (13) сходятся.

Определение 1. Пусть в—неотрицательное целое число. Будем говорить, что последовательность г принадлежит классу если существует М такое, что \z(k)\ < М{ 1 + \к\У для всех к £ Ъ.

Обозначим С = (Хо ■

Теорема 2. Пусть г £ Тогда ряды (13) сходятся для любого I и определяют коэффициенты с{1). Сплайн оо

-ад = Е с(озд - ь) (м)

1=-00 является решением интерполяционной задачи (10). Последовательность с = {с(0} также принадлежит классу Решение интерполяционной задачи единственно в классе сплайнов с коэффициентами с из С.

10

В п. 2.3 введено пространство квадратично суммируемых сплайнов 8Р)П, состоящее из сплайнов 5(У) вида

1 [2ж

15) где С £ £2(0, 27г). Доказан важный аппаратный результат — равенство Парсеваля.

Теорема 3. Всякий сплайн в Е принадлежит пространству £2(ъ). Если есть два сплайна 6 представленные в виде (15) и

1 С2п

ВД = ^ у0 где £> € Ь2(0,2ТГ), то справедливо равенство Парсеваля 1 р2п

5, Я) := ]Г = ^ / С(х)Б(х)Т2р(х) йх, (16) в частности

1 /*27Г

1|51|2 := £ = 5- / «¡х- (")

Здесь Т2р — полином Эйлера-Фробениуса порядка 2р.

В §3 рассматриваются ТВ-сплайны и двойственные к ним сплайны. Рассмотрим сплайн вида

1 /2?г г,

18) где функция £ предполагается бесконечно дифференцируемой и 2тг-периодической, т.е. £ еТ>. Как отмечалось выше, функция ср представляется в виде оо р(:1) = (¡вРа - 1п),

19) = — 00 где & = — коэффициенты Фурье функции £(ж). Поскольку 6 2), то коэффициенты убывают при £ —> оо быстрее любой степени 1/1, а тогда и ср^) убывает при ] оо быстрее любой степени 1/^'. и

Определение 2. Сплайн <р называется ТВ-сплайном, если сдвиги {(р(- — кп)}ке% образуют базис в пространстве сплайнов \р<п, т.е. всякий сплайн 5 Е Ур,п разлагается в ряд

00

5У) = £ с(к)сри - кп), (20) к=—оо сходящийся для каждого ] £ 2.

Теорема 4. Ясли ^ О Уж б К, то сплайн (р является ТВ-сплайном.

В пространстве квадратично суммируемых сплайнов 8Р]П система сдвигов {</?(■ - &п)}Ае2 образует базис Рисса и ряд (20) сходится по норме £2(ъ).

Пусть кроме ТВ-сплайна ср есть также ТВ-сплайн

1 Г27Г

Л') = Ф)Ер,п(хЛ)<Ьв, (21) где 7] е I), 77(0?) Ф 0 для всех х.

Определение 3. ТВ-сплайны (риф называются двойственными, если

00 - кпЩэ - Яп) = д(к — д), д £ г, (22)

3=-оо где черта обозначает комплексное сопряжение.

Теперь можно сформулировать критерий двойственных ТВ-сплайнов.

Теорема 5. Сплайны (18) и (21) являются двойственными ТВ-сплайнами тогда и только тогда, когда выполнено соотношение х)ф)Т2р(х) = 1 \/х е К. (23)

С помощью этой теоремы строится самодвойственный сплайн </?(.?)> сдвиги которого образуют ортонормированный базис в УРуП. Он получается при £(х) = 7}(х) = 1/л/Т2р(х).

12

В §4 разрабатываются основы сплайн-вейвлетного анализа. Фактически в нашем изложении нет никакой масштабирующей функции y>(j), а масштабирующее уравнение записывается для Ep>n(x,j):

Ер,ф>Л = с (|) Ер,п j) + с + тг) £Р)П + тг, j) , (24) где с(х) — |(1 + егж)р. Показывается, что Угл2и С Vp,n. Хотя пространство VP;U не вкладывается в ^2(z), тем не менее можно определить ортогональное дополнение WP;2n к Vp^n в пространстве Ур>п, используя понятие галеркинской проекции. Мы используем запись

Vp,n = Vp,2n ф wр,2п.

Показывается, что пространство WP)2п состоит из сплайнов вида w(j) = (D(x), WPi2n(x:j)): где WP;2n(x,j) — экспоненциальный вейвлет, введенный в п. 4.3, a D{x) — произвольное 2к - периодическое распределение.

Далее вводятся ТВ-вейвлеты и двойственные к ним вейвлеты, в частности В-вейвлет ( с конечным носителем ), хорошо известный в непрерывном случае.

§5 посвящен декомпозиции и реконструкции сигналов. Пространство всех сигналов F медленного (степенного) роста совпадает с Урд (при п = 1). Удваивая гг, приходим к разложению f = vPi2fr © wPî2n е wa2*-i е. wp,2.

Выведены формулы декомпозиции и реконструкции (в непрерывном случае такие формулы довольно традиционны; алгоритм на их основе называют каскадным алгоритмом).

Отдельно (пп. 5.4 и 5.5) рассмотрен вопрос о декомпозиции пространства квадратично-суммируемых сигналов i2(z) и при каждом р получен своеобразный кратномасштабный анализ в ¿2{ъ). В частности, о 00 (z) = е wk. к=1

При р = 1 подпространства Wk являются "хааровскими", т.е. базис в них образуют сдвиги дискретного хааровского вейвлета

Mj) = 1 при j е 0 : 2к~1 - 1, фк{з) = -1 при j е 2fc-1 : 2к - 1, и tpk{j) = 0 при остальных j.

13

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

Изложение в этой главе начинается не с построения вейвлетного базиса в пространстве сигналов, а с алгоритма получения коэффициентов разложения сигнала по пока еще неизвестному базису.

Основой получения вейвлетных разложений является лифтинго-вая схема. Для дискретного сигнала {#(&)} она начинается с расщепления на четный и нечетный подмассивы е\(к) = х{2к), й\(к) = х{2к -Н 1), к £ Ъ. Затем четный массив е\{к) используется, чтобы предсказать значения нечетного. В главе 3 будем использовать интерполяцию дискретными периодическими сплайнами. В главе 2 используется дискретный непериодический сплайн степени 2г — 1, удовлетворяющий интерполяционным условиям 5Г(2&) = е\(к), к £ % (эта задача исследована в главе 1). Такой вариант более подходит для цифровой обработки сигналов. Наша схема идейно близка к схеме, реализованной в [141], где были использованы непрерывные интерполяционные сплайны. Метод предсказания нечетных элементов массива с помощью интерполяции на четных элементах был предложен в работе Донохоу [113], которая была модифицирована Свелденсом [132, 133] в "лифтинговую схему".

С помощью ^-преобразований ед = £>!(*:)*-*, = и = 1, этапы декомпозиции и реконструкции записываются в следующем виде.

1. Декомпозиция сигнала {х(к)} в лифтинговой форме осуществляется в три этапа:

Расщепление - Расщепим массив х на четный и нечетный подмассивы: в! = {в!(к) = х(2к)}, (11 = {к) = х(2к + 1)}, к £ 2.

Предсказание - Используем четный массив в1 чтобы предсказать значения нечетного массива (11. Переопределим <11, взяв в качестве нового значения ¿\{к) разность между (1\(к) и предсказанным значением а (к). В качестве предиктора используем значения а (к) = 8т{2к 4- 1), где вг удовлетворяет интерполяционным условиям 5г(2/с) = ег(к), к £ Z. В ^-области получается формула

14

25)

Е(г2) = ги(г)Е1(г2), где

V } (1 4.3-1)*+(1)г(1 2-1)* •

Функция и (г) будет играть важную роль в дальнейшем. Отметим, что и(-г) = -и(г) и и{г~1) =

Окончательно получаем

Ьг(г2) = А(^2) - ги(г)Ег{г2). (26)

Обновление - Обновим четный массив с помощью нового нечетного: х(г2) = Ех{г2) 4 ^(ф-1 ^(г2). (27)

Потребуем, чтобы функция (3(г) = имела вещественные значения (при \г\ = 1) и удовлетворяла условию /3(—г) = — (3(г), так что произведение (5(г)г'1 есть функция от г2.

2. Реконструкция. Восстановление сигнала х из массивов в! и (11 осуществляется в обратном порядке:

E1(z2) = E1(z2)-(3(z)z~lDl(z2),

D^z2) = D1{z2) + zU{z)El(z2). Далее полагаем х(2к) = е\(к), х(2к 4l) = d\(k).

28) (29)

Для нас важна формула, выражающая X(z) через Ei(z2) и Di(z2): X(z) = h(z)E\(z2) 4 g(z)Di(z2), где h(z) = 1 4 U(z), g(z) = z-'l 1 - 0(z)( 1 4 tf(s))]. (30)

3. Базис в пространстве сигналов

Функции h(z) и g(z) разлагаюся в ряды le Ъ le Ъ сходящиеся для всех z, \z\ = 1. Дискретные функции у>1(1), ф1{1) назовем низкочастотным и высокочастотным вейвлетами. Их сдвиги образуют базис в пространстве сигналов как показывает следующая теорема.

15

Теорема 6. Каждый сигнал х представляется в виде х{1) = ^ ёх{к) <рг{1 + ^ <*!(*) ~ 2к)> (31) кеЪ к£Ъ где коэффициенты ё\(к), (к) получаюся в процессе декомпозиции сигнала х по формулам (26), (27).

4. Биортогональный базис

Формулы декомпозиции можно записать в фильтровой форме

Ч*2) = ~ [ЩВД + , (32)

Ч*2) = \ ЩХ{г) + Ж^)Х(-г)], (33) где ОД = 1 + /3(*)(1 - и (г)) = 1 + /?(*)&(-*), д{г) = ^(1 - ^М) -По предположению /?(;г) имеет вещественые значения ( при \г\ = 1), поэтому Н{х) также вещественна. Функции К(г) и д(г) разлагаются в ряды где ф1(1),ф1(1) называются двойственными вейвлетами. В литературе неоднократно рассматривался вопрос о биортогональных базисах. Условия биортогональности в терминах ¿-преобразований записываются в виде

ЦгЩг) + = 2, д(г)ф) + = 2, ( ,

Цг)д(2) + Ц-2)д(-г) = О, д(г)Н(г) + д(-г)Н(-г) = 0. 1 ;

Легко проверить, что для выбранных фильтров Н, д, К, д эти условия выполняются (напомним, что функция = 1 + и (г) вещественна). Отсюда следует

Теорема 7. Справедливы соотношения биортогональности ф1^ - 2к), - 2т)) = 6(к - т), (фх(- - 2к), ф1(- - 2т)) - 5{к - т) {ф1^ - 2к),ф {• - 2т)) = 0, - 2к), - 2т)) = 0,

35) для всех к:т £ Z. Здесь #(0) = 1, 5(к) = 0 при к ф 0 и {•, •)— скалярное произведение в ¿2(ъ).

16

5. Полифазная матрица Р(г) и ее факторизация

Решен вопрос о факторизации полифазной матрицы Р{г) устанавливает связь между она ад ш Р(г)

Щг), 2ЭД] и [ВД, 2М*)1 : , где Р(г) =

9е(г) 9о{%).

Чтобы выписать Р(г) в явном виде выберем /3(г) по формуле = ¿¡и(г) (обоснование разумности такого выбора в непрерывном случае приведено в [141]). Как уже отмечалось, является функцией от г2: = Рг(г2). На основе этого получена факторизация вида

Последовательное умножение

1 1 0"

0 1 ,-ЗД 1

36) ад на матрицы-сомножители эквивалентно лифтинговому алгоритму (26), (27). Вопросы факторизации полифазных матриц подробно рассматривались в [78], [112].

Построен двойственный лифтинговый алгоритм— он служит для разложения произвольного сигнала х по двойственному базису {ф1(1-2к), ф1(1~2к),

Показано, что вейвлеты ф1, ф1 имеют 2г исчезающих моментов. Центральным разделом главы 2 является §3 "Рекурсивная реализация лифтингового алгоритма". Идея такой рекурсивной реализации является довольно известной, см., например, [79].

В (26) присутствует фильтр г11{г). Функция х1](г) в действительности зависит от 2

2.

1 + г)* -(-1Г(1г) г£/(г) = га(г-1) = г

1 + г)2г + (-1)1-(1 - г)

2 г

2г'

Основную формулу (26) можно записать в виде

Й1(г) = АМ - адад.

37)

Надо реализовать фильтр с передаточной функцией Рг(г), т.е. по данному сигналу х вычислить сигнал у такой, что У (г) = Рг(г)Х(г).

Функция является дробно-рациональной. Удалось найти в явном виде корни ее числителя и знаменателя. Итогом является

17

Теорема 8. Функцию Fr(z) можно представить в виде: р

Fr(z) = Ar(l + z)l[Rk(z)Rk{z~1), где при г = 2р -f-1 А>г k=1 aia2 • • • oi p

2r7i72 . 7P 1 + а* я

Если же г = 2р, то

2rai(*2 • • • 1 + =-, = --,

7172 • • • 7p-I 1, ад = г avz

Для ска; и выведены явные формулы и при этом 0 < ак < 1, О < 7* < 1.

В результате оператор хыу реализуется в виде каскада р прямых рекурсивных фильтров, обозначаемых Нк (с передаточной функцией /4(г-1)) и р обратных рекурсивных фильтров, обозначаемых ^ (с передаточной функцией Нк^)), а также простейшего фильтра С} с передаточной функцией 1 + z. Эти фильтры действуют следующим образом

У = У = у = Qx< у{1) = х{1) + 7kx(l - 1) - aky(l - 1), (38) y(l) = ®(i) + 7kx(l + 1) - aky(l + 1), (39) y(!) = x(l) + x(l + l). (40)

При реализации (38) полагают у(1о) = 0 и далее вычисляют у(1о + 1)> у[1 о + 2), — При реализации (39) полагают у(1 о) = 0и вычисляют У{к~ 1), ~ 2), —

В формуле обновления (27) содержится управляющий фильтр /3(г). Наиболее простым выбором является /?(г) - \и{г). Имеем z

-1 zU(z)]z-2 = = Фг(г2), где ФР(з) = \Fr(z)z~l.

Поэтому (27) переписывается в виде

El{z) = El{z) + $r{z)D1{z)i

41)

18 где Фг отличается от отставанием на один отсчет.

В явном виде выписаны фильтры при г = 1, 2, 3 и кроме разложения на множители приведены также разложения на простейшие дроби, что делает возможным параллельные вычисления.

В §4 указан способ вычисления вейвлетов ф1 и (р1 и пр г = 2 получены явные формулы для этих вейвлетов.

§5 посвящен многоуровневому вейвлетному преобразованию. Сначала получается двухуровневое разложение сигнала. На втором уровне преобразуется массив {ёг(к)}. Сначала расщепим на четный и нечетный подмассивы: е2(к) = ё\{2к), д2{к) = ё\(2к + 1), к £ Ъ, и перейдем к новым массивам {ё2{к)}, {с12(к)} по формулам, аналогичным (26) и (27):

Б2(г) = Дг(*) - ВДВД, Ё2{г) = Е2(г) + Фг(г)Г)2(г). (42)

Используются те же фильтры Еп Фг, что и на первом уровне.

Этот двухуровневый процесс приводит к разложению сигнала х по вейвлетным базисам.

Теорема 9. Любой сигнал х представляется в виде ^ё2(к)</?(1-4к)+^42(к)11?(1-4к)+'£1Мк)ф1{1-2к), (43) кеЪ кеЪ где вейвлеты второго уровня определяются по формулам у2(1) = Е - 2т), ф\1) = Е ф1(т)<р\1 - 2т). (44) шей шей

Предлагается экономичный алгоритм реконструкции сигнала х{1) по вейвлетным коэффициентам.

Многоуровневое разложение сигнала. На третьем шаге от {ё2(к)} перейдем к {ёз(&)} и (с/з(&)}. После £ шагов получим ¿-уровневое разложение сигнала г х(1) = ^ Ъ(к)<р*{1 - 2гк) + 53 53 ~ , * € к к где р"{1) - 53 - 2т), фу{1) = 53 ^МЛ* - 2т)- (45) теЖ тбй

19

В ряду вейвлетов ф1, ф2,., ф* первый имеет самую большую частоту. Грубо говоря, каждый следующий вейвлет имеет частоту в два раза меньше, чем предыдущий.

В §6 обсуждается вопрос об ортогональности сдвигов <р1 и ф1. Вейвлеты ф1, ф2, . зависят от управляющего фильтра на который наложено требование нечетности: /?(—г) = —¡3(г). Фильтр /3(г) можно выбрать так, чтобы вейвлеты обладали дополнительными свойствами, например, чтобы подпространства Ип^- - 2к)\к € Ъ}, IV! = Щф1^ - 2т)¡т <Е 1} (46) были ортогональными. Доказывается следующий результат.

Теорема 10. Если фильтр (3(г) выбран в виде то подпространства (71) ортогональны.

В §7 обсуждается вейвлетное преобразование Баттерворта для конечных сигналов.

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

Рассмотрим конечный сигнал х= {ж^')}^1, N = 2п. Продолжим сигнал каким-либо образом на все множество целых чисел Ъ и сделаем Ь шагов многоуровневого вейвлетного разложения по следующей схеме х —>■ ё\ 62 -»•••-» ё* . N . ^ ^ ¿1 й2 • • •

Получим разложение

Ь N3-1 Е № - 2*к)+Е Е <*•(*) и - 2вл), к=0 «=1 к=0 где = N/2**, 5 = 0,. (предполагается, что ./V делится на 2*).

В §9 указаны два способа выполнения вейвлетного преобразования Баттерворта для двумерных сигналов (изображений).

20

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

Отправной точкой послужила статья В.А. Желудева [28], в которой развивается своеобразное сплайн-операционное исчисление (СОИ), основанное на дискретном преобразовании Фурье(ДПФ) и на представлении периодического сплайна S(x) в виде линейной комбинации В-сплайнов. В главе 3 исследуются дискретные сплайны S(j),j (Е Z, имеющие период N.

В основе дискретного варианта СОИ лежит представление дискретного сплайна S(j) в виде линейной комбинации дискретных В-сплайнов т—1 ы о где ji — 1п - узлы крупной сетки на Z. Далее от последовательности коэффициентов {c¿} переходим к ее ДПФ, и задача переносится в пространство Фурье-образов. Использование ДПФ позволяет для сокращения объема вычислений применять алгоритмы быстрого преобразования Фурье.

В §1 дается рекуррентное определение дискретных периодических В-сплайнов (с периодом N).

Дискретные сплайны рассматриваем на множестве целых чисел Ъ. Зафиксируем натуральные г, n, N, такие, что N > 2rn, п > 2.

Определим дискретные В-сплайны Qi(j),. ■, Qr(j) (j Е Z) следующим образом. Положим n-j, j'eOrra-l,

Q1(j) = {0, jen:N-n, (47)

Ij-(N-n), jeN-n + l:N-l.

Определенную на 0 : N—1 функцию Q\ продолжим на всю целочисленную ось Z с периодом N (так, чтобы выполнялось условие Qi(j + N) = Qi(j) Vj 6 Z). Функция Qi представляет собой совокупность "домиков" с вершинами в точках 0, ±N, ±2iV, — Далее используем рекур

21 рентное определение

Як = Я\* Як-ъ к = 2,. ,г,

48) или

ЛГ-1

Як(з) = ^ ЯМЯк-Аз - р), 3 к = 2,., г. о

Лемма 1. В-сплайн имеет период N и обладает следующими свойствами:

Яг{—з) — Яг{з) Для любого целого 0 при /сЛГ - г(п - 1) < з < /сАГ + г(п - 1) и С^г{з) — 0 при остальных

49)

50) г(п—1)

Е Яг(з) = п2г; (51)

-г(п-1)

Яг(г{п- 1)) = 1. (52)

Выразим <5г0) через непериодические В-сплайны, введенные в главе 1. Рассмотрим д^') = Б2Г(^ + г(гг — 1)) — центральный В-сплайн порядка 2г. Его носитель —г(п — 1) : г(п — 1). Выполнены свойства

Яг(~Л = Чг{з) и = *

Лемма 2. В-сплайн есть N-периодизация В-сплайна дг, т.е.

53)

При этом Сдг(з) = при Ь | £ гп.

Пусть теперь Л/" делится нацело на п:

ЛГ = тп.

В силу сделанных предположений п > 2, т > 2г > 2.

Дискретным Л^-периодическим сплайном 5 будем называть линейную комбинацию В-сплайнов т—1 гО'-л) и € 2),

54)

22 где точки 31 = 1п, I е 0 : га — 1, называются узлами сплайна, а с/ — произвольные комплексные коэффициенты.

Можно показать, что сплайн в^) на каждом целочисленном промежутке ¿к : 1 совпадает с некоторым полиномом степени не выше 2г—1. Это можно использовать для быстрого вычисления сплайна 5. Быстрый алгоритм выписан при г = 2.

В §2 "ДПФ и интерполяция дискретными сплайнами" вычисляется в явном виде дискретное преобразование Фурье (ДПФ) от В-сплайна фг. С его помощью выводится формула для значений В-сплайна в узлах jk = кп:

1 т—1 т 1=0 где ит = е2ш!т. Таким образом, последовательность {Яг(Зк)}™=о является обратным ДПФ (длины га) от положительной последовательности

То — п2г1, Т^ = хАзт3—)2\ 3 = 1,. ,гп — 1, (55) 777» ' где

1 П^ 1 ^ = -, л /лт) ' 3 = 0,.,т- 1.

Положительность чисел Т^ позволяет легко решить интерполяционную задачу для дискретных сплайнов: т—1 Е - 31)= ^к, к = О,., га - 1. (56)

1=0

Здесь числа ^ даны, требуется найти коэффициенты с^.

Отметим, что матрица Q с элементами С^-г = {Зк — 31) симметрична и положительно определена.

Решать систему С^с = 2 не нужно. Надо сделать ДПФ над обеими частями (56). Придем к эквивалентной системе уравнений

С/.7) = ^-, з = 0,.,т-1, (57) где то—1

С; = Е У = 0, -., т - 1,

1=0

23

-ДПФ от с, а {Zj} — ДПФ от z. После перехода к Фурье-образам получаем простейшую (диагональную) систему (57), которая ввиду положительности чисел Tj легко решается:

Cj = Zj/Tjl j = 0,. ,т — 1. (58)

Для нахождения неизвестных коэффициентов q сплайна S осталось сделать обратное ДПФ. Поскольку числа Tj можно вычислить заранее, то решение интерполяционной задачи (56) сводится к выполнению двух ДПФ длины т.

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

Теорема 11. Для матрицы Q = {Qr{jk — ji)Yki=o справедливы равенства

Q = F1TF, Q1 = где Т = diag{TQ:., Tmi}, F = {cü^}^ - матрица ДПФ.

В §4 решается задача сглаживания дискретных данных. Пусть z(t) - функция с комплексными значениями, имеющая период Т. Возьмем натуральное число N вида N = mn, т > 2, п > 2. Обозначим h — T/N и введем сетку tj = jh.

Предположим, что в узлах крупной сетки известны значения функции z, измеренные с погрешностями: zk = z(tkn) + к = О,. ,т — 1, где щ - ошибки. Требуется восстановить значения Xj = z(tj) на всей сетке tj.

Эту задачу, как обычно, формализуем следующим образом:

N-1

59) з=о т—1

- V \хкп - zkI2 < е. (60) т f—'

Здесь г - фиксированное натуральное число, АrXj - конечная разность порядка г, {xj} - TV-периодическая последовательность.

Известно [54], что решением задачи сглаживания (59)-(60) является последовательность значений дискретного ^-периодического сплайна S(j).

24

Рассмотрим общую задачу сглаживания на сплайнах

N-1

S):=^|(a*S)(j)|2^min, (61) з=о т-1

E(S):=^\(b*a)(k)-zk\2<^ (62) к=0 где а = {5(^п)}^Г01-вектор значений сплайна в узлах, а = (ао,. •., o>n-i) b = (&о,., ömi)-фиксированные векторы. Оператор АrS легко записать в виде свертки а * S.

Пользуясь равенством Парсеваля, перейдем в (61)-(62) к образам Фурье. В пространстве векторов С — (Со,., Ст-\) задача принимает вид

1 т-1 f(C):=-Y]ßk\Ck\2^mm, (63) т z—' к=О

- т—1

- Е \ßkTkCk - zkI2 < е, (64) к=О где числа ¡лк > 0, а последовательности В, С, Z — ДПФ от 6, с, z.

Для решения (63)-(64) рассмотрим вспомогательную задачу с параметром а > 0: l(C) = af{C) + g{C)^ min .

Эта задача без ограничений распадается на т независимых задач: при каждом к = 0,., т — 1 нужно минимизировать функцию lk{Ck) = atik\Ck\2 + |ВкТкСк - Zk|2. (65)

Здесь наглядно видно достоинство СОИ—многомерная задача распалась на ряд одномерных.

Введем три множества индексов

К0 = {к = 0,., m - 1\Вк = 0 и ßk = 0},

Кг = {к = 0,., m - 1\Вк ф 0 и fAk = 0}, К2 = {к = 0,.,тп-1\цк^0}.

25

При к G К2 минимум (65) достигается в единственной точке

TkBkzk

Ск(а) =

Тк\Вк\2 + ацк

66)

При к £ К\ минимум также достигается в единственной точке Ск (а) = Zk/(TkBk), что совпадает с (66) при = 0. Если же к е К0, то функция 1к от Ск не зависит; будем считать, что Ск(а) = 0 при к £ К0. Вернемся к задаче (63) и вычислим д на полученном решении

V{a) ,= д(С(а)) = i £ \Z„? + ^ £ (

Otllk

Tk\Bk\2 + a/Xfe

Положим

Si <¿>(0) = - \Zkf m ' fceifo 1 e2:=(p{oo) = — Y] \Zk\2. m z—' keK0r\K2

Очевидно, что g (С) > £\ VC. Поэтому если s < £1, то нет векторов С, удовлетворяющих (64).

Если е\ < е < е2, то существует к £ К2 такое, что Zk ф 0, и тогда р(а) строго возрастает от £\ до е2, принимая все значения из промежутка [ei,e2). Поэтому существует единственное а* такое, что <-р(а*) = Легко показать, что вектор С (а*) является единственным решением (63)-(64).

Тем самым в основном случае е\ < е < е2 дело сводится к решению уравнения <р(а) = е. Эффективный численный метод решения уравнения <р(сч) = s предлагается в главе 5 (§7, п. 3).

В §5 метод СОИ применяется к решению задачи о бесконечной цилиндрической оболочке.

Рассмотрим круговую цилиндрическую оболочку радиуса R, толщины d, имеющая бесконечную длину, причем d/R « 1. Предположим, что нормальное давление (изнутри) pi(<p) и касательное усилие р2(<р) не зависят от координаты х вдоль оболочки. Поэтому перемещения u((p), w((p) также не зависят от х и удовлетворяют системе уравнений u' - 2ai«'" + w + ai [к/4) - 2w"] = Aipi(p), и" + w'~ 2aQw'" = —А2р2((р).

26

Требуется найти 27г-периодическое решение системы (68). Если (и, г»)— решение, то {и + С, у)—также решение. Константа С определяется из какого-либо дополнительного условия.

Пусть N = тп. Рассмотрим схему, в которой вычисляются значения функций и((р), у(р) на мелкой сетке щ = уЬ,, ] = 0,., N — 1, где к = 27г/7У, но при этом делаются ДПФ длины т.

Аппроксимируем и((ру) дискретным Аг-периодическим сплайном ¿пОО, а и){1Рз)—сплайном 5*2 т—1 т—1

ЗД) = X ~~ -Й' С?) = XI ^ФгС? ~

1=0 1=0 где ][ = 1п, г - фиксированное натуральное число.

Заменим производные в точках разностными отношениями. ДПФ от {ЗД*)} есть {СкТк}™^. Аналогично ДПФ от {52(й)} есть . Подставив в систему разностных уравнений, получим для каждого к = 0,., т — 1 систему двух уравнений с неизвестными Ск,йк. Обратными ДПФ найдем коэффициенты сплайнов 5х, 512В §6 строится ортогональный базис в пространстве дискретных периодических сплайнов. Введем дискретные функции 771 — 1

МЛ = - X - М, к = 0,., т - 1. (68)

171 1=0

Очевидно, что эти функции принадлежат ибо являются линейными комбинациями В-сплайнов С}г (] — 1п) с комплексными коэффициентами Более того, сплайны (68) образуют базис в так как каждый сплайн 5(У) представляется в виде т—1 ег, (69) к=О где = ^(с). Таким образом, чтобы найти коэффициенты сплайна в новом базисе, нужно сделать ДПФ длины т.

Теорема 12. Справедливы равенства цк, т) = 0, к,1 = 0,.,т-1, кф\. (70)

27

Ввиду ортогональности сплайны Цк будем называть ортсплай-нами.

В §7 вводятся ТВ-сплайны и самодвойственный вейвлет. Следуя В.А.Желудеву [140], введем понятие ТВ-сплайна. Сплайн с/? € 8™ называется ТВ-сплайном, если его сдвиги

I = 0,. ,т — 1, (71) образуют базис 8™.

Теорема 13. Сплайн т—1 (72) к=0 является ТВ-сплайном тогда и только тогда, когда все ф 0.

Два отцовских вейвлета (р^) и ч/^') называются двойственными, если при Л Е 0 : т — 1

Теорема 14. Если ТВ-сплайн задан формулой (72), а ТВтп—1 сплайн ф—формулой ф(з) = X] Ш^С?)* то (риф являются двойка ственными тогда и только тогда, когда ш—1 ^ ~ А; = 0,.,т — 1. (73)

ТТЬ к=0

Очевидно, что существует бесчисленное множество двойственных базисов, полученных с помощью сдвигов двух двойственных ТВ-сплайнов <р и ф. Три случая отметим особо:

1) В-сплайн. Этот случай получается при = 1, к Е 0 : т — 1.

2)Вейвлет, двойственный к В-сплайну—при щ = т^]]^]]"2.

3)Самодвойственный вейвлет — при = Ш = т-1/2!)/^)!-1. Сдвиги этого вейвлета образуют ортонормированный базис в 8™.

28

В главе 4 предлагается общая лифтинговая схема построения базисных функций ф, ф, сдвиги которых образуют биортогональ-ные базисы в пространстве Сдг всех TV-периодических сигналов. Построение ведется в общем виде, не привязываясь к дискретным сплайнам. Лишь в §4 появляюся сплайн-вейвлеты как частный случай общей теории. В непрерывном случае аналогичные схемы рассматривал Свелденс [132].

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

Строятся также прямой и двойственный лифтинговый алгоритмы для быстрого получения коэффициентов разложения по базисам. В итоге получаем быстрое вейвлетное преобразование сигнала. Это преобразование можно записать с использованием фильтров высоких и низких частот [134]. В главе 4 преобразование выполняется в "лиф-тинговой" форме [133], что допускает эффективную компьютерную реализацию. Как и в других лифтинговых схемах, вычисления выполняются "на месте" (в одном массиве), а обратное преобразование заключается в выполнении действий в обратном порядке. Отличие от других лифтинговых схем состоит в том, что вычисления ведутся в частотной области с использованием быстрого дискретного преобразования Фурье.

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

В §4 строится конструкция биортогональных вейвлетов, основанная на интерполяции дискретными периодическими сплайнами [54]. Для данного сигнала z(k), к Е 0 : N — 1, где N является степенью двойки: N = 2*, рассмотрим четный и нечетный подмассивы массива 2: е(к) = z(2k), к Е 0 : т - 1; d(k) = z(2k + 1), к Е 0 : т - 1; т = N/2. При построении вейвлетных схем используем четный массив, чтобы

29 предсказать значения нечетного на основе интерполяции дискретными ^-периодическими сплайнами. Эта схема идейно близка к схеме, реализованной в [141], где были использованы непрерывные интерполяционные сплайны.

Рекурсивная реализация лифтингового алгоритма предложена в §5. Рассмотрим эту реализацию подробнее.

Алгоритм декомпозиции сигнала х £ Сдг при N = 2Агх заключается в нахождении векторов ДПФ которых определяется по формулам где мл = 1 + 1 - ад», ш = «#(1 - ад)), * = ы*)

ДПФ исходного сигнала х.

Формула (74) может быть реализована следующим образом. Найдем у = З^^Х). Тогда ё\(к) = у{2к), к Е 0 : Щ — 1. Таким образом надо реализовать оператор ж и- у.

Когда ^О) является дробно-рациональной функцией от со^, то эффективными оказываются алгоритмы, основанные на разложении числителя и знаменателя рациональной дроби на множители.

Идею таких алгоритмов объясним в самом простом случае г = 2,

МЛ = \ [ ЧЛШ + ки + + М)], (74)

МЛ = I ЫЛх(Л + 01 С? + Юхи + , (75)

АО') = \Uiti), где

76)

Перейдем к переменной г = = е2жг^н\ 1

Подставив в (76) получим

30

Уравнение х1 + + 1 = 0 имеет корни —а и — 1/а, где а = 3 - 2^2 = 0.172. Получим

В непрерывном случае А.П. Петухов ([79], с. 91) рекомендовал оставлять в знаменателе множители типа 1 + асо^).

Оператор, соответствующий умножению Х(у) на к^), реализуется в виде композиции операторов трех типов:

1) Оператор сдвига Я на одну позицию: (5ж)(&) = х(к + 1). Тогда (,81х)(к) = х(к + I) для любого целого I. Умножение на (со^ — I)4 означает применение оператора (5 — I)4, т.е. — 1)4Х(.?)) = х(к + 4) — Ах (к + 3) + 6х(к + 2) — 4х(к — 1) + х(к)—конечная разность 4-го порядка Здесь предполагается, что за пределы диапазона 0.7У — 1 сигнал х продолжен ТУ-периодически: + к) = х(к).

2) Оператор Ра, соответствующий умножению на функцию

3) Оператор соответствующий умножению на функцию

Справедливо равенство у = Э^^чХ) = {/ + 2а(5 + 5-1)5-2(5 - 1)4Р2Я2а}х. (77)

Операторы Ра и а можно реализовать с помощью элементарных рекурсивных фильтров.

Теорема 15. Оператор у = Рах = X = ^^(х)—ДПФ от х, реализуется в виде элементарного рекурсивного фильтра у{к) = -ау(к - 2) + х(к), к = 2,3,., N - 1, (78) где начальные значения у(0) и у( 1) определяются по формуле

N1-1 у(г) = С х(г) + ]П х(Ы + г - 2т)(-а)т г = 0, 1,

79) т=1 где С = 1/(1 - ^ = N/2.

31

Рассмотрим теперь оператор фа, соответствующий умножению Х(з) на 1/(1+

Теорема 16. Оператор у = С2ах = + аш2^)), где

X = —ДПФ от х, реализуется в виде "обратного" рекурсивного фильтра у{к) = —ау{к + 2) + х(к), к = N - 3, N - 4,., 0, (80) где начальные значения у(М — 1) и у(N — 2) определяются по формуле

N1-1 у (г) = С х(г) + X х{г — 2 т)(—а)

Щ-т, т=1 = N -1, N -2.

81)

Аналогично реализуется фильтр д\{з) = ^(1 —

--а г (г — I)4 ашх3 (ш3м - I)4

910')

2(1 + <*г-2)(1 + а*2) (1 + +

Оператор, соответствующий умножению Х^) на реализуется в виде у = ЭЖГгХ) = аБ-^в - 1)4РаЯах, (82) где операторы Ра, Ц0 - те же, что и выше, способ их реализации указан в теоремах 15 и 16.

Темой главы 5 являются сплайны многих переменных, в основном натуральные сплайны. Термин "натуральные" указывает на то, что рассматриваемые сплайны являются решением вариационных задач специального вида.

§§1-4 и п. 1, 2 в §5 носят вводный характер. Центральное место здесь занимает следующая задача. В пространстве Мп даны т произвольно расположенных точек Хг-, ¿61: т, в которых заданы значения функции Хг = /(А";), г 6 1 : т. Требуется построить наиболее плавную функцию 5р£) такую, что г £ 1 : т.

В §5 " наиболее плавной" считается функция, доставляющая минимум в следующей задаче:

V 4 [ Шад)2(1Х ппп ,

9 №)=«!>

83)

32 где Dag — частная производная порядка г от функции д. Минимум (при четном п) достигается на функции ш

S(X) = Qri (X) + diG(X - Xi). (84) г=1 где Qr-г — полином степени < г — 1, G(X) = ||X||2r~nln ||Х||. Этот результат впервые получил Ж. Дюшон [144, 145]. Автором дано новое доказательство, использующее теорему C.JL Соболева о плотности бесконечно дифференцируемых финитных функций в пространстве L^ (Кп). Необходимый подготовительный материал для доказательства изложен в §4.

В приложениях многомерных сплайнов наиболее распространенным является случай п = г — 2. Тогда минимизируемый функционал записывается в виде где А — оператор Лапласа. Сплайны (84) при г = п = 2 используются в геологии для аппроксимации поверхностей месторождений ([17, 37]), в гидрологии и метеорологии — для черчения карт на ЭВМ, для определения формы упругих пластин с точечными опорами и во многих других случаях, когда требуется аппроксимировать поверхности или исследовать пространственную изменчивость изучаемых свойств. Практические примеры приведены в книге М.И. Игнатова, А.Б. Пев-ного [41].

Отметим задачи, в решении которых вклад автора наиболее существен.

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

L(/)=max/(X), (85) где fi — фиксированный компакт в Жп, решается в §5, п. 3, 4. Введем оператор Т, который функции / G 4г)(]Г) ставит в соответствие

33 набор производных r-го порядка

Tf

Класс W задается в виде

W = {f € L<r)(Rn) :||T/||2 < М2},

86) L г) где М — фиксированное число. Информация // о функции / € 1) — это значения функции в т фиксированных точках Хг £ЁП: = (/№),.,/ад).

Методы восстановления будут определяться функциями Ф(yi,., ут) (считаем, что L(f) & $(/(Xi),. ,f(Xm))). На функции Ф наложим ограничение Ф(0,., 0) = 0, в остальном функции Ф произвольны (их будем называть алгоритмами).

Задача состоит в нахождении алгоритма, имеющего наименьшую погрешность R на классе W:

R = inf sup |L(f) - Ф(/(Х0,., /(Xm))|, ф few где инфимум берется по всем алгоритмам Ф, удовлетворяющим условию Ф(О) = 0.

Следующая теорема установлена в работе автора [69], там же можно найти ссылки на одномерный вариант задачи.

Теорема 17. Оптимальным методом восстановления функционала (85) на классе W является метод

Далее оптимально находится максимум без предположения Ф(О) = 0. Рассмотрим снова задачу оптимального восстановления функционала (85) на классе W. Требуется найти

Д, = inf sup \L(f) - Ф(//)|, ф few где инфимум берется по всем алгоритмам Ф (без всяких дополнительных условий). Здесь

If = (f(X1),.,f(Xm)), где Xi — фиксированные точки компакта Q.

34

Теорема 18. Пусть г > 3, 2r > п, Q — выпуклый компакт в Rn. Тогда оптимальным алгоритмом восстановления функционала (85) на классе (5.23) является сплайновый алгоритм

L(/)«max5(/;X) = L(5(/)).

Теорема справедлива при г > 3. При г = 1, 2 сплайновый метод уже не будет оптимальным.

2) В случае, когда значения Z{ — f(X{) задаются с погрешностями, целесообразно рассматривать сглаживающие натуральные сплайны (§6). Предлагается эффективный метод решения задачи сглаживания (§7). Подробно выписан каждый шаг алгоритма решения задачи сглаживания.

3) В §8 вводятся степенные сплайны вида N

S(X) = Qo(X) + dk\\X - Xk\f, (87) к=1 где Q0 G ||Х|| = /3 = 2r + a, a G (0, 2), a dk удовлетворяет условиям N dkQ(Xk) = 0 VQeOV (88) к=1

Здесь Хк — фиксированные попарно различные точки из Мп. Функции вида (87) с коэффициентами dk, удовлетворяющими (88), будем называть степенными сплайнами.

Рассмотрим интерполяционную задачу для степенных сплайнов N

S(Xj) = Qo(Xj) + - xkf = yj: j el: N. k=1

В следующей теореме устанавливается свойство матрицы А с элементами Ajk — \\Xj — XkW13, позволяющее легко доказать однозначную разрешимость интерполяционной задачи. Множество векторов d = ((¿1,., djv), удовлетворяющих (88), образует подпространство в R^: N

Dr = {deRN : = 0 к=1

35

Напомним также обозначение (.X, £) = х16 +. + хп£п для скалярного произведения векторов X, £ € Мп.

Теорема 19. Пусть ¡3 = 2г + а, 0 < а < 2, г = 0,1, 2,. Для любого й Е справедливо равенство

Hill n-ß N к=1 N dt = (-l)r+1cßn £ dA\\xj - (89) j,k=l где i = V'-l, cßn положительная константа.

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

Пусть г, п — натуральные числа.

Теорема 20. Зафиксируем ., Xдг — попарно различные точки из Для любого д = (с?1,., ¿н) из подпространства справедливо равенство

Hill'

-п—2г N к=1 лг j,k=1

90) где с, т положительная постоянная.

5) В §10 рассматриваются натуральные сплайны, заданные на сфере. Натуральные сферические сплайны рассматривались в работе В. Фридена [149]. Они имеют приложения к задаче аппроксимации гравитационного потенциала Земли. В §10 рассматривается новый вариант натуральных сферических сплайнов.

Длину вектора £ = (6,6,6) обозначим |£| = л/й + й + й- Вве" дем единичную сферу ^ = {£ : |£| = 1}. Пусть в точках щ,., щ € ^

36 заданы значения у\,. ,у я- Требуется определить наиболее плавную функцию 5(£) на сфере, такую, что 5(7^) = у^ г € 1 : N.

Вектор х ф О представим в виде х = где р = £ = х/р. Положение точки £ е ^ определим сферическими координатами (в, ф). Оператор Лапласа в сферических координатах записываем в виде

1 д(2д\ 1 где

1 9 I • Пд \ 1 д2 вшвдв дв / вш2 в дф2 оператор Бельтрами. В качестве "функционала плавности" возьмем интеграл где Лш — элемент поверхности сферы = вш г > 0 — фиксированное число, и рассмотрим задачу минимизации ея2г(П)

91)

В работе В. Фридена [149] рассматривался другой "функционал плавности , а именно о

Д^ + А0)(А^ + А1)(А^ + Хт)/]Чсо, Хк = к (к + 1).

Для решения задачи (91) нужно построить функцию Грина оператора (—А^)2г. Положим

1 00

2п + 1

4тг^ Х2г п=1 "

РпШ где Рп - полиномы Лежандра, ^-скалярное произведение векторов £ и г], Хп = п(п + 1).

Натуральным сферическим сплайном будем называть функцию N к=1 при условии, ЧТО 1 = О

37

Теорема 21. Пусть точки £ ^ попарно различны.

Тогда интерполяционная задача Б{г}() = у г, г 6 1 : Я, однозначно разрешима при любых у^.

Обозначим натуральный сплайн, такой, что 5*(?7^) = г £ 1 : N. Теорема 22. Единственным решением задачи (91) является 51*.

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

• Нестационарный кратномасштабный анализ в пространстве квадратично суммируемых сигналов (гл. 1).

• Лифтинговый алгоритм декомпозиции и реконструкции сигналов и его рекурсивная реализация, которая дает возможность находить коэффициенты вейвлетного разложения сигнала за 0(ТУ) операций, где N - длина сигнала (§§2-3 главы 2).

• Применение сплайн-операционного метода к решению задачи сглаживания с помощью дискретных периодических сплайнов и к решению задачи о бесконечной цилиндрической оболочке с помощью дискретных периодических сплайнов (§§4-5 главы 3).

• Общая схема построения биортогональных базисов в пространстве

Сдг всех N - периодических сигналов, лифтинговый алгоритм получения коэффициентов разложения по этим базисам (§§1-2 главы

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

• Использование натуральных сплайнов п переменных для решения следующих задач: задач£ оптимального нахождения максимума тах^еп/РО, где О, - фиксированный компакт в Еп (оптимальным оказывается сплайновый алгоритм — см. п. 3,4 §5 главы 5); решение задачи сглаживания в многомерном случае (§§6-7 главы

5).

• Построение теории степенных сплайнов п переменных. Доказательство интегрального тождества для таких сплайнов. Аналогичная теория для логарифмических сплайнов (§§8-9 главы 5). Один вариант теории сферических сплайнов и свойство минимальной нормы для них (§10 главы 5).

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

Отдельные результаты работы докладывались на семинарах кафедры исследования операций С.-Петербургского ун-та (рук. проф. В.Н. Малоземов), на С.-Петербургском городском семинаре по конструктивной теории функций (рук. проф. Г.И. Натансон), на международной конференции " Optimization of finite-element approximations" (С.-Петербург, 1995 г.), на международной конференции, посвященной 175-летию П.Л. Чебышева (Москва, 1996 г.), на конференции "3rd St. Petersburg Workshop on Simulation" (С.-Петербург, 1998 г.), на 2-й международной конференции "Tools for Math. Modelling" (С.Петербург, 1999 г.), на международной конференции "Optimization of finite-element approximations, splines and wavelets" (С.-Петербург, 2001 г.), на С.-Петербургском городском семинаре "Всплески и их приложения" (рук. проф. Ю.К. Демьянович, В.Н. Малоземов, А.П. Петухов и М.А. Скопина), на семинаре отдела теории функций Института математики и механики Уральского отд. РАН (рук. чл.-корр. РАН Ю.Н. Субботин), на семинаре кафедры вычислительной математики МГУ (рук. акад. РАН Н.С. Бахвалов), на семинаре по вычислительной математике ИВМиМГ СО РАН и НГУ (рук. проф. В.П. Ильин), на семинаре отдела сплайн-функций Института математики Сибирского отд. РАН (рук. проф. B.JI. Мирошниченко), на ежегодных Февральских чтениях Сыктывкарского государственного университета.

Основные результаты диссертации опубликованы в работах [37, 38, 39, 40, 41, 67, 68, 69, 70, 71, 72, 73, 74, 53, 76, 77, 120, 32, 33, 34, 121, 122].

Ряд работ [37, 38, 39, 40, 41, 53, 120, 32, 33, 34, 121, 122] выполнен совместно с В.А. Желудевым, М.И. Игнатовым, В.Н. Малоземовым. В. А. Желудеву в этих работах принадлежит участие в постановках задач и окончательное редактирование статей [120, 32, 33, 34, 121, 122], а также некоторые теоретические результаты (теорема 1.1 и лемма 1.4 главы 1 установлены В.А. Желудевым). М.И. Игнатову принадлежит программная реализация и численные примеры в работах

39

37, 38, 39, 40, 41]. Из статьи с В.Н. Малоземовым [53] взято определение дискретного периодического В-сплайна. Учебное пособие [52] использовалось для ссылок на известные результаты.

40

Список литературы диссертационного исследования доктор физико-математических наук Певный, Александр Борисович, 2002 год

1. Астафьева Н.М. Вейвлет-анализ: основы теории и примеры применения // Успехи физических наук. 1996. Т. 166. N11.0. 1145-1170.

2. Бахвалов Н.С. Численные методы. М. : Наука, 1973. 632 с.

3. Бер М.Г. Дискретные сплайны и задача восстановления дискретных данных. Дисс—канд. физ.-матем. наук. Л.: Ле-нингр. ун-т, 1990. 140 с.

4. Бер М.Г., Малоземов В.Н. Наилучшие формулы для приближенного вычисления ДПФ//Ж. вычисл. матем. и матем. физ. 1992. Т. 32. N И. С. 1709-1719.

5. Бер М.Г., Малоземов В.Н. О восстановлении дискретных периодических данных//Вестн. ЛГУ. Сер.1. 1990. Вып. 3. С. 8-13.

6. Бердышев В. И., Петрак Л. В. Аппроксимация функций. Сжатие численной информации. Приложения. Екатеринбург, 1999. Глава I, раздел 12. Всплески. С. 127-150.]

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

8. Берколайко М.З., Новиков И.Я. О бесконечно гладких почти-всплесках с компактным носителем//Мат. заметки. 1994. Т. 56. N 3. С. 3-12.

9. Бернштейн С.Н. Абсолютно монотонные функции// Собр. соч. М.: Изд-во АН СССР, 1952. Т. 1. С. 5-7.

10. Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов. М.:Мир, 1989.

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

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

13. Василенко В.А., Зюзин М.В., Ковалков A.B. Сплайн-функции и цифровые фильтры. Новосибирск: Изд-во ВЦ СО АН СССР, 1984. 156 с.

14. Вершик A.M., Малоземов В.Н., Певный A.B. Наилучшая кусочно-полиномиальная аппроксимация//Сиб. мат. журн. 1975. Т.16. N 5. С. 925-938.

15. Вершинин В.В., Завьялов Ю.С., Павлов H.H. Экстремальные свойства сплайнов и задача сглаживания. Новосибирск: Наука, 1988. 102 с.

16. Владимиров B.C. Уравнения математической физики. М.: Наука, 1981. 512 с.

17. Волков A.M. Решение практических задач геологии на ЭВМ. М.: Недра, 1980. 224 с.

18. Воеводин В.В., Тыртышников Е.Е. Вычислительные процессы с теплицевыми матрицами. М.: Наука, 1987. 320 с.

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

20. Воскобойников Ю.Е., Преображенский Н.Г., Седельников А.И. Математическая обработка эксперимента в молекулярной газодинамике. Новосибирск: Наука, 1984. 239 с.

21. Гавурин М.К., Малоземов В.Н. Экстремальные задачи с линейными ограничениями. Л.: Изд-во ЛГУ, 1984. 176 с.

22. Гельфанд И.М., Шилов Г.Е. Обобщенные функции и действия над ними. М.: ГИФМЛ, 1958. 440 с.

23. Гордонова В.И., Морозов В.А. Численные алгоритмы выбора параметра в методе регуляризации//Журн. вычисл. математики и мат. физики. 1973. Т. 13. N 3. С. 539-545.

24. Гребенников А.И. Метод сплайнов и решение некорректных задач теории приближения. М.: Изд-во МГУ, 1983. 208 с.

25. Добеши И. Десять лекций по вейвлетам. Ижевск: НИЦ "Регулярная и хаотическая динамика", 2001. 464 с.259

26. Дремин И. М., Иванов О. В., Нечитайло В. А. Вейвлеты и их использование // Успехи физических наук. 2001. Т. 171. N 5. С. 465-561.

27. Дьяконов В.П., Абраменкова И.В. MATLAB. Обработка сигналов и изображений. Специальный справочник. Изд-во "Питер", 2002. Гл. 5. Wavelet Toolbox]

28. Желудев В.А. Периодические сплайны и быстрое преобразование Фурье// Ж. вычисл. матем. и матем. физ. 1992. Т.32. N 2. С. 1296-1309.

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

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

31. Желудев В.А., Певный A.B. Кардинальная интерполяция дискретными сплайнами // Вестник Сыктывкар ун-та. Сер. 1. 1999. Вып. 3. С. 159-172.

32. Желудев В.А., Певный A.B. Лифтинговые схемы для вейвлет-ного преобразования дискретных сигналов // Вестник Сыктывкар. ун-та. Сер. 1. 2001. Вып. 4. С. 137-156.

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

34. Желудев В.А., Певный А.Б. Вейвлетное преобразование Бат-терворта и его реализация с помощью рекурсивных фильтров// Ж. вычисл. матем. и матем. физ. 2002. Т.42. N 4. С. 607-618.

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

36. Игнатов М.И. Метод построения сглаживающих сплайнов одной переменной. Сыктывкар, 1988. 19 с. (Препринт Коми научного центра УрО АН СССР. "Автоматизация научных исследований". Вып. 14).

37. Игнатов М.И., Певный А.Б. Аппроксимация геологических поверхностей сглаживающими натуральными сплайнами с учетом элементов залегания//Методы и алгоритмы подсчета запасов нефтяных месторождений: Тр. Ин-та геологии КФАН. Сыктывкар, 1986. С. 20-35.

38. Игнатов М.И., Певный А.Б. Сплайн-аппроксимация плавных поверхностей. Сыктывкар, 1986. 20 с. (Препринт Коми филиала АН СССР. Сер. "Научные доклады". Вып. 149).

39. Игнатов М.И., Певный А.Б. Решение задачи сглаживания экспериментальных данных в многомерном случае//Вопросы теории и практики создания региональных автоматизированных систем: Тр. Коми научного центра УрО АН СССР. Сыктывкар, 1988. С. 94-112.

40. Игнатов М.И., Певный А.Б. Метод Райнша для решения задачи сглаживания в многомерном случае// Журн. вычисл. математики и мат. физики. 1990. Т.ЗО. N 2. С. 186-192.

41. Игнатов М.И., Певный А.Б. Натуральные сплайны многих переменных. Л.:Наука, 1991.

42. Каппелини В. и др. Цифровые фильтры и их применение. М.: Энергоатомиздат, 1983.

43. Кашин Б. С., Саакян А. А. Ортогональные ряды. М.: АФЦ, 1999. Глава 7. Введение в теорию всплесков. С. 244-296.]

44. Кирушев В. А. Быстрый алгоритм сжатия изображений // Вестник молодых ученых. Прикл. матем. и механика. 1997. N 1. С. 4-10.

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

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

47. Макклеллан Дж.Х.,Рейдер Ч.М. Применение теории чисел в цифровой обработке сигналов. М.: Радио и связь, 1983.

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

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

50. Малоземов В. Н., Машарский С. М. Хааровские спектры дискретных сверток // Ж. вычисл. мат. и матем. физ. 2000. Т. 40. N 6. С. 954-960.

51. Малоземов В. Н., Машарский С. М. Формула Глассмана, быстрое преобразование Фурье и вейвлетные разложения // Электронный архив препринтов СПбМО. Препринт N 200105.

52. Малоземов В.Н., Певный A.B. Полиномиальные сплайны. Л.: Изд-во ЛГУ, 1986. 120 с.

53. Малоземов В.Н., Певный А.Б. Дискретные периодические В-сплайны// Вестник СПбГУ. Сер. 1. 1997. Вып. 4 (N 19). С. 14-19.

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

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

56. Малоземов В.Н., Сергеев А.Н. Дискретные непериодические сплайны на равномерной сетке//Тр. С.-Петербург, матем. об-ва. 2000. Т. 8. С. 199-213.

57. Малоземов В.Н., Третьяков A.A. Алгоритм Кули-Тьюки и дискретное преобразование Хаара // Вестник СПбГУ. Сер. 1. 1998. Вып. 3 (N 15). С. 31-34.

58. Малоземов В.Н., Третьяков A.A. Новый подход к алгоритму Кули-Тьюки // Вестник СПбГУ. Сер. 1. 1997. Вып. 3 (N 15). С. 57-60.

59. Малоземов В.Н., Третьяков A.A. Секционирование, ортогональность и перестановки // Вестник СПбГУ. Сер. 1. 1999. Вып. 1 (N 1). С. 16-21.

60. Машарский С.М. Свертка и корреляция дискретных сигналов в базисах Хаара Крестенсона // Вестник молодых ученых. Прикл. матем. и механика. 2000. N 4. С. 31-40.

61. Машарский С.М. Автореверсные спектры Хаара Крестенсона // Вестник СПбГУ. Сер. 1. 2001. Вып. 2 (N 9). С. 57-65.

62. Морозов В.А. Регулярные методы решения некорректно поставленных задач. М.: Наука, 1987. 240 с.

63. Натансон И.П. Конструктивная теория функций. M.-JL: ГИТТЛ, 1949. 688 с.

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

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

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

67. Певный А.Б. Об оптимальных стратегиях поиска максимума функций с ограниченной старшей производной//Журн. вычисл. математики и мат. физики. 1982. Т. 22. N 5. С. 1061-1066.263

68. Певный A.B. Натуральные сплайны двух и трех переменных// Методы вычислений, вып. 14. Л.: Изд-во ЛГУ, 1985. С. 160— 170.

69. Певный A.B. Об оптимальности некоторых сплайновых алгоритмов// Изв. вузов. Математика. 1986. N 5. С. 6-12.

70. Певный A.B. Оптимальность сплайнового алгоритма при нахождении максимума одного класса функций многих переменных/ /Журн. вычисл. математики и мат. физики. 1988. Т. 28. N 1. С. 130-134.

71. Певный A.B. Шкала степенных сплайнов// Методы вычислений, вып. 15. Л.: Изд-во ЛГУ, 1988. С. 136-141.

72. Певный A.B. Некоторые интегральные тождества связанные со сплайнами п переменных//Изв. вузов. Математика. 1989. N 4. С. 51-55.

73. Певный A.B. Многомерные натуральные сплайны нечетной степени//Матем. заметки. 1990. Т. 47. Вып. 2. С. 65-68.

74. Певный A.B. Сферические сплайны и интерполирование на сфере// Журн. вычисл. математики и мат. физики. 1995. Т.35. N 1. С. 130-134.

75. Певный A.B. Оптимальные стратегии помска максимума функций класса W// Вестн. С.-Петербург, ун-та. Сер. 1. 1995. Вып. 3 (N 15). С. 48-53.

76. Певный A.B. Дискретные периодические сплайны и решение задачи о бесконечной цилиндрической оболочке//Вестник Сыктывкар, ун-та. Сер.1. 1996. Вып. 2. С. 187-200.

77. Певный A.B. Интерполяция дискретными сплайнами с равноотстоящими узлами //Алгебра и анализ. 1998. Т. 10. N 6. С. 186-197.

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

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

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

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

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

83. Пласкота J1. Оптимальная линейная информация в задаче восстановления глобального максимума вещественной функ-ции//Журн. вычисл. математики и мат. физики. 1986. Т.26. N 6. С. 934-938.

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

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

86. Смоляк С.А. Оптимальное восстановление функций и связанные с ним геометрические характеристики множеств//Тр. III зимней школы по мат. программированию. М.: Изд-во ЦЭМИ АН СССР, 1971. С. 509-557.

87. Смоляк С.А. Сплайны и их применение//Экономика и мат. методы. 1971. N 2. С. 419-431.

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

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

90. Субботин Ю.Н. О связи между конечными разностями и соответствующими производными// Труды МИ АН. 1965. Т. 78. С. 24-44.265

91. Субботин Ю.Н. Функциональная интерполяция в среднем с наименьшей n-ой производной// Труды МИАН. 1967. Т. 88. С. 30-60.

92. Субботин Ю.Н. Экстремальные задачи функциональной интерполяции и интерполяционные в среднем сплайны// Труды МИАН. 1975. Т. 138. С. 118-173.

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

94. Трауб Дж., Вожьняковский X. Общая теория оптимальных алгоритмов. М.: Мир, 1983. 382 с.

95. Треногин В.А. Функциональный анализ. М.: Наука, 1980. 496 с.

96. Уилкинсон Д., Райнш К. Справочник алгоритмов на языке АЛГОЛ: Линейная алгебра. М.: Машиностроение, 1976. 392 с.

97. Фокс А., ПраттМ. Вычислительная геометрия. М.: Мир, 1982. 304 с.

98. Умняшкин C.B. Компрессия цифровых изображений на основе кодирования древовидных структур вейвлет коэффициентов с прогнозированием статистических моделей // Изв. вузов. Электроника. 2001. N 5.

99. Харатишвили Н. Г. Пирамидальное кодирование. М.: Мысль, 1997. 160 с.

100. Харатишвили Н. Г., Чхеидзе И. М., Ронсен Д., Инджия Ф. И. Пирамидальное кодирование изображений. М.: Радио и связь, 1996. 192 с.

101. Чуй К. Введение в вэйвлеты. М.: Мир, 2001. 413 с.

102. Said A., W.A.Pearlman. A new fast and efficient image codec based on set partitioning in hierarchical trees//IEEE Trans, on Circuits and Systems for Video Technology. 1996. V. 6. N 3. P. 243-250.

103. Schoenberg I.J. Cardinal spline interpolation. CBMS, V. 12. Philadelphia: SIAM, 1973.