Поворот Гивенса — в линейной алгебре линейный оператор поворота вектора на некоторый заданный угол .
Матрица Гивенса
G
k
l
{\displaystyle G_{kl}}
имеет следующий вид:
G
k
l
=
[
1
⋯
0
⋯
0
⋯
0
⋮
⋱
⋮
⋮
⋮
0
⋯
cos
ϕ
⋯
−
sin
ϕ
⋯
0
⋮
⋮
⋱
⋮
⋮
0
⋯
sin
ϕ
⋯
cos
ϕ
⋯
0
⋮
⋮
⋮
⋱
⋮
0
⋯
0
⋯
0
⋯
1
]
{\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}}}
Данная матрица отличается от единичной матрицы только подматрицей
M
(
ϕ
)
=
[
cos
ϕ
−
sin
ϕ
sin
ϕ
cos
ϕ
]
{\displaystyle M(\phi )={\begin{bmatrix}\cos {\phi }&-\sin {\phi }\\\sin {\phi }&\cos {\phi }\end{bmatrix}}}
расположенной на строках и столбцах с номерами
k
{\displaystyle k}
и
l
{\displaystyle l}
. Является ортогональной.
Если дан вектор
a
=
[
a
1
…
a
n
]
T
∈
R
n
{\displaystyle a={\begin{bmatrix}a_{1}&\ldots &a_{n}\end{bmatrix}}^{T}\in \mathbb {R} ^{n}}
,
s
=
a
k
2
+
a
l
2
≠
0
{\displaystyle s={\sqrt {a_{k}^{2}+a_{l}^{2}}}\neq 0}
, то выбрав
cos
ϕ
=
a
k
a
k
2
+
a
l
2
{\displaystyle \cos {\phi }={\frac {a_{k}}{\sqrt {a_{k}^{2}+a_{l}^{2}}}}}
sin
ϕ
=
−
a
l
a
k
2
+
a
l
2
{\displaystyle \sin {\phi }={\frac {-a_{l}}{\sqrt {a_{k}^{2}+a_{l}^{2}}}}}
можно обнулить
l
{\displaystyle l}
-ую компоненту вектора
a
{\displaystyle a}
:
[
cos
ϕ
−
sin
ϕ
sin
ϕ
cos
ϕ
]
[
a
k
a
l
]
=
[
cos
ϕ
⋅
a
k
−
sin
ϕ
⋅
a
l
sin
ϕ
⋅
a
k
+
cos
ϕ
⋅
a
l
]
=
[
a
k
2
+
a
l
2
a
k
2
+
a
l
2
−
a
l
⋅
a
k
+
a
k
⋅
a
l
a
k
2
+
a
l
2
]
=
[
a
k
2
+
a
l
2
0
]
{\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-разложение матриц и приводить эрмитовы матрицы к диагональной форме, а матрицы общего вида к трёхдиагональной , треугольной или хессенберговской форме.
Использование матриц Гивенса для трёхдиагонализации [ править | править код ]
Пусть хотим привести к трёхдиагональному виду симметричную матрицу:
A
=
[
a
11
⋯
a
1
p
⋯
a
1
q
⋯
a
1
n
⋮
⋮
⋮
⋮
a
p
1
⋯
a
p
p
⋯
a
p
q
⋯
a
p
n
⋮
⋮
⋮
⋮
a
q
1
⋯
a
q
p
⋯
a
q
q
⋯
a
q
n
⋮
⋮
⋮
⋮
a
n
1
⋯
a
n
p
⋯
a
n
q
⋯
a
n
n
]
{\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}}}
Где
a
p
q
=
a
q
p
{\displaystyle a_{pq}=a_{qp}}
. Тогда домножим её на матрицу вращения Гивенса:
G
p
q
′
(
θ
)
A
G
p
q
(
θ
)
{\displaystyle G'_{pq}(\theta )AG_{pq}(\theta )}
.
G
{\displaystyle G}
— транспонированная матрица.
При этом изменятся только элементы
a
p
p
{\displaystyle a_{pp}}
,
a
p
q
{\displaystyle a_{pq}}
и
a
q
q
{\displaystyle a_{qq}}
a
p
p
′
=
c
2
a
p
p
+
2
c
s
a
p
q
+
s
2
a
q
q
{\displaystyle a'_{pp}=c^{2}a_{pp}+2csa_{pq}+s^{2}a_{qq}}
a
p
q
′
=
s
c
(
a
q
q
−
a
p
p
)
+
(
c
2
−
s
2
)
a
p
q
{\displaystyle a'_{pq}=sc(a_{qq}-a_{pp})+(c^{2}-s^{2})a_{pq}}
a
q
q
′
=
s
2
a
p
p
−
2
c
s
a
p
q
+
c
2
a
q
q
{\displaystyle a'_{qq}=s^{2}a_{pp}-2csa_{pq}+c^{2}a_{qq}}
Здесь штрих обозначает элемент возникающий после вращения. Выберем коэффициенты
c
{\displaystyle c}
и
s
{\displaystyle s}
так, чтобы обнулить недиагональный
элемент и сохранить связь
c
{\displaystyle c}
и
s
{\displaystyle s}
с
cos
ϕ
{\displaystyle \cos \phi }
и
sin
ϕ
{\displaystyle \sin \phi }
Тогда:
ϕ
=
1
/
2
tan
−
1
(
2
a
p
q
/
(
a
p
p
−
a
q
q
)
)
{\displaystyle \phi =1/2\tan ^{-1}(2a_{pq}/(a_{pp}-a_{qq}))}
c
=
cos
ϕ
{\displaystyle c=\cos \phi }
s
=
sin
ϕ
{\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 ;
}
}
↑ Тыртышников Е. Е. Методы численного анализа. — М. , 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.