книги / Линейная алгебра

9.3.ф Я -ал гори тм

фЯ -ал гори тм — это наиболее употребительный в настоящее вре­ мя итерационный метод отыскания характеристических чисел дей­ ствительных и комплексных матриц. Стандартные программы к это­ му методу содержатся в [29]. С?Я-алгоритм состоит в следующем.

Для данной матрицы А = Ао строят (см. п. 6.9) фЯ-разложение

А= Q OR Q. В полученном разложении меняют местами множители. Это приводит к матрице А\ = RoQo, с которой поступают анало­ гично и т.д. В результате получают последовательность матриц

Ао , А \, А2, . •., Ak , ...

Эти матрицы подобны, так как

М = Q0 1AoQo, А2 = Qi lAiQi и т.д.

При довольно общих предположениях построенная последователь­ ность матриц сходится к треугольной матрице. Диагональные эле­ менты треугольной матрицы являются ее характеристическими чи­ слами и характеристическими числами всех подобных матриц, в част­ ности, матрицы Ао = А .

Для ускорения фЯ-алгоритма желательно, чтобы на каждом его шаге быстро строилось фЯ-разложение очередной матрицы А*. Для этого следует исходную матрицу с помощью ортогональных (унитар­ ных) преобразований привести к подобной матрице Ао = U^AU более простого вида, например, почти треугольного вида или трех­ диагональной формы. О приведении матрицы к подобной матрице почти треугольного вида см. п. 6.7 и [3, с. 182-184.]. фЯ-алгоритм практически всегда применяется к почти треугольным матрицам, а в симметрическом случае — к трехдиагональным.

Другим важным приемом ускорения фЯ-алгоритма является ис­ пользование сдвигов <Tk для повышения скорости убывания по абсо­ лютной величине элементов, лежащих ниже главной диагонали. С этой целью на (к + 1)-м шаге вместо матрицы А* разлагают в QR- разложение матрицу А* — ст^Е. Пусть А* — ст^Е = QkRk - QR- разложение этой матрицы. Тогда строят матрицу А*+1 = Rk Qk + (TkE. Такой переход от А* к А*+1 не меняет характеристических чисел, поскольку матрицы А* и А*+1 подобны. Действительно,

Из этого равенства получается фД-разложение

Сначала эту матрицу вращениями приведем к треугольному виду. Здесь следует занулить лишь элемент = 1. Для этого составим

матрицу вращения

и найдем сову» и sin у» из равенства нулю элемента матрицы T^{Ai Е) в позиции (3,2), т.е. из равенства

Эта матрица уже треугольная с характеристическими числами Ai = 1, Аг = 4, Аз = 1. Эти же числа являются характеристическими числами матрицы А .

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

При отыскании наибольшего по абсолютной величине собствен­ ного значения Ai матрицы А и соответствующего ему собственного вектора Х\ = (xi, •••, хп)т можно пользоваться следующим ите­ рационным методом, называемым степенны м .

В качестве нулевого приближения к искомому вектору Х\ берут

Если эта последовательность векторов сходится при к —►оо к век­ тору X i, то он будет искомым собственным вектором, а для соот­ ветствующих координат векторов последовательности (9.28) будут выполняться соотношения

Й 2 , ; р > = А‘ <9 И »

при всех i = 1,п, при которых отношения, стоящие под знаком пре­ дела, имеют смысл.

За вектор Х\ приближенно можно принять вектор х [ к^= Акх[°^ при достаточно большом значении к или ему пропорциональный век­ тор, а за собственное значение Ai - любое из имеющих смысл отно­ шений

ХХ

Причем процесс приостанавливают, когда в А ^ стабилизируется до­ статочное число десятичных знаков после запятой.

Если процесс окажется несходящимся (последнее легко заметить по сильно ’’ прыгающим” значениям соотношений (9.30) при измене­

нии Л), то следует изменить начальный вектор и процесс повто­ рить.

Чтобы избежать чрезмерного роста по абсолютной величине ко­ ординат векторов А 'Х ? \ к = 1,2 , , иногда целесообразно все их координаты умножать на какие-либо числа а*. Например, удоб­

вместо последовательности векторов (9.28) получают последователь­ ность векторов

Yi = a iАХ[°\ У2 = а2А2х{°\ У* = акАкх{°\

Для получения Ai в этом случае следует брать отношения координат векторов AYk и У*, а за вектор Х\ — вектор У*. Более подробные рекомендации об этом можно найти в книгах [3], [32]. Там же можно познакомиться с различными модификациями степенного метода и с обратным степенным методом.

Пример 1. Для матрицы

i4 =

степенным методом найти наибольшее по абсолютной величине соб­ ственное значение Ai и соответствующий ему собственный вектор

Хг.

Решение. За нулевое приближение вектора Х\ примем вектор X = = (1,1,1)т Далее построим векторы АкХ ^ при к = 1 ,1Q. Резуль­ таты приведены в следующей таблице:

2 1 - 1 3 0 7

Теперь вычислим Ai по формуле (9.30) при к = 9, 10; i = 3:

Мы видим, что Ах9\и Ах10) мало отличаются одно от другого. По­ этому, округляя до второго десятичного знака, можно принять Ai = 3,00,

Хх~ Х х(10) = Л10Х х(0) = (59059, 118117, 118107)т

Естественно Х\ заменить ему пропорциональным вектором, на­ пример, вектором

При переходе, например, от А9Х х°^ к А 10АГХ°\ чтобы избежать больших по абсолютной величине координат, вместо вектора можно было взять вектор

У9 = ig^74^9* i 0) = (!. 2,0000508, 2,0005082)т

Тогда вместо A lQX ^ имели бы

AY9 = (3,0018804, 6,0037100, 6,0032018)т

Степенной метод можно приспособить к отысканию других соб­ ственных значений и собственных векторов матрицы. Так, для отыс­ кания собственного значения А2 и соответствующего ему собствен­ ного вектора Хъ можно комбинировать степенной метод с методом исчерпывания (см. [3], [10]), т.е. поступать следующим образом.

Найти степенным методом или из системы (АТ — XiE)U = 0 соб­ ственный вектор U\ матрицы А т , принадлежащей собственному зна­ чению Ai, и положить

W ,U x Y

Так, построенный собственный вектор Х[ матрицы А т удовлетво­ ряет условию (Xi, Х[) = Х~[Х[ = X ^ X i = 1. Если матрица А сим­ метрическая, то за вектор Х[ принимают нормированный по длине вектор Х\. Далее следует составить матрицу

Аг = А - ХгХгХ?

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

Все собственные векторы Х \ 9 Хъ, ..., Х п матрицы А являются также собственными векторами матрицы А\, и наоборот. Причем со­ ответствующие собственные значения сохраняются, за исключением Ai, которому в матрице А\ соответствует нулевое собственное зна­

тор Vi матрицы А\ (их опять можно найти степенным методом) явля­ ются соответственно собственным значением Аг и ему принадлежа­ щим собственным вектором Хъ матрицы А. С матрицей А\ можно поступать аналогично и т.д. В итоге можно найти все собственные значения и собственные векторы матрицы А. Поясним такой подход на примере.

Пример 2. Для матрицы

найти собственные значения и собственные векторы.

Решение. Найдем степенным методом для матрицы А собственное значение Ai и ему принадлежащий собственный вектор Х\. Для этого за нулевое приближение вектора Х\ примем, например, вектор -Xj0^= = (1, 1, 1)т и построим векторы при к = 1,2, 3,4. Результаты вычислений приведены в следующей таблице:

21*

Теперь по формуле (9.30) при к = 4 находим

^.’=4§н

и за вектор X i примем вектор

Чтобы найти собственное значение Аг и собственный вектор X 2 матрицы А у сначала из системы (Ат —■AiE)JJ = 0 или степенным методом найдем собственный вектор U\ = (1, —1, 1)т матрицы Ат , принадлежащий собственному значению Ах = 5 и положим

х ' = Ш Ж ) = ^ - 1' 1)Т

Затем сконструируем матрицу

Для матрицы А\ степенным методом найдем собственное значение /хх и ему принадлежащий собственный вектор V\. Для этого за нуле­ вое приближение собственного вектора V\ примем, например, вектор Vi(0) = (0, 1, 1)т (брать Vx = (1,1,1)т здесь нельзя, так как получи­ лось бы А\V} = (0,0,0)т , что невозможно для дальнейшего проведе­ ния степенного метода) и построим векторы A\v[°^ при к = 1,2,3,4. Результаты вычислений приведены в следующей таблице:

трицы А Аг = 3, и за вектор X* можно принять вектор

Х2 = ш = (0, h 1)Т