Transformación de Householder

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 respecto a 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 ]}

Definición

Operador y transformación

El operador Householder ^{[ 2 ]} puede definirse sobre cualquier espacio de producto interno de dimensión finita. $V$ con producto interior $\langle \cdot ,\cdot \rangle$ y vector unitario $u\in V$ como

H_{u}(x):=x-2\,\langle x,u\rangle \,u\,.

^{[ 3 ]}

Tal como se define aquí, el producto interno $\langle \,\cdot {\text{,}}\,\cdot \rangle$ es lineal en su primer argumento y antilineal en su segundo argumento, de modo que si a y b son escalares, entonces $\langle \,a\,x{\text{,}}\,b\,y\rangle \,=\,a\,{\overline {b}}\,\langle x{\text{,}}\,y\rangle$ . Aquí ${\overline {b}}$ es el conjugado complejo de $b$ .

También es común elegir un vector no unitario. $q\in V$ y normalizarlo directamente en la expresión del operador Householder: ^{[ 4 ]}

H_{q}\left(x\right)=x-2\,{\frac {\langle x,q\rangle }{\langle q,q\rangle }}\,q\,.

Dicho operador es lineal y autoadjunto .

Si $V=\mathbb {C} ^{n}$ , tenga en cuenta que el hiperplano de reflexión se puede definir mediante su vector normal , un vector unitario. ${\textstyle {\vec {v}}\in V}$ (un vector con longitud ${\textstyle 1}$ ) que es ortogonal al hiperplano. La reflexión de un punto ${\textstyle x}$ Acerca de este hiperplano es la transformación de Householder :

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

dónde ${\vec {x}}$ es el vector desde el origen hasta el punto $x$ , y ${\textstyle {\vec {v}}^{*}}$ es la transpuesta conjugada de ${\textstyle {\vec {v}}}$ .

La transformación de Householder actuando como un reflejo de $x$ sobre el hiperplano definido por $v$ .

{\displaystyle x} — La transformación de Householder actuando como un reflejo de $x$ sobre el hiperplano definido por $v$ .

Matriz de Householder

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

P=I-2{\vec {v}}{\vec {v}}^{*}

se conoce como la matriz de Householder , donde ${\textstyle I}$ es la matriz identidad .

Propiedades

La matriz de Householder tiene las siguientes propiedades:

es hermitiano : ${\textstyle P=P^{*}}$ ,
es unitario : ${\textstyle P^{-1}=P^{*}}$ (a través de la fórmula de Sherman-Morrison ),
Por lo tanto, es involutivo : ${\textstyle P=P^{-1}}$ .
Una matriz de Householder tiene valores propios ${\textstyle \pm 1}$ Para ver esto, observe que si ${\textstyle {\vec {x}}}$ es ortogonal al vector ${\textstyle {\vec {v}}}$ que se utilizó para crear el reflector, luego ${\textstyle P_{v}{\vec {x}}=(I-2{\vec {v}}{\vec {v}}^{*}){\vec {x}}={\vec {x}}-2\langle {\vec {v}},{\vec {x}}\rangle {\vec {v}}={\vec {x}}}$ , es decir, ${\textstyle 1}$ es un valor propio de multiplicidad ${\textstyle n-1}$ , puesto que hay ${\textstyle n-1}$ vectores independientes ortogonales a ${\textstyle {\vec {v}}}$ Además, tenga en cuenta que... ${\textstyle P_{v}{\vec {v}}=(I-2{\vec {v}}{\vec {v}}^{*}){\vec {v}}={\vec {v}}-2\langle {\vec {v}},{\vec {v}}\rangle {\vec {v}}=-{\vec {v}}}$ (desde ${\vec {v}}$ es por definición un vector unitario), y por lo tanto ${\textstyle -1}$ es un valor propio con multiplicidad ${\textstyle 1}$ .
El determinante de un reflector Householder es ${\textstyle -1}$ , puesto que el determinante de una matriz es el producto de sus valores propios, en este caso uno de los cuales es ${\textstyle -1}$ siendo el resto ${\textstyle 1}$ (como en el punto anterior), o mediante el lema del determinante de matrices .

Ejemplo

Consideremos la normalización de un vector. ${\vec {v}}$ que contiene $1$ en cada entrada,

{\vec {v}}={\frac {1}{\sqrt {2}}}{\begin{bmatrix}1\\1\end{bmatrix}}.

Luego, la matriz de Householder correspondiente al vector $v$ es

P_{v}={\begin{bmatrix}1&0\\0&1\end{bmatrix}}-2\left({\frac {1}{\sqrt {2}}}{\begin{bmatrix}1\\1\end{bmatrix}}\right)\left({\frac {1}{\sqrt {2}}}{\begin{bmatrix}1&1\end{bmatrix}}\right)

\quad ={\begin{bmatrix}1&0\\0&1\end{bmatrix}}-{\begin{bmatrix}1\\1\end{bmatrix}}{\begin{bmatrix}1&1\end{bmatrix}}

\quad ={\begin{bmatrix}1&0\\0&1\end{bmatrix}}-{\begin{bmatrix}1&1\\1&1\end{bmatrix}}

\quad ={\begin{bmatrix}0&-1\\-1&0\end{bmatrix}}.

Tenga en cuenta que si tenemos otro vector ${\vec {q}}$ representa una coordenada en el plano 2D

{\vec {q}}={\begin{bmatrix}x\\y\end{bmatrix}},

entonces en este caso $P_{v}$ voltea y niega el $x$ y $y$ coordenadas, en otras palabras tenemos

P_{v}{\begin{bmatrix}x\\y\end{bmatrix}}={\begin{bmatrix}-y\\-x\end{bmatrix}},

lo que corresponde a reflejar el vector a través de la línea $y=-x$ , que es nuestro vector original ${\vec {v}}$ es normal.

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

Cabe destacar que la representación de una matriz de Householder solo requiere las entradas de un único vector, no de una matriz completa (que en la mayoría de los algoritmos nunca se forma explícitamente), minimizando así el almacenamiento y las referencias de memoria necesarias para su uso.

Además, multiplicar una matriz de Householder por un vector no implica una multiplicación completa matriz-vector, sino solo un producto escalar de vectores y una operación axpy . Esto significa que su complejidad aritmética es del mismo orden que dos operaciones BLAS-1 de bajo nivel . Por lo tanto, las matrices de Householder son extremadamente eficientes desde el punto de vista aritmético. ^{[ 5 ]}

Finalmente, utilizando ${\hat {\cdot }}$ para denotar el valor calculado y $\cdot$ para denotar el valor matemáticamente exacto, entonces para una matriz de Householder dada $P$ ,

${\widehat {Pb}}=(P+\Delta P)b$

Dónde $\vert \vert \Delta P\vert \vert _{F}\leq {\tilde {\gamma _{n}}}:={\frac {cnu}{1-cnu}}$ (dónde $u$ es redondeo de unidad, $n$ el tamaño de la matriz $P$ , y $c$ alguna pequeña constante). En otras palabras, las multiplicaciones por matrices de Householder también son extremadamente estables hacia atrás . ^{[ 6 ]}

Dado que las transformaciones de Householder minimizan el almacenamiento, las referencias a memoria, la complejidad aritmética y optimizan la estabilidad numérica, se utilizan ampliamente en álgebra lineal numérica , por ejemplo, para aniquilar las entradas debajo de la diagonal principal de una matriz, ^{[ 7 ]} 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 hermíticas , la simetría se puede preservar, lo que resulta en la tridiagonalización . ^{[ 8 ]}^{[ 9 ]}

descomposición QR

Las transformaciones de Householder se pueden usar para calcular una descomposición QR . Consideremos una matriz cuadrada triangularizada superiormente hasta la columna $i-1$ , entonces nuestro objetivo es construir tales matrices de Householder que actúen sobre las submatrices principales de esa matriz, que tiene la forma

$A^{(i)}={\begin{bmatrix}a_{11}&a_{12}&\cdots &&&a_{1n}\\0&a_{22}&\cdots &&&a_{1n}\\\vdots &&\ddots &&&\vdots \\0&\cdots &0&x_{1}=a_{ii}&\cdots &a_{in}\\0&\cdots &0&\vdots &&\vdots \\0&\cdots &0&x_{n+1-i}=a_{ni}&\cdots &a_{nn}\end{bmatrix}}$

La matriz $A^{(i)}$ tiene la forma de bloque

$A^{(i)}={\begin{bmatrix}T_{i-1}^{U}&*\\0&P_{v}\end{bmatrix}}$ .

Tenga en cuenta que $A^{(n)}$ es la matriz $R$ en el $Q\,R$ descomposición. Aquí la submatriz $T_{i-1}^{U}$ es una matriz triangular superior cuadrada de i-1 x i-1, 0 representa la matriz cero de n-i+1 x n-i+1, * representa una matriz de n-i+1 x n-i+1 y $P_{v}$ representa una matriz n-i+1 x n-i+1 que se convertirá en triangular superior trabajando en su subespacio sin cambiar la forma de matriz de bloques dada anteriormente para $A^{(i)}$ .

Si $x_{1}=a_{ii}$ es cero y hay un elemento distinto de cero $a_{ji}$ con j>i, entonces las filas i y j se pueden intercambiar mediante la premultiplicación por la matriz de intercambio de filas, que es unitaria. $a_{ji}=0$ Para todo j>=i, proceda a la siguiente columna.

Si $x_{1}=a_{ii}$ es un complejo no real dado por $x_{1}=r_{1}e^{i\phi _{1}}$ verdadero $r_{1}{\text{,}}\,\phi _{1}$ , entonces esta matriz puede ser premultiplicada por la matriz unitaria diagonal U con $U_{ii}=e^{-i\phi _{1}}$ y con 1 para los demás elementos diagonales para formar el nuevo $x_{1}$ números reales distintos de cero, conservando la forma de bloque. Esto garantiza que $\langle \mathbf {x} ,{\vec {e}}_{1}\rangle \,=\,\langle {\vec {e}}_{1},\mathbf {x} \rangle \,=\,x_{1}$ . Aquí ${\vec {e}}_{1}$ es un vector n-dimensional con 1 en la i-ésima posición y 0 en las demás. (Cabe destacar que previamente establecimos que las transformaciones de Householder son matrices unitarias, y dado que la multiplicación de matrices unitarias es en sí misma una matriz unitaria, esto nos da la matriz unitaria de la descomposición QR).

Dejar $\mathbf {e} _{1}{\text{,}}\,\mathbf {e} _{2}{\text{,}}\,{\text{...}}{\text{,}}\,\mathbf {e} _{n}$ sean los vectores base para las matrices n-dimensionales $A^{(i)}$ y dejar ${\vec {e}}_{1}{\text{,}}\,{\vec {e}}_{2}{\text{,}}\,{\text{...}}{\text{,}}\,{\vec {e}}_{n-i+1}$ sean los vectores base $\mathbf {e} _{i}{\text{,}}\,\mathbf {e} _{i+1}{\text{,}}\,{\text{...}}{\text{,}}\,\mathbf {e} _{n}$ , respectivamente.

Si podemos encontrar un ${\vec {v}}$ de modo que $P_{v}{\vec {x}}=\alpha {\vec {e}}_{1}$ Podemos extender la triangulación superior en una columna. El vector $\mathbf {v}$ es estar en el subespacio generado por los vectores $\{\mathbf {e} _{i}{\text{,}}\,\mathbf {e} _{i+1}{\text{,}}\,{\text{...}}{\text{,}}\,\mathbf {e} _{n}\}$ que el vector $\mathbf {x}$ está dentro. Con $x_{1}$ real, se verá que $\alpha$ También es real. Pensando geométricamente, buscamos un plano tal que la reflexión sobre este plano caiga directamente sobre el vector base. En otras palabras,

por alguna constante $\alpha$ Sin embargo, para que esto suceda, debemos tener ${\vec {v}}\propto {\vec {x}}-\alpha {\vec {e}}_{1}{\text{.}}$ Y dado que ${\vec {v}}$ es un vector unitario, esto significa que debemos tener

Descubriremos que hay dos valores posibles para $\alpha$ . Ese valor que hace $\|{\vec {x}}-\alpha {\vec {e}}_{1}\|_{2}$ El de mayor tamaño es el que debe utilizarse para obtener la mayor precisión.

Ahora, si aplicamos la ecuación ( 2 ) de nuevo en la ecuación ( 1 ), obtenemos ${\vec {x}}-\alpha {\vec {e}}_{1}=2\left\langle {\vec {x}},{\frac {{\vec {x}}-\alpha {\vec {e}}_{1}}{\|{\vec {x}}-\alpha {\vec {e}}_{1}\|_{2}}}\right\rangle {\frac {{\vec {x}}-\alpha {\vec {e}}_{1}}{\|{\vec {x}}-\alpha {\vec {e}}_{1}\|_{2}}}$ O, dicho de otro modo, comparando los escalares que preceden al vector. ${\vec {x}}-\alpha {\vec {e}}_{1}$ debemos tener $\|{\vec {x}}-\alpha {\vec {e}}_{1}\|_{2}^{2}=2\langle {\vec {x}},{\vec {x}}-\alpha e_{1}\rangle {\text{.}}$ Si $x_{1}$ Si es real, entonces alfa también es real y se obtiene de la ecuación. $\|{\vec {x}}\|_{2}^{2}-2\alpha x_{1}+\alpha ^{2}=2(\|{\vec {x}}\|_{2}^{2}-\alpha x_{1})$ lo que significa $\alpha =\pm \|{\vec {x}}\|_{2}$ Si $x_{1}$ no es real, entonces $\alpha$ tampoco es real y se obtiene de la ecuación $\|{\vec {x}}\|_{2}^{2}-\alpha \,x_{1}^{*}-\alpha ^{*}\,x_{1}+|\alpha |^{2}\,=\,2(\|{\vec {x}}\|_{2}^{2}-\alpha ^{*}\,x_{1})$ O, equivalentemente, $|\alpha |^{2}\,=\,\|{\vec {x}}\|_{2}^{2}+(\alpha \,x_{1}^{*}-\alpha ^{*}\,x_{1})$ El término entre paréntesis es puramente imaginario. Esta ecuación requiere que $|\alpha |=\|{\vec {x}}\|_{2}$ y eso $\arg(\alpha )\,=\,\arg(x_{1})$ dentro de un múltiplo de $\pi$ .

Esto completa la construcción; sin embargo, en la práctica queremos evitar la cancelación catastrófica en la ecuación ( 2 ). Para hacerlo en la práctica, $x_{1}$ , elegimos ^{[ 5 ]} el signo de $\alpha$ como $\alpha =-\operatorname {sgn}(\mathrm {Re} (x_{1}))\|{\vec {x}}\|_{2}$ y para complejos $x_{1}$ elegimos el letrero para $\alpha$ como $\alpha =-e^{i\,\arg(x_{1})}\,\|x\|_{2}$ , dónde $i$ es la raíz cuadrada de $-1$ Esto concuerda con la ecuación que se acaba de dar para $\alpha$ cuando $x_{1}$ es real. Estas elecciones de signos hacen $\|{\vec {x}}-\alpha {\vec {e}}_{1}\|_{2}$ el más grande. Cuando $|x_{1}|\ll \|x\|_{2}$ Da igual qué signo se elija.

Las transformaciones de Householder pueden aplicarse de forma similar a una matriz compleja rectangular no cuadrada. Las descomposiciones son algo diferentes.

Tridiagonalización (Hessenberg)

Matriz simétrica real

Este procedimiento se presenta en el libro Análisis Numérico de Burden y Faires para matrices simétricas reales. En el caso no simétrico, sigue siendo útil, ya que un procedimiento similar puede dar como resultado una matriz de Hessenberg.

Utiliza una versión ligeramente modificada $\operatorname {sgn}$ función con $\operatorname {sgn} (0)=1$ . ^{[ 10 ]} En el primer paso, para formar la matriz de Householder en cada paso necesitamos determinar ${\textstyle \alpha }$ y ${\textstyle r}$ , que son:

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

De ${\textstyle \alpha }$ y ${\textstyle r}$ , construir vector ${\textstyle v}$ :

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

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

v_{k}={\frac {a_{k1}}{2r}}

para cada

k=3,4\ldots n

Luego calcula:

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

Desde $P^{1}$ es su propio inverso ( involutivo ), esta es una transformación de similitud . Habiendo encontrado ${\textstyle P^{1}}$ y calculado ${\textstyle A^{(2)}}$ El proceso se repite para ${\textstyle k=2,3,\ldots ,n-2}$ como sigue:

{\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-2{\vec {v}}^{(k)}\left({\vec {v}}^{(k)}\right)^{\textsf {T}}\\A^{(k+1)}&=P^{k}A^{(k)}P^{k}\end{aligned}}

Siguiendo este procedimiento, se forma la matriz tridiagonal y simétrica real. Dado que cada reflexión de Householder es una transformación de semejanza , también lo es la transformación global.

matriz hermitiana

Las transformaciones de Householder también pueden transformar una matriz hermitiana. $A$ en una matriz tridiagonal hermitiana. Seguimos el enfoque del artículo de la Universidad de Connecticut ^{[ 11 ]} excepto que reemplazamos las transpuestas de matrices por conjugadas hermitianas de matrices para la tridiagonalización de matrices hermitianas complejas en lugar de matrices simétricas reales.

Para empezar, dejemos

$A=\left({\begin{array}{c|c}a_{11}&{\vec {a}}_{1}^{*}\\\hline {\vec {a}}_{1}&A_{1}\end{array}}\right)$

frijol $n\times n$ Matriz hermitiana. Aquí $a_{11}$ es un ermitaño $1\times 1$ submatriz, por lo tanto es un número real, ${\vec {a}}_{1}$ es un $(n-1)\times 1$ vector columna, ${\vec {a}}_{1}^{*}$ es su conjugado hermitiano , que es un $1\times (n-1)$ vector fila y $A_{1}$ es un $(n-1)\times (n-1)$ Submatriz hermitiana . Sea la matriz de transformación de Householder. $P_{1}$ tener la forma

$P_{1}=\left({\begin{array}{c|c}1&{\vec {0}}^{*}\\\hline {\vec {0}}&H_{1}\end{array}}\right)$

dónde ${\vec {0}}$ es un $1\times (n-1)$ vector columna de ceros, ${\vec {0}}^{*}$ es su conjugado hermitiano y también lo es un $(n-1)\times 1$ vector fila de ceros, y donde $H_{1}=I\,-\,2\,{\vec {v}}\,{\vec {v}}^{*}$ y $I$ es el $(n-1)\times (n-1)$ matriz identidad. Como antes, ${\vec {v}}^{*}$ es la transpuesta matricial del conjugado complejo o conjugado hermitiano del vector columna ${\vec {v}}$ Además, como antes, la transformación de Householder $H_{1}$ es una matriz involutiva hermitiana unitaria . Entonces

$P_{1}\,A\,P_{1}^{*}=\,\left({\begin{array}{c|c}a_{11}&(H_{1}\,a_{1})^{*}\\\hline H_{1}\,a_{1}&H_{1}\,A_{1}\,H_{1}^{*}\end{array}}\right)$

Desde $H_{1}$ y por lo tanto $P_{1}$ es hermitiano e involutivo ${\begin{aligned}H_{1}&=H_{1}^{*}=H_{1}^{-1}\\P_{1}&=P_{1}^{*}=P_{1}^{-1}\end{aligned}}$ y, por lo tanto, se trata de una transformación de matriz de similitud unitaria .

Si tenemos $H_{1}{\vec {a}}_{1}\,=\,\alpha _{1}\,{\vec {e}}_{1}$

entonces $P_{1}\,A\,P_{1}^{*}\,=\,\left({\begin{array}{c|c|c}a_{11}&\alpha _{1}^{*}&{\vec {0}}^{*}\\\hline \alpha _{1}&a_{22}^{(1)}&{\vec {a}}_{2}^{*}\\\hline {\vec {0}}&{\vec {a}}_{2}&A_{2}\end{array}}\right)$ donde el $(n-2)\times (n-2)$ matriz $A_{2}$ es hermitiana ya que una transformación de similitud unitaria de una matriz hermitiana es también hermitiana. ${\vec {0}}$ es un $(n-2)\times 1$ vector columna de ceros y ${\vec {0}}^{*}$ es su conjugado hermitiano y es un $1\times (n-1)$ vector fila de ceros. Y ${\vec {a}}_{2}$ es un $(n-2)\times 1$ vector columna y ${\vec {a}}_{2}^{*}$ es su conjugado hermitiano y es un $1\times (n-2)$ vector fila. Ya sabemos cómo encontrar las matrices de transformación de Householder. $H_{i}$ .

Repita este proceso para un total de $n-2$ tiempos para $n>2$ para obtener la tridiagonalización mediante una sucesión de transformaciones de similitud involutivas hermíticas unitarias. Por ejemplo, el siguiente ejemplo para un $4\times 4$ una matriz simétrica real requiere dos pasos de transformación de Householder para transformarse en una matriz simétrica real tridiagonal, una $3\times 3$ Una matriz simétrica o hermitiana real requiere solo un paso, y una $1\times 1$ matriz real o una $2\times 2$ Una matriz simétrica o hermitiana real ya está tridiagonalizada.

Dado que el producto de matrices unitarias es de nuevo una matriz unitaria y que la transformación de similitud de una transformación de similitud es de nuevo una transformación de similitud, la transformación global es una transformación de similitud unitaria.

Ejemplos

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

\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 Householder, tenemos:

La primera matriz de Householder:

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

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

{\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 tras dos pasos.

Computación cuántica

{\displaystyle |s\rangle } — Imagen que muestra la interpretación geométrica de la primera iteración del algoritmo de Grover. El vector de estado $|s\rangle$ se rota hacia el vector objetivo $|\omega \rangle$ como se muestra.

Dado que las matrices unitarias son útiles en la computación cuántica , y las transformaciones de Householder son unitarias, resultan muy útiles en la computación cuántica. Uno de los algoritmos centrales donde son útiles es el algoritmo de Grover, en el que intentamos encontrar una representación de una función oráculo representada por lo que resulta ser una transformación de Householder:

${\begin{cases}U_{\omega }|x\rangle =-|x\rangle &{\text{for }}x=\omega {\text{, that is, }}f(x)=1,\\U_{\omega }|x\rangle =|x\rangle &{\text{for }}x\neq \omega {\text{, that is, }}f(x)=0.\end{cases}}$

(aquí el $|x\rangle$ forma parte de la notación bra-ket y es análoga a ${\vec {x}}$ que estábamos usando anteriormente)

Esto se realiza mediante un algoritmo que itera a través de la función oráculo. $U_{\omega }$ y otro operador $U_{s}$ conocido como el operador de difusión de Grover definido por

$|s\rangle ={\frac {1}{\sqrt {N}}}\sum _{x=0}^{N-1}|x\rangle .$ y $U_{s}=2\left|s\right\rangle \!\!\left\langle s\right|-I$ .

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. ${\textstyle v}$ , como se indicó anteriormente. Un ${\textstyle N}$ -por- ${\textstyle N}$ transformación unitaria ${\textstyle U}$ Satisface ${\textstyle UU^{*}=I}$ . Tomando el determinante ( ${\textstyle N}$ La potencia -ésima de la media geométrica) y la traza (proporcional a la media aritmética) de una matriz unitaria revelan que sus valores propios ${\textstyle \lambda _{i}}$ tienen módulo unitario. Esto se puede ver de forma directa y rápida:

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

Puesto que las medias aritmética y geométrica son iguales si las variables son constantes (véase la desigualdad de las medias aritmética y geométrica ), establecemos la afirmación del módulo unitario.

Para el caso de matrices unitarias de valor real obtenemos matrices ortogonales , ${\textstyle UU^{\textsf {T}}=I}$ De ello se deduce fácilmente (véase Matriz ortogonal ) que cualquier matriz ortogonal puede descomponerse en un producto de rotaciones de 2x2, llamadas rotaciones de Givens , y reflexiones de Householder. Esto resulta intuitivamente atractivo, ya que la multiplicación de un vector por una matriz ortogonal conserva la longitud de dicho 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 de Householder tiene una relación biunívoca con la descomposición canónica de clases laterales de matrices unitarias definida en la teoría de grupos, la cual puede utilizarse para parametrizar operadores unitarios de manera muy eficiente. ^{[ 12 ]}

Finalmente, cabe destacar que una única transformación de Householder, a diferencia de una sola transformación de Givens, puede actuar sobre todas las columnas de una matriz, lo que se traduce en el menor coste computacional para la descomposición QR y la tridiagonalización. La desventaja de esta "optimización computacional" radica, por supuesto, en que las operaciones de Householder no pueden paralelizarse con la misma profundidad ni eficiencia. Por ello, Householder se prefiere para matrices densas en máquinas secuenciales, mientras que Givens se prefiere para matrices dispersas y/o máquinas paralelas.

Véase también

Notas

↑ Householder, AS (1958). "Triangularización unitaria de una matriz no simétrica" ( PDF) . Journal of the ACM . 5 (4): 339– 342. doi : 10.1145/320941.320947 . MR 0111128. S2CID 9858625 .
↑ Roman 2008 , págs. 243-244
↑ Métodos de matemáticas aplicadas para ingenieros y científicos . Cambridge University Press. 28 de junio de 2013. pp. Sección E.4.11. ISBN 9781107244467.
↑ Roman 2008 , pág. 244
1 2 Saad, Yousef (2003). Métodos iterativos para sistemas lineales dispersos . Sociedad de Matemáticas Industriales y Aplicadas. págs. 11–14 .
↑ Higham, Nicholas J. (2002). Precisión y estabilidad de los algoritmos numéricos (2.ª ed.). Filadelfia: Society for Industrial and Applied Mathematics. pág. 358. ISBN 0-89871-521-0.
↑Taboga, Marco. "Householder matrix, Lectures on matrix algebra".
↑Schabauer, Hannes; Pacher, Christoph; Sunderland, Andrew G.; Gansterer, Wilfried N. (2010-05-01). "Toward a parallel solver for generalized complex symmetric eigenvalue problems". Procedia Computer Science. 1 (1): 437–445. doi:10.1016/j.procs.2010.04.047.
↑Golub, Gene Howard; Van Loan, Charles F. (1996). Matrix computations (3rd ed.). Baltimore London: Johns Hopkins university press. p. 211. ISBN 0-8018-5414-8.
1 2Burden, Richard; Faires, Douglas; Burden, Annette (2016). Numerical analysis (10th ed.). Thomson Brooks/Cole. ISBN 9781305253667.
↑Rozman. "Tridiagonalization"(PDF).
↑Renan Cabrera; Traci Strohecker; Herschel Rabitz (2010). "The canonical coset decomposition of unitary matrices through Householder transformations". Journal of Mathematical Physics. 51 (8): 082101. arXiv:1008.2477. Bibcode:2010JMP....51h2101C. doi:10.1063/1.3466798. S2CID 119641896.

References

LaBudde, C.D. (1963). "The reduction of an arbitrary real square matrix to tridiagonal form using similarity transformations". Mathematics of Computation. 17 (84). American Mathematical Society: 433–437. doi:10.2307/2004005. JSTOR 2004005. MR 0156455.
Morrison, D.D. (1960). "Remarks on the Unitary Triangularization of a Nonsymmetric Matrix". Journal of the ACM. 7 (2): 185–186. doi:10.1145/321021.321030. MR 0114291. S2CID 23361868.
Cipra, Barry A. (2000). "The Best of the 20th Century: Editors Name Top 10 Algorithms". SIAM News. 33 (4): 1. (Herein Householder Transformation is cited as a top 10 algorithm of this century)
Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). «Sección 11.3.2. Método Householder» . Numerical Recipes: The Art of Scientific Computing (3.ª ed.). Nueva York: Cambridge University Press. ISBN 978-0-521-88068-8Archivado del original el 11 de agosto de 2011. Consultado el 13 de agosto de 2011 .
Roman, Stephen (2008), Álgebra lineal avanzada , Textos de posgrado en matemáticas (Tercera ed.), Springer, ISBN 978-0-387-72828-5

[1] Householder, AS (1958). "Triangularización unitaria de una matriz no simétrica" ( PDF) . Journal of the ACM . 5 (4): 339– 342. doi : 10.1145/320941.320947 . MR 0111128. S2CID 9858625 .

[2] Roman 2008 , págs. 243-244

[3] Métodos de matemáticas aplicadas para ingenieros y científicos . Cambridge University Press. 28 de junio de 2013. pp. Sección E.4.11. ISBN 9781107244467.

[4] Roman 2008 , pág. 244

[saad-5] 1 2 Saad, Yousef (2003). Métodos iterativos para sistemas lineales dispersos . Sociedad de Matemáticas Industriales y Aplicadas. págs. 11–14 .

[Higham-6] Higham, Nicholas J. (2002). Precisión y estabilidad de los algoritmos numéricos (2.ª ed.). Filadelfia: Society for Industrial and Applied Mathematics. pág. 358. ISBN 0-89871-521-0.

[taboga-7] Taboga, Marco. "Householder matrix, Lectures on matrix algebra".

[8] Schabauer, Hannes; Pacher, Christoph; Sunderland, Andrew G.; Gansterer, Wilfried N. (2010-05-01). "Toward a parallel solver for generalized complex symmetric eigenvalue problems". Procedia Computer Science. 1 (1): 437–445. doi:10.1016/j.procs.2010.04.047.

[G&VL-9] Golub, Gene Howard; Van Loan, Charles F. (1996). Matrix computations (3rd ed.). Baltimore London: Johns Hopkins university press. p. 211. ISBN 0-8018-5414-8.

[burden-10] 1 2Burden, Richard; Faires, Douglas; Burden, Annette (2016). Numerical analysis (10th ed.). Thomson Brooks/Cole. ISBN 9781305253667.

[11] Rozman. "Tridiagonalization"(PDF).

[12] Renan Cabrera; Traci Strohecker; Herschel Rabitz (2010). "The canonical coset decomposition of unitary matrices through Householder transformations". Journal of Mathematical Physics. 51 (8): 082101. arXiv:1008.2477. Bibcode:2010JMP....51h2101C. doi:10.1063/1.3466798. S2CID 119641896.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]