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 valores propios 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 hay una descomposición A = QR donde Q es una matriz unitaria (por lo que la transpuesta conjugada ). ${\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 tramo de las primeras k columnas de A para cualquier 1 ≤ k ≤ n . ^[1] El hecho de que cualquier columna k de A sólo 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 A compleja de m × n , con m ≥ n , como el producto de una matriz unitaria Q de m × m y una matriz triangular superior R de m × n . Como las filas inferiores ( m − n ) de una matriz triangular superior m × n consisten enteramente en ceros, a menudo es útil dividir 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 de n × n , 0 es una matriz cero ( m − n ) × n , Q ₁ es m × n , Q ₂ es m × ( m − n ) y Q ₁ y Q ₂ son ambos tener columnas ortogonales.

Golub y Van Loan (1996, §5.2) llaman a Q ₁ R ₁ la factorización QR delgada de A ; Trefethen y Bau llaman a esto 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 .

Calcular 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 tiene una serie de ventajas y desventajas.

Usando el proceso de Gram-Schmidt

Considere 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}}}$

dónde . 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}}.}$

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

Entonces, podemos calcular mediante Gram-Schmidt de la siguiente manera: ${\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í, 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 rectángulo) 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 columnas de A , iniciada desde la primera columna.

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

Ventajas y desventajas

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

Usando reflexiones de cabeza de familia

Reflexión del hogar para la 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 con . Podríamos usar una proyección ortogonal (Gram-Schmidt), pero será numéricamente inestable si los vectores y son cercanos a la ortogonalidad. En cambio, el reflejo del jefe de familia se refleja a través de la línea de puntos (elegida para dividir 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 usar 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 menos una desaparezcan.

Sea un vector columna real arbitrario de m dimensiones tal que para un escalar α . Si el algoritmo se implementa utilizando aritmética de punto flotante , entonces α debería obtener el signo opuesto como la k -ésima coordenada de , donde será la coordenada de 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 significado . 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 sustituya la transposición por transposición conjugada en la construcción de Q a continuación.

Entonces, ¿dónde está 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 de Householder m -por- m , que es a la vez simétrica y ortogonal (hermitiana 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 cabeza de familia 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 de la 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 ′ (que se obtiene de Q ₁ A eliminando la primera fila y la primera columna), lo que da como resultado una matriz de cabeza de familia Q ′ ₂ . Tenga en cuenta que Q ′ ₂ es menor que Q ₁ . Como realmente queremos que opere en Q ₁ A en lugar de A ′, necesitamos expandirlo hacia la parte superior izquierda, completando 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. Entonces, 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 anterior.

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

Sumando estos números en los n − 1 pasos (para una matriz cuadrada de tamaño n ), la complejidad del algoritmo (en términos de multiplicaciones de coma 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 , 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 observa:

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

entonces ya tenemos casi una matriz triangular. Sólo necesitamos poner a cero la entrada (3, 2).

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

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

Por el mismo método anterior, obtenemos la matriz de la transformación del Hogar

${\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 funcione 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, con 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.

Usando rotaciones dadas

Las descomposiciones QR también se pueden calcular con una serie de rotaciones de 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 de Givens forma la matriz Q ortogonal.

En la práctica, las rotaciones de Givens en realidad no se realizan construyendo una matriz completa y haciendo una multiplicación de matrices. En su lugar, se utiliza un procedimiento de rotación de Givens que realiza el equivalente a la escasa multiplicación de matrices de Givens, sin el trabajo adicional de manejar los elementos dispersos. El procedimiento de rotación de Givens es útil en situaciones en las que sólo es necesario poner a cero relativamente pocos elementos fuera de la diagonal y se paraleliza más fácilmente que las transformaciones de 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 dadas 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 de Dados . 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 orden de las filas necesarias para explotar completamente el algoritmo no es trivial de determinar. Sin embargo, tiene una ventaja significativa en que cada nuevo elemento cero afecta solo a la fila con el elemento a poner a cero ( i ) y una fila por encima ( j ). Esto hace que el algoritmo de rotación de Givens sea más eficiente en 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 usar la descomposición QR para encontrar el determinante de una matriz cuadrada. Supongamos que una matriz se descompone como . Entonces nosotros tenemos ${\displaystyle A=QR}$

$${\displaystyle \det A=\det Q\det R.}$$

${\displaystyle Q}$se puede elegir tal que . De este modo, ${\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}$

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

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

De las propiedades de la descomposición en valores singulares (SVD) y el 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}$

Tenga en cuenta 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.

Pivotación de columnas

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

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

El giro de columnas es útil cuando A tiene (casi) un rango deficiente o se sospecha que lo tiene. También puede mejorar la precisión numérica. Generalmente se elige P 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 costo computacional menor que una descomposición en valor singular , formando la base de los llamados algoritmos QR reveladores 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 lineales inversos.

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

Para resolver el problema lineal indeterminado ( ) ${\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 rectángulo 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 se puede encontrar mediante eliminación gaussiana o calcular directamente mediante sustitución directa . Esta ú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 minimiza la norma , primero encuentre la factorización QR de : . Luego, la solución se puede expresar como , donde es una matriz que contiene las primeras columnas de la base ortonormal completa y donde es como antes. Equivalente al caso indeterminado, la sustitución hacia atrás se puede utilizar para encontrar esto de forma rápida y precisa sin invertir explícitamente . ( y, a menudo, las bibliotecas numéricas los 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.

Ver también

• Descomposición polar
• Descomposición de valores propios
• Descomposición espectral
• Descomposición LU
• Valor singular de descomposición

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. pag. 143.ISBN​ 978-0-692-19638-0.
4. Parker, Robert L. (1994). Teoría geofísica inversa. Princeton, Nueva Jersey: Princeton University Press. Sección 1.13. ISBN 978-0-691-20683-7. OCLC  1134769155.

Otras lecturas

• Golub, Gene H .; Van Loan, Charles F. (1996), Computaciones matriciales (3.ª ed.), Johns Hopkins, ISBN 978-0-8018-5414-9.
• Cuerno, Roger A.; Johnson, Charles R. (1985), Análisis matricial , Cambridge University Press, sec. 2.8, ISBN 0-521-38632-2
• Prensa, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Sección 2.10. Descomposición QR", 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

• Calculadora de matrices en línea Realiza la descomposición QR de matrices.
• El manual de usuario de LAPACK brinda detalles de subrutinas para calcular la descomposición QR
• El manual de usuario de Mathematica brinda 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 la implementación en C++ de la descomposición QR.