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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

Приложения[править | править код]

Алгоритмы вычисления[править | править код]

Поиск собственных чисел[править | править код]

Предположим что мы хотим вычислить собственные числа заданной матрицы. Если матрица маленькая (2х2, 3х3) то мы можем найти собственные числа используя характеристический полином. Конечно, этот подход не применим для более крупных матриц, и в этом случае необходимо использовать численные методы.

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

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

Простым и точным итеративным методом считается "степенной метод": задается случайный вектор v и вычисляется последовательность из единичных векторов:

Данная последовательность почти всегда сходится к собственному вектору, соответствующему максимальному по абсолютному значению собственному числу. Этот простой алгоритм полезен в ряде практических приложений, например, Google использует его для определения ранга страницы в своем движке поисковика. Также, степенной метод берется за основу для построения более сложных алгоритмов. Напимер, сохраняя не только последний вектор в последовательности, но вместо этого анализируя все вектора в последовательности, можно построить более быстро сходящуюся апроксимацию собственного вектора, такая идея лежит в основе итеации Арнольди. Или же, один из основных методов QR-алгоритм так же исользует видоизмененный вариант степенного метода.

Поиск собственных векторов[править | править код]

Как только собственные числа определены, собственные вектора можно найти решив уравнение:

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

Тем не менее, в практических реализациях методов поиска собственных чисел, собственных вектора обычно получаются другим путем, как вторичный продукт вычисления собственных чисел. В степенном методе, например, собственный вектор находится до нахождения собственного числа (которое обычно вычисляется через отношения Релея из собственного вектора). В QR алгоритме для эрмитовых матриц (или любых нормальных матриц), ортонормированные собственные вектора получаются в результате произведения Q матриц найденных на каждом шаге алгоритма. (Для матриц общего вида, QR алгоритм сначала использует разложение Шура, из которого собственные вектора можно получить процедурой обратной подстановки). Для эрмитовых матриц разработан алгоритм "Разделяй и влавствуй" который оказывается более эффективным чем QR-алгоритм когда необходимо получить сразу собственные числа и собственные вектора.

Преобразование Якоби[править | править код]

QR/QL метод[править | править код]

Степенные методы[править | править код]

Обратная итерация[править | править код]

Итерация Арнолди[править | править код]

См. также[править | править код]