Поворот Гивенса

Поворот Гивенса — в линейной алгебре линейный оператор поворота вектора на некоторый заданный угол.

Матрица Гивенса

Матрица Гивенса $G_{kl}$ имеет следующий вид:

$G_{kl}=\left[\begin{array}{ccccccc}1& \cdots & 0& \cdots & 0& \cdots & 0\\ ⋮& \ddots & ⋮& & ⋮& & ⋮\\ 0& \cdots & \cos \varphi & \cdots & -\sin \varphi & \cdots & 0\\ ⋮& & ⋮& \ddots & ⋮& & ⋮\\ 0& \cdots & \sin \varphi & \cdots & \cos \varphi & \cdots & 0\\ ⋮& & ⋮& & ⋮& \ddots & ⋮\\ 0& \cdots & 0& \cdots & 0& \cdots & 1\end{array}\right]$

Данная матрица отличается от единичной матрицы только подматрицей

$M(\varphi )=\left[\begin{array}{cc}\cos \varphi & -\sin \varphi \\ \sin \varphi & \cos \varphi \end{array}\right]$

расположенной на строках и столбцах с номерами $k$ и $l$. Является ортогональной.

Если дан вектор $a={\left[\begin{array}{ccc}{a}_1& \dots & a_n\end{array}\right]}^T\in {\mathbb{ℝ}}^n$, $s=\sqrt{a_k^2+a_l^2}\ne 0$, то выбрав

$$\cos \varphi =\frac{a_k}{\sqrt{a_k^2+a_l^2}}$$ $$\sin \varphi =\frac{-a_l}{\sqrt{a_k^2+a_l^2}}$$

можно обнулить $l$-ую компоненту вектора $a$:$$\left[\begin{array}{cc}\cos \varphi & -\sin \varphi \\ \sin \varphi & \cos \varphi \end{array}\right]\left[\begin{array}{c}{a}_k\\ a_l\end{array}\right]=\left[\begin{array}{c}\cos \varphi \cdot a_k-\sin \varphi \cdot a_l\\ \sin \varphi \cdot a_k+\cos \varphi \cdot a_l\end{array}\right]=\left[\begin{array}{c}\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{array}\right]=\left[\begin{array}{c}\sqrt{a_k^2+a_l^2}\\ 0\end{array}\right]$$

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

Использование матриц Гивенса для трёхдиагонализации

Пусть хотим привести к трёхдиагональному виду симметричную матрицу: $A=\left[\begin{array}{ccccccc}{a}_{11}& \cdots & a_{1p}& \cdots & a_{1q}& \cdots & a_{1n}\\ ⋮& & ⋮& & ⋮& & ⋮\\ a_{p1}& \cdots & a_{pp}& \cdots & a_{pq}& \cdots & a_{pn}\\ ⋮& & ⋮& & ⋮& & ⋮\\ a_{q1}& \cdots & a_{qp}& \cdots & a_{qq}& \cdots & a_{qn}\\ ⋮& & ⋮& & ⋮& & ⋮\\ a_{n1}& \cdots & a_{np}& \cdots & a_{nq}& \cdots & a_{nn}\end{array}\right]$

Где $a_{pq}=a_{qp}$. Тогда домножим её на матрицу вращения Гивенса: $G{\text{'}}_{pq}(\theta )A{G}_{pq}(\theta )$. $G$ — транспонированная матрица. При этом изменятся только элементы $a_{pp}$, $a_{pq}$ и $a_{qq}$

$a{\text{'}}_{pp}=c^2{a}_{pp}+2cs{a}_{pq}+s^2{a}_{qq}$

$a{\text{'}}_{pq}=sc(a_{qq}-a_{pp})+(c^2-s^2)a_{pq}$

$a{\text{'}}_{qq}=s^2{a}_{pp}-2cs{a}_{pq}+c^2{a}_{qq}$

Здесь штрих обозначает элемент возникающий после вращения. Выберем коэффициенты $c$ и $s$ так, чтобы обнулить недиагональный элемент и сохранить связь $c$ и $s$ с $\cos \varphi$ и $\sin \varphi$

Тогда: $\varphi =1/2{\tan }^{-1}(2a_{pq}/(a_{pp}-a_{qq}))$

$c=\cos \varphi$

$s=\sin \varphi$

Такое вращение применяют последовательно, чтобы обнулить все элементы первой строки, кроме двух первых. То есть (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;
        }
    }