8 Методы решения задач о собственных значениях и собственных векторах матриц (Лекции по теории оптимизации и численным методам)

Лекция 82. МЕТОДЫ РЕШЕНИЯ ЗАДАЧ О СОБСТВЕННЫХ ЗНАЧЕНИЯХ ИСОБСТВЕННЫХ ВЕКТОРАХ МАТРИЦПОСТАНОВКА ЗАДАЧИПусть A – действительная числовая квадратная матрица размеров (n  n) . Ненулевой вектор X  ( x1 ,..., x n )T размеров (n  1) , удовлетворяющий условиюAX  X ,называется собственным вектором матрицы A . Число  называется собственным значением.

Говорят, что собственный вектор X соответствует (принадлежит) собственномузначению  .Равенство равносильно однородной относительно X системе:( A  E )X  0, ( X  0) .Система имеет ненулевое решение для вектора X (при известном  ) при условииA  E  0 . Это равенство есть характеристическое уравнение:A  E  Pn ()  0 ,где Pn () – характеристический многочлен n -й степени. Корни 1 ,  2 ,...,  n характеристического уравнения являются собственными (характеристическими) значениямиматрицы A , а соответствующие каждому собственному значению  i , i  1,..., n , ненулевые векторы X i , удовлетворяющие системеAX i   i X iA   i E  X iили 0, i  1,2,..., n ,являются собственными векторами.Требуется найти собственные значения и собственные векторы заданной матрицы.Различают полную и частичную проблему собственных значений, когда необходимо найти весь спектр (все собственные значения) и собственные векторы либо частьспектра, например: ( A )  max  i ( A ) и min  i ( A ) .

Величина (A ) называется спекiiтральным радиусом.З а м е ч а н и я.1. Если для собственного значения  i найден собственный вектор X i , то векторX i , где  – произвольное число, также является собственным вектором, соответствующим этому же собственному значению  i .2. Симметрическая матрица имеет полный спектр  i , i  1, n , действительных собственных значений; k-кратному корню характеристического уравнения симметрическойматрицы соответствует ровно k линейно независимых собственных векторов.82А. МЕТОД ИТЕРАЦИЙДля решения частичной проблемы собственных значений и собственных векторовв практических расчетах часто используется метод итераций (степенной метод).

На егооснове можно определить приближенно собственные значения матрицы A и спектральный радиус ( A )  max  i ( A ) .Пусть матрица A имеет n линейно независимых собственных векторовiX , i  1, n ,исобственныезначенияматрицыAтаковы,что( A )  1 ( A )   2 ( A )  ...   n ( A ) .Методика решения задачиШаг 1. Выбрать произвольное начальное (нулевое) приближение собственноговектора X 1(0 ) (второй индекс в скобках здесь и ниже указывает номер приближения, апервый индекс без скобок соответствует номеру собственного значения). Положитьk  0.x i1(1)(1)1(1)1(0) AX, 1 , где i – любой номер 1  i  n , и поШаг 2. Найти Xx i1(0)ложить k  1.Шаг 3. Вычислить X 1(k 1)  AX 1(k ) .Шаг 4. Найти (1k 1) x i1(k 1)x i1(k ), где x i1(k 1) , x i1(k ) – соответствующие координатывекторов X 1(k 1) и X 1(k ) .

При этом может быть использована любая координата с номером i, i  1, n.Шаг 5. Если   (1k 1)  (1k )  , процесс завершить и положить 1  (1k 1) .Если    , положить k  k  1 и перейти к п.3.З а м е ч а н и я.1. Процесс последовательных приближенийX 1(1)  AX 1(0) , X 1(2)  AX 1(1)  A 2 X 1(0) ,...,X 1(k )  AX 1(k 1)  A  A k 1 X 1(0)  A k X 1(0) ,...сходится, т.е. при k   вектор X 1( k ) стремится к собственному вектору X 1 .2. Используя 1 , можно определить следующее значение  2 по формуле2 x i1(k 1)  1 x i1(k )x i1(k )  1 x i1(k 1)(i  1,2,..., n) .Эта формула дает грубые значения для  2 , так как значение 1 является приближенным.

Если модули всех собственных значений различны, то на основе последнейформулы можно вычислять и остальные  j ( j  3,4,..., n) .833. После проведения некоторого числа итераций рекомендуется «гасить» растущиекомпоненты получающегося собственного вектора. Это осуществляется нормировкойX 1(k )вектора, например, по формуле.X 1(k )15 1 2Пример 1. Для матрицы A   1 4 1  найти спектральный радиус методом ите2 1 3раций с точностью   0,1 . 1. Выбирается начальное приближение собственного вектора X (0)  1; 1; 1T .Положим k  0.2. НайдемX1(1) AX1(0) 5 1 2  1   8       1 4 1   1    6  ; 2 1 3  1   6     (11)x11(1)x11(0)8 8,1положим k  1.3. ВычислимX1(2) AX1(1) 5 1 2   8   58       1 4 1    6    38  . 2 1 3   6   40     4.

Найдем(12)5.x11(2)x11(1)58 7,25.8Так как (12)  (11)  0,75   , то процесс необходимо продолжить.Результаты вычислений удобно представить в виде табл. 1.Таблица 1kx11(k )x 21(k )x 31(k )(1k )(1k )  (1k 1)0123418584082838163825016821640274188887,257,0346,95590,750,1160,078  Точность по (1k ) достигнута на четвертой итерации. Таким образом, в качествеприближенного значения 1 берется 6,9559 , а в качестве собственного вектора принима-84ется X 1  2838, 1682, 1888T .

Так как собственный векторопределяется с точно-стью до постоянного множителя, то X 1 лучше пронормировать, т.е. поделить все егокомпоненты на величину нормы, например X 1  max X i1 . Для рассматриваемого приi 2838   1,000  1 мера получим X  1682    0,5927  .2838   1888   0,6652 В качестве собственного значения 11x11(4)x11(3)x 21(4)x 21(3)2838 6,9559 , но и408среднее арифметическоеможно взять не только отношениеx 31(4) 18881682 6,7280 ; 6,8905 , а также их250274x 31(3)6,9559  6,728  6,8905 6,8581 . 3Б.

МЕТОД ВРАЩЕНИЙМетод используется для решения полной проблемы собственных значений симметрической матрицы и основан на преобразовании подобия исходной матрицыA  R n  n с помощью ортогональной матрицы H .Две матрицы A и A (i ) называются подобными ( A  A (i ) или A (i )  A ), еслиA (i )  H 1 AH или A  HA (i ) H 1 , где H – невырожденная матрица.В методе вращений в качестве H берется ортогональная матрица, такая, чтоTHH  H T H  E , т.е.

H T  H 1 . В силу свойства ортогонального преобразованияевклидова норма исходной матрицы A не меняется. Для преобразованной матрицы A (i )сохраняется ее след и собственные значения  i :tr A n aii i 1n  i ( A)  tr A (i ) .i 1При реализации метода вращений преобразование подобия применяется к исходной матрице A многократно:A (k 1)  H (k )1A ( k ) H ( k )  H (k )TA (k ) H (k ) ,k  0,1,... .Формула определяет итерационный процесс, где начальное приближениеA A .

На каждой k -й итерации для некоторого выбираемого при решении задачи недиагонального элемента aij(k ) , i  j , определяется ортогональная матрица H (k ) , приво(0 )дящая этот элемент aij(k 1) (а также и a (jik 1) ) к нулю. При этом на каждой итерации в качестве aij(k ) выбирается наибольший по модулю.

Матрица H (k ) , называемая матрицейвращения Якоби, зависит от угла (k ) и имеет вид85H (k )1000 000000100 cos (k )00000 sin (k )000000010000i -й столбец00000  sin (k )00100 cos (k )0000000000100000.0001 i -я строкаj -я строкаj -й столбецВ данной ортогональной матрице элементы на главной диагонали единичные, кроме hii(k )  cos (k ) и h (jjk )  cos (k ) , а hij(k )   sin (k ) , h (jik )  sin (k ) ( hij – элементыматрицы H ).Угол поворота (k ) определяется по формулеtg 2(k )2aij(k )aii(k )  a (jjk ) Pk ; (k ) 1arctg Pk ,2, i  j (элемент a ij( k ) выбирается в верхней треугольной наддиагональной2части матрицы A ) .

Заметим, что при aii( k )  a (jjk ) получается ( k )  .4В процессе итераций сумма квадратов всех недиагональных элементов (A (k ) )где 2(k ) при возрастании k уменьшается, так что ( A (k 1) )  ( A (k ) ) . Элементы aij(k ) , приведенные к нулю на k -й итерации, на последующей итерации немного возрастают.

Приk   получается монотонно убывающая ограниченная снизу нулем последовательность ( A (1) )  (A (2) )    ( A (k ) )  . Поэтому ( A (k ) )  0 при k   . Это и озна0  1(k )чает сходимость метода. При этом A.0 n Методика решения задачиШаг 1. Положить k  0, A (0)  A и задать   0.86Шаг 2. Выделить в верхней треугольной наддиагональной части матрицы A (k )максимальный по модулю элемент aij(k ) , i  j .Если aij(k )   для всех i  j , процесс завершить.

Собственные значения опреде-ляются по формуле  i A (k )  aii(k ) , i  1, n.Собственные векторы X i находятся как i -е столбцы матрицы, получающейся врезультате перемножения: k  H (0) H (1) H (2)  H (k 1)  X 1 , X 2 , X 3 ,..., X n .Если aij(k )   , процесс продолжается.Шаг 3. Найти угол поворота по формуле(k )(k )2aij1 arctg2aii( k )  a (jjk )(при aii( k )  a (jjk ) получается ( k ) ).4Шаг 4. Составить матрицу вращения H (k ) .Шаг 5. Вычислить очередное приближениеA (k 1)  H (k )TA (k ) H (k ) .Положить k  k  1 и перейти к п.2.З а м е ч а н и я.1. Контроль правильности выполнения действий на каждой итерации осуществляется путем проверки сохранения следа преобразуемой матрицы.2. При n  2 для решения задачи требуется одна итерация. 2 1 методом вращений найти собственные значеПример 2.