Экспериментальная проверка сходимости

23. Мы экспериментировали с LR-алгорифмом (с перестановками) на матрицах Хессенберга, используя сдвиг, определенный текущим значением Естественно, что он использовался лишь для вещественных матриц, про которые известно, что они имеют вещественные собственные значения, или для матриц с комплексными элементами. Вообще говоря, не ясно, когда нужно было бы начинать использовать это значение сдвига, и мы исследовали эффективность следующих процедур:

(i) Сдвиг использовался на каждом этапе.

(ii) Сдвиг использовался, только когда где 8 — некоторый допуск (т. е. сдвиг употребляется, когда уже начали стабилизироваться).

(iii) Сдвиг использовался только тогда, когда где снова некоторый допуск.

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

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

При этом при всех и выбор не дает эффекта. Если мы имеем сходимость, то стремится к нулю, и поэтому использовался сдвиг

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