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

Поворот Гивенса — в линейной алгебре ортогональное преобразование (линейный оператор), представляющее собой поворот двумерного подпространства в многомерном пространстве на заданный угол. Оно часто используется для зануления отдельных элементов матриц при численных вычислениях.

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

Матрица Гивенса $G_{kl}$ представляет собой ортогональную матрицу размера $n\times n$, изменяющую только два столбца (или строки) с номерами $k$ и $l$. Остальные элементы остаются такими же, как в единичной матрице.

Матрица имеет следующий вид:

$G_{kl}=\left[\begin{array}{ccccccc}1& \cdots & 0& \cdots & 0& \cdots & 0\\ ⋮& \ddots & ⋮& & ⋮& & ⋮\\ 0& \cdots & \cos \varphi & \cdots & -\sin \varphi & \cdots & 0\\ ⋮& & ⋮& \ddots & ⋮& & ⋮\\ 0& \cdots & \sin \varphi & \cdots & \cos \varphi & \cdots & 0\\ ⋮& & ⋮& & ⋮& \ddots & ⋮\\ 0& \cdots & 0& \cdots & 0& \cdots & 1\end{array}\right]$

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

$M(\varphi )=\left[\begin{array}{cc}\cos \varphi & -\sin \varphi \\ \sin \varphi & \cos \varphi \end{array}\right]$

расположенной на строках и столбцах с номерами $k$ и $l$. Матрица Гивенса является ортогональной, то есть $G_{kl}^T{G}_{kl}=I$, где $I$ — единичная матрица.

Определение угла поворота

Для зануления элемента $a_l$ вектора $a={\left[\begin{array}{ccc}{a}_1& \dots & a_n\end{array}\right]}^T\in {ℝ}^n$ выбирают:

$$\cos \varphi =\frac{a_k}{\sqrt{a_k^2+a_l^2}}$$ $$\sin \varphi =\frac{-a_l}{\sqrt{a_k^2+a_l^2}}$$

Это позволяет обнулить $l$-ую компоненту вектора $a$:

$$\left[\begin{array}{cc}\cos \varphi & -\sin \varphi \\ \sin \varphi & \cos \varphi \end{array}\right]\left[\begin{array}{c}{a}_k\\ a_l\end{array}\right]=\left[\begin{array}{c}\cos \varphi \cdot a_k-\sin \varphi \cdot a_l\\ \sin \varphi \cdot a_k+\cos \varphi \cdot a_l\end{array}\right]=\left[\begin{array}{c}\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{array}\right]=\left[\begin{array}{c}\sqrt{a_k^2+a_l^2}\\ 0\end{array}\right]$$

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

Метод Гивенса позволяет последовательно занулять элементы под главной диагональю, приводя матрицу $A$ к верхнетреугольному виду. Это делает его удобным для вычисления QR-разложения, особенно в случае разреженных матриц. Основные шаги метода включают:

1. **Выбор элемента** $(i,j)$, который нужно занулить. 2. **Определение коэффициентов вращения** (косинус и синус угла) из соотношений:

  $$c=\frac{a_{jj}}{\sqrt{a_{jj}^2+a_{ij}^2}}$$ $$s=\frac{a_{ij}}{\sqrt{a_{jj}^2+a_{ij}^2}}$$  

3. **Построение матрицы Гивенса** $G$, которая выполняет вращение так, чтобы элемент $a_{ij}$ обнулился:

  $$G=\left[\begin{array}{ccccc}1& & & & \\ & \ddots & & & \\ & & c& -s& \\ & & s& c& \\ & & & & \ddots & 1\end{array}\right]$$  

4. **Умножение матрицы** $A$ на $G$ слева, что приводит к занулению выбранного элемента:

  $$A^{\prime }=GA$$

5. **Повторение процесса**, пока матрица не примет верхнетреугольный вид.

Метод Гивенса особенно полезен для разреженных матриц, так как он позволяет избирательно занулять элементы, в отличие от метода Хаусхолдера, который лучше подходит для масштабных преобразований.Шаблон:Sfn

Использование в методе Якоби

В методе Якоби для нахождения собственных значений симметричных матриц поворотами Гивенса устраняются внедиагональные элементы. При последовательном применении таких преобразований сумма квадратов внедиагональных элементов уменьшается, что способствует диагонализации.

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

Метод Гивенса применяется для сведения симметричных матриц к трёхдиагональному виду, что упрощает дальнейшие вычисления собственных значений. Последовательно вращая плоскости (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-разложения. Основные различия между ними:

Метод Гивенса: 
 - Предпочтителен для разреженных матриц, так как позволяет избирательно занулять элементы.
 - Обеспечивает более точные результаты для матриц с малыми элементами.
Метод Хаусхолдера:
 - Более эффективен для полных матриц, так как требует меньше вычислительных операций.
 - Часто используется для масштабных преобразований.

Выбор метода зависит от структуры матрицы и требуемой точности вычислений.Шаблон:Sfn

Литература

• В. В. Воеводин, Ю. А. Кузнецов. Матрицы и вычисления. — М.: Наука, 1984.
• Шаблон:Книга
• Самарский А. А., Гулин А. В. Численные методы. — М.: Наука, 1989.
• Шаблон:Статья