В линейной алгебре , eigendecomposition или иногда спектральное разложение является разложением из матрицы в каноническую форму , в результате чего матрица представлена в терминах его собственных значений и собственных векторов . Таким способом можно факторизовать только диагонализуемые матрицы .
Фундаментальная теория собственных векторов и собственных значений матриц
(Ненулевой) вектор v размерности N является собственным вектором квадратной матрицы A размера N × N, если он удовлетворяет линейному уравнению
где λ - скаляр, называемый собственным значением, соответствующим v . То есть собственные векторы - это векторы, которые линейное преобразование A просто удлиняет или сжимает, а величина, на которую они удлиняются / сжимаются, является собственным значением. Вышеупомянутое уравнение называется уравнением собственных значений или проблемой собственных значений .
Это дает уравнение для собственных значений
Мы называем р ( Л ) в характеристический полином , и уравнение, называемое характеристическое уравнение , является N - го порядка полиномиальное уравнение в неизвестном Х . Это уравнение будет иметь N Л различных решений, где 1 ≤ ' N А ≤ N . Множество решений, то есть собственные значения, называется спектром из A . [1] [2] [3]
Мы можем разложить p на множители как
Целое число n i называется алгебраической кратностью собственного значения λ i . Если поле скаляров алгебраически замкнуто , сумма алгебраических кратностей равна N :
Для каждого собственного значения λ i у нас есть конкретное уравнение для собственных значений
У каждого уравнения на собственные значения будет 1 ≤ m i ≤ n i линейно независимых решений. Линейные комбинации решений m i являются собственными векторами, связанными с собственным значением λ i . Целое м я называется геометрической кратностью от λ я . Важно иметь в виду, что алгебраическая кратность n i и геометрическая кратность m i могут быть равными или не равными, но мы всегда имеем m i ≤ n i . В простейшем случае, конечно, когда m i = n i = 1 . Общее количество линейно независимых собственных векторов, N v , может быть вычислено путем суммирования геометрических кратностей
Собственные векторы могут быть проиндексированы по собственным значениям с использованием двойного индекса, где v ij является j- м собственным вектором для i- го собственного значения. Собственные векторы также могут быть проиндексированы с использованием более простой записи одного индекса v k , где k = 1, 2, ..., N v .
Собственное разложение матрицы
Пусть A - квадратная матрица размера n × n с n линейно независимыми собственными векторами q i (где i = 1, ..., n ). Тогда A можно разложить на множители как
где Q представляет собой квадрат п × п матрица, я - й столбец является собственным вектором д я из A , и Λ является диагональной матрицей , диагональные элементы которой являются соответствующие собственные значения, Λ II = λ я . Обратите внимание, что таким способом можно факторизовать только диагонализуемые матрицы . Например, дефектная матрица (которая представляет собой матрицу сдвига ) не может быть диагонализована.
П собственных векторов д я обычно нормализовались, но они не должны быть. Ненормированного множество п собственных векторов, v я также могут быть использованы в качестве столбцов матрицы Q . Это можно понять, отметив, что величина собственных векторов в Q сокращается при разложении из-за наличия Q -1 .
Разложение может быть получено из фундаментального свойства собственных векторов:
Пример
Действительная матрица 2 × 2 A
можно разложить на диагональную матрицу путем умножения невырожденной матрицы B
потом
для некоторой реальной диагональной матрицы .
Умножая обе части уравнения слева на B :
Вышеприведенное уравнение можно разложить на два одновременных уравнения :
Выделение собственных значений x и y :
Сдача
это дает нам два векторных уравнения:
И может быть представлено одним векторным уравнением, включающим два решения в качестве собственных значений:
где λ представляет два собственных значения x и y , а u представляет векторы a и b .
Сдвигая λ u влево и вынося u за скобки
Поскольку B неособо, существенно, что u не равно нулю. Следовательно,
Таким образом
давая нам решения собственных значений матрицы A как λ = 1 или λ = 3 , и получившаяся диагональная матрица из собственного разложения матрицы A , таким образом, имеет вид.
Подставляя решения обратно в приведенные выше одновременные уравнения
Решая уравнения, имеем
Таким образом, матрица B, необходимая для собственного разложения матрицы A, равна
это:
Матрица, обратная через собственное разложение
Если матрица может быть eigendecomposed и если ни один из его собственных значений равны нулю, то не обратим и обратный дается
Если является симметричной матрицей, так как формируется из собственных векторов гарантированно будет ортогональной матрицей , поэтому. Кроме того, поскольку Λ - диагональная матрица , ее обратную матрицу легко вычислить:
Практические последствия [4]
Когда собственное разложение используется в матрице измеренных реальных данных , обратное может быть менее достоверным, если все собственные значения используются без изменений в форме выше. Это связано с тем, что по мере того, как собственные значения становятся относительно небольшими, их вклад в инверсию велик. Те, которые близки к нулю или находятся на уровне «шума» измерительной системы, будут иметь чрезмерное влияние и могут затруднить решения (обнаружение) с использованием обратного.
Было предложено два смягчения: усечение малых или нулевых собственных значений и распространение самого низкого надежного собственного значения на те, которые ниже него.
Первый метод смягчения подобен разреженной выборке исходной матрицы, удаляя компоненты, которые не считаются ценными. Однако, если процесс решения или обнаружения близок к уровню шума, усечение может удалить компоненты, которые влияют на желаемое решение.
Второе смягчение расширяет собственное значение, так что более низкие значения имеют гораздо меньшее влияние на инверсию, но все же вносят свой вклад, так что решения вблизи шума все равно будут найдены.
Надежное собственное значение может быть найдено, если предположить, что очень похожие и низкие собственные значения являются хорошим представлением шума измерения (который считается низким для большинства систем).
Если собственные значения отсортированы по рангу по значению, то надежное собственное значение может быть найдено путем минимизации лапласиана отсортированных собственных значений: [5]
где собственные значения имеют индекс s для обозначения сортировки. Положение минимизации - это самое низкое надежное собственное значение. В измерительных системах квадратный корень из этого надежного собственного значения представляет собой средний шум по компонентам системы.
Функциональное исчисление
Собственное разложение позволяет значительно упростить вычисление степенных рядов матриц. Если f ( x ) задается формулой
тогда мы знаем, что
Поскольку Λ - диагональная матрица , функции от Λ очень легко вычислить:
Недиагональные элементы f ( Λ ) равны нулю; то есть f ( Λ ) также является диагональной матрицей. Следовательно, вычисление f ( A ) сводится к простому вычислению функции для каждого из собственных значений.
Аналогичная техника работает в более общем плане с голоморфным функциональным исчислением , используя
от выше . И снова мы находим, что
Примеры
которые являются примерами функций . Более того,- матричная экспонента .
Разложение на специальные матрицы
Нормальные матрицы
Комплексная квадратная матрица A является нормальной (что означает A * A = AA * , где A * - сопряженное транспонирование ) тогда и только тогда, когда она может быть разложена как
где U - унитарная матрица (то есть U * = U −1 ), а Λ = diag ( λ 1 , ..., λ n ) - диагональная матрица . [6] Столбцы U 1 , ..., у п из U образуют ортогональный базис и собственные векторы А с соответствующими собственными значениями А 1 , ..., Х п .
Если A ограничивается эрмитовой матрицей ( A = A * ), то Λ имеет только вещественнозначные элементы. Если A ограничена унитарной матрицей, то Λ принимает все свои значения на комплексной единичной окружности, то есть | λ i | = 1 .
Действительные симметричные матрицы
В качестве особого случая для каждой вещественной симметричной матрицы размера n × n собственные значения являются действительными, а собственные векторы могут быть выбраны действительными или ортонормированными . Таким образом, вещественная симметричная матрица A может быть разложена как
где Q представляет собой ортогональная матрица , столбцы которой являются собственными векторами A , и Λ является диагональной матрицей, элементы которой являются собственными значениями A . [7]
Полезные факты
Полезные факты о собственных значениях
- Произведение собственных значений равно детерминант из А
- Сумма собственных значений равно след от А
- Если собственные значения матрицы A равны λ i и A обратима, то собственные значения матрицы A −1 просто λ−1
я. - Если собственные значения матрицы A равны λ i , то собственные значения f ( A ) суть просто f ( λ i ) для любой голоморфной функции f .
Полезные факты о собственных векторах
- Если A является эрмитовым и полноранговым, можно выбрать базис собственных векторов взаимно ортогональным . Собственные значения действительны.
- Собственные векторы А -1 такие же , как собственные векторы A .
- Собственные векторы определены только с точностью до мультипликативной константы. То есть, если Av = λ v, то c v также является собственным вектором для любого скаляра c ≠ 0 . В частности, - v и e iθ v (для любого θ ) также являются собственными векторами.
- В случае вырожденных собственных значений (собственное значение появляется более одного раза) собственные векторы обладают дополнительной свободой вращения, то есть любая линейная (ортонормированная) комбинация собственных векторов, разделяющих собственное значение (в вырожденном подпространстве), сами являются собственными векторами ( в подпространстве).
Полезные факты о собственном разложении
- A может быть разложен на собственные тогда и только тогда, когда количество линейно независимых собственных векторов, N v , равно размерности собственного вектора: N v = N
- Если p ( λ ) не имеет повторяющихся корней, т. Е. Еслитогда A можно разложить по собственному усмотрению.
- Утверждение « A может быть разложено по собственным значениям» не означает, что A имеет инверсию.
- Утверждение « A имеет инверсию» не означает, что A может быть разложена на собственные элементы. Контрпример, которая представляет собой обратимую дефектную матрицу .
Полезные факты об обратной матрице
- A можно инвертировать тогда и только тогда, когда все собственные значения ненулевые:
- Если λ i ≠ 0 и N v = N , обратное дается формулой
Численные расчеты
Численное вычисление собственных значений
Предположим, что мы хотим вычислить собственные значения данной матрицы. Если матрица мала, мы можем вычислить их символически, используя характеристический полином . Однако это часто невозможно для больших матриц, и в этом случае мы должны использовать численный метод .
На практике собственные значения больших матриц не вычисляются с использованием характеристического полинома. Вычисление полинома само по себе становится дорогостоящим, а точные (символические) корни полинома высокой степени может быть трудно вычислить и выразить: теорема Абеля – Руффини подразумевает, что корни полиномов высокой степени (5 или выше) не могут вообще быть выраженным просто с помощью корней n- й степени. Следовательно, общие алгоритмы поиска собственных векторов и собственных значений являются итеративными .
Существуют итерационные численные алгоритмы для аппроксимации корней многочленов, такие как метод Ньютона , но в целом нецелесообразно вычислять характеристический многочлен, а затем применять эти методы. Одна из причин заключается в том, что небольшие ошибки округления в коэффициентах характеристического полинома могут привести к большим ошибкам в собственных значениях и собственных векторах: корни являются чрезвычайно плохо обусловленной функцией коэффициентов. [8]
Простым и точным итерационным методом является степенной метод : выбирается случайный вектор v и последовательность единичных векторов вычисляется как
Эта последовательность почти всегда будет сходиться к собственному вектору, соответствующему собственному значению наибольшей величины, при условии, что v имеет ненулевую компоненту этого собственного вектора в базисе собственных векторов (а также при условии, что существует только одно собственное значение наибольшей величины). Этот простой алгоритм полезен в некоторых практических приложениях; например, Google использует его для расчета рейтинга страниц документов в своей поисковой системе. [9] Кроме того, степенной метод является отправной точкой для многих более сложных алгоритмов. Например, сохраняя не только последний вектор в последовательности, но вместо того, чтобы смотреть на пролет из всех векторов в последовательности, можно получить лучше (быстрее сходящееся) приближение к собственному вектору, и эта идея является основой Арнольди итерация . [8] В качестве альтернативы, важный алгоритм QR также основан на тонком преобразовании метода мощности. [8]
Численное вычисление собственных векторов
После того, как собственные значения вычислены, собственные векторы могут быть вычислены путем решения уравнения
с использованием исключения Гаусса или любого другого метода решения матричных уравнений .
Однако в практических крупномасштабных методах собственных значений собственные векторы обычно вычисляются другими способами, как побочный продукт вычисления собственных значений. В степенной итерации , например, собственный вектор фактически вычисляется перед собственным значением (которое обычно вычисляется посредством отношения Рэлея к собственному вектору). [8] В QR-алгоритме для эрмитовой матрицы (или любой нормальной матрицы ) ортонормированные собственные векторы получаются как произведение Q- матриц на этапах алгоритма. [8] (Для более общих матриц алгоритм QR сначала дает разложение Шура , из которого собственные векторы могут быть получены с помощью процедуры обратной подстановки . [10] ) Для эрмитовых матриц алгоритм собственных значений «разделяй и властвуй» более эффективен, чем QR-алгоритм, если требуются как собственные векторы, так и собственные значения. [8]
Дополнительные темы
Обобщенные собственные подпространства
Напомним , что геометрическая кратность собственного значения может быть описана как размерность соответствующей собственному пространству, в нуль - пространства из Х I - A . Алгебраическая кратность также может рассматриваться как размерность: это размерность ассоциированного обобщенного собственного подпространства (1-е чувство), которое является нулевым пространством матрицы ( λ I - A ) k для любого достаточно большого k . То есть это пространство обобщенных собственных векторов (в первом смысле), где обобщенный собственный вектор - это любой вектор, который в конечном итоге становится 0, если λ I - A применяется к нему несколько раз подряд. Любой собственный вектор является обобщенным собственным вектором, поэтому каждое собственное подпространство содержится в ассоциированном обобщенном собственном подпространстве. Это дает простое доказательство того, что геометрическая кратность всегда меньше или равна алгебраической кратности.
Это использование не следует путать с описанной ниже обобщенной проблемой собственных значений .
Сопряженный собственный вектор
Конъюгат собственного вектора или coneigenvector является вектором послан после трансформации до скалярного множителя его конъюгата, где скаляр называется сопряженным собственным значением или псевдособственными линейного преобразование. Собственные векторы и собственные значения представляют по существу ту же информацию и значение, что и обычные собственные векторы и собственные значения, но возникают при использовании альтернативной системы координат. Соответствующее уравнение
Например, в теории когерентного электромагнитного рассеяния линейное преобразование A представляет действие, выполняемое рассеивающим объектом, а собственные векторы представляют состояния поляризации электромагнитной волны. В оптике система координат определяется с точки зрения волны, известной как выравнивание прямого рассеяния (FSA), и приводит к регулярному уравнению собственных значений, тогда как в радаре система координат определяется с точки зрения радара, известной как обратная связь. Выравнивание по рассеянию (BSA) и приводит к уравнению на собственные значения.
Обобщенная проблема собственных значений
Проблема обобщенной собственной значения (второй смысл) является задачей нахождения вектора V , подчиняющихся
где A и B - матрицы. Если V удовлетворяет это уравнение с некоторым Л , то мы называем v обобщенным собственным вектором из A и B (во втором смысле), и λ называются обобщенным собственное значение из A и B (во втором смысле) , которое соответствует обобщенному собственный вектор v . Возможные значения λ должны подчиняться следующему уравнению
Если п линейно независимых векторов { v 1 , ..., v п } можно найти, например , что для любого I ∈ {1, ..., п } , Av я = λ я Bv я , то определим матрицы P и D , такие , что
Тогда имеет место равенство
И доказательство
А поскольку P обратимо, мы умножаем уравнение справа на обратное, завершая доказательство.
Набор матриц вида A - λ B , где λ - комплексное число, называется пучком ; термин « матричный пучок» может также относиться к паре ( A , B ) матриц. [11]
Если B обратима, то исходную задачу можно записать в виде
что является стандартной задачей на собственные значения. Однако в большинстве ситуаций предпочтительно не выполнять инверсию, а решать обобщенную проблему собственных значений, как было заявлено изначально. Это особенно важно, если A и B - эрмитовы матрицы , поскольку в этом случае B −1 A не является вообще эрмитовым и важные свойства решения больше не очевидны.
Если A и B оба симметричны или эрмитовы, а B также является положительно определенной матрицей , собственные значения λ i действительны, а собственные векторы v 1 и v 2 с различными собственными значениями являются B -ортогональными ( v 1 * Bv 2 = 0 ). [12] В этом случае собственные векторы могут быть выбраны так, чтобы матрица P, определенная выше, удовлетворяла
- или же ,
и существует база обобщенных собственных векторов (это не дефектная задача). [11] Этот случай иногда называют эрмитово определенным карандашом или определенным карандашом . [11]
Смотрите также
- Разложение матрицы
- Нормальная форма Джордана
- Список матриц
- Собственное значение, собственный вектор и собственное подпространство
- Спектральная теорема
- Разложение по сингулярным числам
- Преобразование домохозяина
- Ковариант Фробениуса
- Формула Сильвестра
- Возмущение собственных значений
Заметки
- ↑ Голуб и Ван Лоан (1996 , с. 310)
- ^ Kreyszig (1972 , стр. 273)
- ^ Nering (1970 , стр. 270)
- ^ Хайд, AF; Тведе, Д.Р. (2002). Шен, Сильвия С. (ред.). «Наблюдения за взаимосвязью между собственными значениями, шумом прибора и характеристиками обнаружения». Спектрометрия изображений VIII . Труды SPIE. 4816 : 355. Bibcode : 2002SPIE.4816..355H . DOI : 10.1117 / 12.453777 .
- ^ Тведе, Д.Р .; Хайден, AF (2004). Шен, Сильвия С; Льюис, Пол Э (ред.). «Уточнение и обобщение метода расширения метода обращения ковариационной матрицы путем регуляризации». Спектрометрия изображений IX . Труды SPIE. 5159 : 299. Bibcode : 2004SPIE.5159..299T . DOI : 10.1117 / 12.506993 .
- ^ Хорн и Джонсон (1985) , стр. 133, теорема 2.5.3
- ^ Хорн и Джонсон (1985) , стр. 136, следствие 2.5.11
- ^ а б в г д е Trefethen, Lloyd N .; Бау, Дэвид (1997). Числовая линейная алгебра . СИАМ. ISBN 978-0-89871-361-9.
- ^ Ипсен, Илзе и Ребекка М. Уиллс, Анализ и вычисление рейтинга страниц Google , 7-й международный симпозиум IMACS по итерационным методам в научных вычислениях, Институт Филдса, Торонто, Канада, 5–8 мая 2005 г.
- ^ Quarteroni, Alfio; Сакко, Риккардо; Салери, Фаусто (2000). «раздел 5.8.2». Вычислительная математика . Springer. п. 15. ISBN 978-0-387-98959-4.
- ^ а б в Bai, Z .; Demmel, J .; Dongarra, J .; Ruhe, A .; Ван дер Ворст, Х., ред. (2000). "Обобщенные эрмитовы задачи на собственные значения". Шаблоны для решения алгебраических задач на собственные значения: Практическое руководство . Филадельфия: СИАМ. ISBN 978-0-89871-471-5.
- ^ Парлетт, Бересфорд Н. (1998). Симметричная проблема собственных значений (Перепечатка. Ред.). Филадельфия: Общество промышленной и прикладной математики. п. 345. DOI : 10,1137 / +1,9781611971163 . ISBN 978-0-89871-402-9.
Рекомендации
- Франклин, Джоэл Н. (1968). Матричная теория . Dover Publications. ISBN 978-0-486-41179-8.
- Golub, Gene H .; Ван Лоан, Чарльз Ф. (1996), Матричные вычисления (3-е изд.), Балтимор: Johns Hopkins University Press , ISBN 978-0-8018-5414-9
- Хорн, Роджер А .; Джонсон, Чарльз Р. (1985). Матричный анализ . Издательство Кембриджского университета. ISBN 978-0-521-38632-6.
- Хорн, Роджер А .; Джонсон, Чарльз Р. (1991). Темы матричного анализа . Издательство Кембриджского университета. ISBN 978-0-521-46713-1.
- Крейсциг, Эрвин (1972), Высшая инженерная математика (3-е изд.), Нью-Йорк: Wiley , ISBN 978-0-471-50728-4
- Неринг, Эвар Д. (1970), Линейная алгебра и теория матриц (2-е изд.), Нью-Йорк: Wiley , LCCN 76091646
- Стрэнг, Г. (1998). Введение в линейную алгебру (3-е изд.). Wellesley-Cambridge Press. ISBN 978-0-9614088-5-5.
Внешние ссылки
- Интерактивная программа и учебник по спектральной декомпозиции .