Поворот Гивенса - NiNa.Az

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

Матрица Гивенса ${\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}}$) в плоскости ${\displaystyle (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}}$) плоскости ${\displaystyle (2,3)}$, ${\displaystyle (2,4)}$, … , ${\displaystyle (2,n)}$ (при этом зануляя элементы ${\displaystyle a_{31},a_{41},...,a_{n1}}$), затем последовательно вращая плоскости ${\displaystyle (3,4)}$, ${\displaystyle (3,5)}$, … , ${\displaystyle (3,n)}$ (при этом зануляя элементы ${\displaystyle a_{42},a_{52},...,a_{n2}}$) и так далее, можно привести эрмитову (симметричную) матрицу к трёхдиагональной форме, а произвольную матрицу к хессенберговой форме.

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

QR-разложение

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

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

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

Примечания

Литература

• Тыртышников Е. Е. Методы численного анализа. — М., 2006. — С. 73—74.
• 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.
• 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.</ref>