Поворот Гивенса (Hkfkjkm Infyuvg)

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

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

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

$G_{kl}={\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}}$

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

$M(\phi )={\begin{bmatrix}\cos {\phi }&-\sin {\phi }\\\sin {\phi }&\cos {\phi }\end{bmatrix}}$

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

Если дан вектор $a={\begin{bmatrix}a_{1}&\ldots &a_{n}\end{bmatrix}}^{T}\in \mathbb {R} ^{n}$, $s={\sqrt {a_{k}^{2}+a_{l}^{2}}}\neq 0$, то выбрав

$$\cos {\phi }={\frac {a_{k}}{\sqrt {a_{k}^{2}+a_{l}^{2}}}}$$ $$\sin {\phi }={\frac {-a_{l}}{\sqrt {a_{k}^{2}+a_{l}^{2}}}}$$

можно обнулить $l$-ую компоненту вектора $a$:$${\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}}$$

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

Свойства

При повороте Гивенса для матрицы ($G_{kl}AG_{kl}^{T}$) в плоскости (p,q) сохраняется сумма квадратов внедиагональных элементов за исключением элементов $a_{pq},a_{qp}$

$(\sum _{i\neq j}|a_{i,j}|^{2})-|a_{pq}|^{2}-|a_{qp}|^{2}=const$

Это свойство используется в методе диагонализации Якоби.

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

Последовательно вращая ($G_{kl}AG_{kl}^{T}$) плоскости (2, 3), (2, 4), ... , (2, n) (при этом зануляя элементы $a_{31},a_{41},...,a_{n1}$), затем последовательно вращая плоскости (3, 4), (3, 5), ... , (3, n) (при этом зануляя элементы $a_{42},a_{52},...,a_{n2}$) и т.д. можно привести эрмитову (симметричную) матрицу к трёхдиагональной форме, а произвольную матрицу к хессенберговой форме.

Также того же самого можно добиться при помощи преобразований Хаусхолдера.

Использование матриц Гивенса для QR-разложения

Последовательно вращая ($G_{kl}A$) столбцы матрицы в плоскостях (1, 2), (1, 3), ... , (1, n) (при этом зануляя элементы $a_{21},a_{31},...,a_{n1}$), затем в плоскостях (2, 3), (2, 4), ... , (2, n) (при этом зануляя элементы $a_{32},a_{42},...,a_{n2}$) и т.д. можно привести матрицу к верхнетреугольному виду.

Также того же самого можно добиться при помощи преобразований Хаусхолдера или метода ортогонализации Грама-Шмидта.

Сложность QR-разложения хессенберговой матрицы $O(n^{2})$ (при этом $RQ$ снова будет хессенберговой), в то время как сложность QR-разложения произвольной матрицы $O(n^{3})$.