Метод Хаусхолдера отражения: схема и пример

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

Что такое преобразование Хаусхолдера

Преобразование Хаусхолдера задаётся вектором $v \neq 0$ и определяет матрицу отражения

$$H = I - 2\frac{v v^{\top}}{v^{\top} v},$$

где $I$ - единичная матрица. Такая матрица обладает двумя ключевыми свойствами: она симметрична ($H^{\top} = H$) и ортогональна ($H^{\top} H = I$), а значит $H^{-1} = H$ - повторное применение возвращает исходный вектор. Действие $H$ на произвольный вектор $x$ есть его отражение относительно гиперплоскости с нормалью $v$. При этом норма сохраняется: $\|Hx\|_2 = \|x\|_2$. Именно ортогональность отвечает за хорошую обусловленность: метод Хаусхолдера отражения не усиливает ошибки округления так, как это делает исключение Гаусса с делением на малый ведущий элемент.

Дальше - интерактивный построитель: задайте вектор или матрицу, выберите задачу, и модель построит матрицу отражения и выполнит шаги метода Хаусхолдера с подробными выкладками.

Как обнулить столбец одним отражением

Базовая задача метода Хаусхолдера отражения - найти такое $H$, чтобы для заданного вектора $x$ результат $Hx$ был коллинеарен первому орту, то есть имел вид $\alpha e_1$. Поскольку отражение сохраняет длину, обязательно $|\alpha| = \|x\|_2$. Вектор отражения выбирается как

$$v = x - \alpha e_1, \qquad \alpha = \pm\|x\|_2.$$

Тогда $Hx = \alpha e_1$, и все компоненты вектора, кроме первой, обращаются в ноль. Знак $\alpha$ выбирают противоположным знаку первой компоненты $x_1$, то есть $\alpha = -\operatorname{sign}(x_1)\|x\|_2$. Это критически важно для численной устойчивости: при таком выборе разность $x_1 - \alpha$ не подвержена катастрофической потере значащих цифр, которая возникла бы при вычитании двух близких чисел. Нормировать $v$ не обязательно - формула для $H$ инвариантна к масштабу $v$, но на практике часто используют нормировку $v_1 = 1$ и хранят коэффициент $\beta = 2/(v^{\top} v)$.

QR-разложение методом Хаусхолдера отражения

Главное применение - построение QR-разложения матрицы $A \in \mathbb{R}^{m \times n}$, то есть представление $A = QR$ с ортогональной $Q$ и верхней треугольной $R$. Идея: последовательно применять отражения $H_1, H_2, \ldots, H_n$ так, чтобы каждое обнуляло поддиагональные элементы очередного столбца.

На шаге $k$ берётся подстолбец $a^{(k)}$ от диагонали вниз и строится отражение $H_k$, обнуляющее всё ниже диагонали в $k$-м столбце:

$$H_n \cdots H_2 H_1 A = R.$$

Поскольку каждое $H_k$ ортогонально, произведение $Q^{\top} = H_n \cdots H_1$ тоже ортогонально, и тогда

$$Q = H_1 H_2 \cdots H_n, \qquad A = QR.$$

Важная деталь реализации: матрицы $H_k$ в явном виде не перемножают. Применение отражения к матрице $A$ выполняется как $H A = A - v(\beta\, v^{\top} A)$, то есть через два матрично-векторных произведения за $O(mn)$ операций вместо $O(m^2 n)$ при явном умножении. Это делает метод Хаусхолдера отражения экономичным: полное QR-разложение стоит примерно $2n^2(m - n/3)$ флопов. По сравнению с алгоритмом LU-разложения метод Хаусхолдера отражения дороже, но зато сохраняет ортогональность и не требует выбора ведущего элемента для устойчивости. Подробнее о треугольных факторизациях см. в разборе LU-разложения матрицы.

Пошаговый пример

Возьмём первый столбец $x = (3, 4)^{\top}$. Тогда $\|x\|_2 = 5$, а знак первой компоненты положителен, поэтому $\alpha = -5$. Вектор отражения:

$$v = x - \alpha e_1 = \begin{pmatrix} 3 \\ 4 \end{pmatrix} - (-5)\begin{pmatrix} 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 8 \\ 4 \end{pmatrix}.$$

Считаем $v^{\top} v = 64 + 16 = 80$ и матрицу отражения:

$$H = I - \frac{2}{80} v v^{\top} = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} - \frac{1}{40}\begin{pmatrix} 64 & 32 \\ 32 & 16 \end{pmatrix} = \begin{pmatrix} -0.6 & -0.8 \\ -0.8 & 0.6 \end{pmatrix}.$$

Проверка: $Hx = (-3\cdot0.6 - 4\cdot0.8,\; -3\cdot0.8 + 4\cdot0.6)^{\top} = (-5, 0)^{\top} = \alpha e_1$. Поддиагональный элемент обнулился, а норма сохранилась ($|-5| = 5$). Для матрицы $n \times n$ эту процедуру повторяют для каждого столбца, работая каждый раз с уменьшающимся подблоком: на шаге $k$ отражение действует только на строки и столбцы с индексами от $k$ до $n$, а уже обнулённая часть $R$ остаётся нетронутой. Если нужна сама матрица $Q$, её собирают, применяя отражения в обратном порядке к единичной матрице, либо хранят все векторы $v_k$ в компактном виде в обнулённой нижней части $A$ - так поступают библиотечные реализации (LAPACK), экономя память. При решении системы $Ax = b$ или задачи наименьших квадратов матрицу $Q$ вообще не формируют: достаточно последовательно применить отражения к правой части $b$, получить $Q^{\top} b$ и затем решить треугольную систему $Rx = Q^{\top} b$ обратной подстановкой.

Связь с другими ортогональными методами

Метод Хаусхолдера отражения - не единственный способ ортогонального обнуления. Вращения Гивенса обнуляют по одному элементу за раз и удобны для разреженных матриц или дообновления QR, когда к уже разложенной матрице добавляется строка или столбец. Процесс Грама–Шмидта строит ортонормированный базис напрямую, но его классическая версия численно неустойчива из-за накопления ошибок ортогональности; модифицированный Грам–Шмидт лучше, но всё равно уступает отражениям по качеству ортогонализации. Для плотных матриц метод Хаусхолдера отражения - стандарт де-факто: он за один шаг обнуляет целый столбец и сохраняет ортогональность с машинной точностью.

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

Частые ошибки

• Неправильный выбор знака $\alpha$: при $\alpha = +\operatorname{sign}(x_1)\|x\|$ разность $x_1 - \alpha$ теряет точность; всегда берите знак, противоположный $x_1$.
• Явное перемножение матриц $H_k$: это лишние $O(m^2)$ операций на шаг; применяйте отражение как $A - v(\beta v^{\top} A)$.
• Нормировка $v$ на ноль: если столбец уже имеет нулевые поддиагональные элементы, $v$ может выйти нулевым - этот случай надо обрабатывать отдельно (отражение не нужно).
• Путаница $Q = H_1\cdots H_n$ и $Q^{\top} = H_n\cdots H_1$: порядок множителей при сборке $Q$ обратен порядку применения.
• Забытое деление на $v^{\top} v$: формула $H = I - 2 vv^{\top}/(v^{\top}v)$ требует нормирующего знаменателя, иначе $H$ не будет ортогональной.

FAQ

Чем метод Хаусхолдера отражения лучше вращений Гивенса? Одно отражение обнуляет сразу весь поддиагональный кусок столбца, тогда как одно вращение Гивенса обнуляет лишь один элемент. Для плотных матриц Хаусхолдер требует меньше операций; Гивенс выигрывает на разреженных задачах и при инкрементальном обновлении.

Почему метод численно устойчив? Все преобразования ортогональны, $\|Hx\|_2 = \|x\|_2$, поэтому относительные ошибки округления не растут. В отличие от исключения Гаусса, здесь нет деления на потенциально малый ведущий элемент.

Можно ли применять отражения к прямоугольным матрицам? Да. Для $A \in \mathbb{R}^{m\times n}$ при $m \ge n$ получается «тонкое» QR-разложение, которое используют для решения переопределённых систем методом наименьших квадратов.

Коротко

Метод Хаусхолдера отражения строит ортогональную матрицу $H = I - 2vv^{\top}/(v^{\top}v)$, которая отражает вектор так, чтобы обнулить все его компоненты ниже выбранной. Последовательное применение таких отражений к столбцам матрицы даёт устойчивое QR-разложение $A = QR$ без выбора ведущего элемента. Ключ к точности - выбор знака $\alpha = -\operatorname{sign}(x_1)\|x\|_2$ и применение отражений без явного перемножения матриц.