Алгоритм вычисления собственных значений — алгоритм, позволяющий определить собственные значения и собственные векторы заданной матрицы. Создание эффективных и устойчивых алгоритмов для этой задачи является одной из ключевых задач вычислительной математики.
Собственные значения и собственные векторы
Если задана квадратная матрица над вещественными или комплексными числами, то собственное значение и соответствующий ему корневой вектор — это пара, удовлетворяющая равенству:
где ненулевой вектор-столбец, является единичной матрицей, — положительным целым, а и могут быть комплексными, даже если вещественна. Если , вектор просто называется собственным вектором. В этом случае . Любое собственное значение матрицы имеет простойТермин «простой» здесь употребляется лишь для подчёркивания различия между «собственным вектором» и «корневым вектором». собственный вектор, соответствующий ему так, что если — наименьшее целое, при котором для корневого вектора , то будет простым собственным вектором. Значение всегда можно взять меньше либо равным . В частности, для всех корневых векторов , соответствующих
Для любого собственного значения матрицы ядро состоит из всех собственных векторов, соответствующих , (вместе с 0) и называется собственным подпространством числа , а векторное подпространство состоит из всех корневых векторов (дополненное нулевым вектором) и называется корневым подпространством. Геометрическая кратность значения является размерностью его собственного подпространства. Алгебраическая кратность значения является размерностью его корневого подпространства. Дальнейшие термины связаны с равенством:
Здесь — определитель, — все различные собственные значения матрицы , а — соответствующие алгебраические кратности. Функция — это характеристический многочлен матрицы . Таким образом, алгебраическая кратность является кратностью собственных значений как корней характеристического многочлена. Поскольку любой собственный вектор является корневым вектором, геометрическая кратность меньше либо равна алгебраической кратности. Сумма алгебраических кратностей равна степени характеристического многочлена. Уравнение называется характеристическим уравнением, поскольку его корни являются в точности собственными значениями матрицы . По теореме Гамильтона — Кэли сама матрица удовлетворяет тому же самому уравнению: где постоянный член умножается на единичную матрицу .. Как следствие, столбцы матрицы должны быть либо 0, либо корневыми векторами, соответствующими собственному значению , поскольку они уничтожаются матрицей
Любой набор корневых векторов различных собственных значений линейно независим, так что базис для всего можно выбрать из набора корневых векторов. Точнее этот базис можно выбрать и выстроить так, что: если и имеют одно и то же собственное значение, то тоже будет верно для любого при между и ; если не является простым собственным вектором и если его собственное значение, то (в частности должен быть простым собственным вектором). Если эти базисные вектора расположить как столбцы матрицы , то можно использовать для преобразования матрицы в её нормальную жорданову форму:
где — собственные значения, если и в других случаях.
Если является обратимой матрицей и — собственное значение матрицы с соответствующим корневым вектором , то . Таким образом, является собственным значением матрицы с соответствующим корневым вектором . Таким образом, подобные матрицы имеют те же самые собственные значения.
Нормальные, эрмитовы и вещественные симметричные матрицы
Эрмитово-сопряжённая матрица к комплексной матрице — это траспонированная матрица с заменой всех элементов на сопряжённые значения: . Квадратная матрица называется нормальной, если она коммутирует с эрмитово-сопряжённой: . Матрица называется эрмитовой, если она равна своей сопряжённой: . Все эрмитовы матрицы нормальны. Если имеет только вещественные элементы, то сопряжённая к ней — это просто транспонированная матрица, и она будет эрмитовой в том и только в том случае, когда она симметрична. Если применить это к столбцам, сопряжённость можно использовать для определения канонического скалярного произведения в : Такой порядок в скалярном произведении (с сопряжённым элементом слева) предпочитают физики. Алгебраисты часто предпочитают запись .. Нормальные, эрмитовы и вещественные симметричные матрицы имеют ряд полезных свойств: Каждый корневой собственный вектор нормальной матрицы является простым собственным вектором. Любая нормальная матрица подобна диагональной, поскольку её нормальная жорданова форма является диагональной матрицей. Собственные вектора, соответствующие различным собственным значениям нормальной матрицы, ортогональны. Для любой нормальной матрицы имеет ортонормальный базис, состоящий из собственных векторов матрицы . Соответствующая матрица собственных векторов является унитарной. Собственные значения эрмитовой матрицы являются вещественными числами, поскольку для ненулевого собственного вектора . Если матрица вещественна, существует ортонормальный базис для , состоящий из собственных векторов матрицы , в том и только в том случае, когда симметрична.
Возможно как для вещественных, так и для комплексных матриц иметь все собственные значения вещественными, не будучи при этом эрмитовой матрицей. Например, вещественная треугольная матрица имеет все свои собственные значения на диагонали, но, в общем случае, не симметрична.
Число обусловленности Любую задачу вычислительной математики можно рассматривать как вычисление некоторой функции ƒ от некоторого аргумента . Число обусловленности задачи — это отношение относительной ошибки результата вычисления к относительной ошибке параметра функции и зависит как от функции, так и от параметра. Число обусловленности описывает насколько возрастает ошибка во время вычислений. Десятичный логарифм этого числа говорит о количестве знаков, которые мы теряем по отношению к исходным данным. Число обусловленности относится к наилучшему сценарию, отражая нестабильность самой задачи, независимо от способа решения. Никакой алгоритм не может дать результат лучше, чем определённый числом обусловленности, разве что случайно. Однако плохо разработанный алгоритм может дать существенно более плохие результаты. Например, как будет упомянуто ниже, задача нахождения собственных значений нормальной матрицы всегда хорошо обусловлена, однако задача нахождения корней многочлена может быть очень плохо обусловлена. Такие алгоритмы вычисления собственных значений, которые работают путём нахождения корней характеристического многочлена, могут оказаться плохо обусловленными, даже если сама задача хорошо обусловлена.
Для задачи решения системы линейных уравнений , где является обратимой, число обусловленности определяется выражением , где — операторная норма, подчинённая обычной евклидовой норме на . Поскольку это число не зависит от и является тем же самым как для , так и для , оно обычно называется числом обусловленности матрицы . Это значение является также абсолютным значением отношения наибольшего собственного значения матрицы к её наименьшему собственному значению. Если является унитарной, то , так что . В общем случае для матриц часто сложно вычислить операторную норму. По этой причине обычно используют другие нормы матрицы для оценки числа обусловленности.
Для задачи вычисления собственных значений , что если является собственным значением диагонализируемой матрицы с матрицей собственных векторов , то абсолютная ошибка вычисления ограничена произведением и абсолютной ошибкой в :
. Как следствие, число обусловленности для вычисления равно . Если матрица нормальна, то является унитарной и . Таким образом, задача вычисления собственных значений нормальных матриц хорошо обусловлена.
Было показано, что число обусловленности задачи вычисления собственного подпространства нормальной матрицы , соответствующего собственному значению , обратно пропорционально минимальному расстоянию между и другими, отличными от , собственными значениями матрицы . В частности, задача определения собственного подпространства для нормальных матриц хорошо обусловлена для изолированных собственных значений. Если собственные значения не изолированы, лучшее, на что мы можем рассчитывать, это определение подпространства всех собственных векторов близлежащих собственных значений.
Алгоритмы Любой нормированный многочлен является характеристическим многочленом сопровождающей матрицы, поэтому алгоритм для вычисления собственных значений можно использовать для нахождения корней многочленов. Теорема Абеля — Руффини показывает, что любой такой алгоритм для размерности большей 4 должен либо быть бесконечным, либо вовлекать функции более сложные, чем элементарные арифметические операции или дробные степени. По этой причине алгоритмы, вычисляющие точно собственные значения за конечное число шагов, существуют только для специальных классов матриц. В общем случае алгоритмы являются итеративными, дающими на каждой итерации очередное приближение к решению.
Некоторые алгоритмы дают все собственные значения, другие дают несколько значений или даже всего одно, однако и эти алгоритмы можно использовать для вычисления всех собственных значений. Как только собственное значение матрицы определено, его можно использовать либо для приведения алгоритма к получению другого собственного значения, либо для сведения задачи к такой, которая не имеет в качестве решения.
Приведение обычно осуществляется сдвигом: заменяется на для некоторой константы . Собственное значение, найденное для , должно быть добавлено к , чтобы получить собственное значение матрицы . Например, в степенном методе . Итерация степенного метода находит самое большое по абсолютной величине значение, так что даже если является приближением к собственному значению, итерация степенного метода вряд ли найдёт его во второй раз. И наоборот, методы, основанные на обратных итерациях находят наименьшее собственное значение, так что выбирается подальше от в надежде оказаться ближе к какому-нибудь другому собственному значению.
Приведение можно совершить путём сужения матрицы к пространству столбцов матрицы . Поскольку вырождена, пространство столбцов имеет меньшую размерность. Алгоритм вычисления собственных значений можно тогда применить к этой суженой матрице. Процесс можно продолжать, пока не будут найдены все собственные значения.
Если алгоритм не даёт к собственные значения, общей практикой является применение алгоритма, основанного на обратной итерации, с приравниванием к ближайшей аппроксимации собственного значения. Это быстро приводит к собственному вектору ближайшего к собственного значения. Для небольших матриц альтернативой служит использование столбцового подпространства произведения для каждого из остальных собственных значений
Матрицы Хессенберга и трёхдиагональные матрицы
Поскольку собственными значениями треугольной матрицы являются диагональные элементы, в общем случае не существует конечного метода, подобного исключениям Гаусса, для приведения матрицы к треугольной форме, сохраняя при этом собственные значения, однако можно получить нечто близкое к треугольной матрице. Верхняя матрица Хессенберга — это квадратная матрица, у которой все элементы ниже первой поддиагонали равны нулю. Нижняя матрица Хессенберга — это квадратная матрица, у которой все члены выше первой наддиагонали равны нулю. Матрицы, которые являются как нижними, так и верхними матрицами Хессенберга — это трёхдиагональные матрицы. Матрицы Хессенберга и трёхдиагональные матрицы являются исходными точками многих алгоритмов вычисления собственных значений, поскольку нулевые значения уменьшают сложность задачи. Существует несколько методов сведения матриц к матрицам Хессенберга с теми же собственными значениями. Если исходная матрица симметрична или эрмитова, то результирующая матрица будет трёхдиагональной.