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

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

Матрица Гивенса^[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 A={\begin{bmatrix}a_{11}&\cdots &a_{1p}&\cdots &a_{1q}&\cdots &a_{1n}\\\vdots &&\vdots &&\vdots &&\vdots \\a_{p1}&\cdots &a_{pp}&\cdots &a_{pq}&\cdots &a_{pn}\\\vdots &&\vdots &&\vdots &&\vdots \\a_{q1}&\cdots &a_{qp}&\cdots &a_{qq}&\cdots &a_{qn}\\\vdots &&\vdots &&\vdots &&\vdots \\a_{n1}&\cdots &a_{np}&\cdots &a_{nq}&\cdots &a_{nn}\end{bmatrix}}}$

Где ${\displaystyle a_{pq}=a_{qp}}$. Тогда домножим её на матрицу вращения Гивенса: ${\displaystyle G'_{pq}(\theta )AG_{pq}(\theta )}$. ${\displaystyle G}$ — транспонированная матрица. При этом изменятся только элементы ${\displaystyle a_{pp}}$, ${\displaystyle a_{pq}}$ и ${\displaystyle a_{qq}}$

${\displaystyle a'_{pp}=c^{2}a_{pp}+2csa_{pq}+s^{2}a_{qq}}$

${\displaystyle a'_{pq}=sc(a_{qq}-a_{pp})+(c^{2}-s^{2})a_{pq}}$

${\displaystyle a'_{qq}=s^{2}a_{pp}-2csa_{pq}+c^{2}a_{qq}}$

Здесь штрих обозначает элемент возникающий после вращения. Выберем коэффициенты ${\displaystyle c}$ и ${\displaystyle s}$ так, чтобы обнулить недиагональный элемент и сохранить связь ${\displaystyle c}$ и ${\displaystyle s}$ с ${\displaystyle \cos \phi }$ и ${\displaystyle \sin \phi }$

Тогда: ${\displaystyle \phi =1/2\tan ^{-1}(2a_{pq}/(a_{pp}-a_{qq}))}$

${\displaystyle c=\cos \phi }$

${\displaystyle s=\sin \phi }$

Такое вращение применяют последовательно, чтобы обнулить все элементы первой строки, кроме двух первых. То есть (1,2), (1,3), (1,4)...(1,n) Потом ко-второй строке (2,3),(2, 4)...(2,n)

Код на C++:

for (unsigned int i=0; i<N-1; ++i) 
    {
    for (unsigned int j=i+2; j<N; ++j)               
        {
            t = 2*matr[i][j]/(matr[i][i] - matr[j][j]);
            phi = 0.5 * atan(t);
            c = cos(phi);
            s = sin(phi);
 
            bii = c*c*matr[i][i] + 2*c*s*matr[i][j] + s*s*matr[j][j];
            bij = s*c*(matr[j][j] - matr[i][i]) + matr[i][j] * (c*c - s*s);
            bjj = s*s*matr[i][i] + c*c*matr[j][j] - 2*c*s*matr[i][j];
            bji = bij;
 
            matr[i][i] = bii;
            matr[i][j] = bij;
            matr[j][i] = bji;
            matr[j][j] = bjj;
        }
    }

Примечания

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.

Эта страница в последний раз была отредактирована 27 ноября 2022 в 07:40.