Уровень метода

Метод Хаусхолдера (отражений) QR-разложения хессенберговой матрицы (вещественный вариант)

Материал из Алговики
Перейти к навигации Перейти к поиску


Метод Хаусхолдера (в советской математической литературе чаще называется методом отражений) используется для разложения матриц в виде A=QR (Q - унитарная, R — правая треугольная матрица)[1]. При этом матрица Q хранится и используется не в своём явном виде, а в виде произведения матриц отражения[2].

Матрица отражений (Хаусхолдера) - матрица вида U=E-2ww^*, где w - вектор, удовлетворяющий равенству w^{*}w=1. Является одновременно унитарной (U^{*}U=E) и эрмитовой (U^{*}=U), поэтому обратна самой себе (U^{-1}=U).

Поскольку для QR-разложения хессенберговой матрицы нужно "обнулить" только элементы одной диагонали, то, в отличие от стандартной реализации метода Хаусхолдера для плотной квадратной матрицы, для него нужно выполнять операции отражения с базой на приведении двумерных векторов к одному из ортов, то есть этот алгоритм квадратичен по порядку выполняемых операций. Критический путь этого алгоритма, как и в случае метода Гивенса, от которого метод Хаусхолдера отличается только коэффициентами в матрицах, линеен.

Алгоритм, однако, в своём чистом виде практически не используется. Дело в том, что в QR-алгоритме, где QR-разложения хессенберговых матриц формально используются, для экономии ресурсов они давно применяются в неявном виде, а именно в составе QR-итераций с неявным двойным сдвигом[3].

Литература

  1. В.В.Воеводин, Ю.А.Кузнецов. Матрицы и вычисления. М.: Наука, 1984.
  2. Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.
  3. Деммель Д. Вычислительная линейная алгебра. – 2001. - С.261-264.