Преобразование Хаусхолдера в численной линейной алгебре¶

Преобразование Хаусхолдера — это линейное ортогональное преобразование векторного пространства, задаваемое матрицей вида H = I − 2vvᵀ/(vᵀv), где v — ненулевой вектор-столбец. В численной линейной алгебре преобразование Хаусхолдера используется для приведения матриц к более простым формам (треугольной, верхней Хессенберга, двухдиагональной) путём последовательного обнуления элементов матрицы. Преобразование названо в честь американского математика Алстона Скотта Хаусхолдера (1904–1993), впервые описавшего его применение к численным методам в 1958 году.

¶Определение и свойства

Матрица Хаусхолдера H является симметричной (H = Hᵀ) и ортогональной (HᵀH = I), что обеспечивает численную устойчивость преобразования: оно не усиливает ошибки округления, поскольку сохраняет норму вектора (‖Hx‖ = ‖x‖). Геометрически преобразование Хаусхолдера представляет собой отражение вектора относительно гиперплоскости с нормалью v, проходящей через начало координат. В отличие от вращений Гивенса, которые обнуляют один элемент за раз, преобразование Хаусхолдера позволяет одновременно обнулить целый блок элементов вектора или столбца матрицы.

Ключевым свойством является возможность подобрать вектор v так, чтобы преобразованный вектор имел лишь одну ненулевую компоненту. Для заданного вектора x выбирается v = x + sign(x₁)‖x‖e₁, где e₁ — первый единичный вектор. Тогда Hx = −sign(x₁)‖x‖e₁, то есть все компоненты, кроме первой, обращаются в ноль. Такой выбор вектора v минимизирует вычислительную погрешность при работе с числами с плавающей запятой.

¶Алгоритм построения

На практике матрица Хаусхолдера не формируется в явном виде, а хранится в компактной форме — в виде вектора v и скалярного коэффициента τ = 2/(vᵀv). Применение преобразования к матрице A выполняется по формуле:

A ← A − τ v (vᵀA)

Это требует O(n²) операций для матрицы размера n×n, что вдвое эффективнее, чем явное умножение на полную матрицу H. Такой подход называется «неявным» представлением преобразования Хаусхолдера.

¶Применение в численных методах

¶QR-разложение

Наиболее известное применение преобразования Хаусхолдера — построение QR-разложения матрицы A = QR, где Q — ортогональная, R — верхняя треугольная матрица. Последовательно применяя преобразования Хаусхолдера к столбцам матрицы, обнуляют поддиагональные элементы. Этот метод, реализованный в пакетах LAPACK и LINPACK, считается стандартным для плотных матриц благодаря высокой численной устойчивости и эффективности.

¶Приведение к форме Хессенберга

Для вычисления собственных значений матриц QR-алгоритмом исходную матрицу сначала приводят к верхней форме Хессенберга (матрица с нулями ниже первой поддиагонали). Это также выполняется преобразованиями Хаусхолдера, что сокращает вычислительные затраты последующего итерационного процесса с O(n³) до O(n²) на итерацию.

¶Двухдиагонализация в SVD

При вычислении сингулярного разложения (SVD) матрица приводится к двухдиагональной форме с помощью преобразований Хаусхолдера, применяемых слева и справа. Этот этап предшествует итерационному QR-алгоритму для двухдиагональных матриц.

¶Решение задач наименьших квадратов

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

¶Преимущества и ограничения

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

Ограничение состоит в том, что преобразование Хаусхолдера не позволяет обнулять элементы выборочно — оно воздействует на весь вектор или столбец. Для разреженных матриц и задач, требующих точечных обнулений, предпочтительнее вращения Гивенса. Кроме того, при работе с очень малыми матрицами (n < 3) накладные расходы на вычисление вектора v могут превышать выигрыш от сокращения операций.

¶Реализации

Преобразование Хаусхолдера реализовано во всех основных библиотеках численной линейной алгебры: LAPACK (подпрограммы dgeqrf, dgehrd, dgebd2), SciPy (функция scipy.linalg.householder), MATLAB (функция qr с опцией экономичного разложения), а также в библиотеках на языках C++ (Eigen, Armadillo) и Julia (LinearAlgebra). Современные реализации учитывают особенности архитектуры процессоров, включая блочные версии алгоритма для эффективного использования кэш-памяти.

¶Источники

• Golub G. H., Van Loan C. F. Matrix Computations. — 4th ed. — Johns Hopkins University Press, 2013.
• Trefethen L. N., Bau D. Numerical Linear Algebra. — SIAM, 1997.
• Деммель Дж. Вычислительная линейная алгебра. Теория и приложения. — М.: Мир, 2001.
• LAPACK Users' Guide. — 3rd ed. — SIAM, 1999.