\section{Двусторонние ортогональные преобразования
и их применение\label{s6.4+++}}

Ортогональные преобразования, будучи применены одновременно слева и справа
к данной матрице $A$, позволяют приводить ее к формам с нулями как ниже, так и выше диагонали. 
Это, в свою очередь, облегчает решение других сложных задач. 
С помощью ортогональных преобразований для квадратной матрицы широко распространены: приведение симметрической матрицы к трехдиагональному виду и приведение квадратной матрицы к двухдиагональному виду. 
При этом в качестве ортогональных преобразований одинаково успешно могут быть использованы преобразования Хаусхолдера или преобразования Гивенса.

\p{\large Приведение симметрической матрицы к трехдиагональному виду.}
Применим к симметрической матрице слева и справа преобразование Хаусхолдера (или Гивенса), выбирая его из задачи желаемого преобразования ведущего столбца и ведущей строки, а именно: сохранение первого диагонального элемента, получение ненулевых элементов в двух смежных с ним позициях и получение нулевых элементов в остальных позициях. 
%Сформулируем базовое утверждение.

\lm\label{l:3} Пусть дана матрица $A=A(n,n)=A^T$. Тогда существует ортогональное преобразование $Q_2$ (Хаусхолдера $T_2$ или Гивенса $P_2$) такое, что
\begin{equation}\label{eq:lemTAT}
\raisebox{-1.5ex}{$
\left[\begin{array}{c|c}
I_1& \boldsymbol{0} \\
\boldsymbol{0} & Q_2 \\
\end{array}\right]A\left[\begin{array}{c|c}
I_1& \boldsymbol{0} \\
\boldsymbol{0} & Q_2^T \\
\end{array}\right]
=\;$   }
\begin{array}{@{}r@{\hspace{-0.4em}}c@{}c@{}c@{}c}
 & \hspace{0.8em}{\overbrace{\hphantom{ss}}^{1}} &\hspace{0.4em}{\overbrace{\hphantom{ss}}^{1}} &
 \multicolumn{2}{l}{{\overbrace{\hphantom{sssss}}^{n-2}}} \\
{\scriptstyle 1}\{ & \multicolumn{4}{c}{\multirow{4}{4cm}{$\left[ 
    \begin{array}{c|cccc} 
    a_1 &\hspace{0.5em} s_1           &  \multicolumn{3}{c}{\Large \boldsymbol{0}}  \\
    \cline{2-5}
    s_1 & \hphantom{s_1} &  & & \\
    \multirow{2}{1em}{$\Large \boldsymbol{0}$} & \hphantom{s_1} &
    \tilde A & &\\
        & \hphantom{s_1}& &&
   \end{array}
\right].
$}}%
\\%!!
{\scriptstyle 1} \{ & & & & \\
 \multirow{2}{1cm}{${\scriptstyle n-2}\biggl\{ $ }  & & & & \\
 & & & & \\
\end{array}
\end{equation}
\rem В (\ref{eq:lemTAT}) транспонирование $Q_2^T$ не требуется, если в качестве $Q_2$ взято преобразование Хаусхолдера (в силу его симметричности).
При этом индекс <<$_2$>>  указывает на позицию того элемента в ведущем столбце (для левостороннего преобразования) или в ведущей строке (для правостороннего преобразования), который остается ненулевым в этом столбце (в результате применения $Q_2$) или в этой строке (в результате применения $Q_2^T$). 
В данном случае, \ie в (\ref{eq:lemTAT}), эти элементы суть $s_1$ и $s_1$.
Элемент $a_1$ не изменяется, так как $I_1$ --- единичная матрица размера $1\times 1$.

\tecom{(Тридиагонализация симметрической матрицы)}\label{tridiagonal} 
Пусть дана симметрическая матрица $A=A(n,n)=A^T$, $A_1:=A(n,n)$ и для каждого $j=1,\ldots, k$, где $k\le N=n-2$, выбрано элементарное преобразование $Q_{j+1}$ (Хаусхолдера $T_{j+1}$  или Гивенса $P_{j+1}$) так, что 
\begin{equation}\label{eq:tridiag}
\raisebox{-1.5ex}{$
\left[\begin{array}{c|c}
I_1& \boldsymbol{0} \\
\boldsymbol{0} & Q_{j+1} \\
\end{array}\right]A_j\left[\begin{array}{c|c}
I_1& \boldsymbol{0} \\
\boldsymbol{0} & Q_{j+1}^T \\
\end{array}\right]
=\;$   }
\begin{array}{@{}r@{\hspace{-1em}}c@{}c@{}c@{}c}
 & \hspace{1.4em}{\overbrace{\hphantom{ss}}^{1}} &\hspace{0.4em}{\overbrace{\hphantom{ss}}^{1}} &
 \multicolumn{2}{l}{{\overbrace{\hphantom{ssssssss}}^{n-j-1}}} \\
{\scriptstyle 1}\{ & \multicolumn{4}{c}{\multirow{4}{4cm}{$\left[ 
    \begin{array}{c|cccc} 
    a_j & \hspace{-0.4em}\bigm| \hspace{0.4em}s_j           &  \multicolumn{3}{c}{\Large \boldsymbol{0}}  \\
    \cline{2-5}
    s_j & \hspace{-0.4em}\hspace{-0.4em}\bigm|\hphantom{s_j} &  & & \\
    \multirow{2}{1em}{$\Large \boldsymbol{0}$} & \hspace{-0.4em}\hspace{-0.4em}\bigm|\hphantom{s_j} &
     A_{j+1} & &\\
        & \hspace{-0.4em}\hspace{-0.4em}\bigm|\hphantom{s_j}& &&
   \end{array}
\right].
$}}%
\\%!!
{\scriptstyle 1} \{ & & & & \\
\multirow{2}{1.45cm}{${\scriptstyle n-j-1}\biggl\{ $ }  & & & & \\
 & & & & \\
\end{array}
\end{equation}
Тогда в процессе после $k$ повторных применений леммы~\ref{l:3} имеем 
отвечающую этому моменту процесса итоговую матрицу преобразований
\begin{equation}\label{eq:tridiagtrans}
Q^{(k)}=\left[\begin{array}{ccc}
I_{k}& & 0 \\
0 & & Q_{k+1}
\end{array}
\right]Q^{(k-1)},\quad 1\le k\le N=n-2, \quad Q^{(0)}=I_n
\end{equation}
и промежуточный результат тридиагонализации данной матрицы $A$ в виде
\begin{equation*}\label{eq:trianH=input}
\raisebox{-2.16cm}{\input{TAQ.txt}} 
\raisebox{0.4cm}{$\,.$}
\end{equation*}
%%%%%%%%%%%%%%%%%%%%%%%%%

\p{\large Приведение квадратной матрицы к двухдиагональному виду.}
Применим к произвольной квадратной матрице слева преобразование $Q_1$
и справа  преобразование $S_2$ (беря любое из них как преобразование Хаусхолдера или как преобразование Гивенса), при этом $Q_1$  выберем из задачи желаемого преобразования ведущего столбца и $S_2$ --- из задачи желаемого преобразования ведущей строки, а именно: при действии $Q_1$ ---
получение ненулевого диагонального элемента и нулевых элементов ниже него
в первом (ведущем) столбце; при действии $S_2$ --- сохранение диагонального элемента, получение в смежной с ним позиции ненулевого элемента и нулевых элементов правее него в первой (ведущей) строке.
\lm\label{l:4} Пусть дана матрица $A=A(n,n)$. Тогда существуют ортогональное преобразование $Q_1$ (Хаусхолдера или Гивенса) и ортогональное преобразование $S_2$ (Хаусхолдера или Гивенса) такие, что
\begin{equation}\label{eq:lemQAS}
\raisebox{-1.5ex}{$
Q^{(1)}AS^{(1)}
=\;$   }
\begin{array}{@{}r@{\hspace{-0.4em}}c@{}c@{}c@{}c}
 & \hspace{0.8em}{\overbrace{\hphantom{ss}}^{1}} &\hspace{0.4em}{\overbrace{\hphantom{ss}}^{1}} &
 \multicolumn{2}{l}{{\overbrace{\hphantom{ssss.}}^{n-2}}} \\
{\scriptstyle 1}\{ & \multicolumn{4}{c}{\multirow{3}{4cm}{$\left[ 
    \begin{array}{c|cccc} 
    s_1 &\;\; a_1  \; &  \multicolumn{3}{c}{\Large \boldsymbol{0}}  \\
    \cline{2-5}
    \multirow{2}{1em}{$\Large \boldsymbol{0}$} &
     & \hspace{-1em}\multirow{2}{1em}{$\tilde A$}
& &\\%[-1.5ex]
        & & 
&&\\
   \end{array}
\right],
$}}%
\\%!!
 \multirow{2}{1cm}{${\scriptstyle n-2}\biggl\{ $ }  & & & & \\
 & & & & \\
\end{array} 
\qquad 
\raisebox{-1.3ex}{$\left\{\begin{aligned}
Q^{(1)}&=Q_1, \\
S^{(1)}&=\left[\begin{array}{c|c}
I_1& \boldsymbol{0} \\
\boldsymbol{0} & S_2 \\
\end{array}\right].
\end{aligned}
\right.$}
\end{equation}

\tecom{(Бидиагонализация квадратной матрицы)}\label{bidiagonal} 
Пусть дана квадратная матрица $A=A(n,n)$, $A_1:=A$ и для каждого $j=1,\ldots, k$, где $k\le n-2$, выбраны элементарное преобразование $Q_{j}$ (Хаусхолдера типа $T_{j}$  или Гивенса типа $P_{j}$) и 
элементарное преобразование $S_{j+1}$ (Хаусхолдера типа $T_{j+1}$  или Гивенса типа $P_{j+1}$)
таким образом, что в результате  получаем
\begin{equation}\label{eq:lemQASj}
\raisebox{-1.5ex}{$
Q_{j}A_j
\left[\begin{array}{c|c}
I_1& \boldsymbol{0} \\
\boldsymbol{0} & S_{j+1} \\
\end{array}\right]
=\;$   }
\begin{array}{@{}r@{\hspace{-0.4em}}c@{}c@{}c@{}c}
 & \hspace{1.2em}{\overbrace{\hphantom{ss}}^{1}} &\hspace{0.4em}{\overbrace{\hphantom{ss}}^{1}} &
 \multicolumn{2}{l}{{\overbrace{\hphantom{ssssssss}}^{n-j-1}}} \\
{\scriptstyle 1}\{ & \multicolumn{4}{c}{\multirow{3}{4cm}{$\left[ 
    \begin{array}{c|cccc} 
    s_j & \;\;a_j           & \multicolumn{3}{c}{\Large \boldsymbol{0}}  \\
    \cline{2-5}
    %s_1 & \hspace{-0.4em}\hspace{-0.4em}\bigm|\hphantom{s_1} &  & & \\   %
    \multirow{2}{1em}{$\Large \boldsymbol{0}$} & \hspace{-0.4em}\hspace{-0.4em}\hphantom{s_1} &
\multirow{2}{1em}{$A_{j+1}$}\hspace{1em}
& &\\%[-1.5ex]
        & \hspace{-0.4em}\hspace{-0.4em}\hphantom{s_1}& 
&&\\
   \end{array}
\right].
$}}%
\\%!!
 \multirow{2}{1cm}{${\scriptstyle n-j}\biggl\{ $ }  & & & & \\
 & & & & \\
\end{array} 
\end{equation}
Тогда в процессе после $k$ повторных применений леммы~\ref{l:4} имеем 
отвечающие этому моменту процесса итоговые матрицы преобразований
\begin{equation}\label{eq:bidiagtransQ}
\left.\begin{aligned}
Q^{(k)}&=\left[\begin{array}{ccc}
I_{k-1}& & 0 \\
0 & & Q_{k}
\end{array}
\right]Q^{(k-1)},\quad k\le n-2, \quad Q^{(0)}=I_n, \quad 
Q^{(1)}=Q_1,\\
S^{(k)}&=S^{(k-1)}\left[\begin{array}{ccc}
I_{k}& & 0 \\
0 & & S_{k+1}
\end{array}
\right],\quad \, k\le n-2, \quad S^{(1)}=\left[\begin{array}{ccc}
I_{1}& & 0 \\
0 & & S_{2}
\end{array}
\right]
\end{aligned}\right\}
\end{equation}
и промежуточный результат бидиагонализации данной матрицы $A$ в виде
\begin{equation*}\label{eq:trianH=input}
\raisebox{-2.16cm}{\input{TAQ2.txt}} 
\raisebox{0.4cm}{$\;.$}
\end{equation*}
Выполнив после $k=n-2$ еще одно левостороннее преобразование 
$Q_{n-1}$ (что отвечает применению верхней формулы (\ref{eq:bidiagtransQ}) для $k=n-1$), получаем окончательно
\begin{equation*}\label{eq:QASfinal=input}
\raisebox{-2.16cm}{\input{QASfinal.txt}} 
\raisebox{0.0cm}{$\;.$}
\end{equation*}

%\input{QASfinal.txt}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%