Transformación del jefe de familia

Concepto en álgebra lineal

En álgebra lineal , una transformación de Householder (también conocida como reflexión de Householder 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 de Householder fue utilizada en un artículo de 1958 por 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 por su vector normal , un vector unitario (un vector con longitud ) que es ortogonal al hiperplano. La reflexión de un punto sobre este hiperplano es la transformación lineal : ${\textstyle v}$ ${\textstyle 1}$ ${\textstyle x}$

${\displaystyle x-2\langle x,v\rangle v=x-2v\left(v^{*}x\right),}$

donde se da como un vector unitario de columna con transpuesta conjugada . ${\textstyle v}$ ${\textstyle v^{\textsf {*}}}$

Matriz de cabeza de familia

La matriz construida a partir de esta transformación se puede expresar en términos de un producto externo como:

${\displaystyle P=I-2vv^{*}}$

Se conoce como matriz de cabeza de familia , donde es la matriz de identidad . ${\textstyle I}$

Propiedades

La matriz de cabeza de familia tiene las siguientes propiedades:

• es hermitiano : , ${\textstyle P=P^{*}}$
• es unitario : , ${\textstyle P^{-1}=P^{*}}$
• por tanto es involutivo : . ${\textstyle P=P^{-1}}$
• Una matriz de cabeza de familia tiene valores propios . Para ver esto, observe que si es ortogonal al vector que se usó para crear el reflector, entonces , es decir, es un valor propio de la multiplicidad , ya que hay vectores independientes ortogonales a . Además, observe que también lo es un valor propio con multiplicidad . ${\textstyle \pm 1}$ ${\textstyle u}$ ${\textstyle v}$ ${\textstyle Pu=u}$ ${\textstyle 1}$ ${\textstyle n-1}$ ${\textstyle n-1}$ ${\textstyle v}$ ${\textstyle Pv=-v}$ ${\textstyle -1}$ ${\textstyle 1}$
• El determinante de un reflector de Householder es , ya que el determinante de una matriz es el producto de sus valores propios, en este caso uno de los cuales queda con el resto (como en el punto anterior). ${\textstyle -1}$ ${\textstyle -1}$ ${\textstyle 1}$

Aplicaciones

Óptica geométrica

En óptica geométrica, la reflexión especular se puede expresar en términos de la matriz de Householder (ver Reflexión especular § Formulación vectorial ).

Álgebra lineal numérica

Las transformaciones de los hogares son muy utilizadas 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 Hessenberg . Para matrices simétricas o hermitianas , la simetría se puede preservar, lo que resulta en tridiagonalización . ^[3]

descomposición QR

Las reflexiones de los hogares se pueden utilizar para calcular descomposiciones QR reflejando primero una columna de una matriz en un múltiplo de un vector de base estándar, calculando la matriz de transformación, multiplicándola por la matriz original y luego recurriendo a los menores de ese producto. Para lograr esto, se busca una matriz unitaria hermitiana Q que convierta un vector complejo x en un múltiplo complejo de un vector complejo e . Para la descomposición QR, e será un vector de coordenadas unitarias, digamos para la k-ésima coordenada. Una matriz compleja Q que tiene la forma Q = I - uu * con u * u = 2 tiene la propiedad deseada de ser unitaria hermitiana. Aquí * denota la transpuesta conjugada. Dado que los únicos dos vectores involucrados son x y e , el vector u debe tener la forma u = a x + b e , donde a y b son coeficientes complejos por determinar. Dado que un factor de fase general para u no importa, se puede elegir que el coeficiente a sea real positivo. Ahora Q x = x (1 – a ( u * x )) - e (b ( u * x )). Para que el coeficiente del vector x sea cero, los dos términos en u * x deben tener la misma fase dentro de un múltiplo de 180 grados, por lo que debemos tener arg(b) = arg( e * x ) dentro de un múltiplo de 180 grados. Existen dos soluciones según se elija un múltiplo par o impar de 180 grados. Entonces, para que el coeficiente complejo del vector x sea cero, se deben resolver dos ecuaciones lineales en los módulos de a y b. Las fases de a y b ya han sido determinadas. Supongamos que e es el k-ésimo vector de coordenadas unitario de modo que e * e = 1 y x _k = e * x y sea | x |= raíz cuadrada ( x * x ). Entonces a y b pueden expresarse simplemente como a =1/sqrt (| x | (| x |+ |x _k |)) y b = a | x | exp(i*arg(x _k )) o como a =1/sqrt (| x | (| x |- |x _k ${\textstyle (i,i)}$ |)) y b = - a | x | exp(i*arg(xk ₎ ). El multiplicador de e es -b/a para ambas soluciones. La primera solución es mejor porque el denominador no puede estar cerca de cero en comparación con | x |.

Tridiagonalización

Este procedimiento se presenta en Análisis Numérico de Burden y Faires. Utiliza una función ligeramente modificada con . ^[4] En el primer paso, para formar la matriz de Jefe de Hogar en cada paso necesitamos determinar y , que son: ${\displaystyle \operatorname {sgn} }$ ${\displaystyle \operatorname {sgn} (0)=1}$ ${\textstyle \alpha }$ ${\textstyle r}$

${\displaystyle {\begin{aligned}\alpha &=-\operatorname {sgn} \left(a_{21}\right){\sqrt {\sum _{j=2}^{n}a_{j1}^{2}}};\\r&={\sqrt {{\frac {1}{2}}\left(\alpha ^{2}-a_{21}\alpha \right)}};\end{aligned}}}$

Desde y , construye el vector : ${\textstyle \alpha }$ ${\textstyle r}$ ${\textstyle v}$

${\displaystyle v^{(1)}={\begin{bmatrix}v_{1}\\v_{2}\\\vdots \\v_{n}\end{bmatrix}},}$

dónde y ​ ${\textstyle v_{1}=0}$ ${\textstyle v_{2}={\frac {a_{21}-\alpha }{2r}}}$

${\displaystyle v_{k}={\frac {a_{k1}}{2r}}}$para cada ${\displaystyle k=3,4\ldots n}$

Luego calcula:

${\displaystyle {\begin{aligned}P^{1}&=I-2v^{(1)}\left(v^{(1)}\right)^{\textsf {T}}\\A^{(2)}&=P^{1}AP^{1}\end{aligned}}}$

Una vez encontrado y calculado, el proceso se repite de la siguiente manera: ${\textstyle P^{1}}$ ${\textstyle A^{(2)}}$ ${\textstyle k=2,3,\ldots ,n-2}$

${\displaystyle {\begin{aligned}\alpha &=-\operatorname {sgn} \left(a_{k+1,k}^{k}\right){\sqrt {\sum _{j=k+1}^{n}\left(a_{jk}^{k}\right)^{2}}}\\[2pt]r&={\sqrt {{\frac {1}{2}}\left(\alpha ^{2}-a_{k+1,k}^{k}\alpha \right)}}\\[2pt]v_{1}^{k}&=v_{2}^{k}=\cdots =v_{k}^{k}=0\\[2pt]v_{k+1}^{k}&={\frac {a_{k+1,k}^{k}-\alpha }{2r}}\\v_{j}^{k}&={\frac {a_{jk}^{k}}{2r}}{\text{ for }}j=k+2,\ k+3,\ \ldots ,\ n\\P^{k}&=I-2v^{(k)}\left(v^{(k)}\right)^{\textsf {T}}\\A^{(k+1)}&=P^{k}A^{(k)}P^{k}\end{aligned}}}$

Continuando de esta manera se forma la matriz tridiagonal y simétrica.

Ejemplos

En este ejemplo, también de Burden y Faires, ^[4] la matriz dada se transforma en la matriz tridiagonal similar A ₃ utilizando el método de Householder.

${\displaystyle \mathbf {A} ={\begin{bmatrix}4&1&-2&2\\1&2&0&1\\-2&0&3&-2\\2&1&-2&-1\end{bmatrix}},}$

Siguiendo esos pasos en el método del amo de casa, tenemos:

La primera matriz de cabeza de familia:

${\displaystyle {\begin{aligned}Q_{1}&={\begin{bmatrix}1&0&0&0\\0&-{\frac {1}{3}}&{\frac {2}{3}}&-{\frac {2}{3}}\\0&{\frac {2}{3}}&{\frac {2}{3}}&{\frac {1}{3}}\\0&-{\frac {2}{3}}&{\frac {1}{3}}&{\frac {2}{3}}\end{bmatrix}},\\A_{2}=Q_{1}AQ_{1}&={\begin{bmatrix}4&-3&0&0\\-3&{\frac {10}{3}}&1&{\frac {4}{3}}\\0&1&{\frac {5}{3}}&-{\frac {4}{3}}\\0&{\frac {4}{3}}&-{\frac {4}{3}}&-1\end{bmatrix}},\end{aligned}}}$

utilizado para formar ${\textstyle A_{2}}$

${\displaystyle {\begin{aligned}Q_{2}&={\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&-{\frac {3}{5}}&-{\frac {4}{5}}\\0&0&-{\frac {4}{5}}&{\frac {3}{5}}\end{bmatrix}},\\A_{3}=Q_{2}A_{2}Q_{2}&={\begin{bmatrix}4&-3&0&0\\-3&{\frac {10}{3}}&-{\frac {5}{3}}&0\\0&-{\frac {5}{3}}&-{\frac {33}{25}}&{\frac {68}{75}}\\0&0&{\frac {68}{75}}&{\frac {149}{75}}\end{bmatrix}},\end{aligned}}}$

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 de Householder es una reflexión sobre un hiperplano con vector normal unitario , como se indicó anteriormente. Una transformación por unidad satisface . Tomar 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 un módulo unitario. Esto se puede ver directa y rápidamente: ${\textstyle v}$ ${\textstyle N}$ ${\textstyle N}$ ${\textstyle U}$ ${\textstyle UU^{*}=I}$ ${\textstyle N}$ ${\textstyle \lambda _{i}}$

${\displaystyle {\begin{aligned}{\frac {\operatorname {Trace} \left(UU^{*}\right)}{N}}&={\frac {\sum _{j=1}^{N}\left|\lambda _{j}\right|^{2}}{N}}=1,&\operatorname {det} \left(UU^{*}\right)&=\prod _{j=1}^{N}\left|\lambda _{j}\right|^{2}=1.\end{aligned}}}$

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 del módulo unitario.

Para el caso de matrices unitarias de valores reales obtenemos matrices ortogonales , . Se deduce bastante fácilmente (ver matriz ortogonal ) que cualquier matriz ortogonal se puede descomponer en un producto de rotaciones de 2 por 2, llamado Rotaciones dadas y reflexiones de Householder. 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. ${\textstyle UU^{\textsf {T}}=I}$

Se demostró que la transformación de Householder tiene una relación uno a uno con la descomposición lateral canónica de matrices unitarias definidas en la teoría de grupos, que puede usarse para parametrizar operadores unitarios de una manera muy eficiente. ^[5]

Finalmente, observamos que una única transformada de Householder, a diferencia de una transformada de Givens solitaria, puede actuar sobre todas las columnas de una matriz y, como tal, presenta el costo computacional más bajo para la descomposición QR y la tridiagonalización. La penalización por esta "optimidad computacional" es, por supuesto, que las operaciones de Householder no pueden paralelizarse de manera tan profunda o eficiente. Como tal, se prefiere Householder para matrices densas en máquinas secuenciales, mientras que se prefiere Givens en matrices dispersas y/o máquinas paralelas.

Ver también

• Rotación de dados
• rotación jacobi

Notas

1. Jefe de familia, AS (1958). "Triangularización unitaria de una matriz no simétrica" ​​(PDF) . Revista de la ACM . 5 (4): 339–342. doi :10.1145/320941.320947. SEÑOR  0111128. S2CID  9858625.
2. Taboga, Marco. "Matriz de hogares, Conferencias sobre álgebra matricial".
3. Schabauer, Hannes; Pacher, Christoph; Sunderland, Andrew G.; Gansterer, Wilfried N. (1 de mayo de 2010). "Hacia un solucionador paralelo de problemas de valores propios simétricos complejos generalizados". Procedia Ciencias de la Computación . 1 (1): 437–445. doi : 10.1016/j.procs.2010.04.047 .
4. Carga, Richard; Ferias, Douglas; Carga, Annette (2016). Análisis numérico (10ª ed.). Thomson Brooks/Cole. ISBN 9781305253667.
5. Renán Cabrera; Traci Strohecker; Herschel Rabitz (2010). "La descomposición canónica de matrices unitarias mediante transformaciones de Householder". Revista de Física Matemática . 51 (8): 082101. arXiv : 1008.2477 . Código Bib : 2010JMP....51h2101C. doi : 10.1063/1.3466798. S2CID  119641896.

Referencias

• 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 . 17 (84). Sociedad Estadounidense de Matemáticas: 433–437. doi :10.2307/2004005. JSTOR  2004005. SEÑOR  0156455.
• Morrison, DD (1960). "Observaciones sobre la triangularización unitaria de una matriz no simétrica". Revista de la ACM . 7 (2): 185–186. doi : 10.1145/321021.321030 . SEÑOR  0114291. S2CID  23361868.
• Cipra, Barry A. (2000). "Lo mejor del siglo XX: los editores nombran los 10 algoritmos principales". 33 (4): 1. {{cite journal}}: Cite Journal requiere |journal=( ayuda ) (Aquí se cita a Householder Transformation como uno de los 10 algoritmos principales de este siglo)
• Prensa, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Sección 11.3.2. Método del jefe de familia". Recetas numéricas: el arte de la informática científica (3ª ed.). Nueva York: Cambridge University Press. ISBN 978-0-521-88068-8.