\section{Преобразование Хаусхолдера\label{s6.3}}
Преобразования Хаусхолдера суть матричные представления, которые 
соответствуют геометрическому понятию отражения.
Пусть задан некоторый ненулевой вектор $u$, который мы называем \emph{направляющим вектором}. Подпространство, ортогональное ему,
есть гиперплоскость $U_{\perp}$. Если взять произвольный вектор $y$,
то можно отразить его от  $U_{\perp}$, в точности соблюдая законы обычного оптического отражения от плоского зеркала (\ris\ref{f:reflect}).

Обозначим отраженный вектор $y_{\mathrm{r}}$. Поскольку положение гиперплоскости  $U_{\perp}$ не зависит от длины направляющего вектора,
пронормируем его, \ie образуем орт $\hat u=u/\Vert u \Vert$.
Проекция $(y\bigm|u)$ вектора $y$ на прямую, задаваемую направлением $u$, равна $(y^T\hat u)\hat u$. Следовательно,
\begin{equation}\label{y=}
y=(y\bigm|u)+v,\quad v\perp u,\quad v\in U_{\perp}.
\end{equation}

Отраженный вектор $y_{\mathrm{r}}$, как видно из \ris\ref{f:reflect}, имеет разложение
\begin{equation}\label{yr=}
y_{\mathrm{r}}=-(y\bigm|u)+v,\quad v\perp u,\quad v\in U_{\perp}
\end{equation}
\begin{figure}%[h]
\input{reflect.txt}
\caption{Геометрия преобразования Хаусхолдера. Задача 1 (прямая): даны векторы $u$ и $y$, найти вектор $y_{\mathrm{r}}$, отраженный от гиперплоскости $U_{\perp}$}\label{f:reflect}
\end{figure}
с той же составляющей $v$, которая ортогональна вектору  $u$, но с
проекцией $-(y\bigm|u)$, которая (в силу знака $-$) направлена  противоположно проекции  $(y\bigm|\hat u)$
вектора  $y$ на направление $u$. Исключая  $v$
из (\ref{y=}) и (\ref{yr=}), находим
\begin{equation}\label{yr==}
y_{\mathrm{r}}=y-2(y\bigm|u)=(I-\beta uu^T)y=T_uy,
\end{equation}
где $\beta\triangleq 2/\Vert u \Vert^2=2/ u^Tu$. Матрица $T_u\triangleq (I-\beta uu^T)$,
в вычислениях явно не участвующая, имеет фундаментальное значение для 
приложений в силу своих замечательных свойств. 

\s{\large Свойство 1.} $T_u=T_u^T$, \ie $T_u$ --- \emph{симметрическая} матрица.

\s{\large Свойство 2.} $T_u^2=I$, \ie $T_u$ --- \emph{идемпотентная} матрица.
Это легко продемострировать алгебраически разложением матрицы $T_u^2$ или же геометрически по \ris\ref{f:reflect} как двукратное отражение вектора $y$ относительно $U_{\perp}$.

\s{\large Свойство 3.} Если $u(j)=0$, то $(T_uy)(j)=y(j)$, \ie  если $j$-я
компонента вектора $u$ --- нулевая, то $T_u$ оставляет $j$-ю компоненту
вектора $y$ неизменной.

\s{\large Свойство 4.} Если $u\perp y$, то $T_uy=y$.

\s{\large Свойство 5.} 
\begin{equation}\label{T_uy=}
T_uy=y-\gamma u, \qquad \gamma\triangleq 2y^Tu/u^Tu=\beta y^Tu.
\end{equation}

Свойство 5 важно с практической точки зрения. Формирование матрицы $T_u$
в качестве множителя для $y$ потребовало бы на порядок больше вычислений, чем того требует прямое вычисление $T_uy$ по свойству 5. Это также означает, что не нужно тратить память для хранения  $T_u$, что наиболее существенно проявляется при больших $m$.

\p{\large Триангуляризация матрицы преобразованиями Хаусхолдера.}

Обратимся к основному применению ортогональных преобразований. Для этого решим задачу, обратную  к  той, что рассмотрена выше, а именно: дан
вектор $y$  и дано желаемое расположение отраженного вектора $y_{\mathrm{r}}$, --- найти направление $u$ такое, что $T_uy=(s,0,\ldots,0)^T$ (\ris\ref{f:reflect2}). Из свойства C, разд.~\ref{s6.1}, норма (евклидова длина) вектора $y$ не изменяется при ортогональном преобразовании, следовательно, определим ее как
\begin{equation}\label{sigma=}
\sigma\triangleq \Vert T_uy \Vert =|s|=(y^Ty)^{1/2}.
\end{equation}
Направление  $u$ может быть получено из свойства 5 (уравнение (\ref{T_uy=})), \ie
\begin{equation}\label{u=}
u=\mathrm{const}\cdot(y-se_1).
\end{equation}
Этот результат приводит к следующему свойству.
\s{\large Свойство 6.} Пусть $s=-\sgn{y(1)}\sigma$, где $\sgn{\cdot}$ --- функция знака,
$$\sgn{x}=\begin{cases} 1, & x\ge 0,\\ -1, & x<0, \end{cases}$$ и 
элементы вектора $u$ определены выражением (\ref{u=}), \ie $u(1)=y(1)-s$, $u(i)\hm=y(i)$, $i>1$. Тогда $T_uy=se_1$ и
 $\beta\triangleq 2/u^Tu\hm=-1/(su(1))$.
\rem Геометрический смысл выражения (\ref{u=}) ясен из \ris\ref{f:reflect2}, где видно, что вектор $y_{\mathrm{r}}$ ортогонален гиперплоскости $U_{\perp}$ и параллелен вектору $u$.

\begin{figure}%[h]
\input{reflect2.txt}
\caption{Геометрия преобразования Хаусхолдера. Задача 2 (обратная): даны векторы $y$ и $y_{\mathrm{r}}$, найти вектор $u$, задающий отражающую гиперплоскость $U_{\perp}$; здесь $y_{\mathrm{r}}\hm=se_1\hm=\left[s\bigm|{0}\cdots {0}\right]^T$}\label{f:reflect2}
\end{figure}

Непосредственное вычисление $u^Tu$ показывает, что $u^Tu=-2su(1)$, при этом знак для 
$s$ выбран противоположно знаку первого элемента $y(1)$, \ie так, чтобы максимизировать $|u(1)|$ и тем уменьшить относительную погрешность вычисления разности
$u(1)=y(1)-s$.
Если свойство~6 применить к матрице $A$, взяв в качестве $y$ ее первый столбец, то это даст первый шаг, который послужит основой приведения матрицы к верхнетреугольному виду. Повторение таких действий шаг за шагом позволит осуществлять верхнюю триангуляризацию любой заданной матрицы $A$.

\lm\label{l:1} Пусть дана матрица $A(m,n)$. Тогда существует ортогональное преобразование Хаусхолдера $T_u$ такое, что
\begin{equation}\label{eq:lem1}
\raisebox{-1.5ex}{$T_uA=\;$   }\begin{array}{@{}r@{}c@{}c}
  & \hspace{1em}{\overbrace{\hphantom{sss}}^{1}} & \hspace{-0.2em}{\overbrace{\hphantom{sssss}}^{n-1}} \\
 {\scriptstyle 1} \{ & \multicolumn{2}{c}{\multirow{2}{3cm}{%
 $\left[ \begin{array}{ccc} 
 s & \bigm| & \\
 \multirow{2}{1em}{$\boldsymbol{0}$} & \bigm| & \tilde A\hphantom{s} \\
  & \bigm| & 
\end{array}
 \right].$
 }}   \\
 \multirow{2}{1.1cm}{${\scriptstyle m-1}\biggl\{ $ } &  &  \\
  &  &  
\end{array}
\end{equation}
\rem\label{r:Haus} Скаляр $s$ и матрица $\tilde A$ в (\ref{eq:lem1}) вычисляются непосредственно по данным в матрице $A$; $s$ --- по выражению (\ref{sigma=}) и свойству~6,
а $\tilde A$ --- по свойству~5, (\ref{T_uy=}). Первый столбец, который уместно назвать \emph{ведущим} столбцом, используют как вектор $y$ в задаче~2 (\smr\ref{f:reflect2}) для определения вектора $u$. 
Второй и далее столбцы, обозначенные на \ris\ref{f:reflect2} произвольно как вектор $a$, отражают от найденной таким образом гиперплоскости $U_{\perp}$, решая для этого задачу 1 (\smr\ref{f:reflect}) с $y:=a$ и тем самым получая блок $\tilde A$.

\tecom{(Триангуляризация матрицы по методу Хаусхолдера)}\label{trianhaus} 
Пусть $A_1:=A(m,n)$ и для каждого $j$ выбрано элементарное преобразование Хаусхолдера $T_j$ так, что 
\begin{equation}\label{eq:trianH}
\raisebox{1.5ex}{$\raisebox{-1.5ex}{$T_jA_j=\;$   }\begin{array}{@{}r@{}r@{}c}
  & \hspace{1em}{\overbrace{\hphantom{sss}}^{1}} & \hspace{1em}{\overbrace{\hphantom{sssssss}}^{n-j}} \\
 {\scriptstyle 1} \{ & \multicolumn{2}{l}{\multirow{2}{3cm}{%
 $\left[ \begin{array}{ccc} 
 s_j & \bigm| & a_j^T \\
 \multirow{2}{1em}{$\boldsymbol{0}$} & \bigm| &
 \multirow{2}{3em}{$A_{j+1}$} \\
  & \bigm| & 
\end{array}
 \right],$
 }}   \\
 \multirow{2}{1.1cm}{${\scriptstyle m-j}\biggl\{ $ } &  &  \\
  &  &  
\end{array}$}
\qquad j=1,\ldots,k;\quad k\le\min~(m-1,n).
\end{equation}
Тогда в процессе после $k$ повторных применений свойства 6 и леммы~\ref{l:1} имеем следующий промежуточный результат триангуляризации матрицы $A$:
%\input{TAH.txt}
\begin{equation}\label{eq:trianH=input}
\raisebox{-2.16cm}{\input{TAH.txt}}%{-0.75cm}
\end{equation}
с отвечающей этому моменту процесса итоговой матрицей преобразований
\begin{equation}\label{eq:trianHtrans}
T^{(k)}=\left[\begin{array}{ccc}
I_{k-1}& & 0 \\
0 & & T_{k}
\end{array}
\right]\cdots
\left[\begin{array}{ccc}
I_{1}& & 0 \\
0 & & T_{2}
\end{array}
\right]T_1\,.
\end{equation}

\rem\label{afterteorrem}
Важно подчеркнуть, что алгоритм триангуляризации (\ref{eq:trianH}) не требует вычисления или запоминания ортогональной матрицы $T^{(k)}$, так как правая часть равенства (\ref{eq:trianH=input}) вычисляется непосредственно в соответствии с замечанием~\ref{r:Haus}.
Стоит также  заметить, как неявно определяется $A_{j+1}$ рекурсией по $j$ в алгоритме (\ref{eq:trianH}). Кроме $A_{j+1}$, на шаге $j$ этой рекурсии определяются 
скаляр $s_j$  и $(n-j)$ компонент вектор-строки $a_j^T$. Эти неявные соотношения для  $s_j$,   $a_j^T$ и $A_{j+1}$ и весь процесс вычислений (\ris\ref{f:schematic}) представлены в явном виде в разд.~\ref{s6.3+}.

\begin{figure}[h]
\input{schematic.txt}
\caption{Схематическое представление возможных случаев применения теоремы~\ref{trianhaus} к матрице $A(m,n)$; (a) недоопределенная система: $k=m-1\le n$; (b) определенная система: $k=n-1$, $m\hm=n$; (c) переопределенная система: $k=n<m$; (d)~~$k<n<m$}\label{f:schematic}
\end{figure}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%