Белорусский государственный университет
Факультет прикладной математики и информатики
Кафедра математической физики
ГРОМОВА МАРИЯ МИХАЙЛОВНА
ОПРЕАТОРЫ В ВЕЙВЛЕТНОМ БАЗИСЕ
Курсовая работа студентки 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