№26. QR-алгоритм

 

Этот метод определения собственных значений матрицы  А  использует тот факт, что всякую неособенную матрицу можно представить в виде  A = QR,,  где Q - ортогональная матрица, а  R - левая треугольная. Представление А  в данном виде  (QR-разложение матрицы) осуществляется при помощи итерационного процесса: строится последовательность матриц   А1, А2, … , таким образом, чтобы , где   А* - левая треугольная (в случае различных вещественных собственных значений), либо левая блочно-треугольная матрица, если среди собственных значений есть кратные или комплексные (см. п. 8.1). Процесс продолжают, пока не будет выполнено условие  .  В результате на главной диагонали матрицы  Ak  окажутся квадратные блоки 1 – го и (или) 2 – го порядков:

 

Description: C:\Мои документы\pic1.bmp

Блоки 1–го порядка – это собственные значения  матрицы А. Чтобы найти парные собственные значения блоков 2–го  порядка  , нужно решить квадратные уравнения = 0.

 

 

         Описание QR – алгоритма.

k = 1.    Будем считать  Умножим    на ортогональную матрицу   Qсправа, получим . Находим .

k = 2.    Умножаем    на   Q2  справа:    ,  находим   и т.д. 

Таким образом, ,   k = 1, 2,,

где   – произведение матриц вращения:

.

 

Матрицей вращения называется ортогональная матрица  размерности , полученная из единичной матрицы  этой же размерности заменой  4–х элементов:

;      ;      ;  где               

 

Матрица  имеет вид:

 

А величины   и  находят по формулам:

 с использованием элементов матрицы .

 

В результате подобного преобразования    матрица  Ak  остается симметричной, если Ak-1  симметричная, или левой почти треугольной, если Ak-1  – левая почти треугольная, сохраняя свои собственные значения.

 

Если матрица  А  предварительно была приведена к трехдиагональному либо левому почти треугольному виду (например, при помощи метода Гивенса), то это уменьшает количество вычислений: .