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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Матрица Гивенса[править | править исходный текст]

Поворот Гивенса вектора на плоскости определяется матрицей линейного оператора:

G(\theta) = 
       \begin{bmatrix}  \cos \theta  \ -\sin \theta  \\
                        \sin \theta  \ \cos \theta \\
       \end{bmatrix}

Поэтому для некоторого вектора V = \begin{bmatrix} x \\ y\end{bmatrix}:
G(\theta) V = \begin{bmatrix} x \cos \theta -y \sin \theta \\ x \sin \theta + y \cos \theta \end{bmatrix}

К примеру, для \theta=\pi:
G(\theta) V = \begin{bmatrix} -x\\ -y \end{bmatrix}

Использование матриц Гивенса для трёхдиагонализации[править | править исходный текст]

Пусть хотим привести к трёхдиагональному виду симметричную матрицу: A = 
       \begin{bmatrix}  a_{1\, 1}  & \cdots    &  a_{1\,p}  & \cdots  & a_{1\,q} & \cdots & a_{1\, n}  \\
                        \vdots     &           &  \vdots    &         & \vdots  &         & \vdots    \\
                        a_{p\, 1}  & \cdots    &  a_{p\,p}  & \cdots & a_{p,q} & \cdots   & a{p\,n}\\
                         \vdots     &     &  \vdots   &   & \vdots  &   & \vdots  \\
                        a_{q\, 1}  & \cdots    &  a_{q\,p}  & \cdots & a_{q,q} & \cdots & a_{q\, n}  \\
                        \vdots     &           &  \vdots    &         & \vdots  &         & \vdots    \\
                        a_{n\, 1}  & \cdots    &  \cdots   & \cdots  & \cdots & \cdots & a_{n\, n}
       \end{bmatrix}

Где  a_{p\,q} =  a_{q\,p} . Тогда домножим её на матрицу вращения Гивенса:  G'_{p\,q}(\theta)AG_{p\,q}(\theta) . G' - транспонированная матрица. При этом изменятся только элементы  a_{p\,p} ,   a_{p\,q} и  a_{q\,q}

 a'_{p\, p} = c^2 a_{p\, p} +2csa_{p\,q}+s^2a_{q\,q}

 a'_{p\, q} = sc( a_{q\, q} - a_{p\, p}) + a_{p\,q} (c^2-s^2)

 a'_{q\, q} = s^2 a_{p\, p} -2csa_{p\,q}+c^2a_{q\,q}

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

Тогда:  \phi = 1/2 \tan ^{-1} (2a_{p\, q}/(a_{p\, p} - a_{q\,q}))

 c = \cos\phi

 s = \sin\phi

Такое вращение применяют последовательно, чтобы обнулить все элементы первой строки, кроме двух первых. То есть (1,2), (1,3), (1,4)...(1,n) Потом ко-второй строке (2,3),(2, 4)...(2,n)

Код на C++:

     for (int i=0; i<N-1; i++)
               for (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;
       }