Полная Проблема

Собственных значений — задача вычисления всех (в отличие от частичной проблемы).собственных значений квадратной матрицы, обычно действительной или комплексной. Часто помимо собственных значений требуется еще и построение базиса из собственных или корневых векторов матрицы. Решение П. п. собственных значений матрицы Асводится к построению характеристич. многочлена j А этой матрицы и вычислению его корней, действительных или комплексных (последнее обусловливает невозможность нахождения собственных значений конечным вычислительным процессом). Для каждого собственного значения l соответствующие собственные векторы могут быть определены из однородной системы линейных уравнений ( А-lЕ) х=0 ( Е — единичная матрица). При вычислениях над полем комплексных чисел достаточным условием существования базиса из собственных векторов является простота спектра, а необходимое и достаточное условие состоит в том, чтобы алгебраич. кратность каждого собственного значения l. (т. е. его кратность как корня характеристич. многочлена jA) совпадала с его геометрич. кратностью, под к-рой понимается дефект матрицы А-l Е. При необходимости вычисления корневых векторов высоты, превосходящей единицу, приходится рассматривать однородные системы вида Примерно по этой схеме строились и численные методы решения П. п. собственных значений, практиковавшиеся до кон. 1940-х гг. В 1930-х гг. были разработаны высокоэффективные (по количеству арифметич. операций) алгоритмы вычисления характеристич. многочлена матрицы по ее коэффициентам. Так, в методе Данилевского построение характеристич. многочлена матрицы порядка пвыполняется с затратой ~n3 мультипликативных операций (см. [1], [2]). Методы этой группы получили название прямых, или точных, по той причине, что, проводимые в точной арифметике, они дают точные значения коэффициентов характеристич. многочлена. Их поведение в условиях реальных вычислений, сопровождающихся ошибками округлений, не могло быть проверено для задач сколько-нибудь значительного порядка до появления цифровых ЭВМ. Такая проверка произошла в 1950-х гг., в результате чего прямые методы были полностью вытеснены из численной практики. Катастрофич. неустойчивость вычисления собственных значений, связанная с этими методами, имеет две основные причины. Во-первых, коэффициенты характеристич. многочлена в большинстве точных методов прямо или косвенно определяются как компоненты решения системы линейных уравнений, матрица к-рой составлена по столбцам из векторов v, Av, A2v, . . ., An-1v, где v — начальный вектор метода. Такая матрица обычно очень плохо обусловлена, что видно хотя бы из того, что длины ее столбцов, как правило, весьма различны, причем тем больше, чем больше п. Тем самым коэффициенты характеристич. многочлена в общем случае вычисляются с очень большими ошибками. Во-вторых, сама по себе задача вычисления корней многочлена зачастую оказывается численно неустойчивой. В этом отношении показателен пример (см. [3]): если у многочлена изменить коэффициент при x19 с -210 на -210+2-23, то у возмущенного многочлена появится пять пар комплексно сопряженных корней; у одной из этих пар мнимые части достигают Подобная чувствительность собственных значений матрицы к изменениям коэффициентов характеристич. многочлена обычно не сопровождается сравнимой чувствительностью в отношении элементов самой матрицы. Так, если указанный многочлен р(х).является характеристич. многочленом симметрич. матрицы А, то изменения порядка 2-23 в любом элементе матрицы приводят самое большее к изменениям того же порядка в ее собственных значениях. Современные численные методы решения П. п. собственных значений находят собственные значения без предварительного вычисления характеристич. многочлена (см. Итерационные методы решения проблемы собственных значений матрицы). Трудоемкость лучших из этих методов составляет ~kn3 мультипликативных операций, где п — порядок матрицы, k — константа, не зависящая от п и имеющая смысл среднего числа итераций метода, приходящегося на вычисление одного собственного значения. В QR -алгоритме значения kобычно заключены между 1,5 и 2. Приближенные собственные значения (векторы) ( )-матрицы А, вычисленные ортогональным методом М(QR -алгоритмом для матриц общего вида, методом Якоби или методами, основанными на делении спектра, в случае симметрических и эрмитовых матриц), можно интерпретировать как точные собственные значения (векторы) возмущенной(ых) матрицы (матриц) A+FM. Здесь FM- матрица эквивалентного возмущения метода М — допускает оценку вида (1) где e — относительная точность машинной арифметики, — евклидова матричная норма, f(n) — функция вида Ckna. Число 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 становится кратным, сама постановка вопроса о чувствительности отдельного собственного направления теряет смысл и нужно говорить о чувствительности собственного (или инвариантного) подпространства. Качественно оценки (3) и (4) означают, что величина возмущения каждого собственного значения диагона-лизуемой матрицы Апропорциональна величине возмущения F, а множителями пропорциональности выступают числа обусловленности, индивидуальные либо глобальные. Если жорданова форма А — недиагональная и собственному значению l отвечает элементарный делитель (z-l)m, то возмущение l в общем случае пропорционально уже не ||F||, a . Наиболее важным частным случаем П. п. собственных значений является вычисление всех собственных значений (собственных векторов) действительной симметрической либо комплексной эрмитовой матрицы А . Коэффициенты перекоса такой матрицы равны единице, и приближенная оценка (3) переходит в точное неравенство Матрицу Рв (4) можно выбрать ортогональной либо унитарной, и потому глобальное число обусловленности в спектральной норме равно единице. Независимо от кратности точек спектра Асуществует такое упорядочение собственных значений матрицы A+F, что выполняются при всех iсоотношения Еще более точные оценки возможны, если не только сама матрица Аявляется симметрической (эрмитовой), но и ее возмущение F(см. [5]). Помимо указанных имеется еще ряд апостериорных оценок точности вычисленных собственных значений и векторов. Они наиболее эффективны для симметрических и эрмитовых матриц А. Пусть — приближенный, а х i — точный собственный вектор для простого собственного значения l матрицы А . Оба вектора предполагаются нормированными. Наилучшую оценку li, к-рую можно получить посредством вектора , дает значение функционала Рэлея соответствующее , т. е. число (этот факт имеет силу для произвольной, не обязательно эрмитовой матрицы А). Вектор наз. вектором невязки. Пусть Оценку величины алегко получить но вычисленным собственным значениям . Справедливы оценки: Если li — кратное собственное значение или имеется группа близких к li собственных значений, то нужно оценивать суммарное возмущение всей этой группы и возмущение соответствующего ей инвариантного подпространства (см. [5]). Наряду с описанной П. п. собственных значений часто возникает необходимость в решении т. н. обобщенной проблемы собственных значений (5) В наиболее важном случае обобщенной проблемы собственных значений матрицы Аи Вявляются симметрическими (эрмитовыми), и одна из них положительно определена. Теория и методы численного решения задачи (5) в этом случае параллельны теории и методам для обычной симметрической (эрмитовой) проблемы собственных значений. Если ни одна из матриц Аи Вне является определенной или хотя бы одна из них даже симметрической, то пользуются т. н. QZ -алгоритмом (см. [6]), своеобразным обобщением QR -алгоритма. Необходимо отметить, что здесь возможны новые эффекты, ненаблюдаемые в обычной П. п. собственных значений: бесконечные собственные значения, непрерывный спектр. Еще более сложны нелинейные задачи на собственные значения Такие задачи решают обычно путем сведения к линейным более высокого порядка (см. [7]). Лит.:[1] Данилевский A.M., "Матем. сб.", 1937, т. 2, № 1, с. 169-71; [2] Фаддеев Д. К., Фаддеева В. Н., Вычислительные методы линейной алгебры, 2 изд., М., 1963; [3] Wilkinsоn J. H., Hounding errors in algebraic processes, Englewood cliffs (N.Y.), 1963; [4] Уилкинсон Д ж. Х., Алгебраическая проблема собственных значений, пер. с англ., М., 1970; (5] Парлетт Б., Симметричная проблема собственных значений. Численные методы, пер. с англ., М., 1983; [6] Моlеr С. В., Stewart G. W., "SIAM J. Num. Anal.", 1973, v. 10, p. 241; [7] Кублановская В. Н., в сб.: Вычислительные методы линейной алгебры, Новосиб., 1980, с. 37-53. X. Д. Икрамов.