|
|
Ваш вопрос в свое время был для меня тоже очень актуальным. Попробую ответить на него так же, какой ответ был бы мне понятен.
Сразу сделаем оговорку, что мы будем рассматривать здесь только дискретные сигналы конечной длительности. Почему? Если ответить просто, то потому что конечный сигнал длиной N может быть представлен в виде вектора размерности N. (Вообще, можно еще добавить, что при обработке дискретных сигналов бесконечной длины работают уже не с матрицами, а с линейными операторами. Правда, матрица это частный случай линейного оператора). Скажем больше, в ходе всей настоящей заметки мы не будем выходить за рамки пространства конечномерных векторов. Это означает, что нам не будут интересны фильтры с бесконечной импульсной характеристикой.
Матрица размером NxN, умноженная на вектор-столбец слева, описывает некоторую линейную операцию над вектором. Мы можем говорить, что матрица является фильтром для данного сигнала. Или еще мы увидим, что умножением матрицы определенного вида на вектор-столбец слева мы описываем операцию свертки двух сигналов. Впрочем, все сказанное можно в равной степени употребить и к умножению вектора-строки на матрицу справа. Для удобства изложения примем по умолчанию, что когда речь идет об умножении вектора на матрицу, подразумевается умножение матрицы слева на вектор-столбец.
Говоря о собственных числах и собственных векторах, Вы действительно правильно заметили, что матрица, умноженная на собственный вектор, сохраняет его направление. Здесь лишь замечу, что собственные числа, по смыслу являющиеся коэффициентом удлинения (или укорочения) могут быть не обязательно действительными, а как раз наиболее частый случай в обработке сигналов, когда собственные числа комплексные.
Теперь постараюсь изложить все главное в тезисах.
1. Наиболее частая операция в обработке сигналов – это свертка. Свертка бывает обычной и циклической. Здесь ограничимся лишь циклической сверткой. (Считаю, что о циклической свертке Вам более-менее известно все. Если нет, спрашивайте). Для обозначения операции циклической свертки будем использовать в тексте символ (*). Например, х(*)у означает цикл. свертку двух векторов. Далее говоря "свертка", будем опускать определение "циклическая". Результатом свертки двух векторов длиной N будет также вектор длиной N.
2. Важное понятие: «МАТРИЦА-ЦИРКУЛЯНТ». С ее помощью очень удобно описывать цикл. свертку. Пример. Пусть N=4. Пусть также z=x(*)y. Рассмотрим матрицу-циркулянт Х размером NхN, составленную из элементов xi вектора x:
X =
x4 x3 x2 x1
x3 x2 x1 x4
x2 x1 x4 x3
x1 x4 x3 x2
Тогда свертку можно представить в виде произведения матрицы на вектор: z=Xy, где z=(z1 z2 z3 z4)’, y=(y1 y2 y3 y4)’. Здесь штрих сверху означает операцию транспонирования.
3. ВАЖНО! ЗАПОМНИТЕ. Собственные значения матрицы-циркулянта - это комплексные экспоненты (те самые, что в дискр. преобр. Фурье). Собственные же векторы - векторы, составленные из таких же комплексных экспонент. Откуда это следует? Я рекомендую самостоятельно доказать это. Доказывая данный факт без помощи доп. литературы, до меня многое дошло. Я немного помогу. Тезисы для доказательства:
3-А. Понятие УНИТАРНОЙ МАТРИЦЫ. – Очень полезная штука. Если русским языком описать, то это матрица, будучи подействованной (умноженной) на вектор, сохраняет его длину. Отсюда сразу же очевидное ее свойство: все ее собственные числа по модулю равны единице. Не торопитесь полагать, что это либо 1 либо -1. Ими могут быть, например, числа 0.707+0.707i, или просто мнимая единица i.
3-А-1. Поскольку унитарная матрица сохраняет длину вектора, то обратная к ней матрица – это просто транспонированная (для случая матрицы с действительными коэффициентами), или сопряженная (это общий случай, когда коэффициенты матрицы комплексны).
3-Б. Посмотрите, что сделает матрица R вида
0 1 0 0
0 0 1 0
0 0 0 1
1 0 0 0
Эта матрица называется матрицей цикл. сдвига вверх. (Нетрудно при необходимаости построить аналог, сдвигающий вниз). Обратим внимание на факты (проверьте):
3-Б-1. R^0 = I (единичная матрица), R^1 = R, R^2 – матрица сдвига на два вверх, R^3 – матрица сдвига на три вверх, или, в данном примере, на один вниз. R^4=R^0=I
3-Б-2. Матрица R является унитарной. Покажите это, найдя ее собственные значения и собственные векторы. Обобщите это на случай, когда матрица R имеет произвольный размер. Очень интересный результатик получится! (Фурье)
3-Б-3. Матрицы R^0, R^2 и R^3 также являются унитарными (операция ^ означает возв. в степень). Более того, все они, включая R^1, имеют один и тот же набор собственных векторов. Т.е. все они имеют в качестве собственных векторов столбцы (строки) матрицы-Фурье W.
3-В. Матрица-циркулянт X может быть представлена как
X=x4*R^0+x3*R^1+x2*R^2+x1*R^3 (помните, что xi - это просто числа? См. п.2)
3-Г. Допустим, что v1 – это собственный вектор матрицы R. Тогда, согласно 3-В v1, будет являться как собственным вектором матрицы R^1, так и собственным вектором матриц R^0, R^2 и R^3.
3-Д. Выполните теперь умножение: X*v1=…, воспользуйтесь представлением 3-В, а также фактом 3-Г, и получите доказательство!
3-Е. В качестве упражнения постройте обратную матрицу к матрице сдвига вверх (R) и посмотрите, что за матрица получилась.
4. ОЧЕНЬ ВАЖНАЯ ШТУКА ПРО СОБСТВЕННЫЕ ВЕКТОРЫ! Если из собственных векторов vi произвольной невырожденной матрицы A (количество таких векторов будет, как известно, равно N) составить матрицу S размера NxN:
S=[v1; v2; …, vN],
то посмотрите, что будет, если умножить матрицу A на матрицу S:
A*S = [h1*v1; h2*v2; …, hN*vN].
Здесь hi – собственные числа матрицы A.
4-A. Пофантазируйте теперь, что было бы если бы собственные векторы v1…vN были бы взаимно-ортогональными?
(т.е. vi(*)vj = [0 0 … 0]’ при i не равном j;
vi(*)vj = [0 0 …0 vv 0 … 0]’ при i=j, где число vv, стоящее на i-ой позиции – модуль вектора vi в квадрате). Заметим также, что при если бы собственные векторы были бы еще и ортонормированными (т.е. их модуль равен 1), то
Чтобы фантазия проходила в нужном русле, рассмотрите такую штуку:
S~*A*S, где значок ~ означает сопряженную матрицу к матрице S. У Вас получится диагональная матрица с собственными числами матрицы A на главной диагонали!
4-Б. Если A - матрица-циркулянт, то нетрудно видеть, что ее собственные вектора ортогональны (см. выше, пп.3-х; что там получилось?!)
4-В. Значит, если поступить хитро и сделать S~*A*S при наличии у матрицы A ортогональной системы собственных векторов, то при помощи такого преобразования можно получить диагональную матрицу.
4-Г. (Кстати, заметим, что S~*S=diag; если же собственные векторы матрицы A ортонормированные, то S~*S=I).
А это круто! Почему? Потому что умножение диагональной матрицы на вектор занимает не N^2 операций, а всего лишь N. Далее попробуем разобраться, как же можно все это применить.
Пусть X – матрица-цируклянт. Тогда рассмотрим X*y’. Напомним, что по доказанному, собственные векторы X - это векторы составленные из комплексных экспонент. Более того, нетрудно видеть, что все они ортонормированные. Значит, если мы составим из собственных векторов матрицы X матрицу W, то из п. 4-Г следует, что W~*W=. Да и к тому же мы видим, что W есть ни что иное, как матрица дискр. преобразования Фурье. Ясно, что W~ - матрица обратного дискретного преобразования Фурье.
Докажите теперь самостоятельно, базируясь на всем вышеперечисленном, что свертку X*y’ можно выполнить через дискретное преобразование Фурье, диагонализировав матрицу X.
Ну вот, скажете Вы, велосипед изобрел! Это было и так известно. Ради чего все это надо было делать? И впрямь, ради чего?
E-mail: 
info@telesys.ru
