Matriz de Hessenberg

Tipos de matrices cuadradas en álgebra lineal

En álgebra lineal , una matriz de Hessenberg es un tipo especial de matriz cuadrada , una que es "casi" triangular . Para ser exactos, una matriz de Hessenberg superior tiene cero entradas debajo de la primera subdiagonal , y una matriz de Hessenberg inferior tiene cero entradas encima de la primera superdiagonal . ^[1] Su nombre se debe a Karl Hessenberg . ^[2]

Una descomposición de Hessenberg es una descomposición matricial de una matriz en una matriz unitaria y una matriz de Hessenberg tal que donde denota la transpuesta conjugada . ${\displaystyle A}$ ${\displaystyle P}$ ${\displaystyle H}$ $${\displaystyle PHP^{*}=A}$$ ${\displaystyle P^{*}}$

Definiciones

Matriz del Alto Hessenberg

Se dice que una matriz cuadrada está en forma de Hessenberg superior o es una matriz de Hessenberg superior si para todos con . ${\displaystyle n\times n}$ ${\displaystyle A}$ ${\displaystyle a_{i,j}=0}$ ${\displaystyle i,j}$ ${\displaystyle i>j+1}$

Una matriz de Hessenberg superior se denomina no reducida si todas las entradas subdiagonales son distintas de cero, es decir, si para todos los . ^[3] ${\displaystyle a_{i+1,i}\neq 0}$ ${\displaystyle i\in \{1,\ldots ,n-1\}}$

Matriz del Bajo Hessenberg

Se dice que una matriz cuadrada está en forma de Hessenberg inferior o es una matriz de Hessenberg inferior si su transpuesta es una matriz de Hessenberg superior o, equivalentemente, si para todos con . ${\displaystyle n\times n}$ ${\displaystyle A}$ ${\displaystyle }$ ${\displaystyle a_{i,j}=0}$ ${\displaystyle i,j}$ ${\displaystyle j>i+1}$

Una matriz de Hessenberg inferior se denomina no reducida si todas las entradas superdiagonales son distintas de cero, es decir, si para todos los . ${\displaystyle a_{i,i+1}\neq 0}$ ${\displaystyle i\in \{1,\ldots ,n-1\}}$

Ejemplos

Consideremos las siguientes matrices. $${\displaystyle A={\begin{bmatrix}1&4&2&3\\3&4&1&7\\0&2&3&4\\0&0&1&3\\\end{bmatrix}}}$$ $${\displaystyle B={\begin{bmatrix}1&2&0&0\\5&2&3&0\\3&4&3&7\\5&6&1&1\\\end{bmatrix}}}$$ $${\displaystyle C={\begin{bmatrix}1&2&0&0\\5&2&0&0\\3&4&3&7\\5&6&1&1\\\end{bmatrix}}}$$

La matriz es una matriz de Hessenberg superior no reducida, es una matriz de Hessenberg inferior no reducida y es una matriz de Hessenberg inferior pero no está no reducida. ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle C}$

Programación de computadoras

Muchos algoritmos de álgebra lineal requieren un esfuerzo computacional significativamente menor cuando se aplican a matrices triangulares , y esta mejora a menudo se traslada también a las matrices de Hessenberg. Si las restricciones de un problema de álgebra lineal no permiten que una matriz general se reduzca convenientemente a una triangular, la reducción a la forma de Hessenberg es a menudo la siguiente mejor opción. De hecho, la reducción de cualquier matriz a una forma de Hessenberg se puede lograr en un número finito de pasos (por ejemplo, a través de la transformación de Householder de transformadas de similitud unitaria). La reducción posterior de la matriz de Hessenberg a una matriz triangular se puede lograr a través de procedimientos iterativos, como la factorización QR desplazada . En los algoritmos de valor propio , la matriz de Hessenberg se puede reducir aún más a una matriz triangular a través de la factorización QR desplazada combinada con pasos de deflación. Reducir una matriz general a una matriz de Hessenberg y luego reducir aún más a una matriz triangular, en lugar de reducir directamente una matriz general a una matriz triangular, a menudo economiza la aritmética involucrada en el algoritmo QR para problemas de valor propio.

Reducción a la matriz de Hessenberg

Transformaciones de los jefes de familia

Cualquier matriz puede transformarse en una matriz de Hessenberg mediante una transformación de similitud utilizando transformaciones de Householder . El siguiente procedimiento para dicha transformación es una adaptación de A Second Course In Linear Algebra de Garcia & Roger . ^[4] ${\displaystyle n\times n}$

Sea cualquier matriz real o compleja , entonces sea la submatriz de construida eliminando la primera fila en y sea la primera columna de . Construya la matriz de jefes de hogar donde ${\displaystyle A}$ ${\displaystyle n\times n}$ ${\displaystyle A^{\prime }}$ ${\displaystyle (n-1)\times n}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle \mathbf {a} _{1}^{\prime }}$ ${\displaystyle A'}$ ${\displaystyle (n-1)\times (n-1)}$ ${\displaystyle V_{1}=I_{(n-1)}-2{\frac {ww^{*}}{\|w\|^{2}}}}$ $${\displaystyle w={\begin{cases}\|\mathbf {a} _{1}^{\prime }\|_{2}\mathbf {e} _{1}-\mathbf {a} _{1}^{\prime }\;\;\;\;\;\;\;\;,\;\;\;a_{11}^{\prime }=0\\\|\mathbf {a} _{1}^{\prime }\|_{2}\mathbf {e} _{1}+{\frac {\overline {a_{11}^{\prime }}}{|a_{11}^{\prime }|}}\mathbf {a} _{1}^{\prime }\;\;\;,\;\;\;a_{11}^{\prime }\neq 0\\\end{cases}}}$$

Esta matriz de jefes de hogar se asignará a y, como tal, la matriz de bloques asignará la matriz a la matriz que solo tiene ceros debajo de la segunda entrada de la primera columna. Ahora construya la matriz de jefes de hogar de manera similar a la que asigna la primera columna de a , donde es la submatriz de construida eliminando la primera fila y la primera columna de , luego sea que se asigna a la matriz que solo tiene ceros debajo de la primera y segunda entrada de la subdiagonal. Ahora construya y luego de manera similar, pero para la matriz construida eliminando la primera fila y la primera columna de y proceda como en los pasos anteriores. Continúe así por un total de pasos. ${\displaystyle \mathbf {a} _{1}^{\prime }}$ ${\displaystyle \|\mathbf {a} _{1}^{\prime }\|\mathbf {e} _{1}}$ ${\displaystyle U_{1}={\begin{bmatrix}1&\mathbf {0} \\\mathbf {0} &V_{1}\end{bmatrix}}}$ ${\displaystyle A}$ ${\displaystyle U_{1}A}$ ${\displaystyle (n-2)\times (n-2)}$ ${\displaystyle V_{2}}$ ${\displaystyle V_{1}}$ ${\displaystyle V_{2}}$ ${\displaystyle A^{\prime \prime }}$ ${\displaystyle \|\mathbf {a} _{1}^{\prime \prime }\|\mathbf {e} _{1}}$ ${\displaystyle A^{\prime \prime }}$ ${\displaystyle A^{\prime }}$ ${\displaystyle A^{\prime }}$ ${\displaystyle U_{2}={\begin{bmatrix}1&0&0\\0&1&0\\0&0&V_{2}\end{bmatrix}}}$ ${\displaystyle U_{1}A}$ ${\displaystyle U_{2}U_{1}A}$ ${\displaystyle V_{3}}$ ${\displaystyle U_{3}}$ ${\displaystyle A^{\prime \prime \prime }}$ ${\displaystyle A^{\prime \prime }}$ ${\displaystyle n-2}$

Por construcción de , las primeras columnas de cualquier matriz son invariantes ante la multiplicación por desde la derecha. Por lo tanto, cualquier matriz puede transformarse en una matriz de Hessenberg superior mediante una transformación de similitud de la forma . ${\displaystyle U_{k}}$ ${\displaystyle k}$ ${\displaystyle n\times n}$ ${\displaystyle U_{k}^{*}}$ ${\displaystyle U_{(n-2)}(\dots (U_{2}(U_{1}AU_{1}^{*})U_{2}^{*})\dots )U_{(n-2)}^{*}=U_{(n-2)}\dots U_{2}U_{1}A(U_{(n-2)}\dots U_{2}U_{1})^{*}=UAU^{*}}$

Rotaciones de Jacobi (Givens)

Una rotación de Jacobi (también llamada rotación de Givens) es una transformación matricial ortogonal en la forma

${\displaystyle A\to A'=J(p,q,\theta )^{T}AJ(p,q,\theta )\;,}$

donde , , es la matriz de rotación de Jacobi con todos los elementos de la matriz iguales a cero excepto ${\displaystyle J(p,q,\theta )}$ ${\displaystyle p<q}$

${\displaystyle \left\{{\begin{aligned}J(p,q,\theta )_{ii}&{}=1\;\forall i\neq p,q\\J(p,q,\theta )_{pp}&{}=\cos(\theta )\\J(p,q,\theta )_{qq}&{}=\cos(\theta )\\J(p,q,\theta )_{pq}&{}=\sin(\theta )\\J(p,q,\theta )_{qp}&{}=-\sin(\theta )\;.\end{aligned}}\right.}$

Se puede poner a cero el elemento de la matriz eligiendo el ángulo de rotación para satisfacer la ecuación. ${\displaystyle A'_{p-1,q}}$ ${\displaystyle \theta }$

${\displaystyle A_{p-1,p}\sin \theta +A_{p-1,q}\cos \theta =0\;,}$

Ahora, la secuencia de tales rotaciones de Jacobi con la siguiente ${\displaystyle (p,q)}$

${\displaystyle (p,q)=(2,3),(2,4),\dots ,(2,n),(3,4),\dots ,(3,n),\dots ,(n-1,n)}$

reduce la matriz a la forma Hessenberg inferior. ^[5] ${\displaystyle A}$

Propiedades

Para , es vacuamente cierto que cada matriz es a la vez Hessenberg superior y Hessenberg inferior. ^[6] ${\displaystyle n\in \{1,2\}}$ ${\displaystyle n\times n}$

El producto de una matriz de Hessenberg con una matriz triangular es nuevamente Hessenberg. Más precisamente, si es Hessenberg superior y es triangular superior, entonces y son Hessenberg superiores. ${\displaystyle A}$ ${\displaystyle T}$ ${\displaystyle AT}$ ${\displaystyle TA}$

Una matriz que es a la vez Hessenberg superior e inferior es una matriz tridiagonal , de la que la matriz de Jacobi es un ejemplo importante. Esto incluye las matrices de Hessenberg simétricas o hermíticas. Una matriz hermítica se puede reducir a matrices simétricas reales tridiagonales. ^[7]

Operador de Hessenberg

El operador de Hessenberg es una matriz de Hessenberg de dimensión infinita. Suele presentarse como la generalización del operador de Jacobi a un sistema de polinomios ortogonales para el espacio de funciones holomorfas integrables al cuadrado sobre algún dominio, es decir, un espacio de Bergman . En este caso, el operador de Hessenberg es el operador de desplazamiento a la derecha , dado por ${\displaystyle S}$ $${\displaystyle [Sf](z)=zf(z).}$$

Los valores propios de cada submatriz principal del operador de Hessenberg están dados por el polinomio característico de esa submatriz. Estos polinomios se denominan polinomios de Bergman y proporcionan una base polinómica ortogonal para el espacio de Bergman.

Véase también

• Variedad Hessenberg

Notas

1. Horn y Johnson (1985), página 28; Stoer y Bulirsch (2002), página 251
2. Biswa Nath Datta (2010) Álgebra lineal numérica y aplicaciones, 2.ª edición, Sociedad de Matemáticas Industriales y Aplicadas (SIAM) ISBN  978-0-89871-685-6 , pág. 307
3. Horn y Johnson 1985, pág. 35
4. Ramon Garcia, Stephan; Horn, Roger (2017). Un segundo curso de álgebra lineal . Cambridge University Press. ISBN 9781107103818.
5. Bini, Dario A.; Robol, Leonardo (2016). "Reducción de Hessenberg cuasiseparable de matrices diagonales reales más matrices de bajo rango y aplicaciones". Álgebra lineal y sus aplicaciones . 502 : 186–213. arXiv : 1501.07812 . doi :10.1016/j.laa.2015.08.026.
6. Notas de la conferencia. Notas del 21 de octubre de 2016 Universidad de Cornell
7. "Rutinas computacionales (valores propios) en LAPACK". sites.science.oregonstate.edu . Consultado el 24 de mayo de 2020 .

Referencias

• Horn, Roger A.; Johnson, Charles R. (1985), Análisis de matrices , Cambridge University Press , ISBN 978-0-521-38632-6.
• Stoer, Josef; Bulirsch, Roland (2002), Introducción al análisis numérico (3.ª ed.), Berlín, Nueva York: Springer-Verlag , ISBN 978-0-387-95452-3.
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Sección 11.6.2. Reducción a la forma de Hessenberg", Recetas numéricas: el arte de la computación científica (3.ª ed.), Nueva York: Cambridge University Press, ISBN 978-0-521-88068-8, archivado desde el original el 11-08-2011 , consultado el 13-08-2011

Enlaces externos

• Matriz de Hessenberg en MathWorld .
• Matriz de Hessenberg en PlanetMath .
• Algoritmos de alto rendimiento para reducción a forma condensada (Hessenberg, tridiagonal, bidiagonal)
• Descripción general del algoritmo