Использование перестановок

44. Мы описали процесс, аналогичный процессу § 11, а не § 8, так как первый более экономичен при рассмотрении ошибок округления. При рассмотрении перестановок несколько более удобно вернуться к § 8. Если задана как нижняя форма Хессенберга, то при предположении, что перестановки не использовались, имеет, например, для случая вид

Основной шаг заключается в следующем.

Для всех значений от до выполняем операции (i) и (ii):

(i) Вычисляем .

(ii) Вычитаем (строка ) из строки (Заметим, что строка имеет только два отличных от нуля элемента, кроме

(iii) Для всех значений до прибавляем (столбец) к столбцу

Очевидно, что шаг не портит ни один из нулей первоначальной или введенных на предыдущих шагах.

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

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

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

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