Математическая энциклопедия - полная проблема

собственных значений задача вычисления всех (в отличие от частичной проблемы).собственных значений квадратной матрицы, обычно действительной или комплексной. Часто помимо собственных значений требуется еще и построение базиса из собственных или корневых векторов матрицы.

Решение П. п. собственных значений матрицы Асводится к построению характеристич. многочлена j А этой матрицы и вычислению его корней, действительных или комплексных (последнее обусловливает невозможность нахождения собственных значений конечным вычислительным процессом). Для каждого собственного значения l соответствующие собственные векторы могут быть определены из однородной системы линейных уравнений ( А-lЕ) х=0 ( Е - единичная матрица). При вычислениях над полем комплексных чисел достаточным условием существования базиса из собственных векторов является простота спектра, а необходимое и достаточное условие состоит в том, чтобы алгебраич. кратность каждого собственного значения l. (т. е. его кратность как корня характеристич. многочлена jA) совпадала с его геометрич. кратностью, под к-рой понимается дефект матрицы А-l Е. При необходимости вычисления корневых векторов высоты, превосходящей единицу, приходится рассматривать однородные системы вида

Примерно по этой схеме строились и численные методы решения П. п. собственных значений, практиковавшиеся до кон. 1940-х гг. В 1930-х гг. были разработаны высокоэффективные (по количеству арифметич. операций) алгоритмы вычисления характеристич. многочлена матрицы по ее коэффициентам. Так, в методе Данилевского построение характеристич. многочлена матрицы порядка пвыполняется с затратой ~n³ мультипликативных операций (см. [1], [2]).

Методы этой группы получили название прямых, или точных, по той причине, что, проводимые в точной арифметике, они дают точные значения коэффициентов характеристич. многочлена. Их поведение в условиях реальных вычислений, сопровождающихся ошибками округлений, не могло быть проверено для задач сколько-нибудь значительного порядка до появления цифровых ЭВМ. Такая проверка произошла в 1950-х гг., в результате чего прямые методы были полностью вытеснены из численной практики. Катастрофич. неустойчивость вычисления собственных значений, связанная с этими методами, имеет две основные причины. Во-первых, коэффициенты характеристич. многочлена в большинстве точных методов прямо или косвенно определяются как компоненты решения системы линейных уравнений, матрица к-рой составлена по столбцам из векторов v, Av, A²v, . . ., A^n-1v, где v - начальный вектор метода. Такая матрица обычно очень плохо обусловлена, что видно хотя бы из того, что длины ее столбцов, как правило, весьма различны, причем тем больше, чем больше п. Тем самым коэффициенты характеристич. многочлена в общем случае вычисляются с очень большими ошибками. Во-вторых, сама по себе задача вычисления корней многочлена зачастую оказывается численно неустойчивой. В этом отношении показателен пример (см. [3]): если у многочлена

изменить коэффициент при x¹⁹ с -210 на -210+2^-23, то у возмущенного многочлена появится пять пар комплексно сопряженных корней; у одной из этих пар мнимые части достигают

Подобная чувствительность собственных значений матрицы к изменениям коэффициентов характеристич. многочлена обычно не сопровождается сравнимой чувствительностью в отношении элементов самой матрицы. Так, если указанный многочлен р(х).является характеристич. многочленом симметрич. матрицы А, то изменения порядка 2^-23 в любом элементе матрицы приводят самое большее к изменениям того же порядка в ее собственных значениях.

Современные численные методы решения П. п. собственных значений находят собственные значения без предварительного вычисления характеристич. многочлена (см. Итерационные методы решения проблемы собственных значений матрицы). Трудоемкость лучших из этих методов составляет ~kn³ мультипликативных операций, где п - порядок матрицы, k - константа, не зависящая от п и имеющая смысл среднего числа итераций метода, приходящегося на вычисление одного собственного значения. В QR -алгоритме значения kобычно заключены между 1,5 и 2.

Приближенные собственные значения (векторы) ( )-матрицы А, вычисленные ортогональным методом М(QR -алгоритмом для матриц общего вида, методом Якоби или методами, основанными на делении спектра, в случае симметрических и эрмитовых матриц), можно интерпретировать как точные собственные значения (векторы) возмущенной(ых) матрицы (матриц) A+FM. Здесь FM- матрица эквивалентного возмущения метода М - допускает оценку вида

(1)

где e относительная точность машинной арифметики, евклидова матричная норма, f(n) функция вида Ckn^a. Число kописано выше, а точные значения константы Си показателя a зависят от таких деталей вычислительного процесса, как способ округления, использование операции накопления скалярных произведений и т. д. Обычное значение aравно 2.

Располагая априорной оценкой (1), можно оценить точность вычисления собственных значений (векторов), достигаемую в методе М. Эта точность зависит от обусловленности отдельных собственных значений (собственных подпространств).

Пусть l простое собственное значение матрицы А, х - соответствующий нормированный собственный вектор, у - нормированный собственный вектор транспонированной матрицы для того же собственного значения. При возмущении матрицы Ана матрицу Fвозмущение собственного значения l с точностью до малых 2-го порядка выражается величиной

(2) и оценивается как

(3)

(|| ||2 спектральная норма). Таким образом, чувствительность lк возмущениям матрицы Ахарактеризуется числом , наз. (индивидуальным) числом обусловленности этого собственного значения. В случае, когда оба вектора хи удействительные, число s^-1(l) имеет простой геометрич. смысл: это косинус угла между векторами хи у, что объясняет другое наименование s(l) коэффициент перекоса, соответствующий l.

Если матрица Адиагонализуема (т. е. имеет базис из собственных векторов), то обусловленность ее собственных значений li может быть охарактеризована и интегрально. Пусть Р - матрица, составленная по столбцам из собственных векторов li и имеющая среди всех таких матриц наименьшее число обусловленности. Справедлива теорема (см. [4]): все собственные значения возмущенной матрицы А+F заключены в области комплексной плоскости, являющейся объединением кругов

(4)

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

Число cond Рназ. числом обусловленности матрицы Апо отношению к П. п. собственных значений. Выражаемое в спектральной норме, оно связано с коэффициентами перекоса следующим образом:

Более сложно зависит от возмущения матрицы Авозмущение собственного вектора х, относящегося к простому собственному значению l. Оно определяется, вообще говоря, не только коэффициентом перекоса, соответствующим самому l, но и коэффициентами перекоса для прочих собственных значений. Чувствительность собственного вектора хвозрастает и при наличии собственных значений, близких к l. В предельном случае, когда l становится кратным, сама постановка вопроса о чувствительности отдельного собственного направления теряет смысл и нужно говорить о чувствительности собственного (или инвариантного) подпространства.