Rotação de Givens

Em álgebra linear numérica, uma rotação de Givens é uma rotação no plano gerado por dois eixos de coordenadas. As rotações de Givens foram nomeadas em homenagem à Wallace Givens, que apresentou a técnica aos analistas numéricos na década de 1950, enquanto trabalhava no Argonne National Laboratory.

Representação matricial

Uma rotação de Givens é representada por uma matriz da forma

$G(i,j,\theta )={\begin{bmatrix}1&\cdots &0&\cdots &0&\cdots &0\\\vdots &\ddots &\vdots &&\vdots &&\vdots \\0&\cdots &c&\cdots &-s&\cdots &0\\\vdots &&\vdots &\ddots &\vdots &&\vdots \\0&\cdots &s&\cdots &c&\cdots &0\\\vdots &&\vdots &&\vdots &\ddots &\vdots \\0&\cdots &0&\cdots &0&\cdots &1\end{bmatrix}}$

onde $c = cos θ$ e $s = sen θ$ aparecem nas interseções das $i$ -ésima e $j$ -ésima linhas e colunas. Isto é, os elementos não-nulos da matriz de Givens são dados por: ${\begin{aligned}g_{k\,k}&{}=1\qquad {\text{para}}\ k\neq i,\,j\\g_{i\,i}&{}=c\\g_{j\,j}&{}=c\\g_{j\,i}&{}=-s\\g_{i\,j}&{}=s\qquad {\text{para}}\ i>j\end{aligned}}$ Note que o sinal dos senos muda quando $j > i$ .

O produto $G (i, j, θ) x$ representa a rotação no sentido anti-horário do vector $x$ no plano $(i, j)$ de $θ$ radianos, por isso o nome de rotação de Givens.

O principal uso das rotações de Givens na álgebra linear numérica é para introduzir zeros em vetores e matrizes. Esse efeito pode, por exemplo, ser usado no cálculo da decomposição QR de uma matriz. Uma vantagem sobre as transformações de Householder é que elas podem ser paralelizadas facilmente, e outra é que frequentemente, para matrizes bastante esparsas elas exigem uma quantidade pequena de operações.

Referências

Anderson, Edward (2000), Discontinuous Plane Rotations and the Symmetric Eigenvalue Problem . LAPACK Working Note 150, University of Tennessee, UT-CS-00-454, December 4, 2000.
D. Bindel, J. Demmel, W. Kahan, O. Marques. (2001) On Computing Givens rotations reliably and efficiently. LAPACK Working Note 148, University of Tennessee, UT-CS-00-449, January 31, 2001.
Cybenko, George (Março–Abril 2001), «Reducing Quantum Computations to Elementary Unitary Operations» (PDF), Computing in Science and Engineering, 3 (2): 27–32, doi:10.1109/5992.908999
Golub, Gene H.; Van Loan, Charles F. (1996), Matrix Computations, ISBN 978-0-8018-5414-9 3rd ed. , Johns Hopkins .
Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), «Section 11.3.1. Givens Method», Numerical Recipes: The Art of Scientific Computing, ISBN 978-0-521-88068-8 3rd ed. , New York: Cambridge University Press