Сдвиг

36. Так же как и в LR-алгоритме, в -алгоритме может быть введен сдвиг с восстановлением или без восстановления. Процесс с восстановлением имеет вид

и, как и раньше, мы можем показать, что

и

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

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