ПРЕОБРАЗОВАНИЕ ХАУСХОЛДЕРА


Смотрите также: qr, lsm

Матрица Хаусхолдера описывается резольвентой Q=I–2uu'/(u'u), где I – диагональная единичная матрица, u – вектор. Матрицы ортогональных преобразований – это матрицы вращения. Преобразование с ней разворачивает вектор u в противоположном направлении: Qu=–u, ортогональные к u векторы не меняют своего положения. Определение не затрагивает напрямую область практического приложения, а вводит полезное понятие: матрицу вектора.

Полезная нагрузка иная – аннулирование части компонент вектора v сведением его к орту e, т.е. Qv=se или Qv=–se, все равно, матрица Q определяется искомым вектором u. При повороте абсолютное значение ведущего неанулируемого элемента с индексом i возрастает до нормы всего вектора s=(v'v)1/2, для определенности знак при норме противоположен знаку ведущего элемента до поворота вектора. Разновидность этой задачи состоит в увеличении веса ведущего элемента за счет части нижних компонент, начиная с индекса k. В 1953 году Хаусхолдер публикует в своей книге примерно следующий алгоритм.


Экономия памяти. Заметим, что вектор u содержит ведущий элемент, нулевые элементы и элементы исходного вектора v, начиная с номера k. Как видно, достаточно рассчитывать только ведущий элемент u, хранимый отдельно. Вектор x=Qv отличен от нуля только в верхней его части, которую можно размещать в v. Операция тогда приобретает вид пересчета вектора v, с изменением его верхней части.

Применение этой операции последовательно к вектор-столбцам некоторой матрицы P, с постепенным наращиванием k, приводит к QR-разложению ее, от матрицы остается верхний правый ее треугольник R=QP. Сначала к единичному орту с некоторым весом приводится первый столбец матрицы. Остальные столбцы как преобразуются, так и преобразуются. Далее объектом преобразования становится прямоугольная матрица без верхней строки, ее первый столбец нулевой и преобразования не изменяют его. Если отбросить и его, то алгоритм повторяется. Матрица Q состоит из произведений матриц Хаусхолдера уменьшающегося порядка, для согласования размерностей множители сверху наращиваются единичной матрицей.


Rambler's Top100