matriz de hessenberg

Tipo de matriz cuadrada en álgebra lineal

En álgebra lineal , una matriz de Hessenberg es un tipo especial de matriz cuadrada , 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] Llevan el nombre de 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 ${\displaystyle A}$ ${\displaystyle P}$ ${\displaystyle H}$

$${\displaystyle PHP^{*}=A}$$

transpuesta conjugada ${\displaystyle P^{*}}$

Definiciones

Matriz de Hessenberg superior

Se dice que una matriz cuadrada está en forma de Hessenberg superior o que es una matriz de Hessenberg superior si es 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 llama no reducida si todas las entradas subdiagonales son distintas de cero, es decir, si para todos . ^[3] ${\displaystyle a_{i+1,i}\neq 0}$ ${\displaystyle i\in \{1,\ldots ,n-1\}}$

Matriz de Hessenberg inferior

Se dice que una matriz cuadrada está en forma de Hessenberg inferior o que es una matriz de Hessenberg inferior si su transpuesta es una matriz de Hessenberg superior o, de manera equivalente, si es para todo 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 llama no reducida si todas las entradas superdiagonales son distintas de cero, es decir, si para todos . ${\displaystyle a_{i,i+1}\neq 0}$ ${\displaystyle i\in \{1,\ldots ,n-1\}}$

Ejemplos

Considere 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á 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 reducir convenientemente una matriz general a una triangular, la reducción a la forma de Hessenberg suele ser la 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, mediante 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 mediante procedimientos iterativos, como la factorización QR desplazada . En los algoritmos de valores propios , la matriz de Hessenberg se puede reducir aún más a una matriz triangular mediante la factorización QR desplazada combinada con pasos de deflación. Reducir una matriz general a una matriz de Hessenberg y luego reducirla 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 valores propios.

Reducción a matriz de Hessenberg

Transformaciones de cabeza de familia

Cualquier matriz se puede transformar en una matriz de Hessenberg mediante una transformación de similitud utilizando transformaciones de Householder . El siguiente procedimiento para dicha transformación está adaptado de Un segundo curso de álgebra lineal de García y Roger . ^[4] ${\displaystyle n\times n}$

Sea cualquier matriz real o compleja , luego sea la submatriz de construida eliminando la primera fila y sea la primera columna de . Construya la matriz de cabeza de familia 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 cabeza de familia se asignará 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 cabeza de familia de una manera similar que asigne la primera columna de a , donde se construye la submatriz de eliminando la primera fila y la primera columna de , luego deje que se asigne a la matriz que solo tiene ceros debajo del primero 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 y proceda como en los pasos anteriores. Continúe así durante 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 cuando se multiplica 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 de matriz 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 las siguientes ${\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 inferior de Hessenberg. ^[5] ${\displaystyle A}$

Propiedades

Para , es vagamente cierto que toda 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 por una matriz triangular es nuevamente Hessenberg. Más precisamente, si es Hessenberg superior y es triangular superior, entonces y son Hessenberg superior. ${\displaystyle A}$ ${\displaystyle T}$ ${\displaystyle AT}$ ${\displaystyle TA}$

Una matriz que es a la vez Hessenberg superior y Hessenberg inferior es una matriz tridiagonal , de la cual la matriz de Jacobi es un ejemplo importante. Esto incluye las matrices simétricas o hermitianas de Hessenberg. Una matriz hermitiana 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. Comúnmente ocurre 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 vienen dados por el polinomio característico de esa submatriz. Estos polinomios se denominan polinomios de Bergman y proporcionan una base polinomial ortogonal para el espacio de Bergman.

Ver 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.ª ed., Sociedad de Matemáticas Industriales y Aplicadas (SIAM) ISBN  978-0-89871-685-6 , p. 307
3. Horn y Johnson 1985, pág. 35
4. Ramón García, Stephan; Cuerno, Roger (2017). Un segundo curso de álgebra lineal . Prensa de la Universidad de Cambridge. ISBN 9781107103818.
5. Bini, Darío A.; Robol, Leonardo (2016). "Reducción de Hessenberg cuasiseparable de diagonal real más matrices y aplicaciones de bajo rango". Á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 para 2016-10-21 Universidad de Cornell
7. "Rutinas computacionales (valores propios) en LAPACK". sitios.science.oregonstate.edu . Consultado el 24 de mayo de 2020 .

Referencias

• Cuerno, Roger A.; Johnson, Charles R. (1985), Análisis matricial , 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.
• Prensa, 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 informática científica (3.ª ed.), Nueva York: Cambridge University Press, ISBN 978-0-521-88068-8

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