Двойной QR-шаг с использованием матриц отражения

43. Мы описали двойной QR-шаг в терминах преобразования Гйвенса. В случае одного сдвига метод Хаусхолдера не лучше, но в случае двойного сдвига он значительно более экономен.

Мы используем обозначение где

и покажем, что может быть получена следующим способом. Сначала находится такая матрица отражения что

Очевидно, что только три компоненты соответствующего отличны от нуля. Затем вычисляется матрица которая имеет форму

Эта форма почти совпадает с формой матрицы полученной при помощи плоских вращений (см. (42.1)). Единственное отличие состоит в том, что теперь уже нет нуля в позиции (4.2), но это не имеет особого значения.

Матрица затем приводится к форме Хессенберга методом Хаусхолдера (гл. 6, § 3). Это производится при помощи последовательных умножений слева и справа на матрицы Результирующая матрица В Хессенберга такова, что

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

к треугольному виду. Следовательно, В равна .

Покажем, что перед умножением слева на текущая матрица имеет форму, показанную в (43.3) для случая Действительно, предположим, что это верно для При помощи аннулируются только два элемента в столбце и следовательно, соответствующий имеет отличные от нуля элементы только в позициях Умножение справа и слева на заменяет строки и столбцы их линейными комбинациями, и таким образом аннулируются элементы в позициях Следовательно, матрица имеет ту же форму, что и и так как нужного вида, результат установлен. Как и в § 42, мы можем включить начальное преобразование в общую схему при помощи добавления к матрице дополнительного первого столбца, состоящего из элементов