Ранее мы установили связь между числом обусловленности матрицы и ее собственными значениями, одна из рассмотренных норм матрицы также требовала вычисления собственных значений. Определение спектральных характеристик оператора – часто встречаемая и весьма важная задача прикладной математики. В нашем случае, когда оператор действует в конечномерном векторном пространстве и является линейным, вопрос определения его собственных значений может быть сформулирован в терминах собственных значений матрицы, представляющей оператор. Различают полную и неполную проблему собственных значений – нахождение всех собственных значений и соответствующих векторов и нахождение одного или нескольких (не всех) собственных значений и соответствующих собственных векторов. Неполная проблема возникает, например, при оценке сходимости итерационных методов решения СЛАУ, когда достаточно определить максимальное по модулю собственное значение.
Различают прямые и итерационные методы.
Прямые методы основаны на применении преобразований подобия. Матрица приводится к такому виду, для которого просто выписать коэффициенты характеристического уравнения, затем ищутся его корни какими-либо известными методами. Основным достоинством прямых методов является их возможность применения к широкому классу матриц. Их недостатком является чувствительность корней многочлена к вариации коэффициентов (к погрешностям, с которыми считаются коэффициенты многочлена). Прямые методы, являясь экономичными по числу необходимых вычислительных операций, устойчивы только для матриц невысокого порядка ( ), а в случае близких по значению или кратных корней – меньшего порядка. Т.о. область использования прямых методов не велика.
В итерационных методах вычисление собственных значений определяется без вычисления характеристического многочлена лишь по исходной матрице. Как правило, вычисления сопровождаются и определением собственного вектора. Собственные значения и собственные векторы в итерационных методах вычисляются как пределы итерационных последовательностей. Итерационные методы более трудоемки, чем прямые, но обладают простотой реализации, единообразием действий и большей устойчивостью, что выдвигает их в лидеры при компьютерном решении задач большой размерности.
Ненулевой вектор , удовлетворяющий уравнению , называется собственным вектором оператора . Число называется собственным значением. Совокупность собственных значений оператора образует его спектр. Собственное значение и соответствующий собственный вектор образуют собственную пару .
Собственный вектор совместно с нулевым вектором образуют инвариантное подпространство пространства , вектора этого подпространства коллинеарны, т.е. под действием оператора не изменяют своего направления, а лишь «растягиваются».
На основе определения могут быть доказаны следующие свойства:
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:
, ,
.
Условие окончания – выполнено.
Составим из элементов главной диагонали матрицы вектор приближенных собственных значений . Сравните, с точными их значениями .
Матрица с приближенными компонентами собственных векторов .
Степенной метод
Степенной метод является итерационным методом. Он решает неполную проблему собственных значений. С его помощью приближенно определяются наибольшее по модулю собственное значение и соответствующий ему собственный вектор матрицы.
Идея метода:
Вспомним, что такое собственные векторы и собственные значения линейного оператора . Собственные вектора определяют в инвариантные подпространства, таких подпространств для операторов (матриц) простой структуры. Собственные значения являются коэффициентами растяжения векторов подпространств под действием оператора.
Если ввести в пространстве базис из собственных векторов и многократно воздействовать оператором на произвольный ненулевой вектор , то координаты этого вектора будут быстрее расти по направлению того базисного (собственного) вектора, который обладает большим по модулю собственным значением. Сам вектор при этом будет поворачиваться, стремясь к этому базисному направлению, т.е. к собственному вектору, соответствующему наибольшему по модулю собственному значению. (Рис.????)
Пусть квадратная матрица оператора имеет полный набор различных собственных значений и соответствующих им собственных векторов . Без ограничения общности рассуждения будем считать, что собственные значения упорядочены и – наибольшее среди них по модулю: .
Возьмем ненулевой вектор и построим последовательность векторов по следующему правилу:
, , … , , …
Собственные векторы линейно независимы. В пространстве они образуют базис. Следовательно, любой вектор пространства можно разложить по этому базису. Разложим вектор :
.
Тогда
…
.
Последнее равенство в покомпонентном виде: