Спектральное разложение матрицы

Спектральное разложение матрицы или разложение матрицы на основе собственных векторов — это представление квадратной матрицы в виде произведения трёх матриц, , где — матрица, столбцы которой являются собственными векторами матрицы , — диагональная матрица с соответствующими собственными значениями на главной диагонали, — матрица, обратная матрице .

Не все матрицы могут быть представлены в таком виде, а только те, которые обладают полным набором собственных векторов, то есть набором из n линейно независимых собственных векторов, где n — это порядок матрицы .

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


Теория собственных векторов и собственных значений матрицы[ | ]

Основная статья: Собственный вектор

Ненулевой вектор размерности N является собственным вектором квадратной матрицы , если он удовлетворяет линейному уравнению

где является скаляром, называемым собственным значением, соответствующим вектору . То есть, собственные вектора — это вектора, которые линейное преобразование всего лишь удлиняет или укорачивает, а коэффициент изменения длины равен собственному значению. Уравнение выше называется уравнением собственных значений или задачей собственных значений.

Из уравнения выше вытекает уравнение для собственных значений

Мы называем многочлен характеристическим многочленом матрицы, а уравнение, называемое характеристическим уравнением, является полиномиальным уравнением N-ого порядка от переменной . Это уравнение будет иметь различных решений, где . Множество решений, то есть, собственных значений, называется спектром матрицы [1][2][3].

Мы можем разложить p на множители

Целое число ni называется алгебраической кратностью собственного значения . Если поле скаляров алгебраически замкнуто, сумма алгебраических кратностей равна N:

Для каждого собственного значения мы имеем отдельное уравнения для собственного значения

Имеется линейно независимих решений каждого такого уравнения для собственных значений. Линейные комбинации mi решений являются собственными векторами, связанными м собственным значением . Целое число mi называется геометрической кратностью значения . Важно понимать, что алгебраическая кратность и геометрическая кратность могут не совпадать, но всегда }}. Простейшим случаем, конечно, является случай, когда . Общее число линейно независимых собственных векторов может быть вычислено путём суммирования геометрических кратностей

Собственные вектора можно проиндексировать собственными значениями с помощью двойного индекса, то есть, будет означать j-й собственный вектор для i-го собственного значения. Собственные вектора можно проиндексировать с помощью более простой нотации одним индексом , где .

Разложение матрицы с помощью собственных векторов[ | ]

Пусть будет квадратной матрицей, состоящей из n линейно независимых собственных векторов qi (). Тогда можно разложить

где является квадратной матрицей, i-ым столбцом которой является собственный вектор матрицы , а является диагональной матрицей, диагональными элементами которой являются соответствующие собственные значения, . Заметим, что только диагонализируемые матрицы могут быть разложены таким образом. Например, дефектная матрица[en] (являющаяся матрицей сдвига) не может быть диагонализирована.

Обычно n собственных векторов qi нормализуются, но это не обязательно. Ненормализованный набор из n собственных векторов vi может быть также использовано в качестве столбцов матрицы . Это можно понять, если заметить, что величина собственных векторов в сокращается в разложении наличием .

Разложение может быть получено из фундаментального свойства собственных векторов:

Пример[ | ]

Вещественная матрица

может быть приведена к диагональному виду путём умножения на невырожденную матрицу

Тогда

для некоторой вещественной диагональной матрицы .

Умножив обе стороны равенства слева на получим:

Равенство выше может быть разложено на две системы уравнений:

Выносим собственные значения x и y:

Получаем

что даёт нам два векторных уравнения:

Последняя система может быть представлена одним векторным равенством, вовлекающих два решения собственных значений:

где представляет два собственных значения x and y, а представляет вектора и .

Перенося в левую часть и вынеся , получим

Поскольку матрица не вырождена, важно, чтобы вектор не был нулевым. Поэтому,

Тогда

даёт нам решения собственных значений для матрицы как или , а результирующая диагональная матрица из разложения матрицы тогда равна .

Если подставить решения обратно в систему уравнений выше получим

Решив уравнения, мы получим

Тогда матрица , требуемая для разложения матрицы равна

То есть:

Обращение матрицы через разложение по собственным векторам[ | ]

Основная статья: Обратная матрица

Если матрицу можно разложить с помощью собственных векторов и если никакое из собственных значений матрицы не равно нулю, матрица является невырожденной и её обратная задаётся равенством

Если матрица является симметричной матрицей, поскольку образуется из собственных векторов матрицы , она гарантированно будет ортогональной, а поэтому . Более того, поскольку является диагональной, её обратную легко вычислить:

Практическое значение[4][ | ]

Если разложение с помощью собственных векторов используется для матрицы измерений с реальными данными, обратная матрица может быть менее значима, если все собственные значения используются в неизменной форме как выше. Это потому, что когда собственные значения становятся относительно маленькими, их вклад в обращение велик. Эти близкие к нулю значения или «шум» системы измерения будет иметь чрезмерное влияние и может помешать решению с помощью обращения.

Было предложено два варианта смягчения последствий : отбрасывание малых или нулевых собственных значений и распространение наименьшего надёжного значения ниже.

Первый вариант смягчения подобен разрежению исходной матрицы, в которой удаляются элементы, которые посчитали незначимыми. Однако, если процесс решения окажется близок к уровню шума, откидывание может удалить компоненты, которые влияют на желаемое решение.

Второй вариант смягчения распространяет собственное значение, так что меньшие значения имею меньшее влияние на обращение, но по-прежнему вносят вклад, так что могут быть найдены решения, близкие к шуму.

Надёжное собственное значение может быть найдено в предположении, что собственные значения крайне близки и низкое значение является хорошим представлением шума измерения (который предполагается низким для большинства систем).

Если собственные значения выстроены по величине, надёжное собственное значение может быть найдено путём минимизации лапласиана отсортированных собственных значений[5]:

где собственные значения помечены буквой s для обозначения сортировки (от английского sorted). Место минимума является наименьшим надёжным собственным значением. В системах измерения квадратный корень из этого надёжного собственного значения является средним шумом относительно других компонент системы.

Функциональное исчисление[ | ]

Разложение по собственным значениям матрицы позволяет много более простое вычисление степенного ряда матриц. Если f (x) задана рядом

то мы знаем, что

Поскольку является диагональной матрицей, функции от очень легко вычислить:

Недиагональные элементы матрицы равны нулю. То есть, также является диагональной матрицей. Таким образом, вычисление сводится просто к вычислению функции от каждого из собственных значений.

Похожая техника работает работаю в более общем виде в голоморфном функциональном исчислении[en], с помощью

. Снова мы находим, что

Примеры[ | ]

которые являются примерами для функций . Более того, является экспонентой матрицы.

Разложение специальных матриц[ | ]

Нормальные матрицы[ | ]

Комплексная квадратная матрица нормальна (что означает, что , где является эрмитово-сопряжённой) тогда и только тогда, когда она может быть разложена

где является унитарной (что означает, что ) и является диагональной матрицей[6]. Столбцы матрицы образуют ортонормальный базис и являются собственными векторами матрицы с соответствуюшими собственными значениями .

Если класс матриц ограничен эрмитовыми матрицами (), то имеет только вещественные значения. Если класс матриц ограничен унитарными матрицами, то все значения лежат на комплексной единичной окружности, то есть, .

Вещественные симметричные матрицы[ | ]

Для любой вещественной симметричной матрицы собственные значения вещественны и собственные вектора можно выбрать вещественными и ортонормальными. Таким образом, вещественная симметричная матрица может быть разложена в

где ортогональная матрица, столбцами которой служат собственные вектора матрицы , а — диагональная матрица, у которой значения на диагонали равны собственным значениям матрицы [7].

Полезные факты[ | ]

Полезные факты о собственных значениях[ | ]

  • Произведение собственных значений равно определителю матрицы
    Заметим, что каждое собственное значение возведено в степень ni, алгебраическую кратность.
  • Сумма собственных значений равна следу матрицы
    Заметим, что каждое собственное значение умножается на ni, алгебраическую кратность.
  • Если собственные значения матрицы есть и обратима, собственные значения матрицы просто равны .
  • Если собственные значения матрицы есть , то собственные значения матрицы просто равны для любой голоморфной функции f.

Полезные факты о собственных векторах[ | ]

  • Если матрица эрмитова и имеет полный ранг, базис собственных векторов можно выбрать взаимно ортогональным. Собственные значения вещественны.
  • Собственные вектора матрицы те же самые, что и собственные вектора матрицы .
  • Собственные вектора определены с точностью до постоянного множителя. То есть, если , то является также собственным вектором для любого скаляра c ≠ 0. В частности, и (для любого ) также являются собственными векторами.
  • В случае вырожденных собственных значений (собственное значение появляются более одного раза), собственные вектора имеют дополнительную степень свободы вращения, то есть любая линейная (ортонормальная) комбинация собственных векторов с одним и тем же собственным значением является сама собственным вектором.

Полезные факты о разложении с помощью собственных векторов[ | ]

  • Матрица может быть разложена с помощью собственных векторов тогда и только тогда, когда число линейно независимых собственных векторов равно размерности собственного вектора:
  • Если не имеет кратных корней, то есть, если , то может быть разложена.
  • Из утверждения «матрица может быть разложена» не следует, что имеет обратную.
  • Из утверждения «матрица имеет обратную » не следует, что может быть разложено с помощью собственных векторов. Контрпримером является матрица , которая является обратимой дефектной матрицей[en].

Полезные факты об обратной матрице[ | ]

  • Матрица обратима тогда и только тогда, когда
  • Если и , обратная матрица задаётся равенством

Численные вычисления[ | ]

Подробное рассмотрение темы: Алгоритм вычисления собственных значений

Численное вычисление собственных значений[ | ]

Предположим, что мы желаем вычислить собственные значения заданной матрицы. Если матрица маленькая, мы может их вычислить символьно с помощью характеристического многочлена. Однако, это часто невозможно для больших матриц и в этом случае мы должны использовать численные методы.

На практике собственные значения больших матриц не вычисляются с помощью характеристического многочлена. Вычисление многочлена становится само по себе затратным, а точные (символьные) корни многочлена высокой степени трудно вычислить и выразить — из Теорема Абеля о неразрешимости уравнений в радикалах следует, что корни многочленов высокой степени (5 и выше) не могут быть в общем случае представлены как выражения от корней n-ой степени. По этой причине общие алгоритмы поиска собственных векторов и собственных значений работают итеративно.

Существуют итеративные численные алгоритмы аппроксимации корней многочленов, такие как метод Ньютона, но, как правило, непрактично строить характеристический многочлен, а затем применять эти методы. Одной из причин является то, что малые ошибки округления[en] в коэффициентах характеристического многочлена могут привести к большим ошибкам в собственных значениях и собственных векторах — корни являются крайне плохо обусловленной функцией от коэффициентов[8].

Простым и точным итеративным методом является степенной метод — выбирается случайный вектор и вычисляется последовательность единичных векторов

Эта последовательность почти всегда сходится к собственному вектору, соответствующему собственному значению наибольшей величины, что обеспечивает наличие ненулевых компонент собственного вектора в базисе собственных векторов (а также обеспечивает, что имеется только одно собственное значение наибольшей величины). Этот простой алгоритм полезен в некоторых практических приложениях. Напримерample, Google использует его для вычисления ссылочного ранжирования документов в их поисковике[9]. Также степенной метод является отправной точкой для многих других сложных алгоритмов. Например, если хранить не только последний вектор последовательности, а смотреть в линейной оболочке всех векторов последовательности, можно получить лучшую (сходящуюся быстрее) аппроксимацию собственного вектора, и эта идея является основой итерации Арнольди[8]. Также важный QR-алгоритм также основан на слегка изменённом степенном методе[8].

Численное вычисление собственных векторов[ | ]

Если собственные значения вычислены, собственные вектора можно вычислить путём решения уравнения

с помощью исключения Гаусса или любого другого метода решения матричного уравнения.

Однако, в практических методах нахождения собственных значений матриц большого размера собственные вектора обычно вычисляются другими способами как побочный продукт вычисления собственного значения. В степенном методе, например, собственный вектор, в общем-то, вычисляется перед вычислением собственного значения (который обычно вычисляется согласно отношению Рэлея для собственного вектора)[8]. В QR-алгоритме для эрмитовой матрицы (или любой нормальной матрицы), ортономальные собственные вектора получаются как произведение матриц из шагов алгоритма[8]. (Для матриц более общего вида QR-алгоритм сначала осуществляет разложение Шура, из которого собственные вектора могут быть получены обратной подстановкой[10]) Для эрмитовых матриц алгоритм поиск собственных значений «разделяй и властвуй»[en] более эффективен чем QR-алгоритм, если нужны как собственные вектора, так и собственные значения[8].

Дополнительные темы[ | ]

Обобщённые собственные пространства[ | ]

Напомним, что геометрическую кратность собственного значения можно описать как размерность связанного собственного пространства, ядра матрицы . Алгебраическая кратность может также рассматриваться как размерность — это размерность связанного обобщённого собственного пространства (в 1-м смысле), которое является ядром матрицы для любого достаточно большого k. То есть, это пространство обобщённых собственных векторов (в первом смысле), где обобщённый собственный вектор — это любой вектор, который рано или поздно станет 0, если применить достаточное число раз. Любой собственный вектор является обобщённым собственным вектором, а потому любое собственное пространство содержится в связанном обобщённом собственном пространстве. Это даёт простое доказательство, что геометрическая кратность никогда не превосходит алгебраическую кратность.

Такое использование не следует путать с обобщённой задачей собственных значений, описанной ниже.

Сопряжённый собственный вектор[ | ]

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

Например, в теории когерентного электромагнитного рассеяния линейное преобразование представляет действие, осуществляемое рассеивающим объектом, а собственные вектора представляют поляризационные состояния электромагнитной волны. В оптике координатная система определяется с волновой точки зрения, известной как выравнивание прямого рассеивания[en] (англ. Forward Scattering Alignment, FSA), и порождает уравнения обычных собственных значений, в то время как в радарах координатная система определяется со стороны радара, она известна как выравнивание обратного рассеивания[en] (англ. Back Scattering Alignment, BSA) и порождает уравнения для сопряжённых собственных векторов.

Обобщённая задача нахождения собственных значений[ | ]

Обобщённая задача нахождения собственных значений (во втором смысле) — это задача нахождения вектора , удовлетворяющего равенству

где и являются матрицами. Если удовлетворяет этому равенству для некоторого , то мы называем обобщённым собственным вектором матриц и (во втором смысле), а называется обобщённым собственным значением матриц и (во втором смысле), соответствующим обобщённому собственному вектору . Возможные значения должны удовлетворять следующему равенству

Если можно найти линейно независимых векторов , таких что для любого , , мы определяем матрицы и следующим образом

Тогда выполняется следующее равенство

Доказательство

А поскольку обратима, умножим на эту обратную и получим требуемый результат.

Множество матриц вида , где — комплексное число, называется пучком. Термин пучок матриц может относиться также к паре матриц [11].

Если матрица обратима, то исходную задачу можно переписать в виде

что является стандартной задачей собственных значений. В большинстве ситуаций, однако, нежелательно осуществлять это обращение, а решать обобщённую задачу собственных значений. Это особенно важно, если матрицы и эрмитовы, поскольку в этом случае в общем случае обычно не эрмитова и важные свойства решения больше не проявляются.

Если обе матрицы и симметричны и эрмитовы и является кроме того положительно определённой, собственные значения вещественны и собственные вектора и с различными собственные значения -ортогональны ()[12]. В этом случае собственные вектора можно выбрать так, что матрица , определённая выше, удовлетворяет условиям

or ,

и существует базис обобщённых собственных векторов (он не является дефектной матрицей[en])[11]. Этот случай иногда называется эрмитово определённым пучком[11].

См. также[ | ]

Примечания[ | ]

  1. Golub, Van Loan, 1996, с. 310.
  2. Kreyszig, 1972, с. 273.
  3. Nering, 1970, с. 270.
  4. Hayde, Twede, 2002, с. 355.
  5. Twede, Hayden, 2004, с. 299.
  6. Horn, Johnson, 1985, с. 133 Theorem 2.5.3.
  7. Horn, Johnson, 1985, с. 136 Theorem 2.5.3 Corollary 2.5.11.
  8. 1 2 3 4 5 6 Trefethen, Bau, 1997.
  9. Ipsen, Wills, 2005.
  10. Quarteroni, Sacco, Saleri, 2000, с. 15.
  11. 1 2 3 Bai, Demmel, 2000.
  12. Parlett, 1998, с. 345.

Литература[ | ]

Ссылки[ | ]