Два представления о сходимости QR-, QL-алгоритмов

Рассмотрим вопрос о сходимости -алгоритма. Если сдвиги не используются, то -алгоритм называется основным.

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

Однако можно понимать сходимость несколько иначе.

Теорема (случай симметричной матрицы). Пусть собственные значения матрицы удовлетворяют условию:

.

Пусть матричная последовательность получена основным -алгоритмом, тогда имеет место равенство:

,

где .

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