Descomposición QR

Descomposición matricial

En álgebra lineal , una descomposición QR , también conocida como factorización QR o factorización QU , es una descomposición de una matriz A en un producto A  =  QR de una matriz ortonormal Q y una matriz triangular superior R. La descomposición QR se utiliza a menudo para resolver el problema de mínimos cuadrados lineales (LLS) y es la base de un algoritmo de valor propio particular , el algoritmo QR .

Casos y definiciones

Matriz cuadrada

Cualquier matriz cuadrada real A puede descomponerse como

${\displaystyle A=QR,}$

donde Q es una matriz ortogonal (sus columnas son vectores unitarios ortogonales , es decir , ) y R es una matriz triangular superior (también llamada matriz triangular recta). Si A es invertible , entonces la factorización es única si requerimos que los elementos diagonales de R sean positivos. ${\displaystyle Q^{\textsf {T}}=Q^{-1}}$

Si en cambio A es una matriz cuadrada compleja, entonces existe una descomposición A = QR donde Q es una matriz unitaria (por lo que la transpuesta conjugada es ). ${\displaystyle Q^{\dagger }=Q^{-1}}$

Si A tiene n columnas linealmente independientes , entonces las primeras n columnas de Q forman una base ortonormal para el espacio de columnas de A . De manera más general, las primeras k columnas de Q forman una base ortonormal para el espacio de las primeras k columnas de A para cualquier 1 ≤ k ≤ n . ^[1] El hecho de que cualquier columna k de A solo dependa de las primeras k columnas de Q corresponde a la forma triangular de  R . ^[1]

Matriz rectangular

De manera más general, podemos factorizar una matriz compleja m × n A , con m ≥ n , como el producto de una matriz unitaria m × m Q y una matriz triangular superior m × n R . Como las filas inferiores ( m − n ) de una matriz triangular superior m × n consisten completamente en ceros, a menudo es útil particionar R , o tanto R como Q :

${\displaystyle A=QR=Q{\begin{bmatrix}R_{1}\\0\end{bmatrix}}={\begin{bmatrix}Q_{1}&Q_{2}\end{bmatrix}}{\begin{bmatrix}R_{1}\\0\end{bmatrix}}=Q_{1}R_{1},}$

donde R ₁ es una matriz triangular superior n × n , 0 es una matriz cero ( m − n )× n , Q ₁ es m × n , Q ₂ es m ×( m − n ) , y Q ₁ y Q ₂ tienen columnas ortogonales.

Golub y Van Loan (1996, §5.2) llaman a Q ₁ R ₁ la factorización QR delgada de A ; Trefethen y Bau la llaman la factorización QR reducida . ^[1] Si A es de rango completo n y requerimos que los elementos diagonales de R ₁ sean positivos, entonces R ₁ y Q ₁ son únicos, pero en general Q ₂ no lo es. R ₁ es entonces igual al factor triangular superior de la descomposición de Cholesky de A * A (=  A ^T A si A es real).

Descomposiciones QL, RQ y LQ

De manera análoga, podemos definir descomposiciones QL, RQ y LQ, siendo L una matriz triangular inferior .

Cálculo de la descomposición QR

Existen varios métodos para calcular la descomposición QR, como el proceso de Gram-Schmidt , las transformaciones de Householder o las rotaciones de Givens . Cada uno de ellos tiene una serie de ventajas y desventajas.

Utilizando el proceso de Gram-Schmidt

Consideremos el proceso de Gram-Schmidt aplicado a las columnas de la matriz de rango de columna completa , con producto interno (o para el caso complejo). ${\displaystyle A={\begin{bmatrix}\mathbf {a} _{1}&\cdots &\mathbf {a} _{n}\end{bmatrix}}}$ ${\displaystyle \langle \mathbf {v} ,\mathbf {w} \rangle =\mathbf {v} ^{\textsf {T}}\mathbf {w} }$ ${\displaystyle \langle \mathbf {v} ,\mathbf {w} \rangle =\mathbf {v} ^{\dagger }\mathbf {w} }$

Definir la proyección :

${\displaystyle \operatorname {proj} _{\mathbf {u} }\mathbf {a} ={\frac {\left\langle \mathbf {u} ,\mathbf {a} \right\rangle }{\left\langle \mathbf {u} ,\mathbf {u} \right\rangle }}{\mathbf {u} }}$

entonces:

${\displaystyle {\begin{aligned}\mathbf {u} _{1}&=\mathbf {a} _{1},&\mathbf {e} _{1}&={\frac {\mathbf {u} _{1}}{\|\mathbf {u} _{1}\|}}\\\mathbf {u} _{2}&=\mathbf {a} _{2}-\operatorname {proj} _{\mathbf {u} _{1}}\mathbf {a} _{2},&\mathbf {e} _{2}&={\frac {\mathbf {u} _{2}}{\|\mathbf {u} _{2}\|}}\\\mathbf {u} _{3}&=\mathbf {a} _{3}-\operatorname {proj} _{\mathbf {u} _{1}}\mathbf {a} _{3}-\operatorname {proj} _{\mathbf {u} _{2}}\mathbf {a} _{3},&\mathbf {e} _{3}&={\frac {\mathbf {u} _{3}}{\|\mathbf {u} _{3}\|}}\\&\;\;\vdots &&\;\;\vdots \\\mathbf {u} _{k}&=\mathbf {a} _{k}-\sum _{j=1}^{k-1}\operatorname {proj} _{\mathbf {u} _{j}}\mathbf {a} _{k},&\mathbf {e} _{k}&={\frac {\mathbf {u} _{k}}{\|\mathbf {u} _{k}\|}}\end{aligned}}}$

Ahora podemos expresar s sobre nuestra base ortonormal recién calculada: ${\displaystyle \mathbf {a} _{i}}$

${\displaystyle {\begin{aligned}\mathbf {a} _{1}&=\left\langle \mathbf {e} _{1},\mathbf {a} _{1}\right\rangle \mathbf {e} _{1}\\\mathbf {a} _{2}&=\left\langle \mathbf {e} _{1},\mathbf {a} _{2}\right\rangle \mathbf {e} _{1}+\left\langle \mathbf {e} _{2},\mathbf {a} _{2}\right\rangle \mathbf {e} _{2}\\\mathbf {a} _{3}&=\left\langle \mathbf {e} _{1},\mathbf {a} _{3}\right\rangle \mathbf {e} _{1}+\left\langle \mathbf {e} _{2},\mathbf {a} _{3}\right\rangle \mathbf {e} _{2}+\left\langle \mathbf {e} _{3},\mathbf {a} _{3}\right\rangle \mathbf {e} _{3}\\&\;\;\vdots \\\mathbf {a} _{k}&=\sum _{j=1}^{k}\left\langle \mathbf {e} _{j},\mathbf {a} _{k}\right\rangle \mathbf {e} _{j}\end{aligned}}}$

donde . Esto se puede escribir en forma matricial: ${\displaystyle \left\langle \mathbf {e} _{i},\mathbf {a} _{i}\right\rangle =\left\|\mathbf {u} _{i}\right\|}$

${\displaystyle A=QR}$

dónde:

${\displaystyle Q={\begin{bmatrix}\mathbf {e} _{1}&\cdots &\mathbf {e} _{n}\end{bmatrix}}}$

y

${\displaystyle R={\begin{bmatrix}\langle \mathbf {e} _{1},\mathbf {a} _{1}\rangle &\langle \mathbf {e} _{1},\mathbf {a} _{2}\rangle &\langle \mathbf {e} _{1},\mathbf {a} _{3}\rangle &\cdots &\langle \mathbf {e} _{1},\mathbf {a} _{n}\rangle \\0&\langle \mathbf {e} _{2},\mathbf {a} _{2}\rangle &\langle \mathbf {e} _{2},\mathbf {a} _{3}\rangle &\cdots &\langle \mathbf {e} _{2},\mathbf {a} _{n}\rangle \\0&0&\langle \mathbf {e} _{3},\mathbf {a} _{3}\rangle &\cdots &\langle \mathbf {e} _{3},\mathbf {a} _{n}\rangle \\\vdots &\vdots &\vdots &\ddots &\vdots \\0&0&0&\cdots &\langle \mathbf {e} _{n},\mathbf {a} _{n}\rangle \\\end{bmatrix}}.}$

Ejemplo

Considere la descomposición de

${\displaystyle A={\begin{bmatrix}12&-51&4\\6&167&-68\\-4&24&-41\end{bmatrix}}.}$

Recordemos que una matriz ortonormal tiene la propiedad . ${\displaystyle Q}$ ${\displaystyle Q^{\textsf {T}}Q=I}$

Luego podemos calcular mediante Gram–Schmidt lo siguiente: ${\displaystyle Q}$

${\displaystyle {\begin{aligned}U={\begin{bmatrix}\mathbf {u} _{1}&\mathbf {u} _{2}&\mathbf {u} _{3}\end{bmatrix}}&={\begin{bmatrix}12&-69&-58/5\\6&158&6/5\\-4&30&-33\end{bmatrix}};\\Q={\begin{bmatrix}{\frac {\mathbf {u} _{1}}{\|\mathbf {u} _{1}\|}}&{\frac {\mathbf {u} _{2}}{\|\mathbf {u} _{2}\|}}&{\frac {\mathbf {u} _{3}}{\|\mathbf {u} _{3}\|}}\end{bmatrix}}&={\begin{bmatrix}6/7&-69/175&-58/175\\3/7&158/175&6/175\\-2/7&6/35&-33/35\end{bmatrix}}.\end{aligned}}}$

Así pues, tenemos

${\displaystyle {\begin{aligned}Q^{\textsf {T}}A&=Q^{\textsf {T}}Q\,R=R;\\R&=Q^{\textsf {T}}A={\begin{bmatrix}14&21&-14\\0&175&-70\\0&0&35\end{bmatrix}}.\end{aligned}}}$

Relación con la descomposición RQ

La descomposición RQ transforma una matriz A en el producto de una matriz triangular superior R (también conocida como triangular derecha) y una matriz ortogonal Q. La única diferencia con la descomposición QR es el orden de estas matrices.

La descomposición QR es la ortogonalización de Gram-Schmidt de las columnas de A , iniciada desde la primera columna.

La descomposición RQ es la ortogonalización de Gram-Schmidt de las filas de A , comenzando desde la última fila.

Ventajas y desventajas

El proceso de Gram-Schmidt es inherentemente inestable numéricamente. Si bien la aplicación de las proyecciones tiene una analogía geométrica atractiva con la ortogonalización, la ortogonalización en sí misma es propensa a errores numéricos. Una ventaja significativa es la facilidad de implementación.

Utilizando las reflexiones de los jefes de hogar

Reflexión de Householder para descomposición QR: el objetivo es encontrar una transformación lineal que cambie el vector en un vector de la misma longitud que sea colineal a . Podríamos usar una proyección ortogonal (Gram-Schmidt), pero esto será numéricamente inestable si los vectores y son casi ortogonales. En cambio, la reflexión de Householder se refleja a través de la línea de puntos (elegida para bisecar el ángulo entre y ). El ángulo máximo con esta transformación es de 45 grados. ${\displaystyle \mathbf {x} }$ ${\displaystyle \mathbf {e} _{1}}$ ${\displaystyle \mathbf {x} }$ ${\displaystyle \mathbf {e} _{1}}$ ${\displaystyle \mathbf {x} }$ ${\displaystyle \mathbf {e} _{1}}$

Una reflexión de Householder (o transformación de Householder ) es una transformación que toma un vector y lo refleja sobre algún plano o hiperplano . Podemos utilizar esta operación para calcular la factorización QR de una matriz m por n con m ≥ n . ${\displaystyle A}$

Q se puede utilizar para reflejar un vector de tal manera que todas las coordenadas excepto una desaparezcan.

Sea un vector columna real arbitrario de dimensión m de tal que para un escalar α . Si el algoritmo se implementa utilizando aritmética de punto flotante , entonces α debe tener el signo opuesto como la coordenada k -ésima de , donde debe ser la coordenada pivote después de la cual todas las entradas son 0 en la forma triangular superior final de la matriz A , para evitar la pérdida de significancia . En el caso complejo, establezca ^[2] ${\displaystyle \mathbf {x} }$ ${\displaystyle A}$ ${\displaystyle \|\mathbf {x} \|=|\alpha |}$ ${\displaystyle \mathbf {x} }$ ${\displaystyle x_{k}}$

${\displaystyle \alpha =-e^{i\arg x_{k}}\|\mathbf {x} \|}$

y sustituir la transposición por la transposición conjugada en la construcción de Q a continuación.

Entonces, donde es el vector [1 0 ⋯ 0] ^T , || · || es la norma euclidiana y es una matriz identidad m × m , establecida ${\displaystyle \mathbf {e} _{1}}$ ${\displaystyle I}$

${\displaystyle {\begin{aligned}\mathbf {u} &=\mathbf {x} -\alpha \mathbf {e} _{1},\\\mathbf {v} &={\frac {\mathbf {u} }{\|\mathbf {u} \|}},\\Q&=I-2\mathbf {v} \mathbf {v} ^{\textsf {T}}.\end{aligned}}}$

O si es complejo ${\displaystyle A}$

${\displaystyle Q=I-2\mathbf {v} \mathbf {v} ^{\dagger }.}$

${\displaystyle Q}$es una matriz Householder de m por m , que es a la vez simétrica y ortogonal (hermítica y unitaria en el caso complejo), y

${\displaystyle Q\mathbf {x} ={\begin{bmatrix}\alpha \\0\\\vdots \\0\end{bmatrix}}.}$

Esto se puede utilizar para transformar gradualmente una matriz A de m por n a la forma triangular superior . Primero, multiplicamos A por la matriz de jefes de hogar Q ₁ que obtenemos cuando elegimos la primera columna de la matriz para x . Esto da como resultado una matriz Q ₁ A con ceros en la columna izquierda (excepto en la primera fila).

${\displaystyle Q_{1}A={\begin{bmatrix}\alpha _{1}&\star &\cdots &\star \\0&&&\\\vdots &&A'&\\0&&&\end{bmatrix}}}$

Esto se puede repetir para A ′ (obtenido de Q ₁ A eliminando la primera fila y la primera columna), lo que da como resultado una matriz de jefes de hogar Q ′ ₂ . Nótese que Q ′ ₂ es menor que Q ₁ . Como queremos que realmente opere en Q ₁ A en lugar de A ′ , necesitamos expandirlo hacia la parte superior izquierda, completando con un 1, o en general:

${\displaystyle Q_{k}={\begin{bmatrix}I_{k-1}&0\\0&Q_{k}'\end{bmatrix}}.}$

Después de iteraciones de este proceso, , ${\displaystyle t}$ ${\displaystyle t=\min(m-1,n)}$

${\displaystyle R=Q_{t}\cdots Q_{2}Q_{1}A}$

es una matriz triangular superior. Por lo tanto, con

${\displaystyle {\begin{aligned}Q^{\textsf {T}}&=Q_{t}\cdots Q_{2}Q_{1},\\Q&=Q_{1}^{\textsf {T}}Q_{2}^{\textsf {T}}\cdots Q_{t}^{\textsf {T}},\\&=Q_{1}Q_{2}\cdots Q_{t},\end{aligned}}}$

${\displaystyle A=QR}$es una descomposición QR de . ${\displaystyle A}$

Este método tiene mayor estabilidad numérica que el método de Gram-Schmidt mencionado anteriormente.

La siguiente tabla muestra el número de operaciones en el k -ésimo paso de la descomposición QR por la transformación de Householder, asumiendo una matriz cuadrada con tamaño n .

Sumando estos números en los pasos n − 1 (para una matriz cuadrada de tamaño n ), la complejidad del algoritmo (en términos de multiplicaciones de punto flotante) viene dada por

${\displaystyle {\frac {2}{3}}n^{3}+n^{2}+{\frac {1}{3}}n-2=O\left(n^{3}\right).}$

Ejemplo

Calculemos la descomposición de

${\displaystyle A={\begin{bmatrix}12&-51&4\\6&167&-68\\-4&24&-41\end{bmatrix}}.}$

Primero, necesitamos encontrar una reflexión que transforme la primera columna de la matriz A , el vector , en . ${\displaystyle \mathbf {a} _{1}={\begin{bmatrix}12&6&-4\end{bmatrix}}^{\textsf {T}}}$ ${\displaystyle \left\|\mathbf {a} _{1}\right\|\mathbf {e} _{1}={\begin{bmatrix}\alpha &0&0\end{bmatrix}}^{\textsf {T}}}$

Ahora,

${\displaystyle \mathbf {u} =\mathbf {x} -\alpha \mathbf {e} _{1},}$

y

${\displaystyle \mathbf {v} ={\frac {\mathbf {u} }{\|\mathbf {u} \|}}.}$

Aquí,

${\displaystyle \alpha =14}$y ${\displaystyle \mathbf {x} =\mathbf {a} _{1}={\begin{bmatrix}12&6&-4\end{bmatrix}}^{\textsf {T}}}$

Por lo tanto

${\displaystyle \mathbf {u} ={\begin{bmatrix}-2&6&-4\end{bmatrix}}^{\textsf {T}}=2{\begin{bmatrix}-1&3&-2\end{bmatrix}}^{\textsf {T}}}$y , y luego ${\displaystyle \mathbf {v} ={\frac {1}{\sqrt {14}}}{\begin{bmatrix}-1&3&-2\end{bmatrix}}^{\textsf {T}}}$

${\displaystyle {\begin{aligned}Q_{1}={}&I-{\frac {2}{{\sqrt {14}}{\sqrt {14}}}}{\begin{bmatrix}-1\\3\\-2\end{bmatrix}}{\begin{bmatrix}-1&3&-2\end{bmatrix}}\\={}&I-{\frac {1}{7}}{\begin{bmatrix}1&-3&2\\-3&9&-6\\2&-6&4\end{bmatrix}}\\={}&{\begin{bmatrix}6/7&3/7&-2/7\\3/7&-2/7&6/7\\-2/7&6/7&3/7\\\end{bmatrix}}.\end{aligned}}}$

Ahora observe:

${\displaystyle Q_{1}A={\begin{bmatrix}14&21&-14\\0&-49&-14\\0&168&-77\end{bmatrix}},}$

Así que ya tenemos una matriz casi triangular. Solo nos falta poner a cero la entrada (3, 2).

Tome el menor (1, 1) y luego aplique el proceso nuevamente a

${\displaystyle A'=M_{11}={\begin{bmatrix}-49&-14\\168&-77\end{bmatrix}}.}$

Por el mismo método que el anterior, obtenemos la matriz de transformación Householder

${\displaystyle Q_{2}={\begin{bmatrix}1&0&0\\0&-7/25&24/25\\0&24/25&7/25\end{bmatrix}}}$

después de realizar una suma directa con 1 para asegurarse de que el siguiente paso del proceso funciona correctamente.

Ahora, encontramos

${\displaystyle Q=Q_{1}^{\textsf {T}}Q_{2}^{\textsf {T}}={\begin{bmatrix}6/7&-69/175&58/175\\3/7&158/175&-6/175\\-2/7&6/35&33/35\end{bmatrix}}.}$

O, hasta cuatro dígitos decimales,

${\displaystyle {\begin{aligned}Q&=Q_{1}^{\textsf {T}}Q_{2}^{\textsf {T}}={\begin{bmatrix}0.8571&-0.3943&0.3314\\0.4286&0.9029&-0.0343\\-0.2857&0.1714&0.9429\end{bmatrix}}\\R&=Q_{2}Q_{1}A=Q^{\textsf {T}}A={\begin{bmatrix}14&21&-14\\0&175&-70\\0&0&-35\end{bmatrix}}.\end{aligned}}}$

La matriz Q es ortogonal y R es triangular superior, por lo que A = QR es la descomposición QR requerida.

Ventajas y desventajas

El uso de transformaciones de Householder es inherentemente el más simple de los algoritmos de descomposición QR numéricamente estables debido al uso de reflexiones como mecanismo para producir ceros en la matriz R. Sin embargo, el algoritmo de reflexión de Householder requiere mucho ancho de banda y no es paralelizable, ya que cada reflexión que produce un nuevo elemento cero cambia la totalidad de las matrices Q y R.

Uso de rotaciones Givens

Las descomposiciones QR también se pueden calcular con una serie de rotaciones Givens . Cada rotación pone a cero un elemento en la subdiagonal de la matriz, formando la matriz R. La concatenación de todas las rotaciones Givens forma la matriz ortogonal Q.

En la práctica, las rotaciones Givens no se realizan construyendo una matriz completa y haciendo una multiplicación de matrices. En su lugar, se utiliza un procedimiento de rotación Givens que hace el equivalente de la multiplicación de matrices Givens dispersas, sin el trabajo adicional de manejar los elementos dispersos. El procedimiento de rotación Givens es útil en situaciones en las que solo es necesario poner a cero relativamente pocos elementos fuera de la diagonal y es más fácil de paralelizar que las transformaciones Householder .

Ejemplo

Calculemos la descomposición de

${\displaystyle A={\begin{bmatrix}12&-51&4\\6&167&-68\\-4&24&-41\end{bmatrix}}.}$

Primero, necesitamos formar una matriz de rotación que ponga a cero el elemento más inferior izquierdo, . Formamos esta matriz usando el método de rotación de Givens y llamamos a la matriz . Primero rotaremos el vector , para que apunte a lo largo del eje X. Este vector tiene un ángulo . Creamos la matriz de rotación ortogonal de Givens, : ${\displaystyle a_{31}=-4}$ ${\displaystyle G_{1}}$ ${\displaystyle {\begin{bmatrix}12&-4\end{bmatrix}}}$ ${\textstyle \theta =\arctan \left({\frac {-(-4)}{12}}\right)}$ ${\displaystyle G_{1}}$

${\displaystyle {\begin{aligned}G_{1}&={\begin{bmatrix}\cos(\theta )&0&-\sin(\theta )\\0&1&0\\\sin(\theta )&0&\cos(\theta )\end{bmatrix}}\\&\approx {\begin{bmatrix}0.94868&0&-0.31622\\0&1&0\\0.31622&0&0.94868\end{bmatrix}}\end{aligned}}}$

Y el resultado de ahora tiene un cero en el elemento. ${\displaystyle G_{1}A}$ ${\displaystyle a_{31}}$

${\displaystyle G_{1}A\approx {\begin{bmatrix}12.64911&-55.97231&16.76007\\6&167&-68\\0&6.64078&-37.6311\end{bmatrix}}}$

De manera similar, podemos formar matrices Givens y , que pondrán a cero los elementos subdiagonales y , formando una matriz triangular . La matriz ortogonal se forma a partir del producto de todas las matrices Givens . Por lo tanto, tenemos , y la descomposición QR es . ${\displaystyle G_{2}}$ ${\displaystyle G_{3}}$ ${\displaystyle a_{21}}$ ${\displaystyle a_{32}}$ ${\displaystyle R}$ ${\displaystyle Q^{\textsf {T}}}$ ${\displaystyle Q^{\textsf {T}}=G_{3}G_{2}G_{1}}$ ${\displaystyle G_{3}G_{2}G_{1}A=Q^{\textsf {T}}A=R}$ ${\displaystyle A=QR}$

Ventajas y desventajas

La descomposición QR mediante rotaciones de Givens es la más complicada de implementar, ya que el ordenamiento de las filas necesarias para explotar completamente el algoritmo no es fácil de determinar. Sin embargo, tiene una ventaja significativa en el sentido de que cada nuevo elemento cero afecta solo a la fila con el elemento que se va a poner a cero ( i ) y a una fila superior ( j ). Esto hace que el algoritmo de rotación de Givens sea más eficiente en cuanto al ancho de banda y paralelizable que la técnica de reflexión de Householder. ${\displaystyle a_{ij}}$

Conexión con un determinante o un producto de valores propios

Podemos utilizar la descomposición QR para hallar el determinante de una matriz cuadrada. Supongamos que una matriz se descompone como . Entonces tenemos ${\displaystyle A=QR}$ $${\displaystyle \det A=\det Q\det R.}$$

${\displaystyle Q}$se puede elegir de tal manera que . Por lo tanto, ${\displaystyle \det Q=1}$ $${\displaystyle \det A=\det R=\prod _{i}r_{ii}}$$

donde son las entradas en la diagonal de . Además, como el determinante es igual al producto de los valores propios, tenemos ${\displaystyle r_{ii}}$ ${\displaystyle R}$ $${\displaystyle \prod _{i}r_{ii}=\prod _{i}\lambda _{i}}$$

donde son valores propios de . ${\displaystyle \lambda _{i}}$ ${\displaystyle A}$

Podemos extender las propiedades anteriores a una matriz compleja no cuadrada introduciendo la definición de descomposición QR para matrices complejas no cuadradas y reemplazando los valores propios con valores singulares. ${\displaystyle A}$

Comencemos con una descomposición QR para una matriz no cuadrada A :

${\displaystyle A=Q{\begin{bmatrix}R\\0\end{bmatrix}},\qquad Q^{\dagger }Q=I}$

donde denota la matriz cero y es una matriz unitaria. ${\displaystyle 0}$ ${\displaystyle Q}$

A partir de las propiedades de la descomposición en valores singulares (SVD) y del determinante de una matriz, tenemos

${\displaystyle {\Big |}\prod _{i}r_{ii}{\Big |}=\prod _{i}\sigma _{i},}$

donde son los valores singulares de . ${\displaystyle \sigma _{i}}$ ${\displaystyle A}$

Nótese que los valores singulares de y son idénticos, aunque sus valores propios complejos pueden ser diferentes. Sin embargo, si A es cuadrado, entonces ${\displaystyle A}$ ${\displaystyle R}$

${\displaystyle {\prod _{i}\sigma _{i}}={\Big |}\prod _{i}\lambda _{i}{\Big |}.}$

De ello se deduce que la descomposición QR se puede utilizar para calcular eficientemente el producto de los valores propios o valores singulares de una matriz.

Columna pivotante

El QR pivotado se diferencia del Gram-Schmidt ordinario en que toma la columna restante más grande al comienzo de cada nuevo paso (pivotamiento de columnas) ^[3] y, por lo tanto, introduce una matriz de permutación P :

${\displaystyle AP=QR\quad \iff \quad A=QRP^{\textsf {T}}}$

El pivoteo de columnas es útil cuando A es (casi) deficiente en rango , o se sospecha que lo es. También puede mejorar la precisión numérica. P se elige generalmente de modo que los elementos diagonales de R no sean crecientes: . Esto se puede utilizar para encontrar el rango (numérico) de A con un menor costo computacional que una descomposición en valores singulares , formando la base de los llamados algoritmos QR de revelación de rango . ${\displaystyle \left|r_{11}\right|\geq \left|r_{22}\right|\geq \cdots \geq \left|r_{nn}\right|}$

Uso para la solución de problemas inversos lineales

En comparación con la matriz inversa directa, las soluciones inversas que utilizan la descomposición QR son numéricamente más estables, como lo evidencian sus números de condición reducidos . ^[4]

Para resolver el problema lineal subdeterminado ( ) ${\displaystyle m<n}$ donde la matriz tiene dimensiones y rango , primero encuentre la factorización QR de la transpuesta de : , donde Q es una matriz ortogonal (es decir ), y R tiene una forma especial: . Aquí hay una matriz triangular recta cuadrada, y la matriz cero tiene dimensión . Después de algo de álgebra, se puede demostrar que una solución al problema inverso se puede expresar como: donde uno puede encontrar por eliminación gaussiana o calcular directamente por sustitución hacia adelante . La última técnica disfruta de una mayor precisión numérica y cálculos más bajos. ${\displaystyle A\mathbf {x} =\mathbf {b} }$ ${\displaystyle A}$ ${\displaystyle m\times n}$ ${\displaystyle m}$ ${\displaystyle A}$ ${\displaystyle A^{\textsf {T}}=QR}$ ${\displaystyle Q^{\textsf {T}}=Q^{-1}}$ ${\displaystyle R=\left[{\begin{smallmatrix}R_{1}\\0\end{smallmatrix}}\right]}$ ${\displaystyle R_{1}}$ ${\displaystyle m\times m}$ ${\displaystyle (n-m)\times m}$ ${\displaystyle \mathbf {x} =Q\left[{\begin{smallmatrix}\left(R_{1}^{\textsf {T}}\right)^{-1}\mathbf {b} \\0\end{smallmatrix}}\right]}$ ${\displaystyle R_{1}^{-1}}$ ${\displaystyle \left(R_{1}^{\textsf {T}}\right)^{-1}\mathbf {b} }$

Para encontrar una solución al problema sobredeterminado ( ) que minimice la norma , primero encuentre la factorización QR de : . La solución puede entonces expresarse como , donde es una matriz que contiene las primeras columnas de la base ortonormal completa y donde es como antes. Equivalente al caso subdeterminado, se puede utilizar la sustitución hacia atrás para encontrar esto de forma rápida y precisa sin invertir explícitamente . ( y a menudo las bibliotecas numéricas las proporcionan como una descomposición QR "económica"). ${\displaystyle {\hat {\mathbf {x} }}}$ ${\displaystyle m\geq n}$ ${\displaystyle A\mathbf {x} =\mathbf {b} }$ ${\displaystyle \left\|A{\hat {\mathbf {x} }}-\mathbf {b} \right\|}$ ${\displaystyle A}$ ${\displaystyle A=QR}$ ${\displaystyle {\hat {\mathbf {x} }}=R_{1}^{-1}\left(Q_{1}^{\textsf {T}}\mathbf {b} \right)}$ ${\displaystyle Q_{1}}$ ${\displaystyle m\times n}$ ${\displaystyle n}$ ${\displaystyle Q}$ ${\displaystyle R_{1}}$ ${\displaystyle {\hat {\mathbf {x} }}}$ ${\displaystyle R_{1}}$ ${\displaystyle Q_{1}}$ ${\displaystyle R_{1}}$

Generalizaciones

La descomposición de Iwasawa generaliza la descomposición QR a grupos de Lie semisimples.

Véase también

• Descomposición polar
• Descomposición propia (descomposición espectral)
• Descomposición LU
• Descomposición en valores singulares

Referencias

1. Trefethen, Lloyd N. ; Bau, David III (1997). Álgebra lineal numérica . Filadelfia, PA: Sociedad de Matemáticas Industriales y Aplicadas . ISBN 978-0-898713-61-9.
2. Stoer, Josef; Bulirsch, Roland (2002), Introducción al análisis numérico (3.ª ed.), Springer, pág. 225, ISBN 0-387-95452-X
3. Strang, Gilbert (2019). Álgebra lineal y aprendizaje a partir de datos (1.ª ed.). Wellesley: Wellesley Cambridge Press. pág. 143. ISBN 978-0-692-19638-0.
4. Parker, Robert L. (1994). Teoría inversa geofísica. Princeton, NJ: Princeton University Press. Sección 1.13. ISBN 978-0-691-20683-7.OCLC 1134769155  .

Lectura adicional

• Golub, Gene H. ; Van Loan, Charles F. (1996), Cálculos matriciales (3.ª ed.), Johns Hopkins, ISBN 978-0-8018-5414-9.
• Horn, Roger A.; Johnson, Charles R. (1985), Análisis de matrices , Cambridge University Press, sec. 2.8, ISBN 0-521-38632-2
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Sección 2.10. Descomposición QR", Recetas numéricas: el arte de la computación científica (3.ª ed.), Nueva York: Cambridge University Press, ISBN 978-0-85-0-312-0 978-0-521-88068-8

Enlaces externos

• Calculadora de matrices en línea Realiza la descomposición QR de matrices.
• El manual del usuario de LAPACK proporciona detalles de las subrutinas para calcular la descomposición QR
• El manual del usuario de Mathematica proporciona detalles y ejemplos de rutinas para calcular la descomposición QR
• ALGLIB incluye un puerto parcial de LAPACK a C++, C#, Delphi, etc.
• Eigen::QR Incluye implementación en C++ de la descomposición QR.