Спектральные задачи линейной алгебры

Ранее мы установили связь между числом обусловленности матрицы и ее собственными значениями, одна из рассмотренных норм матрицы также требовала вычисления собственных значений. Определение спектральных характеристик оператора – часто встречаемая и весьма важная задача прикладной математики. В нашем случае, когда оператор действует в конечномерном векторном пространстве и является линейным, вопрос определения его собственных значений может быть сформулирован в терминах собственных значений матрицы, представляющей оператор. Различают полную и неполную проблему собственных значений – нахождение всех собственных значений и соответствующих векторов и нахождение одного или нескольких (не всех) собственных значений и соответствующих собственных векторов. Неполная проблема возникает, например, при оценке сходимости итерационных методов решения СЛАУ, когда достаточно определить максимальное по модулю собственное значение.

Различают прямые и итерационные методы.

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

В итерационных методах вычисление собственных значений определяется без вычисления характеристического многочлена лишь по исходной матрице. Как правило, вычисления сопровождаются и определением собственного вектора. Собственные значения и собственные векторы в итерационных методах вычисляются как пределы итерационных последовательностей. Итерационные методы более трудоемки, чем прямые, но обладают простотой реализации, единообразием действий и большей устойчивостью, что выдвигает их в лидеры при компьютерном решении задач большой размерности.

Ненулевой вектор , удовлетворяющий уравнению , называется собственным вектором оператора . Число называется собственным значением. Совокупность собственных значений оператора образует его спектр. Собственное значение и соответствующий собственный вектор образуют собственную пару .

Собственный вектор совместно с нулевым вектором образуют инвариантное подпространство пространства , вектора этого подпространства коллинеарны, т.е. под действием оператора не изменяют своего направления, а лишь «растягиваются».

На основе определения могут быть доказаны следующие свойства:

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:

, ,

.

Условие окончания – выполнено.

Составим из элементов главной диагонали матрицы вектор приближенных собственных значений . Сравните, с точными их значениями .

Матрица с приближенными компонентами собственных векторов .

Степенной метод

 

Степенной метод является итерационным методом. Он решает неполную проблему собственных значений. С его помощью приближенно определяются наибольшее по модулю собственное значение и соответствующий ему собственный вектор матрицы.

Идея метода:

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

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

Пусть квадратная матрица оператора имеет полный набор различных собственных значений и соответствующих им собственных векторов . Без ограничения общности рассуждения будем считать, что собственные значения упорядочены и – наибольшее среди них по модулю: .

Возьмем ненулевой вектор и построим последовательность векторов по следующему правилу:

, , …, , …

Собственные векторы линейно независимы. В пространстве они образуют базис. Следовательно, любой вектор пространства можно разложить по этому базису. Разложим вектор :

.

Тогда

…

_.

Последнее равенство в покомпонентном виде: