Русская Википедия:Поворот Гивенса
Поворот Гивенса — в линейной алгебре линейный оператор поворота вектора на некоторый заданный угол.
Матрица Гивенса[1][2][3]
Матрица Гивенса <math>G_{kl}</math> имеет следующий вид:
<math>G_{k l} =
\begin{bmatrix} 1 & \cdots & 0 & \cdots & 0 & \cdots & 0 \\
\vdots & \ddots & \vdots & & \vdots & & \vdots \\
0 & \cdots & \cos{\phi} & \cdots & -\sin{\phi} & \cdots & 0 \\
\vdots & & \vdots & \ddots & \vdots & & \vdots \\
0 & \cdots & \sin{\phi} & \cdots & \cos{\phi} & \cdots & 0 \\
\vdots & & \vdots & & \vdots & \ddots & \vdots \\
0 & \cdots & 0 & \cdots & 0 & \cdots & 1
\end{bmatrix}</math>
Данная матрица отличается от единичной матрицы только подматрицей
<math>M (\phi) = \begin{bmatrix} \cos{\phi} & -\sin{\phi} \\ \sin{\phi} & \cos{\phi} \end{bmatrix}</math>
расположенной на строках и столбцах с номерами <math>k</math> и <math>l</math>. Является ортогональной.
Если дан вектор <math>a = \begin{bmatrix} a_1 & \ldots & a_n \end{bmatrix}^T \in \mathbb{R}^n</math>, <math>s = \sqrt{ a_k ^ 2 + a_l ^ 2} \neq 0</math>, то выбрав
<math display="block">\cos{\phi} = \frac{a_k}{\sqrt{a_k^2 + a_l^2}}</math> <math display="block">\sin{\phi} = \frac{-a_l}{\sqrt{a_k^2 + a_l^2}}</math>
можно обнулить <math>l</math>-ую компоненту вектора <math>a</math>:<math display="block">\begin{bmatrix} \cos{\phi} & -\sin{\phi} \\ \sin{\phi} & \cos{\phi} \end{bmatrix} \begin{bmatrix} a_k \\ a_l \end{bmatrix} = \begin{bmatrix} \cos{\phi} \cdot a_k - \sin{\phi} \cdot a_l \\ \sin{\phi} \cdot a_k + \cos{\phi} \cdot a_l \end{bmatrix} = \begin{bmatrix} \frac{a_k ^ 2 + a_l ^ 2}{\sqrt{a_k ^ 2 + a_l ^ 2}} \\ \frac{-a_l \cdot a_k + a_k \cdot a_l}{\sqrt{a_k ^ 2 + a_l ^ 2}} \end{bmatrix} =
\begin{bmatrix} \sqrt{a_k ^ 2 + a_l ^ 2} \\ 0 \end{bmatrix}</math>
С помощью поворотов Гивенса можно вычислять QR-разложение матриц и приводить эрмитовы матрицы к диагональной форме, а матрицы общего вида к трёхдиагональной, треугольной или хессенберговской форме.
Использование матриц Гивенса для трёхдиагонализации
Пусть хотим привести к трёхдиагональному виду симметричную матрицу: <math>A =
\begin{bmatrix} a_{11} & \cdots & a_{1p} & \cdots & a_{1q} & \cdots & a_{1n} \\
\vdots & & \vdots & & \vdots & & \vdots \\
a_{p1} & \cdots & a_{pp} & \cdots & a_{pq} & \cdots & a_{pn} \\
\vdots & & \vdots & & \vdots & & \vdots \\
a_{q1} & \cdots & a_{qp} & \cdots & a_{qq} & \cdots & a_{qn} \\
\vdots & & \vdots & & \vdots & & \vdots \\
a_{n1} & \cdots & a_{np} & \cdots & a_{nq} & \cdots & a_{nn}
\end{bmatrix}</math>
Где <math>a_{pq} = a_{qp}</math>. Тогда домножим её на матрицу вращения Гивенса: <math>G'_{pq}(\theta)AG_{pq}(\theta)</math>. <math>G</math> — транспонированная матрица. При этом изменятся только элементы <math>a_{pp}</math>, <math>a_{pq}</math> и <math>a_{qq}</math>
<math>a'_{pp} = c^2 a_{pp} + 2cs a_{pq} + s^2 a_{qq} </math>
<math>a'_{pq} = sc(a_{qq} - a_{pp}) + (c^2-s^2) a_{pq}</math>
<math>a'_{qq} = s^2 a_{pp} -2cs a_{pq} + c^2 a_{qq}</math>
Здесь штрих обозначает элемент возникающий после вращения. Выберем коэффициенты <math>c</math> и <math>s</math> так, чтобы обнулить недиагональный элемент и сохранить связь <math>c</math> и <math>s</math> с <math>\cos\phi</math> и <math>\sin\phi</math>
Тогда: <math>\phi = 1/2 \tan ^{-1} (2a_{pq}/(a_{pp} - a_{qq}))</math>
<math>c = \cos\phi</math>
<math>s = \sin\phi</math>
Такое вращение применяют последовательно, чтобы обнулить все элементы первой строки, кроме двух первых. То есть (1,2), (1,3), (1,4)...(1,n) Потом ко-второй строке (2,3),(2, 4)...(2,n)
Код на C++:
for (unsigned int i=0; i<N-1; ++i)
{
for (unsigned int j=i+2; j<N; ++j)
{
t = 2*matr[i][j]/(matr[i][i] - matr[j][j]);
phi = 0.5 * atan(t);
c = cos(phi);
s = sin(phi);
bii = c*c*matr[i][i] + 2*c*s*matr[i][j] + s*s*matr[j][j];
bij = s*c*(matr[j][j] - matr[i][i]) + matr[i][j] * (c*c - s*s);
bjj = s*s*matr[i][i] + c*c*matr[j][j] - 2*c*s*matr[i][j];
bji = bij;
matr[i][i] = bii;
matr[i][j] = bij;
matr[j][i] = bji;
matr[j][j] = bjj;
}
}
Примечания
