§ 45. QR-алгорифм

Пусть А — произвольная вещественная матрица порядка Построим последовательность ортогональных матриц и правых треугольных матриц по следующим рекуррентным формулам:

Легко показать, что для всех матрицы из (45.1) подобны исходной матрице А. Действительно,

Обозначив заключаем, что

Так как матрицы ортогональные, то будут ортогональными и матрицы Поэтому ортогонально подобны А.

Соотношения (45.1), (45.2) позволяют получить еще одно следствие. Рассмотрим произведение правых треугольных матриц

имеем

Следовательно,

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

Исследуем теперь строение матриц при больших Будем считать, что матрица А невырожденная. Представим ее в виде

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

заключаем, что матрица

является правой треугольной. Далее находим

откуда в соответствии с (45.2), (45.3) вытекает, что

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

Рассмотрим матрицу Принимая во внимание вид нетрудно установить, что В является левой почти треугольной матрицей и имеет над главной диагональю такие же элементы, Если — элементы В, то матрицы из (45.4) имеют элементы

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

то из (45.5), (45.6) следует, что при неограниченном увеличении числа элементы диагональных клеток не меняют свои модули, а элементы поддиагональных клеток сходятся к нулю. Обозначив через величину модулей собственных значений из группы в (45.5), заключаем, что элементы поддиагональных клеток убывают как

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

Напомним, что матрицы в (45.4) являются правыми треугольными. Если бы элементы оставались ограниченными при всех то из формулы (45.4) и вида матриц сразу вытекало бы, что при неограниченном увеличении матрицы со скоростью (45.7) будут приближаться по форме к клеточной правой треугольной матрице с диагональными блоками таких же размеров, как у матриц С.

Матрицы заведомо ограничены, если А имеет простую структуру. В самом деле, в этом случае и тогда

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

В общем случае исследование матриц осуществляется несколько сложнее. Запишем в следующем виде:

Ясно, что если элементы матриц растут, то по порядку они растут не быстрее, чем элементы матриц

Лемма 45.1. Пусть матрица А невырожденная и максимальный порядок канонического ящика Жордана для нее равен Тогда при больших элементы матриц суть величины

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

Итак, предположим, что А есть ящик Жордана порядка с ненулевым собственным значением К. Очевидно, что этому ящику будет соответствовать матрица Воспользуемся [2] асимптотическим представлением матрицы

Здесь диагональная матрица с элементами

правая треугольная матрица с элементами

все элементы матрицы стремятся к нулю с ростом Теперь получаем, что

Согласно (45.8) максимальный элемент этих матриц при больших находится в позиции и имеет величину

Если вернуться к оценке возможной скорости роста элементов матриц то из доказанной леммы вытекает, что

Элементы матриц по порядку роста не превосходят если порядок жордановых ящиков матрицы не превосходит

Построенные в соответствии с (45.1) матрицы унитарно подобны марице поэтому элементы этих матриц ограничены равномерно по Представим матрицы в клеточном виде

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

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

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

Проведем процесс (45.1) настолько далеко, чтобы все элементы поддиагональных клеток матрицы стали малыми. Заменив эти элементы нулями, мы получим клеточную правую треугольную матрицу Для нее

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

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

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

УПРАЖНЕНИЯ

(см. скан)

(см. скан)