Сдвиг
36. Так же как и в LR-алгоритме, в
-алгоритме может быть введен сдвиг с восстановлением или без восстановления. Процесс с восстановлением имеет вид
и, как и раньше, мы можем показать, что
и
Эти сдвиги важны на практике. Если
вещественная и известно, что она имеет вещественные собственные значения, или если
комплексная, мы можем выбирать сдвиг в точности так же, как в § 24. В первом случае вся арифметика вещественная. В общем случае число итераций при
-преобразованиях оказалось значительно меньше по сравнению с модифицированным LR-процессом при использовании сдвигов, определенных в каждом случае по одному и тому же принципу.
Если
вещественная, но имеет несколько комплексно сопряженных собственных значений, то, вообще говоря, на некоторой стадии итераций матрица второго порядка в нижнем правом углу будет иметь комплексно сопряженные собственные значения
Если мы выполним два шага QR, используя сдвиги
то точные вычисления дадут в результате вещественную матрицу, хотя промежуточная матрица будет комплексной. Хотя теперь мы не имеем трудностей, подмеченных в § 27 в связи с перестановками, все же на практике конечная матрица может иметь значительную мнимую часть, хотя собственные значения в точности сохраняются. Френсис описал элегантный метод комбинирования этих двух шагов таким образом, что избегается использование комплексной арифметики. Окончательная матрица получается вещественной, и процесс столь же устойчив, как и стандартный
-алгоритм. Прежде чем обсуждать этот метод, рассмотрим, однако, два других способа, которые дают значительную экономию в объеме вычислений. Они могут быть использованы как с
так и с модифицированным LR-алгоритмами, и будет проще рассмотреть последний случай.