Ранее мы установили связь между числом обусловленности матрицы и ее собственными значениями, одна из рассмотренных норм матрицы также требовала вычисления собственных значений. Определение спектральных характеристик оператора – часто встречаемая и весьма важная задача прикладной математики. В нашем случае, когда оператор действует в конечномерном векторном пространстве и является линейным, вопрос определения его собственных значений может быть сформулирован в терминах собственных значений матрицы, представляющей оператор. Различают полную и неполную проблему собственных значений – нахождение всех собственных значений и соответствующих векторов и нахождение одного или нескольких (не всех) собственных значений и соответствующих собственных векторов. Неполная проблема возникает, например, при оценке сходимости итерационных методов решения СЛАУ, когда достаточно определить максимальное по модулю собственное значение.
Различают прямые и итерационные методы.
Прямые методы основаны на применении преобразований подобия. Матрица приводится к такому виду, для которого просто выписать коэффициенты характеристического уравнения, затем ищутся его корни какими-либо известными методами. Основным достоинством прямых методов является их возможность применения к широкому классу матриц. Их недостатком является чувствительность корней многочлена к вариации коэффициентов (к погрешностям, с которыми считаются коэффициенты многочлена). Прямые методы, являясь экономичными по числу необходимых вычислительных операций, устойчивы только для матриц невысокого порядка ( ), а в случае близких по значению или кратных корней – меньшего порядка. Т.о. область использования прямых методов не велика.
В итерационных методах вычисление собственных значений определяется без вычисления характеристического многочлена лишь по исходной матрице. Как правило, вычисления сопровождаются и определением собственного вектора. Собственные значения и собственные векторы в итерационных методах вычисляются как пределы итерационных последовательностей. Итерационные методы более трудоемки, чем прямые, но обладают простотой реализации, единообразием действий и большей устойчивостью, что выдвигает их в лидеры при компьютерном решении задач большой размерности.
Ненулевой вектор
, удовлетворяющий уравнению
, называется собственным вектором оператора
. Число
называется собственным значением. Совокупность собственных значений оператора образует его спектр. Собственное значение и соответствующий собственный вектор образуют собственную пару
.
Собственный вектор совместно с нулевым вектором образуют инвариантное подпространство пространства , вектора этого подпространства коллинеарны, т.е. под действием оператора
не изменяют своего направления, а лишь «растягиваются».
На основе определения могут быть доказаны следующие свойства:
1) Собственные вектора определяются с точностью до множителя: если – собственная пара, то для любой неравной нулю константы
– тоже является собственной парой.
2) Если – собственная пара оператора
, то
– собственная пара оператора
.
3) Если – собственная пара оператора
, то
– собственная пара оператора
.
4) Спектр диагональных и треугольных матриц состоит из диагональных элементов этих матриц.
5) Определитель матрицы равен произведению ее собственных значений.
6) Собственные вектора, соответствующие различным собственным значениям линейно независимы. Кратному собственному значению соответствует от 1 до k линейно независимых собственных векторов. Если матрица имеет полный набор различных собственных значений, то собственные векторы образуют в пространстве базис, в котором матрица оператора имеет диагональный вид.
Из определения следует, что для определения собственного вектора необходимо найти нетривиальные решения однородного уравнения . Ненулевые решения этого уравнения возможны лишь при условии вырожденности матрицы
, т.е когда
. (4.5.1)
Уравнение (4.5.1) называется характеристическим уравнением. Оно определяет собственные значения оператора.
Если раскрыть определитель в левой части уравнения, то получим относительно характеристический многочлен
-й степени вида:
. (4.5.2)
Непосредственно можно убедиться, что коэффициент при равен сумме элементов главной диагонали матрицы – следу
матрицы –
, а
.
Собственные числа являются корнями этого многочлена. Теорема Вейерштрасса гласит, что многочлен -й степени имеет ровно
возможно комплексных корней с учетом их кратности.
Характеристический многочлен трехдиагональных матриц может быть выписан по рекуррентным формулам вида (4.4.3):
введя обозначение
,
формула (4.4.3) приобретет вид:
, (4.5.2)
и будет применима для , если формально положить
.
Пример:
Решение.
При малых значениях (
) характеристическое уравнение является линейным, квадратным или кубическим уравнением и аналитически просто решается. Проблема раскрытия определителя
возрастает с ростом порядка
матрицы.
Отметим, что характеристический многочлен вида (4.5.2) может быть явно выписан для матрицы вида , которая называется матрицей Фробениуса или нормальной формой Фробениуса. Коэффициенты первой строки матрицы Фробениуса со знаком минус являются коэффициентами характеристического многочлена
.
Напомним, что преобразование подобия вида с невырожденной матрицей
связывает преобразование базиса пространства и сохраняет собственные значения, т.е. спектр матриц
и
совпадает. Вектора (в том числе и собственные) при таком преобразовании меняются по правилу
.
Преобразования подобия с унитарными матрицами , в том числе с матрицами вращения и отражения, имеют вид:
.
Возникают следующие основные «идеи» прямых методов решения спектральных задач линейной алгебры – с помощью преобразований подобия, т.е. сохраняя собственные значения матрицы, преобразовать матрицу к виду, характеристический многочлен которой легко выписывается (например к форме Фробениуса, к трехдиагональному виду с последующим применением формулы (4.5.2), к диагональному или треугольному виду). Прямые методы решают полную проблему собственных значений. Итерационные методы могут решать как полную, так и частичную проблемы.
Рассмотрим некоторые, практически часто используемые.
Метод А.М. Данилевского
В конце тридцатых годов прошлого века А.М. Данилевским был предложен метод сведения исходной матрицы к нормальной форме Фробениуса
с помощью преобразований подобия вида
с невырожденной матрицей
. Поскольку
, то спектры матриц
и
совпадают, но, как было показано выше, характеристический многочлен матрицы Фробениуса легко может быть выписан. Следовательно, задача сводится к нахождению матрицы
.
Данилевский предложил преобразовывать матрицу путем (
) –го преобразования подобия, последовательно преобразуя строки матрицы
, начиная с нижних, в строки матрицы Фробениуса.
Приведем последнюю строку матрицы в строку вида
. Предположим, что разрешающий элемент
, разделим элементы (
) –го столбца матрицы
на
. В этом случае последняя строка примет вид
. Новый (
)–й столбец, умноженный соответственно на числа
,
,
,
вычтем из остальных столбцов матрицы. Данные элементарные преобразования над столбцами матрицы
реализуются умножением справа матрицы
на матрицу
, определитель которой
– существует и отличен от нуля, при
, и, следовательно, существует обратная матрица
. Нетрудно проверить, что
.
Сделаем преобразование подобия . Матрица
будет иметь вид:
. На этом первый шаг преобразования заканчивается.
Второй шаг заключается в приведении предпоследней строки матрицы к виду предпоследней строки матрицы Фробениуса и аналогичен первому шагу в предположении, что
. Матрица
преобразуется:
, где матрицы
и
формируются аналогично. Если все разрешающие элементы отличны от нуля (так называемый регулярный случай), то за
шаг данного процесса, получим форму Фробениуса:
.
Здесь . (4.5.3)
В нерегулярном случае: пусть сделано шагов преобразования, в результате которых получена матрица
и на
-м шаге метода, в строке с номером
, разрешающий элемент обратился в ноль –
.
Здесь возможны два случая:
1) Левее элемента в строке найдется ненулевой элемент, например
.
Переставим -й и
-й столбцы и, одновременно
-ю и
-ю строки матрицы
. Полученная матрица
будет подобна
. Продолжим применение метода Данилевского для матрицы
.
2) Все элементы -й строки, находящиеся левее элемента
равны нулю.
В этом случае имеем блочно-треугольное представление и
. Но матрица
уже имеет вид Фробениуса и ее характеристический многочлен может быть выписан. Следовательно, необходимо применить метод Данилевского для матрицы
порядка
.
Метод позволяет найти собственные векторы матрицы , не решая СЛАУ
. Собственные векторы
матрицы
и собственные векторы
матрицы Фробениуса
связаны соотношением
, (4.5.4)
где определяется формулой (4.5.3).
Действительно, . Умножая на матрицу
слева, получим
. Сравнение с формулой
, дает
.
Считая, что собственные значения найдены, найдем собственный вектор
матрицы Фробениуса, соответствующий некоторому собственному значению
.
Система линейных алгебраических уравнений имеет вид:
.
Из системы видно, что у собственного вектора формы Фробениуса все компоненты не нулевые (в противном случае вектор был бы нулевым, и следовательно, не мог бы быть собственным). Т.к. собственный вектор определяется с точностью до константы, то можно осуществить нормировку вектора так, чтобы его последняя компонента стала равной единице.
Пусть , тогда из последнего уравнения системы получим
, из предпоследнего определим
и т.д. Второе уравнение даст. Т.о., собственный вектор
. Первое уравнение системы при этом должно тождественно выполняться. Это тождество используют для проверки правильности счета.
Пример: Методом Данилевского выписать характеристический многочлен матрицы , найти ее собственные значения и векторы.
Решение: Первый шаг преобразования:
;
;
.
Второй шаг преобразования:
;
;
.
Коэффициента первой строки – есть коэффициенты искомого многочлена: ,
,
. Тогда,
.
Собственные значения – корни уравнения – можно найти, например, по формулам Кардано с точностью до тысячных:
,
,
. Имеем один корень действительный и два комплексных взаимно сопряженных корня.
Найдем собственные векторы формы Фробениуса :
Для :
.
Для :
.
Для :
.
Т.к. и
, то
,
,
.
Проверкой можно убедиться, что действительно выполняются равенства определения 4.5.1: .
Вектор , и следовательно,
, можно было и не искать, поскольку, комплексно сопряженному к
собственному значению
соответствует и комплексно сопряженный к вектору
вектор
.
Метод Леверье
Характеристический многочлен матрицы , как было показано выше, имеет вид
, а собственные числа являются корнями этого полинома.
Введем обозначения . Методом индукции по степеням
, можно показать выполнение следующих рекуррентных соотношений Ньютона:
,
. (4.5.5)
Очевидно, что. Поскольку и, в частности,
, то алгоритм вычисления коэффициентов
характеристического многочлена сводится к вычислению степеней матрицы
, определению следов матриц
и применению рекуррентной формулы (4.5.5).
Отметим, что объем вычислений в методе Леверье, по сравнению с методом Данилевского, возрастает, но метод менее чувствителен к частным особенностям матриц.
Некоторое сокращение объема вычислений можно получить, на последнем шаге, поскольку нужно вычислить лишь диагональные элементы, дающие след матрицы.
Пример: Методом Леверье выписать характеристический многочлен матрицы .
Решение: При :
;
.
При :
;
;
.
При :
;
;
.
Следовательно, .
Существует модификация Д. Фаддеева метода Леверье, позволяющая не только построить характеристический многочлен матрицы , но и, по ходу алгоритма, получить обратную матрицу
. Здесь вместо степеней матрицы
строят последовательность матриц
и коэффициентов характеристического многочлена
по правилу:
,
,
,
,
. (4.5.6)
Матрица связана с обратной матрицей равенством
, откуда
. Матрица
при правильных вычислениях должна обращаться в ноль.
Пример: Модифицированным методом Леверье выписать характеристический многочлен матрицы .
Решение: .
При :
,
,
При :
,
,
. При
:
,
,
Следовательно, искомый характеристический многочлен имеет вид:
.
Проверьте, что матрица является обратной.
Метод вращений Якоби
Метод К.Якоби решает полную проблему собственных значений симметричной матрицы . Симметричную матрицу (
) можно представить в виде
, (4.5.7)
где – ортогональная матрица, а
– матрица диагональная. Поскольку для ортогональных матриц
, то разложение (4.5.7) или преобразование подобия над матрицей
вида
(4.5.8)
приводит к нахождению собственных значений, которые будут элементами диагонали матрицы . Следовательно, требуется найти ортогональную матрицу
.
Будем строить ее с помощью преобразований вращения, обнуляя на каждом шаге максимальный недиагональный элемент (и симметричный ему): ,
, …,
, … . Здесь
– номер итерации,
– индекс разрешающего или, в терминологии некоторых авторов, обреченного элемента матрицы
, подлежащего обнулению.
К сожалению, нельзя гарантировать, обнуление всех недиагональных элементов за конечное число шагов, поскольку очередное преобразование вращения может сделать уже обнуленный элемент ненулевым.
Для контроля приближения к диагональной матрице введем количественную характеристику – – сумму квадратов всех недиагональных элементов матрицы
на
-м шаге.
Опишем процедуру преобразования и покажем, что .
Напомним, что преобразование вращения определяется матрицей , с подматрицей
, коэффициенты которой интерпретируются как косинус и синус некоторого угла поворота.
Основной переход метода Якоби включает следующие шаги:
1) выбор пары индексов преобразования;
2) вычисление пары косинус-синус такой, что матрица
– диагональная (
);
3) включение подматрицы в матрицу
и осуществление преобразования
.
Преобразование вращения сохраняет евклидову норму матрицы, т.е. .
Следовательно,
оно уменьшает характеристику на каждом шаге, приближая матрицу к диагональной.
Шаг 1: Будем обнулять максимальный по модулю недиагональный элемент, т.е. будем выбирать пару индексов преобразования из условия:
.
Шаг 2: Вычислим косинус и синус угла поворота – пару – из условия
. Откуда, разделив уравнение на
и обозначив новую переменную
(тангенс угла поворота), получим квадратное уравнение
где
. Корни уравнения
. Наименьший по модулю корень
обеспечивает угол поворота
. Неизвестная пара
находится:
,
. (4.5.9)
Шаг 3 труда не представляет.
Т.к. – максимальный внедиагональный элемент, то
, где (
) – количество недиагональных элементов матрицы. Тогда,
, при
, и для равенства
может быть получена оценка:
,
,
.
Применив преобразование вращения раз, получим
. Видно, что итерационный метод Якоби сходится со скоростью геометрической прогрессии со знаменателем
.
Более точные оценки, при больших номерах , дают квадратичную сходимость метода.
Замечание_1: Значения и
по формулам (4.5.9) должны вычисляться с удвоенной точностью, в противном случае может нарушится условие ортогональности матрицы
и, как следствие, симметричность преобразованной матрицы. Это значительно ухудшает устойчивость метода вращений.
Замечание_2: Столбцы матрицы являются собственными векторами матрицы
. Действительно, т.к.
и
– ортогональная, то
и столбцы матрицы
состоят из собственных векторов.
Пример: Методом вращений найти собственные значения и собственные векторы симметричной матрицы .
Решение: Зададимся точностью расчетов . Счет будем вести до выполнения условия:
.
Т.к. , то делаем преобразование.
При :
Ш1: Максимальный по модулю недиагональный элемент – число 6 – находится во второй строке и третьем столбце. Следовательно, и
.
Ш2: ,
,
,
.
Ш3: Подматрица .
,
,
.
Т.к. , то делаем следующий итерационный шаг преобразования.
.
Ш1: Максимальный по модулю недиагональный элемент – число 1,902. Следовательно, и
.
Ш2: ,
,
,
.
Ш3: Подматрица .
,
,
.
Т.к. , то
.
Ш1: Индексы максимального по модулю недиагонального элемента и
.
Ш2: ,
,
,
.
Ш3:
,
,
.
Условие окончания – выполнено.
Составим из элементов главной диагонали матрицы вектор приближенных собственных значений
. Сравните, с точными их значениями
.
Матрица с приближенными компонентами собственных векторов .
Степенной метод
Степенной метод является итерационным методом. Он решает неполную проблему собственных значений. С его помощью приближенно определяются наибольшее по модулю собственное значение и соответствующий ему собственный вектор матрицы.
Идея метода:
Вспомним, что такое собственные векторы и собственные значения линейного оператора . Собственные вектора определяют в
инвариантные подпространства, таких подпространств
для операторов (матриц) простой структуры. Собственные значения являются коэффициентами растяжения векторов подпространств под действием оператора.
Если ввести в пространстве базис из собственных векторов и многократно воздействовать оператором на произвольный ненулевой вектор
, то координаты этого вектора будут быстрее расти по направлению того базисного (собственного) вектора, который обладает большим по модулю собственным значением. Сам вектор
при этом будет поворачиваться, стремясь к этому базисному направлению, т.е. к собственному вектору, соответствующему наибольшему по модулю собственному значению. (Рис.????)
Пусть квадратная матрица оператора имеет полный набор различных собственных значений
и соответствующих им собственных векторов
. Без ограничения общности рассуждения будем считать, что собственные значения упорядочены и
– наибольшее среди них по модулю:
.
Возьмем ненулевой вектор и построим последовательность векторов
по следующему правилу:
,
, … ,
, …
Собственные векторы линейно независимы. В пространстве
они образуют базис. Следовательно, любой вектор пространства можно разложить по этому базису. Разложим вектор
:
.
Тогда
…
.
Последнее равенство в покомпонентном виде: