En álgebra lineal , una transformación de jefe de hogar (también conocida como reflexión de jefe de hogar o reflector elemental ) es una transformación lineal que describe una reflexión sobre un plano o hiperplano que contiene el origen. La transformación Householder se utilizó en un artículo de 1958 de Alston Scott Householder . [1]
Su análogo sobre los espacios de productos internos generales es el operador Householder .
Definición
Transformación
El hiperplano de reflexión se puede definir mediante un vector unitario (un vector con longitud ) que es ortogonal al hiperplano. Ese es su vector normal. El reflejo de un punto sobre este hiperplano es la transformación lineal :
dónde se da como un vector unitario de columna con transposición hermitiana .
Matriz de cabezas de familia
La matriz construida a partir de esta transformación se puede expresar en términos de un producto externo como:
se conoce como la matriz de jefes de hogar , dondees la matriz de identidad
Propiedades
La matriz de jefe de hogar tiene las siguientes propiedades:
- es hermitiano :,
- es unitario :,
- de ahí que sea involutivo :.
- Una matriz de jefe de hogar tiene valores propios . Para ver esto, observe que si es ortogonal al vector que se utilizó para crear el reflector, luego , es decir, es un valor propio de multiplicidad , puesto que hay vectores independientes ortogonales a . Además, tenga en cuenta, y entonces es un valor propio con multiplicidad .
- El determinante de un reflector Householder es, dado que el determinante de una matriz es el producto de sus valores propios, en este caso uno de los cuales es siendo el resto (como en el punto anterior).
Aplicaciones
Óptica geométrica
En óptica geométrica, la reflexión especular se puede expresar en términos de la matriz Householder (ver Reflexión especular § Formulación vectorial ).
Álgebra lineal numérica
Las transformaciones de cabezas de familia se utilizan ampliamente en álgebra lineal numérica , por ejemplo, para aniquilar las entradas debajo de la diagonal principal de una matriz, [2] para realizar descomposiciones QR y en el primer paso del algoritmo QR . También se utilizan ampliamente para transformar a una forma de Hessenberg . Para matrices simétricas o hermitianas , la simetría se puede conservar, lo que da como resultado la tridiagonalización . [3]
Descomposición QR
Las reflexiones de los dueños de casa se pueden usar para calcular las descomposiciones QR reflejando primero una columna de una matriz en un múltiplo de un vector base estándar, calculando la matriz de transformación, multiplicándola con la matriz original y luego volviendo a la menores de ese producto.
Tridiagonalización
Este procedimiento se presenta en Análisis numérico de Burden and Faires. [4] En el primer paso, para formar la matriz de jefes de hogar en cada paso, debemos determinar y , que son:
De y , construir vector :
dónde , , y
- para cada
Luego calcule:
Habiendo encontrado y calculado el proceso se repite para como sigue:
Continuando de esta manera, se forma la matriz tridiagonal y simétrica.
Ejemplos de
En este ejemplo, también de Burden and Faires, [4] la matriz dada se transforma en la matriz tridiagonal similar A 3 utilizando el método Householder.
Siguiendo esos pasos en el método Householder, tenemos:
La primera matriz de jefes de hogar:
Usó formar
Como podemos ver, el resultado final es una matriz simétrica tridiagonal similar a la original. El proceso finaliza después de dos pasos.
Relación computacional y teórica con otras transformaciones unitarias
La transformación Householder es una reflexión sobre un hiperplano con un vector normal unitario , como se dijo anteriormente. Un-por- transformación unitaria satisface . Tomando el determinante (-ésima potencia de la media geométrica) y la traza (proporcional a la media aritmética) de una matriz unitaria revela que sus valores propios tienen módulo unitario. Esto se puede ver de forma directa y rápida:
Dado que las medias aritméticas y geométricas son iguales si las variables son constantes (ver desigualdad de medias aritméticas y geométricas ), establecemos la afirmación de módulo unitario.
Para el caso de matrices unitarias de valor real obtenemos matrices ortogonales ,. Se deduce con bastante facilidad (ver matriz ortogonal ) que cualquier matriz ortogonal se puede descomponer en un producto de 2 por 2 rotaciones, llamadas Rotaciones de Givens y Reflexiones de los jefes de hogar. Esto es atractivo intuitivamente ya que la multiplicación de un vector por una matriz ortogonal preserva la longitud de ese vector, y las rotaciones y reflexiones agotan el conjunto de operaciones geométricas (de valor real) que hacen invariante la longitud de un vector.
Se demostró que la transformación Householder tiene una relación uno a uno con la descomposición de clases laterales canónicas de matrices unitarias definidas en la teoría de grupos, que se puede utilizar para parametrizar operadores unitarios de una manera muy eficiente. [5]
Finalmente, observamos que una sola transformada Householder, a diferencia de una transformada Givens solitaria, puede actuar en todas las columnas de una matriz y, como tal, exhibe el menor costo computacional para la descomposición QR y la tridiagonalización. El castigo por esta "optimización computacional" es, por supuesto, que las operaciones de los jefes de hogar no pueden paralelizarse de manera tan profunda o eficiente. Como tal, se prefiere Householder para matrices densas en máquinas secuenciales, mientras que Givens se prefiere en matrices dispersas y / o máquinas paralelas.
Referencias
- ^ Jefe de hogar, AS (1958). "Triangularización unitaria de una matriz asimétrica" (PDF) . Revista de la ACM . 5 (4): 339–342. doi : 10.1145 / 320941.320947 . Señor 0111128 .
- ^ Taboga, Marco. "Matriz de amo de casa, Conferencias sobre álgebra matricial" .
- ^ Schabauer, Hannes; Pacher, Christoph; Sunderland, Andrew G .; Gansterer, Wilfried N. (1 de mayo de 2010). "Hacia un solucionador paralelo para problemas de valores propios simétricos complejos generalizados" . Procedia Informática . 1 (1): 437–445. doi : 10.1016 / j.procs.2010.04.047 .
- ^ a b Burden, Richard; Faires, Douglas (10 de diciembre de 2004). Análisis numérico (8ª ed.). Thomson Brooks / Cole. ISBN 9780534392000.
- ^ Renan Cabrera; Traci Strohecker; Herschel Rabitz (2010). "La descomposición de clases laterales canónicas de matrices unitarias a través de transformaciones de Householder". Revista de Física Matemática . 51 (8): 082101. arXiv : 1008.2477 . Código bibliográfico : 2010JMP .... 51h2101C . doi : 10.1063 / 1.3466798 .
- LaBudde, CD (1963). "La reducción de una matriz cuadrada real arbitraria a forma tridiagonal mediante transformaciones de similitud". Matemáticas de la Computación . Sociedad Matemática Estadounidense. 17 (84): 433–437. doi : 10.2307 / 2004005 . JSTOR 2004005 . Señor 0156455 .
- Morrison, DD (1960). "Observaciones sobre la triangularización unitaria de una matriz asimétrica". Revista de la ACM . 7 (2): 185–186. doi : 10.1145 / 321021.321030 . Señor 0114291 .
- Cipra, Barry A. (2000). "Lo mejor del siglo XX: los editores nombran los 10 algoritmos principales" . 33 (4): 1. Cite journal requiere
|journal=
( ayuda ) (Aquí, la Transformación de los jefes de hogar se cita como uno de los 10 mejores algoritmos de este siglo) - Presione, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Sección 11.3.2. Método de jefe de hogar" . Recetas numéricas: el arte de la informática científica (3ª ed.). Nueva York: Cambridge University Press. ISBN 978-0-521-88068-8.