Меню Главная Случайная статья Настройки Поворот Гивенса Материал из https://ru.wikipedia.org Поворот Гивенса — линейный оператор поворота вектора на некоторый заданный угол. Матрица Гивенса ${\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}$ Это свойство используется в методе диагонализации Якоби. Содержание 1 Трёхдиагонализация 2 QR-разложение 3 Примечания 4 Литература Трёхдиагонализация Последовательно вращая (${\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.