§ 8.4. QR-алгоритм

В настоящее время лучшим методом вычисления всех собственных значений квадратных заполненных матриц общего вида (умеренного порядка) является QR-алгоритм.

1. Основной QR-алгоритм.

Опишем итерационную процедуру, являющуюся основой алгоритма. Она существенно использует возможность разложения произвольной матрицы в произведение ортогональной и верхней треугольной матриц, т.е. так называемое QR-разложение (см. § 5.10).

На 1-й итерации с помощью метода отражений или метода вращений вычисляют QR-разложение матрицы имеющее вид

Затем строят матрицу Заметим, что из равенства (8.32) следует, что и поэтому Таким образом, матрицы подобны (см. § 8.1) и поэтому имеют общий набор собственных значений

На 2-й итерации находят QR-разложение матрицы имеющее вид и вычисляют матрицу подобную мат рице

На итерации вычисляют разложение и строят матрицу Неограниченное продолжение этого процесса дает последовательность матриц подобных матрице А.

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

Здесь крестиками помечены элементы, в общем случае не равные нулю.

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

т.е. скорость сходимости к нулю определяется величиной отношения , (заметим, что при ).

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

2. Ускорение QR-алгоритма.

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

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

Матрица в которой равны нулю все элементы такие, что

+1 (т.е. все элементы, расположенные ниже диагонали, непосредственно примыкающей к главной диагонали), называется матрицей Хессенберга. Существуют эффективные стандартные процедуры преобразования матрицы А к виду (8.35), поэтому мы не будем останавливаться подробно на этом преобразовании. Для дальнейшего важно то, что матрицы подобны и обладают общим набором собственных значений, а матрица подобия для которой выполняется равенство

ортогональна.

После преобразования матрицы А к виду (8.35) к матрице применяют -алгоритм. Эффективность такого подхода обусловлена наличием следующих двух замечательных свойств матриц Хессенберга.

1°. Матрицы порождаемые QR-алгоритмом из матрицы сами являются матрицами Хессенберга, т.е. для них

2°. Для выполнения одной итерации QR-алгоритма для матрицы Хессенберга требуется число арифметических операций, пропорциональное

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

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

полагая После выполнения этой операции матрицы А и снова имеют общий набор собственных значений.

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

Итак, прежде чем применять QR-алгоритм, следует преобразовать исходную матрицу А к форме Хессенберга. Без такого преобразования QR-алгоритм практически не применяется. Затем целесообразно использовать один из вариантов QR-алгоритма со сдвигами.

Пусть теперь собственные значения найдены и требуется найти один собственный вектор матрицы А, отвечающий собственному значению или несколько собственных векторов. Тогда целесообразно сначала найти соответствующий собственный вектор матрицы Я (например, методом обратных итераций), а затем вычислить по формуле где матрица подобия из (8.36).

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

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

Замечание -алгоритм обладает хорошей обусловленностью. Например, как показано в [19], в одном из его вариантов после числа итераций, не превосходящего 5, для каждого собственного значения получаются приближения

являющиеся точными собственными значениями некоторой матрицы такой, что

(это утверждение сформулировано в терминах обратного анализа ошибок).