En álgebra lineal numérica , una rotación de Givens es una rotación en el plano atravesado por dos ejes de coordenadas. Las rotaciones de Givens llevan el nombre de Wallace Givens , quien las presentó a los analistas numéricos en la década de 1950 mientras trabajaba en el Laboratorio Nacional de Argonne .
Representación matricial
Una rotación de Givens está representada por una matriz de la forma
donde c = cos θ y s = sin θ aparecen en las intersecciones i ésima y j ésima filas y columnas. Es decir, para i > j fijo , los elementos distintos de cero de la matriz Givens están dados por:
El producto G ( i , j , θ ) x representa una rotación en sentido antihorario del vector x en el plano ( i , j ) de θ radianes, de ahí el nombre de rotación de Givens.
El uso principal de las rotaciones de Givens en álgebra lineal numérica es introducir ceros [ aclaración necesaria ] en vectores o matrices. Este efecto se puede emplear, por ejemplo, para calcular la descomposición QR de una matriz. Una ventaja sobre las transformaciones de Householder es que pueden ser fácilmente paralelizadas y otra es que a menudo para matrices muy dispersas tienen un recuento de operaciones más bajo.
Cálculo estable
Cuando una matriz de rotación de Givens, G ( i , j , θ ) , multiplica otra matriz, A , de la izquierda, G A , solo las filas i y j de A se ven afectadas. Por lo tanto, restringimos la atención al siguiente problema en sentido contrario a las agujas del reloj. Dados a y b , encuentre c = cos θ y s = sin θ tal que
dónde es la longitud del vector . El cálculo explícito de θ rara vez es necesario o deseable. En lugar de ello buscamos directamente c y s . Una solución obvia sería
Sin embargo, el cálculo de r puede desbordarse o subdesbordarse. Una formulación alternativa que evita este problema ( Golub & Van Loan 1996 , §5.1.8) se implementa como función hipot en muchos lenguajes de programación.
El siguiente código de Fortran es una implementación minimalista de la rotación Givens para números reales. Si los valores de entrada 'a' o 'b' son frecuentemente cero, el código puede optimizarse para manejar estos casos como se presenta aquí .
subrutina givens_rotation ( a , b , c , s , r )real a , b , c , s , r real h , dsi ( b . ne . 0.0 ) entonces h = hypot ( a , b ) d = 1.0 / h c = abs ( a ) * d s = sign ( d , a ) * b r = sign ( 1.0 , a ) * h de lo contrario c = 1.0 s = 0.0 r = un final sivolver al final
Además, como descubrió Edward Anderson al mejorar LAPACK , una consideración numérica que antes se pasaba por alto es la continuidad. Para lograr esto, necesitamos que r sea positivo. [2] El siguiente código MATLAB / GNU Octave ilustra el algoritmo.
función [c, s, r] = givens_rotation ( a, b )si b == 0 ;c = signo ( a );si ( c == 0 );c = 1,0 ; % A diferencia de otros lenguajes, la función de signo de MatLab devuelve 0 en la entrada 0.terminar ;s = 0 ;r = abs ( a );elseif a == 0 ;c = 0 ;s = signo ( b );r = abs ( b );elseif abs ( a ) > abs ( b );t = b / a ;u = signo ( a ) * sqrt ( 1 + t * t );c = 1 / u ;s = c * t ;r = a * u ;demást = a / b ;u = signo ( b ) * sqrt ( 1 + t * t );s = 1 / u ;c = s * t ;r = b * u ;finalfinal
La función IEEE 754 copysign (x, y) proporciona una forma segura y económica de copiar el signo de y a x . Si no está disponible, | x | ⋅sgn ( y ) , usando las funciones abs y sgn , es una alternativa como se hizo anteriormente.
Triangularización
Dada la siguiente matriz 3 × 3 :
Realice dos iteraciones de la rotación de Givens (tenga en cuenta que el algoritmo de rotación de Givens utilizado aquí difiere ligeramente del anterior) para producir una matriz triangular superior para calcular la descomposición QR .
Para formar la matriz deseada, debemos poner a cero los elementos (2, 1) y (3, 2) . Primero seleccionamos el elemento (2, 1) a cero. Usando una matriz de rotación de:
Tenemos la siguiente multiplicación de matrices:
dónde
La conexión de estos valores para c y s y realizar la multiplicación de la matriz por encima de los rendimientos A 2 :
Ahora queremos poner a cero el elemento (3, 2) para finalizar el proceso. Usando la misma idea que antes, tenemos una matriz de rotación de:
Se nos presenta la siguiente multiplicación de matrices:
dónde
La conexión de estos valores de c y s y realizar las multiplicaciones nos da un 3 :
Esta nueva matriz A 3 es la matriz triangular superior necesaria para realizar una iteración de la descomposición QR . Q ahora se forma utilizando la transposición de las matrices de rotación de la siguiente manera:
Al realizar esta multiplicación de matrices se obtiene:
Esto completa dos iteraciones de Givens Rotation y ahora se puede calcular la descomposición QR .
Rotaciones de Givens en álgebras de Clifford
En las álgebras de Clifford y sus estructuras hijas, como las rotaciones del álgebra geométrica, se representan mediante bivectores . Las rotaciones dadas están representadas por el producto exterior de los vectores base. Dado cualquier par de vectores base Los bivectores de rotaciones dados son:
Cuando las rotaciones se realizan en el orden correcto, los valores de los ángulos de rotación del cuadro final serán iguales a los ángulos de Euler del cuadro final en la convención correspondiente. Por ejemplo, un operador transforma la base del espacio en un marco con ángulos de balanceo, cabeceo y guiñada en la convención de Tait-Bryan z - x - y (convención en la que la línea de nodos es perpendicular a los ejes z e Y , también denominada Y - X ′ - Z ″ ).
El significado de la composición de dos rotaciones de Givens g ∘ f es un operador que transforma vectores primero por f y luego por g , siendo f y g rotaciones alrededor de un eje de base del espacio. Esto es similar a la equivalencia de rotación extrínseca para los ángulos de Euler.
Tabla de rotaciones compuestas
La siguiente tabla muestra las tres rotaciones de Givens equivalentes a las diferentes convenciones de ángulos de Euler usando composición extrínseca (composición de rotaciones sobre los ejes base) de rotaciones activas y la regla de la mano derecha para el signo positivo de los ángulos.
La notación se ha simplificado de tal manera que c 1 significa cos θ 1 y s 2 significa sen θ 2 ) . Los subíndices de los ángulos son el orden en el que se aplican utilizando composición extrínseca (1 para rotación intrínseca, 2 para nutación, 3 para precesión)
Como las rotaciones se aplican justo en el orden opuesto de la tabla de rotaciones de ángulos de Euler , esta tabla es la misma pero intercambiando los índices 1 y 3 en los ángulos asociados con la entrada correspondiente. Una entrada como zxy significa aplicar primero la rotación y , luego x , y finalmente z , en los ejes base.
Todas las composiciones asumen la convención de la derecha para las matrices que se multiplican, dando los siguientes resultados.
^ ElLa matriz de rotación inmediatamente debajo no es una rotación de Givens. Lala matriz inmediatamente debajo respeta la regla de la mano derecha y es esta matriz habitual que se ve en Computer Graphics; sin embargo, una rotación de Givens es simplemente una matriz como se define en la sección Representación de la matriz anterior y no necesariamente respeta la regla de la mano derecha. La siguiente matriz es en realidad la rotación de Givens a través de un ángulo de -.
Referencias
^ Björck, Ake (1996). Métodos numéricos para problemas de mínimos cuadrados . Estados Unidos: SIAM. pag. 54. ISBN 9780898713602. Consultado el 16 de agosto de 2016 .
^Anderson, Edward (4 de diciembre de 2000). "Rotaciones de planos discontinuos y el problema de valores propios simétricos" (PDF) . Nota de trabajo LAPACK. Universidad de Tennessee en Knoxville y Laboratorio Nacional Oak Ridge . Consultado el 16 de agosto de 2016 .
Notas
Bindel, D .; Demmel, J .; Kahan, W .; Marques, O. (2000), On Computing Da rotaciones de manera confiable y eficiente. LAPACK Working Note 148, Universidad de Tennessee, UT-CS-00-449, 31 de enero de 2001.
Cybenko, George (marzo-abril de 2001), "Reducing Quantum Computations to Elementary Unitary Operations" (PDF) , Computación en ciencia e ingeniería , 3 (2): 27–32, doi : 10.1109 / 5992.908999
Golub, Gene H .; Van Loan, Charles F. (1996), Matrix Computations (3.a ed.), Johns Hopkins, ISBN 978-0-8018-5414-9.
Presione, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Sección 11.3.1. Método Givens" , Recetas numéricas: El arte de la informática científica (3ª ed.), Nueva York: Cambridge University Press, ISBN 978-0-521-88068-8