Близкие и кратные собственные значения

10. Все оценки скорости сходимости содержат множитель 1/6, и это могло бы навести на мысль, что когда 6 мало, начало квадратичной сходимости будет задерживаться. Если 6 равно нулю, до доказательства не проходят, хотя было показано, что когда нет собственных значений кратности больше чем два, то квадратичная сходимость может быть гарантирована, если порядок исключения элементов несколько изменен (см., например, Шенхаге (1961)). В исследовании скорости сходимости, когда существуют собственные значения кратности больше чем два, сделано пока немного. Наш опыт работы с частным циклическим методом Якоби привел к мысли, что на практике очень близкие и кратные собственные значения обычно влияют на число итераций, необходимых для приведения внедиагональных элементов ниже предписанного уровня, существенно меньше, чем можно было бы ожидать, учитывая настоящий уровень наших знаний. Для матриц до 50-го порядка и для длин слов от 32 до 48 двоичных разрядов общее число циклов в среднем равно 5—6, а число итераций, необходимое для матриц, имеющих кратные собственные значения, часто оказывалось несколько меньше чем среднее. Следующие рассуждения показывают, как это может происходить.

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

где мало по сравнению с а. Тогда

для некоторой ортогональной матрицы следовательно,

Далее мы имеем

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

(мы даем лишь верхний треугольник элементов) углы вращения, очевидно, такие же, как для матрицы С,

Однако если мы имеем дело с матрицей С, то должны помнить, что нам нужно привести ее внедиагональные элементы лишь до уровня для того, чтобы сделать внедиагональные элементы матрицы В порядка

Далее можно показать, что если матрица А имеет собственное значение а кратности то она будет приведена к диагональному виду меньше чем за один цикл. Обозначая другое собственное значение через 6, А можно представить в виде

Матрица не влияет на процесс Якоби, а элемент второй матрицы в правой части (10.7) равен Отсюда сразу же заключаем, что требуется вращений для того, чтобы исключить все элементы первой строки матрицы А, а в действительности для того, чтобы исключить все внедиагональные элементы.