\section{Преобразование Гивенса\label{s6.4}}
Преобразование Гивенса осуществляет вращение вектора в плоскости двух координат. Поскольку поворот вектора $y=(y_1 \bigm| y_2)^T$ на угол $\theta$
по часовой стрелке эквивалентен повороту системы координат против часовой стрелки на тот же угол, легко найти  (\ris\ref{f:rotate}), что координаты $y_1^\prime$, $y_2^\prime$ повернутого вектора
$y_{\mathrm{r}}\hm=(y_1^\prime \bigm| y_2^\prime)^T$  определяются в виде
$y_1^\prime=y_1\cos\theta+y_2\sin\theta$, 
$y_2^\prime=-y_1\sin\theta+y_2\cos\theta$.
\begin{figure}%[h]
\input{rotate.txt}
\caption{Геометрия вращений}\label{f:rotate}
\end{figure}

Записывая это в матричной форме и требуя, чтобы поворот $P_{1,2}$ в плоскости $(e_1,e_2)$ происходил до совмещения с первой координатной осью, получим
\[
y_{\mathrm{r}}=\left[ \begin{array}{ccc}
c &&s\\
-s&&c
\end{array}\right]y=P_{1,2}y=\left[ \begin{array}{c}
r\\
0\end{array}\right],\quad 
\left\{\begin{array}{c}
c\triangleq \cos\theta=y_1/r \\
s\triangleq \sin\theta=y_2/r
\end{array}\right\},
\quad r\triangleq \sqrt{y_1^2+y_2^2},
\]
где, очевидно, матрица $P_{1,2}$ плоского вращения ортогональна при любом $\theta$. 
\p{\large Триангуляризация матрицы преобразованиями Гивенса.}

Выбор $\theta$ такой, что вторая координата вектора $y_{\mathrm{r}}$ становится равной нулю, используем для триангуляризации матрицы $A(m,n)$. На первом шаге нужны преобразования, делающие равными нулю все элементы ниже первого диагонального элемента. 
Для этого, очевидно, нужно выполнить последовательно элементарные вращения
$P_{1,2}$, $P_{1,3}$, $\cdots$, $P_{1,m}$. Так определенные преобразования воздействуют на все столбцы матрицы, но только первый столбец, который уместно назвать \emph{ведущим столбцом}, приобретает желаемый вид.
\lm\label{l:2} Пусть дана матрица $A(m,n)$ и $y$ --- ее ведущий (левый) столбец. Тогда существует ортогональное преобразование Гивенса, задаваемое матрицей $P_1=P_1(m,m)$, такое, что
\begin{equation}\label{eq:lem2}
\raisebox{-1.5ex}{$P_1A=\;$   }\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} 
 r & \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}
\[
  P_1=P_{1,m}\cdots P_{1,3}P_{1,2}\:, 
\]
\input{P1givens.txt}


\tecom{(Триангуляризация матрицы по методу Гивенса)}\label{triangivens} 
Пусть $A_1:=A(m,n)$ и для каждого $j=1.2.\ldots, k$, $k\le\min~\!(m-1,n)$ серия элементарных преобразований Гивенса, задаваемая матрицей $P_j$ размера $(m+1-j)\times(m+1-j)$, выбрана для ведущего (левого) столбца $y_j$ матрицы $A_j$ так, что 
\begin{equation}\label{eq:trianG}
\raisebox{1.5ex}{$\raisebox{-1.5ex}{$P_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} 
 r_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$ повторных применений  леммы~\ref{l:2} имеем следующий промежуточный результат триангуляризации матрицы $A$:
%\input{TAG.txt}
\begin{equation}\label{eq:trianG=input}
\raisebox{-2.16cm}{\input{TAG.txt}}%{-0.75cm}
\end{equation}
с отвечающей этому моменту процесса итоговой матрицей преобразований
\begin{equation}\label{eq:trianGtrans}
P^{(k)}=\left[\begin{array}{ccc}
I_{k-1}& & 0 \\
0 & & P_{k}
\end{array}
\right]\cdots
\left[\begin{array}{ccc}
I_{1}& & 0 \\
0 & & P_{2}
\end{array}
\right]P_1\,, \quad P_j=P_{j,m-j+1}\cdots P_{j,3}P_{j,2}\,,
\end{equation}
\input{Pjgivens.txt}

Формула (\ref{eq:trianGtrans}) имеет рекуррентный вид произведения
\begin{equation}\label{eq:trianGrecurrent}
\left.\begin{aligned}
P^{(j)}&=\left[\begin{array}{ccc}
I_{j-1}& & 0 \\
0 & & P_{j}
\end{array}
\right]P^{(j-1)}\,, \quad P^{(1)}=P_1\\
 P_j &=P_{j,m-j+1}\cdots P_{j,3}P_{j,2}\,,\quad  j=2,\ldots,N
\end{aligned} \right\},\;   N=\min~\!(m-1,n).
\end{equation}
Все участвующие здесь матрицы являются ортогональными, поэтому
финальная матрица $P\triangleq P^{(N)}$ также ортогональна. 
Общее число используемых при этом элементарных матриц вращения равно $(m-1)\hm+(m-2)\hm+\ldots\hm+(m-N)\hm=(2m-N-1)N/2$. В результате (в случае $m>n$) получим
\begin{equation}\label{eq:trianGR=}
PA=\left[
\begin{array}{c}
R \\ \cdots \\ \boldsymbol{0} \\
\end{array}
\right],\quad\quad \raisebox{-0.75cm}{\input{R=ne.txt}}\triangleq R_{\mathrm{ne}},
\end{equation}
где индекс $_{\mathrm{ne}}$ подчеркивает, что в треугольной матрице $R$ заполненной  частью может быть только <<северо-восточная>> (\emph{north-by-east})
часть.
Полагая $Q=P^{T}$, при $m=n$ имеем
$QR$-разложение матрицы $A=A(n,n)$, \ie $A=QR$.
Матрицы в (\ref{eq:trianGtrans}) и (\ref{eq:trianGrecurrent}) непосредственно не вычисляются.

Для алгоритма Гивенса --- так же, как и для других матричных алгоритмов, --- имеются две схемы вычислений: (1) строчно
ориентированная схема и (2) столбцово ориентированная схема (\ris\ref{f:PjAcombine=}).
\begin{figure}
\input{PjAcombine=.txt}
\caption{Преобразование Гивенса: 
(a) столбцово ориентированная схема вычисления матрицы $PA$, где $P=P^{(j)}$ при
$j=\min~\!(m-1,n)$ (нижняя матрица слева);\;  
(б) вычисление координаты $r$ вектора $(a,\; b)^T$, повернутого до совмещения с первой осью, а также косинуса и синуса угла поворота и рабочего признака $\zeta$;\;
(в) строчно ориентированная схема вычисления матрицы $PA$ (верхняя матрица слева);\;  
(г) восстановление косинуса и синуса угла поворота из признака $\zeta$;\;  
(д) получение вектора $y$ теми преобразованиями $P_{j,i}$ произвольного вектора  $z\in\Rset^m$, которые сохранены в рабочих признаках 
$\zeta_{j,i}$ и восстанавливаются из них;\;
(е) вследствие (б), векторы 1, 2, 3 и 4 поворачиваются к положительному направлению первой координатной оси, а векторы 5, 6, 7 и 8
поворачиваются к отрицательному направлению этой оси.}\label{f:PjAcombine=}
\end{figure}
Как и в алгоритме преобразований Хаусхолдера (\smr\ref{f:TkA=}), здесь
обычно требуется сохранять информацию о произведенных по ходу алгоритма
(\ref{eq:trianGrecurrent}) элементарных преобразованиях, чтобы впоследствии
иметь возможность решать системы уравнений $Ax=z$ (совместные или несовместные, в последнем случае --- по методу
наименьших кdадратов, см.~подразд.~\ref{s6.2+}) 
или же находить обратную матрицу $A^{-1}$ (когда $m=n$).

Необходимая информация означает значения косинуса и синуса, однако их сохранение было бы неэффективным решением. 
Gentleman (1973) предложил эффективный способ, включенный 
в рис.~\ref{f:PjAcombine=}(б) и (г) с геометрической иллюстрацией его действия на рис.~\ref{f:PjAcombine=}(е).
Введенный им рабочий признак  $\zeta$ --- это одно число, которое можно хранить в  позиции $(i,j)$ как $\zeta_{j,i}$ вместо нулевого элемента, появляющегося в  позиции $(i,j)$  матрицы (\ref{eq:trianGR=}) в момент преобразования $P_{j,t}$ ($t=i+1-j$) в (\ref{eq:trianGtrans}). 
Как и с преобразованиями Хаусхолдера, нахождение $A^{-1}$ после преобразований Гивенса требует такой же последовательности процедур:
сначала находят $R^{-1}$ (см.~\ref{s6.3++}), затем к $R^{-1}$ применяют с правой стороны финальное преобразование $P\triangleq P^{(N)}$ (\ref{eq:trianGrecurrent}), так как $A^{-1}=R^{-1}P$. Для этого на \ris\ref{f:abcd} надо взять алгоритм из \ris\ref{f:PjAcombine=}(д), который также отыскивает $Pz$ при решении уравнения $Ax=z$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%