|
Реферат: Матричные операции в вейвлетном базисе (Математика)
Белорусский государственный университет
Факультет прикладной математики и информатики
Кафедра математической физики
ГРОМОВА МАРИЯ МИХАЙЛОВНА
МАТРИЧНЫЕ ОПЕРАЦИИ В ВЕЙВЛЕТНОМ БАЗИСЕ
Курсовая работа студентки 3 курса
Научный руководитель:
Глушцов Анатолий Ильич
кафедры МФ
кандидит физ.-мат. наук
Минск 2003
СОДЕРЖАНИЕ
ВВЕДЕНИЕ………..………………………………………………………..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) столкнулся с
проблемой анализа сигналов, которые характеризовались высокочастотной
компонентой в течение короткого промежутка времени и низкочастотными
колебаниями при рассмотрении больших временных масштабов. Оконные
преобразования позволяли проанализировать либо высокие частоты в коротком
окне времени, либо низкочастотную компоненту, но не оба колебания
одновременно. В результате был предложен подход, в котором для различных
диапазонов частот использовались временные окна различной длительности.
Оконные функции получались в результате растяжения-сжатия и смещения по
времени гаусиана. 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, даже если в них используются
величины, связаные с ( и (.
2. БЫСТРОЕ ВЕЙВЛЕТ-ПРЕОБРАЗОВАНИЕ
После того, как вычислены коэффициенты hk и gk, т.е. выбран
определенный вейвлет, можно проводить вейвлет-преобразование сигнала f(x),
поскольку задан ортонормальный базис ((j,k, ( j,k). Любая
функция f(x)(L2(R) полностью характеризуется ее вейвлет-
коэффициентами разложения по этому базису и потому может быть представлена
формулой
[pic].
(2.1)
Зададим все пределы суммирования в формуле (2.1). Функцию f(x) можно
рассматривать на любом n-м уровне разрешения jn. Тогда разделение между ее
усредненными значениями на этом уровне и флуктуациями вокруг них выглядят
как
[pic].
(2.4)
На бесконечном интервале первая сумма может быть опущена, и в результате
получается «чистое» вейвлет-разложение.
Коэффициенты sj,k и dj,k содердат информацию о составе сигнала на
разных масштабах и вычисляются по формулам:
[pic],
(2.2)
[pic].
(2.3)
Однако при этом компьютерные расчеты занимают довольно длительное
время, т.к. при вычислении приходится проводить O(N2) операций, где N –
число имеющихся значений функции. Опишем более быстрый алгоритм.
В реальных ситуациях с оцифрованным сигналом мы всегда имеем дело с
конечным набором цифр (точек). Поэтому всегда существует наилучший уровень
разрешения, когда каждый интервал содержит по одному числу. Соответственно
и суммирование по k будет идти в конечных пределах. Удобно изменить шкалу
разрешения (или шкалу f), приписав значение j=0 этому наилучшему уровню
разрешения. В этом случае легко вычислить вейвлет-коэффициенты для более
усредненных уровней j(1. Многомасштабный анализ приводит естественным путем
к иерархической и быстрой схеме вычисления вейвлет-коэффициентов заданной
функции.
В общем случае итерационные формулы быстрого вейвлет-преобразования
имеют вид:
[pic],
(2.4)
[pic]
(2.5)
с
[pic].
(2.6)
Эти уравнения обеспечивают быстрые (или пирамидальные) алгоритмы вычисления
вейвлет-коэффициентов, поскольку требуют только O(N) операций для своего
завершения. Начав с s0,k, мы вычислим все другие вейвлет-коэффициенты, если
параметры вейвлета hm и gm известны. Явный вид вейвлета при этом не
используется. Простая форма полученных итерационных уравнений служит
единственным оправданием введения множителя [pic] в функциональное
уравнение (1.8). В принципе, коэффициенты hm и gm можно было бы
перенормировать. Однако, уравнения (2.4), (2.5) используются на практике
значительно чаще других, и поэтому эту нормировку не изменяют. Любые
дополнительные сомножители в них могут привести лишь к усложнению численных
расчетов.
Остающиеся проблемы связаны с начальными данными. Если известен явный
вид функции f(x), то коэффициенты s0,k можно вычислить, используя формулу
(2.6). Но ситуация отличается от этой, если доступны только дискретные
значения f(x). Чтобы достичь высокой точности, хорошо бы задать очень малые
интервалы (плотную решетку), но это зачастую недоступно из-за конечности
интервалов сбора информации. В таком случае простейшее принимаемое решение
состоит в непосредственном использовании величин f(k) из доступного набора
данных в виде коэффициентов s0,k и применении быстрого вейвлет-
преобразования с использованием формул (2.4), (2.5). Это безопасная
операция, т.к. пирамидальный алгоритм обеспечивает полную реконструкцию
сигнала, а коэффициенты s0,k по сути представляют собой локальные средние
значения сигнала, взвешенные со скейлинг-функцией.
В общем случае можно выбрать
[pic].
(2.7)
Рассмотренная ситуация отвечает условию s0,k=f(k), что соответствует
cm=(0m.
Обратное быстрое вейвлет-преобразование позволяет реконструировать
функцию по значениям ее вейвлет-коэффициентов.
3. ДВУМЕРНЫЕ ВЕЙВЛЕТЫ
Многомасштабный анализ можно проводить и с многомерными функциями.
Существует два способа обобщить его на двумерный случай, но чаще
используется построение, заданное тензорными произведениями.
Тривиальный путь построения двумерного ортонормального базиса исходя
из одномерного ортонормального вейвлет-базиса (j,k(x)=2j/2((2jx-k) состоит
в том, чтобы путем тензорного произведения образовать соответствующие
функции из двух одномерных базисов:
[pic].
(3.1)
В этом базисе две переменных x1 и x2 сжимаются по-разному.
Больший интерес для многих приложений имеет другая конструкция, в
которой масштабирование полученного ортонормального вейлет-базиса
происходит по обеим переменным одинаковым образом и двумерные вейвлеты
задаются следующим выражением:
[pic], j,k,l(Z,
(3.2)
но ( уже не является единственной функцией, наоборот, она будет
сформирована из трех элементарных вейвлетов. Чтобы создать ортонормальный
базис W0, теперь придется использовать три семейства
[pic], [pic], [pic].
Тогда двумерные вейвлеты запишутся в виде
[pic], [pic], [pic].
На двумерной плоскости происходит анализ по горизонталям, вертикалям и
диагоналям с одинаковым разрешением в соответствии с тремя выписанными выше
вейвлетами.
4. МАТРИЧНЫЕ ОПЕРАЦИИ
4.1 Матричное умножение
Существует два возможных способа воздействовать оператором на функцию
в рамках вейвлет-теории. Они называются стандартным и нестандартным
матричным умножением.
У достаточно гладких функций большинство их вейвлет-коэффициентов
достаточно маленькие. Для широкого класса операторов большинство их
матричных элементов также оказываются небольшими. Рассмотрим структуру тех
элементов матричного представления некоторого оператора Т, которые
достаточно велики. Матричные элементы удовлетворяют следующим соотношениям.
[pic] при [pic],
(4.1.1)
[pic] при [pic],
(4.1.2)
Топология распределения этих матричных элементов внутри матрицы может
оказаться весьма запутанной.
Рассметрим действие оператора Т на функцию f, которое превращает ее в
функцию g.
[pic]
(4.1.3)
Как g, так и f могут быть представлены в виде вейвлет-рядов с вейвлет-
коэффициентами (f sj,k;f dj,k) и (g sj,k;g dj,k). На наиболее детальном
уровне разрешения jn отличны от нуля только s-коэффициенты, и
преобразование имеет вид
[pic].
(4.1.4)
На следующем уровне получаем
[pic], (4.1.5)
[pic], (4.1.6)
где
[pic]
и замена нижних индексов S(D соответствует подстановке ((( под знаком
интеграла.
Имеется связь между разными уровнями, потому что все s-коэффициенты
на этом (jn-1)-м уровне должны быть разложены с помощью быстрого вейвлет-
преобразования на s- и d-коэффициенты более высоких уровней. Поэтому, даже
имея почти диагональный вид на начальном этапе, стандартная матрица
преобретает затем довольно сложный вид, как это показано на рис.1.
На конечном этапе мы имеем дело с вейвлет-представлением, описываемым
формулой (2.1), в которой в векторах остается только один s-коэффициент,
представляющий взвешенное среднее функции по всему интервалу ее задания, а
SS-переход от f к g описывается верхним левым квадратиком на этом рисунке.
В то же время на пути к этой формуле от скейлинг-представления нам
приходилось иметь дело со средними величинами на промежуточных уровнях,
разлагая их затем на каждом этапе на части, s и d, последующих уровней
разрешения. Эти промежуточные s-коэффициенты были опущены, потому что мы
заменяли их на s- и d-коэффициенты поледующих уровней. Именно поэтому
окончательная матрица при стандартном подходе приобретает такой сложный
вид.
Рис.1. Матричное представление при стандартном подходе к вейвлет-анализу.
Части матрицы с ненулевыми вейвлет-коэффициентами заштрихованы.
С целью упрощения вида матричного представления было предложено
использовать переопределенный набор вейвлет-коэффициентов. Сохраним эти
усредненные величины в виде соответствующих промежуточных s-коэффициентов
как в начальных, так и в конечных векторах, представляющих функции f и g.
Конечно, в этом случае придется иметь дело с приводимыми векторами, которые
намного больше требуемых для конечного ответа. Однако, известен алгоритм
приведения этих переопределенных выражений к окончательной
непереопределенной форме. В то же время таким образом можно существенно
упростить вид матрицы преобразования и численные расчеты.
Рис.2. Нестандартное матричное умножение при вейвлет-анализе.
Различные уровни оказались полностью развязанными, потому что в матрице
теперь полностью отсутствуют блоки, которые ранее перепутывали их. Блок с
SS-элементами извлечен, а на его место вставлена нулевая матрица. Полная
матрица соответстваенно искусственным образом увеличилась. Вместе с ней
увеличились и векторы, характеризующие функции f и g. Теперь здесь
удерживаются все промежуточные s-коэффициенты вейвлет-разложения
функции f. Каждый блок Sj+1 получается из Sj и Dj. В матрице преобразования
равны нулю все SS-элементы за исключением их величин на низшем уровне S0S0.
Все остальные SD-, DS-, DD-матрицы почти диагональны вследствие конечности
области задания вейвлетов и скейлинг функций. Приведенная на рис. 2 форма
функции g преобразуется в ее обычное вейвлет-представление из рис. 1 путем
разделения каждого Sj в Sj-1 и Dj-1 стандартным методом. Затем эти Sj-1 и
Dj-1 добавляются в соответствующие компоненты вектора. Эта процедура
итерируется, начиная теперь уже с Sj-1, вполоть до S0, когда мы приходим к
обычному вейвлет-представлению функции g. Таким способом мы избавляемся от
всех s-коэффициентов за исключением s0. Вычисления можно теперь проделать
очень быстро.
4.2 Обращение матрицы
Утверждение 1. Последовательность матриц Xk такова, что
Xk+1=2Xk -XkАXk,
(4.2.1)
X0=(А*,
(4.2.2)
где А* - сопряженная матрица и ( выбирается таким образом, чтобы наибольшее
собственное значение матрицы (А*А меньше двух. Тогда последовательность
сходится к обобщенной обратной матрице А-1.
Если это утверждение скомбинировать с алгоритмом быстрого матричного
умножения, то получается алгоритм для построения обратной матрицы в
стандартной форме с трудоемкостью [pic] и в нестандартной форме с
трудоемкостью [pic], где R – число обусловленности матрицы. С помощью
числа R можно оценить соотношение между наибольшим и наименьшим
сингулярными числами выше порога точности.
4.3 Вычисление экспоненты, синуса и косинуса от матрицы.
При обращения матрицы использовался ранее известный алгоритм, который
выходит на совершенно иной уровень, когда применяется вместе с вейвлет-
представлением.
Алгоритм вычисления экспоненты матрицы основывается на тождестве
[pic].
(4.3.1)
Во-первых, exp(2-LA) может быть посчитана, например, с помощью ряда
Тейлора. Число L выбирается таким образом, чтобы наибольшее сингулярное
число матрицы 2-LA было меньше единицы. На втором шаге алгоритма для
достижения результата матрица 2-LA возводится в квадрат L раз.
Аналогично, синус и косинус от матрицы могут быть посчитаны с
исподьзованием формул двойного угла.
[pic]
(4.3.2)
[pic],
(4.3.3)
при l=0,…,L-1
[pic]
(4.3.4)
[pic],
(4.3.5)
где I – тождество. Снова выбираем L таким образом, чтобы наибольшее
сингулярное число матрицы 2-LA было меньше единицы, вычисляем синус и
косинус матрицы 2-LA, с помощью рядов Тейлора, а затем используем формулы
(4.3.4) и (4.3.5).
Обычно такие алгоритмы требуют по меньшей мере O(N3) операций, так
как должне быть выполнено достаточно много операций по умножению густых
матриц. Быстрый алгоритм для умножения матриц в стандартной форме уменьшает
сложность до не более чем [pic] операций, а быстрый алгоритм для умножения
матриц в нестандартной форме – до O(N) операций.
ЛИТЕРАТУРА
1. Beylkin G. Wavelets and Fast Numerical Algorithms.
2. Beylkin G. Wavelets, Multiresolution Analysis and Fast Numerical
Algorithms.
3. Дремин И.М., Иванов О.В., Нечитайло В.А. Вейвлеты и их использование
// Успехи физических наук – 2001, №5. – С.465-500
-----------------------
[pic]
[pic]
Реферат на тему: Матричный анализ
Курс лекций по дисциплине
«Матричный анализ»
для студентов II курса
математического факультета специальности
«Экономическая кибернетика»
(лектор Дмитрук Мария Александровна)
Глава 3. Функции от матриц.
1. Определение функции.
Df. Пусть [pic]– функция скалярного аргумента. Требуется определить, что
понимать под f(A), т.е. нужно распространить функцию f(x) на матричное
значение аргумента.
Решение этой задачи известно, когда f(x) – многочлен: [pic], тогда [pic].
Определение f(A) в общем случае.
Пусть m(x) – минимальный многочлен А и он имеет такое каноническое
разложение [pic], [pic], [pic]– собственные значения А. Пусть многочлены
g(x) и h(x) принимают одинаковые значения.
Пусть g(A)=h(A) (1), тогда многочлен d(x)=g(x)-h(x) – аннулирующий
многочлен для А, так как d(A)=0, следовательно, d(x) делится на линейный
многочлен, т.е. d(x)=m(x)*q(x) (2).
Тогда [pic], т.е. [pic](3), [pic], [pic], [pic].
Условимся m чисел для f(x) таких [pic] называть значениями функции f(x) на
спектре матрицы А, а множество этих значений будем обозначать [pic].
Если множество f(Sp A) определено для f(x), то функция определена на
спектре матрицы А.
Из (3) следует, что многочлены h(x) и g(x) имеют одинаковые значения на
спектре матрицы А.
Наши рассуждения обратимы, т.е. из (3) ( (3) ( (1). Таким образом, если
задана матрица А, то значение многочлена f(x) вполне определяется
значениями этого многочлена на спектре матрицы А, т.е. все многочлены
gi(x), принимающие одинаковые значения на спектре матрицы имеют одинаковые
матричные значения gi(A). Потребуем, чтобы определение значения f(A) в
общем случае подчинялось такому же принципу.
Значения функции f(x) на спектре матрицы А должны полносильно определить
f(A), т.е. функции, имеющие одни и те же значения на спектре должны иметь
одно и то же матричное значение f(A). Очевидно, что для определения f(A) в
общем случае, достаточно найти многочлен g(x), который бы принимал те же
значения на спектре А, что и функция f(A)=g(A).
Df. Если f(x) определена на спектре матрицы А, то f(A)=g(A), где g(A) –
многочлен, принимающий на спектре те же значения, что и f(A), [pic]
Df. Значением функции от матрицы А назовем значение многочлена от этой
матрицы при [pic].
Среди многочленов из С[x], принимающих одинаковые значения на спектре
матрицы А, что и f(x), степени не выше (m-1), принимающий одинаковые
значения на спектре А, что и f(x) – это остаток от деления любого
многочлена g(x), имеющего те же значения на спектре матрицы А, что и f(x),
на минимальный многочлен m(x)=g(x)=m(x)*g(x)+r(x).
Этот многочлен r(x) называют интерполяционным многочленом Лагранжа-
Сильвестра для функции f(x) на спектре матрицы А.
Замечание. Если минимальный многочлен m(x) матрицы А не имеет кратных
корней, т.е. [pic], то значение функции на спектре [pic].
Пример:
Найти r(x) для произвольной f(x), если матрица
[pic]. Построим f(H1). Найдем минимальный многочлен H1 – последний
инвариантный множитель [xE-H1]:
[pic], dn-1=x2; dn-1=1;
mx=fn(x)=dn(x)/dn-1(x)=xn( 0 – n –кратный корень m(x), т.е. n-кратные
собственные значения H1.
[pic], r(0)=f(0), r’(0)=f’(0),…,r(n-1)(0)=f(n-1)(0) ( [pic].
2. Свойства функций от матриц.
Свойство № 1. Если матрица [pic]имеет собственные значения [pic] (среди них
могут быть и кратные), а [pic], то собственными значениями
матрицы f(A) являются собственные значения многочлена f(x):
[pic].
Доказательство:
Пусть характеристический многочлен матрицы А имеет вид:
[pic], [pic], [pic]. Посчитаем [pic]. Перейдем от равенства к
определителям: [pic][pic]
Сделаем замену в равенстве:
[pic] (*)
Равенство (*) справедливо для любого множества f(x), поэтому заменим
многочлен f(x) на [pic], получим:
[pic].
Слева мы получили характеристический многочлен для матрицы f(A),
разложенный справа на линейные множители, откуда следует, что [pic] –
собственные значения матрицы f(A).
ЧТД.
Свойство № 2. Пусть матрица [pic]и [pic] – собственные значения матрицы А,
f(x) – произвольная функция, определенная на спектре матрицы
А, тогда собственные значения матрицы f(A) равны [pic].
Доказательство:
Т.к. функция f(x) определена на спектре матрицы А, то существует
интерполяционный многочлен матрицы r(x) такой, что [pic], а тогда
f(A)=r(A), а у матрицы r(A) собственными значениями по свойству № 1 будут
[pic] которым соответственно равны [pic].
ЧТД.
Свойство № 3. Если А и В подобные матрицы, [pic], т.е. [pic], и f(x) –
произвольная функция, определенная на спектре матрицы А,
тогда [pic]
Доказательство:
Т.к. А и В подобны, то их характеристические многочлены одинаковы (
одинаковы и их собственные значения, поэтому значение f(x) на спектре
матрицы А совпадает со значение функции f(x) на спектре матрицы В, при чем
существует интерполяционный многочлен r(x) такой, что f(A)=r(A), [pic],
[pic] ( [pic].
ЧТД.
Свойство № 4. Если А – блочно-диагональная матрица [pic], то [pic]
Следствие: Если [pic], то [pic], где f(x) – функция, определенная на
спектре матрицы А.
4. Интерполяционный многочлен Лагранжа-Сильвестра.
Случай № 1.
Пусть дана [pic]. Рассмотрим первый случай: характеристический многочлен
[pic] имеет ровно n корней, среди которых нет кратных, т.е. все собственные
значения матрицы А различны, т.е. [pic], Sp A – простой. В этом случае
построим базисные многочлены lk(x):
[pic].
Пусть f(x) – функция, определенная на спектре матрицы А и значениями этой
функции на спектре будут [pic]. Надо построить [pic].
Построим:
[pic].
Обратим внимание, что [pic].
[pic][pic]
Пример: Построить интерполяционный многочлен Лагранжа-Сильвестра для
матрицы [pic].
[pic]Построим базисные многочлены:
[pic]
[pic]
[pic]
Тогда для функции f(x), определенной на спектре матрицы А, мы получим:
[pic].
Возьмем [pic], тогда интерполяционный многочлен
[pic].
Случай № 2.
Характеристический многочлен матрицы А имеет кратные корни, но минимальный
многочлен этой матрицы является делителем характеристического многочлена и
имеет только простые корни, т.е. [pic]. В этом случае интерполяционный
многочлен строится так же как и в предыдущем случае.
Случай № 3.
Рассмотрим общий случай. Пусть минимальный многочлен имеет вид:
[pic],
где m1+m2+…+ms=m, deg r(x)B, если [pic].
Вспомним матрицу перестановки [pic], т.е. матрицы перестановки обязательно
ортогональны. Произведение [pic] приводит к перестановке столбцов матрицы
А.
DF. При [pic] матрица [pic] называется приводимой матрицей, если существует
такая матрица перестановки Р, что [pic] совподает с матрицей [pic], где
А11, А12, А22 – квадратные матрицы меньшего чем n порядка. Если матрица Р
не существует, то матрица А называется неприводимой.
Понятие приводимости имеет значение при решении матричных уравнений [pic] ,
ибо если Ф – приводима, то осуществив замену переменных, которую
подсказывают равенства [pic], получаем
[pic], где [pic], [pic].
[pic] и решаем матричное уравнение с матрицей более низкого порядка. Затем,
[pic] и решаем матричное уравнение. Таким образом, если А – приводима, то
решение уравнения высокого порядка сводится к решению уравнений более
низкого порядка, при чем собственные значения матриц А11 и А22 в своей
совокупности составляет множество значений матрицы А.
Интересно, что явление приводимости не связано с величиной матрицы, а
зависит лишь от расположения нулевых элементов в матрице.
В связи с этим, используют идею направленного графа матрицы, которую можно
взять в качестве характеризации неприводимости матрицы. Наметим первые шаги
тоерии и получим вторую характеризацию неприводимости матриц.
DF. Пусть р1, р2, …, рn – n различных точек комплексной плоскости и [pic].
Для каждого нулевого элемента матрицы А [pic] составим направленную линию
от рi к рj [pic]. Получающаяся в результате фигура на комплексной
плоскости называется направленным графом матрицы.
Например:
[pic]
DF. Говорят, что любой направленный граф связен, если для каждой пары точек
[pic] существует направленный путь [pic].
Легко доказать, что квадратная матрица неприводима тогда и только тогда,
когда ее граф является связным.
8.Теорема Фробениуса-Перона.
Очевидно, что если [pic], то для [pic] [pic]. Более того, мы покажем, что
для достаточно больших p [pic].
Лемма № 1. Если матрица [pic] неотрицательна и неприводима, то [pic].
Доказательство:
Если взять произвольный вектор [pic] и [pic], то [pic]. И пусть вектор
[pic] имеет место, очевидно, что Z имеет по крайней мере столько же нулевых
положительных элементов, что и y. В самом деле, если предположить, что Z
имеет меньше нулевых компонент, то обозначим [pic], тогда [pic] и разбив
матрицу А на блоки следующим образом
[pic] мы будем иметь [pic].
Учитывая, что [pic], то [pic], тогда получаем, что [pic], что противоречит
неприводимости матрицы.
Для следующего вектора повторим рассуждения и т.д. В итоге получим, что для
некоторого ненулевого вектора y [pic].
ЧТД.
Для ненулевой неприводимой матрицы А рассмотрим действительную функцию
r(x), определенную для ненулевых векторов [pic] следующим образом: [pic],
(Ax)i – i-я координата вектора Ах.
[pic]. Из определения следует, что [pic] и кроме того, r(x) –такое
наименьшее значение [pic], что [pic].
Очевидно, что r(x) инвариантна относительна замены x на [pic], поэтому в
дальнейшем можно рассматривать замкнутое множество [pic], такое [pic].
Однако, r(x) может иметь разрывы в точках, где координата x обращается в 0,
поэтому рассмотрим множество векторов [pic] и обозначим [pic]. По лемме № 1
каждый вектор из N будет положительным, а поэтому [pic]т.е. [pic]для [pic].
Обозначим через [pic] наибольшее число, для которого [pic], [pic]. [pic] –
спектральный радиус матрицы А. Если [pic] Можно показать, что существует
вектор y, что [pic].
Замечание. Могут существовать и другие векторы в L для которых r(x)
принимает значение r, поэтому любой такой вектор называется экстремальным
для матрицы А (Az=rz).
Интерес к числу r объясняется следующим результатом.
Лемма № 2. Если матрица [pic] неотрицательна и неприводима, то число
[pic][pic] является собственным значением матрицы А, кроме того каждый
экстремальный вектор для А положителен и является правым собственным
вектором для А, отвечающим собственному значению r.
Основным результатом является теорема Фробениуса-Перона для непрерывных
матриц.
Теорема Фробениуса-Перона. Если матрица [pic] неотрицательна и неприводима,
то:
1. А имеет положительное собственное значение, равное спектральному
радиусу матрицы А;
2. существует положительный правый собственный вектор,
соответствующий собственному значению r.
3. собственное значение имеет алгебраическую кратность равную 1.
Эта теорема была опубликована в 1912 году Фробениусом и явилась обобщением
теоремы Перона, которая является следствием.
Теорме Перона (следствие). Положительная квадратная матрица А имеет
положительное и действительное собственное значение r, имеющее
алгебраическую кратность 1 и превосходит модули всех других собственных
значений матрицы А. Этому r соответствует положительный собственный вектор.
Используя теорему Фробениуса-Перона, можно найти максимальное
действительное значение матрицы, не используя характеристического
многочлена матрицы.
-----------------------
р1
р3
р2
[pic]
| |
