WikiSort.ru - Не сортированное

Поиск собственных чисел

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

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

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

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

${\displaystyle {\frac {Av}{\|Av\|}},{\frac {A^{2}v}{\|A^{2}v\|}},{\frac {A^{3}v}{\|A^{3}v\|}},\dots }$

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

Поиск собственных векторов

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

${\displaystyle \left(\mathbf {A} -\lambda _{i}\mathbf {I} \right)\mathbf {v} _{i,j}=0\!\ }$

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

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

Преобразование Якоби

QR/QL метод

Степенные методы