6.2.4. QR-алгоритм

Существует ряд хорошо отработанных алгоритмов и программ решения полной проблемы собственных значений, основанных на различных модификациях QR-алгоритма. Поэтому рекомендуется в случае решения этой проблемы пользоваться стандартными программами решения таких задач.

QR-алгоритм был одновременно предложен В.Н. Кублановским и Д.Френсисом в 1961 году (см. [2, с. 194–196]; [5, с. 178–181]).

Пусть  – произвольная вещественная матрица. В соответствии с леммой из [9, с. 267] эту матрицу можно представить в виде , где  – ортогональная,  – транспонированная к  матрица, а  – правая треугольная матрица. Обозначив , получим, что

.

Из этого равенства имеем:

.

Поэтому матрица  подобна матрице .

Далее строим последовательность матриц  по такому правилу: представляем матрицу  в виде произведения ортогональной и правой треугольной матрицы:

 и полагаем

В силу того, что , все матрицы  подобны между собой и подобны исходной матрице .

Построение последовательности матриц  осуществляется с помощью матриц отражений. Более подробно с алгоритмом построения этой последовательности можно познакомиться, например, в [9, с. 265–268].

Если требуется определить не только собственные значения матрицы , но и её собственные векторы, то в процессе построения последовательности матриц  следует запоминать ортогональные матрицы , вычисляемые по рекуррентной формуле: .

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

По устойчивости и характеру сходимости QR-метод аналогичен ортогональному степенному методу (см. [8, с. 187]).