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

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

Матрица Гивенса[1][2][3]

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

${\displaystyle 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}}}$

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

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

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

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

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

можно обнулить ${\displaystyle l}$-ую компоненту вектора ${\displaystyle a}$:$${\displaystyle {\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-разложение матриц и приводить эрмитовы матрицы к диагональной форме, а матрицы общего вида к трёхдиагональной, треугольной или хессенберговской форме.

Свойства

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

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

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

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

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

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

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

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

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

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

Примечания

1. Тыртышников Е. Е. Методы численного анализа. — М., 2006. — С. 73-74.
2. Björck, Åke, 1934-. Numerical methods for least squares problems. — Philadelphia: SIAM, 1996. — С. 121-123. — xvii, 408 pages с. — ISBN 0-89871-360-9, 978-0-89871-360-2.
3. Demmel, James W. Applied numerical linear algebra. — Philadelphia: Society for Industrial and Applied Mathematics, 1997. — С. 53-56. — xi, 419 pages с. — ISBN 0-89871-389-7, 978-0-89871-389-3, 0-89871-361-7, 978-0-89871-361-9.