Белорусский государственный университет

Факультет прикладной математики и информатики

Кафедра математической физики

ГРОМОВА МАРИЯ МИХАЙЛОВНА

ОПРЕАТОРЫ В ВЕЙВЛЕТНОМ БАЗИСЕ

Курсовая работа студентки 4 курса

Научный руководитель:

Глушцов Анатолий Ильич кафедры МФ кандидат физ.-мат. наук

Минск 2004

СОДЕРЖАНИЕ

ВВЕДЕНИЕ………..………………………………………………………..3

1. МНОГОМАСШТАБНЫЙ АНАЛИЗ И ВЕЙВЛЕТЫ………………...5

2. БЫСТРОЕ ВЕЙВЛЕТ-ПРЕОБРАЗОВАНИЕ….……………………...9

3. ДВУМЕРНЫЕ ВЕЙВЛЕТЫ…………………………………………..12

4. МАТРИЧНЫЕ ОПЕРАЦИИ………………………………………….13

4.1. Матричное умножение………………………………………...13

4.2. Обращение матрицы…………………………………………...16

4.3. Вычисление экспоненты, синуса и косинуса от матрицы.….16

ЛИТЕРАТУРА……………………………………………………………18

ВВЕДЕНИЕ

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

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

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

Что прежде всего отличает вейвлет-анализ от анализа Фурье? Основным недостатком Фурье-преобразования является его "глобальная" чувствительность к "локальным" скачкам и пикам функции. При этом модификация коэффициентов
Фурье (например, обрезание высоких гармоник с целью фильтрации шума) вносит одинаковые изменения в поведение сигнала на всей области определения. Это особенность оказывается полезной для стационарных сигналов, свойства которых в целом мало меняются со временем.

При исследовании же нестационарных сигналов требуется использование некоторых локализованных во времени компактных волн, коэффициенты разложения по которым сохраняют информацию о дрейфе параметров аппроксимируемой функции. Первые попытки построения таких систем функций сводились к сегментированию сигнала на фрагменты ("окна") с применением разложения Фурье для этих фрагментов. Соответствующее преобразование - оконное преобразование Фурье - было предложено в 1946-47 годах Jean Ville и, независимо, Dennis Gabor. В 1950-70-х годах разными авторами было опубликовано много модификаций времени-частотных представлений сигналов.

В конце 70-х инженер-геофизик Морли (Jean Morlet) столкнулся с проблемой анализа сигналов, которые характеризовались высокочастотной компонентой в течение короткого промежутка времени и низкочастотными колебаниями при рассмотрении больших временных масштабов. Оконные преобразования позволяли проанализировать либо высокие частоты в коротком окне времени, либо низкочастотную компоненту, но не оба колебания одновременно. В результате был предложен подход, в котором для различных диапазонов частот использовались временные окна различной длительности.
Оконные функции получались в результате растяжения-сжатия и смещения по времени гаусиана. Морли назвал эти базисные функции вейвлетами (wavelets) - компактными волнами. В дальнейшем благодаря работам Мейера (Yves Meyer),
Добеши (Ingrid Daubechies), Койфмана (Ronald Coifman), Маллы (Stephane
Mallat) и других теория вейвлетов приобрела свое современное состояние.

Среди российских ученых, работавших в области теории вейвлетов, необходимо отметить С.Б. Стечкина, И.Я. Новикова, В.И. Бердышева.

1. МНОГОМАСШТАБНЫЙ АНАЛИЗ И ВЕЙВЛЕТЫ

Определение 1. Многомасштабный анализ (multiresolutional analysis) – разложение гильбертова пространства L2(Rd), d(1, в последовательность замкнутых подпространств

[pic],

(1.1) обладающих следующими свойствами:
1. [pic], и [pic] полно в L2(Rd),

2. Для любого f( L2(Rd), для любого j( Z, f(x)(Vj тогда и только тогда, когда f(2x) (Vj-1,
3. Для любого f( L2(Rd), для любого k( Zd, f(x)(V0 тогда и только тогда, когда f(x-k)(V0,
4. Существует масштабирующая (scaling) функция ((V0, что {((x-k)}k(Zd образует базис Ритца в V0.
Для ортонормальных базисов можно переписать свойство 4 в виде:
4’. Существует масштабирующая функция ((V0, что {((x-k)}k(Zd образует ортонормальный базис в V0.
Определим подпространство Wj как ортогональное дополнение к Vj в Vj-1,

[pic],

(1.2) и представим пространство L2(Rd) в виде прямой суммы

[pic]

(1.3)

Выбирая масштаб n, можем заменить последовательность (1.1) следующей последовательностью:

[pic]

(1.4) и получить

[pic]

(1.5)

Если имеем конечное число масштабов, то, не нарушая общности, можно положить j=0 и рассматривать

[pic], V0( L2(Rd)

(1.6) вместо (1.4). В числовой реализации подпространство V0 конечномерно.

Функция ( - так называемая масштабирующая (скейлинг-) функция. С ее помощью можно определить функцию ( - вейвлет - такую, что набор {((x- k)}k(Z образует ортонормальный базис в W0. Тогда

[pic], m=0..M-1.

(1.7)
Из свойства 4’ непосредственно следует, что, во-первых, функция ( может быть представлена в виде линейной комбинации базисных функций пространства
V-1 . Так как функции {(j,k(x)=2-j/2((2-jx-k)}k(Z образуют ортонормальный базис в Vj, то имеем

[pic].

(1.8)
Вообще говоря, сумма в выражении (1.8) не обязана быть конечной. Можно переписать (1.8) в виде

[pic],

(1.9) где

[pic],

(1.10) а 2(-периодическая функция m0 определяется следующим образом:

[pic].

(1.11)

Во-вторых, ортогональность {((x-k)}k(Z подразумевает, что

[pic]
(1.12) и значит

[pic]

(1.13) и [pic].

(1.14)
Используя (1.9), получаем

[pic]

(1.15) и, рассматривая сумму в (1.15) по четным и нечетным индексам, имеем

[pic]. (1.16)
Используя 2(-периодичность функции m0 и (1.14), после замены (/2 на (, получаем необходимое условие

[pic]

(1.17) для коэффициентов hk в (1.11). Заметив, что

[pic]

(1.18) и определив функцию ( следующим образом:

[pic],

(1.19) где

[pic], k=0,…,L-1 ,

(1.20) или преобразование Фурье для (

[pic],

(1.21) где

[pic],

(1.22) можно показать, что при каждом фиксированном масштабе j(Z вейвлеты
{(j,k(x)=2-j/2((2-jx-k)}k(Z образуют ортонормальный базис пространства Wj.

Равенство (1.17) определяет пару квадратурных зеркальных фильтров
(quadrature mirror filters, QMF) H и G, где [pic] и [pic]. Коэффициенты QMF
H и G вычисляются с помощью решения системы алгебраических уравнений. Число
L коэффициентов фильтра в (1.11) и (1.22) связано с числом исчезающих моментов М, и всегда четно.

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

4. ОПЕРАТОРЫ

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

Нестандартная форма оператора Т с ядром K(x,y) достигается вычислением следующих выражений:

[pic]

(4.1)

[pic]

(4.2)

[pic]

(4.3)

4.1 Оператор d/dx в вейвлетном базисе

Нестандартные формы некоторых часто используемых операторов могут быть вычислены явно. Построим нестандартную форму оператора d/dx. Матричные элементы [pic], [pic], [pic] матриц [pic], [pic], [pic] и [pic] матрицы
[pic], где i, l, j( Z для оператора d/dx легко вычисляются как

[pic] (4.4)

[pic] (4.5)

[pic] (4.6)

[pic] (4.7) где

[pic]

(4.8)

[pic]

(4.9)

[pic]

(4.10)

[pic]

(4.11)
Кроме того, используя (1.8) и (1.19), имеем

[pic]

(4.12)

[pic]

(4.13)

[pic]

(4.14)
Таким образом представление d/dx полностью определяется величинами [pic] или, другими словами, отображением d/dx на подпространство V0.
Предложение 4.1. 1. Если существует интеграл (4.11), тогда коэффициенты
[pic], l( Z в (5.8) удлвлетворяют следующей системе линейных алгебраических уравнений:

[pic]

(4.15)

[pic]

(4.16) где

[pic] [pic]

(4.17)
2. Если [pic], тогда система (4.15)-(4.16) имеет единственное решение с конечным числом ненулевых [pic], а именно с [pic] и [pic].
Замечание. Если М=1, тогда система (4.15)-(4.16) имеет единственное решение, но интеграл (4.11) может не быть абсолютно сходящимся. Для базиса
Хаара ([pic]) [pic], [pic] мы получаем простейший конечный дифференциальный оператор [pic].
Замечание 2. Заметим, что выражения (4.12) и (4.13) для [pic] и [pic]
([pic]) могут быть упрощены с помощью смены порядка суммирования в (5.10) и
(5.11) и введения коэффициентов корреляции [pic], [pic] и [pic].
Выражение для [pic] особенно просто: [pic].

Для доказательства Предложения 4.1 можно обратиться к [2].

Для решения системы (4.15)-(4.16) можно также воспользоваться итерационным алгоритмом. Начать можно с [pic] и [pic], а дальше итерировать, используя (4.15) для вычисления [pic].

4.2 Оператор dn/dxn в вейвлетном базисе

Так же как и для оператора d/dx, нестандартная форма оператора dn/dxn полностью определяется своим отображением на подпространство V0, т.е. коэффициентами

[pic], l( Z,

(4.18) если интеграл существует.
Предложение 4.2. 1. Если интеграл в выражении (4.18) существует, тогда коэффициенты [pic], l( Z удовлетворяют следующей системе линейных алгебраических уравнений

[pic]
(4.19)

[pic]

(4.20) где [pic] дано в формуле (4.17).
2. Пусть M ? (n+1)/2, где М – число исчезающих моментов. Если интеграл в
(4.18) существует, тогда система (4.19)-(4.20) имеет единственное решение с конечным числом нулевых коэффициентов [pic], а именно [pic] для [pic].
Также для четных n

[pic]

(4.21)

[pic] [pic]

(4.22)

[pic]

(4.23) а для нечетных n

[pic]

(4.24)

[pic] [pic]

(4.25)
Замечание 3. Если M ? (n+1)/2, тогда решение линейной системы в Предложении
2 может существовать, когда интеграл в (4.18) не является абсолютно сходящимся.

Интегральные уравнения второго рода

Линейное интегральное уравнение Фредгольма есть выражение вида

[pic], где ядро [pic], а неизвестная функция f(x) и функция в правой части [pic],
[pic]. Для простоты будем рассматривать интервал [pic]и введём следующее обозначение для всех [pic] и [pic]:

[pic]
Предположим, что {?1, ?1,…} – ортонормальный базис для [pic]; ядро представимо в этом базисе в следующем виде:

[pic] где коэффициенты Kij вычисляются по формуле

[pic], [pic]
Аналогично функции f и g представимы в виде

[pic], [pic], где коэффициенты fi и gi вычисляются по формулам:

[pic], [pic], i=1,2,…
Интегральное уравнение в этом случае соответствует бесконечной системе уравнений

[pic], i=1,2,…
Представление ядра может быть урезано до конечного числа слагаемых, что приводит к представлению интегрального оператора R:

[pic], [pic], [pic], который аппроксимирует K. Тогда интегральное уравнение аппроксимируется системой n уравнений с n неизвестными:

[pic], i=1,2,…,n

ПРИЛОЖЕНИЕ 1

function [a,r]=dif_r(wname)

[LO_D,HI_D,LO_R,HI_R] = wfilters(wname);
% вычисление коэффициентов a2k-1 len=length(LO_D); a=zeros(len-1,1); for k=1:len-1; for i=0:len-2*k; a(2*k-1)=a(2*k-1)+2*LO_D(i+1)*LO_D(i+2*k); end; end;
% вычисление коэффициентов rl f=zeros(len-2,1); f(1)=-1/2;
R=zeros(len-2); for l=len-2:-1:2;

R(l,l)=-1; if (2*l