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 de Alston Scott Householder . ^[1]

Su análogo en 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 respecto de 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 jefes de hogar

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 la matriz Householder , donde es la matriz identidad . ${\textstyle I}$

Propiedades

La matriz de jefes de hogar tiene las siguientes propiedades:

• es hermitiano : , ${\textstyle P=P^{*}}$
• es unitario : , ${\textstyle P^{-1}=P^{*}}$
• Por lo tanto es involutivo : . ${\textstyle P=P^{-1}}$
• Una matriz Householder tiene valores propios . Para ver esto, observe que si es ortogonal al vector que se utilizó para crear el reflector, entonces , es decir, es un valor propio de multiplicidad , ya que hay vectores independientes ortogonales a . Además, observe que , y por lo tanto 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 Householder es , ya 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). ${\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 (véase Reflexión especular § Formulación vectorial ).

Álgebra lineal numérica

Las transformaciones de Householder se utilizan ampliamente en álgebra lineal numérica , por ejemplo, para eliminar 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 hermíticas , la simetría se puede conservar, lo que resulta en tridiagonalización . ^[3]

Descomposición QR

Las reflexiones de Householder se pueden utilizar para calcular 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 por la matriz original y luego recurriendo hacia abajo a los menores de ese producto. Para lograr esto, se busca una matriz unitaria hermítica Q que tome 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 unitario, digamos para la coordenada kth. Una matriz compleja Q que tiene la forma Q = I - uu * con u * u = 2 tiene la propiedad deseada de ser unitaria hermítica. 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 a determinar. Dado que un factor de fase general para u no importa, el coeficiente a puede elegirse para que 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. Hay 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 se han determinado. Supóngase que e es el késimo vector de coordenadas unitario de modo que e * e = 1 y x _k = e * x y sea | x |= sqrt( 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(x _k )). 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 Householder 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}}}$

A partir de y , construya el vector : ${\textstyle \alpha }$ ${\textstyle r}$ ${\textstyle v}$

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

donde , , y ${\textstyle v_{1}=0}$ ${\textstyle v_{2}={\frac {a_{21}-\alpha }{2r}}}$

${\displaystyle v_{k}={\frac {a_{k1}}{2r}}}$Para cada uno ${\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 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 estos pasos del método Householder, tenemos:

La primera matriz de jefes de hogar:

${\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}}}$

Se utiliza 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 observar, el resultado final es una matriz simétrica tridiagonal similar a la original. El proceso finaliza en 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 un vector normal unitario , como se dijo anteriormente. Una transformación unitaria -por- satisface . Tomando el determinante ( la -ésima potencia de la media geométrica) y la traza (proporcional a la media aritmética) de una matriz unitaria se revela que sus valores propios tienen módulo unitario. Esto se puede ver de manera directa y rápida: ${\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 (véase desigualdad de las medias aritméticas y geométricas ), establecemos la afirmación del 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 rotaciones de 2 por 2, llamadas Rotaciones de Givens 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 ha demostrado que la transformación de 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 única transformación Householder, a diferencia de una transformación Givens solitaria, puede actuar sobre todas las columnas de una matriz y, como tal, presenta el menor costo computacional para la descomposición QR y la tridiagonalización. La desventaja de esta "optimización computacional" es, por supuesto, que las operaciones Householder no pueden paralelizarse de manera tan profunda o eficiente. Como tal, Householder es preferible para matrices densas en máquinas secuenciales, mientras que Givens es preferible para matrices dispersas y/o máquinas paralelas.

Véase también

• Reflector de bloque
• Rotación de Givens
• Rotación de Jacobi

Notas

1. Householder, 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. MR  0111128. S2CID  9858625.
2. Taboga, Marco. "Matriz de hogares, Lecciones sobre álgebra matricial".
3. 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 Computer Science . 1 (1): 437–445. doi : 10.1016/j.procs.2010.04.047 .
4. Burden, Richard; Faires, Douglas; Burden, Annette (2016). Análisis numérico (10.ª ed.). Thomson Brooks/Cole. ISBN 9781305253667.
5. Renan Cabrera; Traci Strohecker; Herschel Rabitz (2010). "La descomposición en clases laterales canónicas de matrices unitarias mediante transformaciones de Householder". Journal of Mathematical Physics . 51 (8): 082101. arXiv : 1008.2477 . Bibcode :2010JMP....51h2101C. doi :10.1063/1.3466798. S2CID  119641896.

Referencias

• LaBudde, CD (1963). "La reducción de una matriz cuadrada real arbitraria a la forma tridiagonal utilizando transformaciones de similitud". Matemáticas de la computación . 17 (84). Sociedad matemática estadounidense: 433–437. doi :10.2307/2004005. JSTOR  2004005. MR  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 . MR  0114291. S2CID  23361868.
• Cipra, Barry A. (2000). "Lo mejor del siglo XX: los editores nombran los 10 mejores algoritmos". SIAM News . 33 (4): 1.(Aquí se cita Householder Transformation como uno de los 10 mejores algoritmos de este siglo)
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Sección 11.3.2. Método Householder". Recetas numéricas: el arte de la computación científica (3.ª ed.). Nueva York: Cambridge University Press. ISBN 978-0-521-88068-8Archivado desde el original el 11-08-2011 . Consultado el 13-08-2011 .