24. Проблема собственных значений. Общая характеристика методов решения. Метод Гивенса.

 

Решение проблемы собственных значений

Если  А - квадратная матрица размерности  n  и  матричное равенство

               

 выполнено  при некотором  , тогда  li   называют собственным значением (собственным числом) матрицы А, а ненулевой вектор Xi ,  соответствующий li , называют собственным вектором матрицы  А

.

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

Как известно, легко находятся собственные значения для треугольной и диагональной матрицы: они равны диагональным элементам данных матриц. Поэтому  некоторые методы решения полной проблемы собственных значений основаны на приведении матрицы  А  к одному из этих видов при помощи подобных преобразований     . (Подобными преобразованиями  матрицы А называют такие преобразования вида , где S - невырожденная матрица, что собственные значения матриц А и В одинаковые,   то есть подобные преобразования не изменяют собственных значений матрицы). В случае, когда U - ортогональная матрица, выполнено  и  преобразование подобия можно записать так: . После определения собственных значений матрицы А собственные векторы легко найти, решая систему однородных уравнений AXi = li×Xi для каждого  li  (i =1, 2, . . . , n).

 

Приведение  матрицы  к  трехдиагональному  или  почти треугольному виду при помощи метода Гивенса.

1) Если  А - вещественная матрица, имеющая различные вещественные собственные значения l1, l2, . . . ,ln , то ее при помощи последовательности подобных преобразований  можно привести  (с определенной точностью) к диагональному виду

где   ,  (i =1, 2, . . . , n).

 

(Столбцы результирующей матрицы U,  использованной  при этом, есть собственные векторы матрицы А).

2) Если среди собственных значений матрицы А есть кратные либо комплексные, то ее удается привести лишь к блочно - треугольному виду:

,                          

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

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

 Метод Гивенса позволяет за N шагов привести матрицу А к трехдиагональному виду, если  А - симметричная, либо к левому почти треугольному виду, если  А - произвольная квадратная матрица. Этот процесс осуществляется посредством подобных преобразований вида:

 ,

где   i = 2, 3, ... n - 1;      j = i+1, i+2, . . . n;          к = 1, 2, . . . ,N,

;          - матрица вращения.

В итоге получаем:

,

если  А была симметричной, либо

,

если  А - была произвольной матрицей.

Матрица вращения  имеет структуру, описанную в п.4.5.1, т.е элементы  ;         , но величины и  вычисляют по другим формулам:

;                .

В результате  преобразования вида   обнуляется элемент  матрицы , т.е.   = 0. Для получения матрицы  потребуется   таких  преобразований.

Пусть   T = T23 × T24 × . . . × T2n × . . . × Tn-1,n,   тогда

TТ = TTn-1,n × . . . × TT2n × . . . × TT24 × TT23    и  можно записать: AN = TT × A × T ,

где T - ортогональная матрица. Это означает, что матрица  AN  подобна A и имеет те же собственные значения.

Если вместо матриц вращения использовать матрицы отражения, то аналогичный метод носит имя Хаусхолдера.