Hispanopedia Wiki
Articulo de referencia

descomposición QR

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 matr...

Hispanopedia WikiContenido en espanolLectura gratuita

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 usa a menudo para resolver el problema de mínimos cuadrados lineales (LLS) y es la base de un algoritmo de valores propios en particular , el algoritmo QR . 

Casos y definiciones

Matriz cuadrada

Cualquier matriz cuadrada real A puede descomponerse como

A=QR,{\displaystyle A=QR,}

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

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)Q†=Q−1{\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 columna de A. De manera más general, las primeras k columnas de Q forman una base ortonormal para el espacio generado por 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 ] 

Interpretación geométrica de la descomposición QR en dos dimensiones, que muestra una transformación triangular superior seguida de una transformación ortogonal.

Matriz rectangular

De forma 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 enteramente en ceros, a menudo es útil particionar R , o tanto R como Q :

A=QR=Q[R10]=[Q1Q2][R10]=Q1R1,{\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 1 es una matriz triangular superior n × n , 0 es una matriz cero ( m − n )× n , Q 1 es m × n , Q 2 es m ×( m − n ) , y Q 1 y Q 2 tienen columnas ortogonales.

Golub y Van Loan (1996 , §5.2) llaman a Q 1 R 1 la factorización QR delgada de A ; Trefethen y Bau la llaman factorización QR reducida . [ 1 ] Si A tiene rango completo n y requerimos que los elementos diagonales de R 1 sean positivos, entonces R 1 y Q 1 son únicos, pero en general Q 2 no lo es. R 1 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 forma análoga, podemos definir las descomposiciones QL, RQ y LQ, donde L es 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 presenta 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.A=[a1⋯anorte]{\displaystyle A={\begin{bmatrix}\mathbf {a} _{1}&\cdots &\mathbf {a} _{n}\end{bmatrix}}}, con producto interno⟨v,w⟩=vTw{\displaystyle \langle \mathbf {v} ,\mathbf {w} \rangle =\mathbf {v} ^{\textsf {T}}\mathbf {w} }(o⟨v,w⟩=v†w{\displaystyle \langle \mathbf {v} ,\mathbf {w} \rangle =\mathbf {v} ^{\dagger }\mathbf {w} }para el caso complejo).

Defina la proyección :

proyectotú⁡a=⟨tú,a⟩⟨tú,tú⟩tú{\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:

tú1=a1,mi1=tú1‖tú1‖tú2=a2−proyectotú1⁡a2,mi2=tú2‖tú2‖tú3=a3−proyectotú1⁡a3−proyectotú2⁡a3,mi3=tú3‖tú3‖⋮⋮túk=ak−∑j=1k−1proyectotúj⁡ak,mik=túk‖túk‖{\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 laai{\displaystyle \mathbf {a} _{i}}s sobre nuestra base ortonormal recién calculada:

a1=⟨mi1,a1⟩mi1a2=⟨mi1,a2⟩mi1+⟨mi2,a2⟩mi2a3=⟨mi1,a3⟩mi1+⟨mi2,a3⟩mi2+⟨mi3,a3⟩mi3⋮ak=∑j=1k⟨mij,ak⟩mij{\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⟨mii,ai⟩=‖túi‖{\displaystyle \left\langle \mathbf {e} _{i},\mathbf {a} _{i}\right\rangle =\left\|\mathbf {u} _{i}\right\|}Esto se puede escribir en forma matricial :

A=QR{\displaystyle A=QR}

dónde:

Q=[mi1⋯minorte]{\displaystyle Q={\begin{bmatrix}\mathbf {e} _{1}&\cdots &\mathbf {e} _{n}\end{bmatrix}}}

y

R=[⟨mi1,a1⟩⟨mi1,a2⟩⟨mi1,a3⟩⋯⟨mi1,anorte⟩0⟨mi2,a2⟩⟨mi2,a3⟩⋯⟨mi2,anorte⟩00⟨mi3,a3⟩⋯⟨mi3,anorte⟩⋮⋮⋮⋱⋮000⋯⟨minorte,anorte⟩].{\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

Interpretación geométrica de la descomposición QR en tres dimensiones, que ilustra la estructura de la factorización como una transformación triangular superior seguida de una transformación ortogonal.

Consideremos la descomposición de

A=[12−5146167−68−424−41].{\displaystyle A={\begin{bmatrix}12&-51&4\\6&167&-68\\-4&24&-41\end{bmatrix}}.}

Recordemos que una matriz ortonormalQ{\displaystyle Q}tiene la propiedadQTQ=I{\displaystyle Q^{\textsf {T}}Q=I}.

Entonces, podemos calcularQ{\displaystyle Q}mediante el método de Gram-Schmidt de la siguiente manera:

U=[tú1tú2tú3]=[12−69−58/561586/5−430−33];Q=[tú1‖tú1‖tú2‖tú2‖tú3‖tú3‖]=[6/7−69/175−58/1753/7158/1756/175−2/76/35−33/35].{\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}}}

Por lo tanto, tenemos

QTA=QTQR=R;R=QTA=[1421−140175−700035].{\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 radica en el orden de estas matrices.

La descomposición QR es la ortogonalización de Gram-Schmidt de las columnas de A , comenzando 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 desde el punto de vista numérico. Si bien la aplicación de las proyecciones presenta una atractiva analogía geométrica con la ortogonalización, esta última es propensa a errores numéricos . Una ventaja significativa es su facilidad de implementación.

Utilizando las reflexiones de Householder

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

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

La función Q se puede utilizar para reflejar un vector de tal manera que todas las coordenadas, excepto una, desaparezcan.

Dejarincógnita{\displaystyle \mathbf {x} }sea ​​un vector columna real m -dimensional arbitrario deA{\displaystyle A}de tal manera que‖incógnita‖=|α|{\displaystyle \|\mathbf {x} \|=|\alpha |}para un escalar α . α debería tener el mismo signo que elk{\displaystyle k}-ésima coordenada deincógnita{\displaystyle \mathbf {x} }, dóndeincógnitak{\displaystyle x_{k}}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. Si el algoritmo se implementa utilizando aritmética de punto flotante , entonces α debe tener el signo opuesto para evitar la pérdida de significado (por ejemplo, cuandoincógnita{\displaystyle \mathbf {x} }es casi colineal conmi1{\displaystyle \mathbf {e} _{1}},‖tú‖{\displaystyle \|\mathbf {u} \|}se vuelve "pequeño" ytú/‖tú‖{\displaystyle \mathbf {u} /\|\mathbf {u} \|}es numéricamente inestable; el caso extremo es‖tú‖=0{\displaystyle \|\mathbf {u} \|=0}, lo que provoca que la división anterior dé como resultado NaN ).

En el caso complejo, establezca [ 2 ]

α=−miiarg⁡incógnitak‖incógnita‖{\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, ¿dónde?mi1{\displaystyle \mathbf {e} _{1}}es el vector [1 0 ⋯ 0] T , || · || es la norma euclidiana yI{\displaystyle I}es una matriz identidad m × m , conjunto

tú=incógnita−αmi1,v=tú‖tú‖,Q=I−2vvT.{\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, siA{\displaystyle A}es complejo

Q=I−2vv†.{\displaystyle Q=I-2\mathbf {v} \mathbf {v} ^{\dagger }.}

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

Qincógnita=[α0⋮0].{\displaystyle Q\mathbf {x} ={\begin{bmatrix}\alpha \\0\\\vdots \\0\end{bmatrix}}.}

Esto se puede usar para transformar gradualmente una matriz A de m por n a la forma triangular superior . Primero, multiplicamos A por la matriz de Householder Q 1 que obtenemos al elegir la primera columna de la matriz para x . Esto da como resultado una matriz Q 1 A con ceros en la columna izquierda (excepto en la primera fila).

Q1A=[α1⋆⋯⋆0⋮A′0]{\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 1 A eliminando la primera fila y la primera columna), lo que da como resultado una matriz de Householder Q ′ 2 . Nótese que Q ′ 2 es más pequeña que Q 1 . Como queremos que realmente opere sobre Q 1 A en lugar de A ′, necesitamos expandirla hacia la esquina superior izquierda, rellenando un 1, o en general:

Qk=[Ik−100Qk′].{\displaystyle Q_{k}={\begin{bmatrix}I_{k-1}&0\\0&Q_{k}'\end{bmatrix}}.}

Despuést{\displaystyle t}iteraciones de este proceso,t=min(metro−1,norte){\displaystyle t=\min(m-1,n)},

R=Qt⋯Q2Q1A{\displaystyle R=Q_{t}\cdots Q_{2}Q_{1}A}

es una matriz triangular superior. Entonces, con

QT=Qt⋯Q2Q1,Q=Q1TQ2T⋯QtT{\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}}\end{aligned}}}

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

Este método presenta una mayor estabilidad numérica que el método de Gram-Schmidt descrito anteriormente.

En las pruebas numéricas los factores calculadosQdo{\displaystyle Q_{c}}yRdo{\displaystyle R_{c}}satisfacer ‖QR−QdoRdo‖∞‖A‖∞=O(ε){\displaystyle {\frac {\|QR-Q_{c}R_{c}\|_{\infty }}{\|A\|_{\infty }}}=O(\varepsilon )} con precisión de máquina. Además, se conserva la ortogonalidad:‖QdoTQdo−I‖∞=O(ε){\displaystyle \|Q_{c}^{\mathsf {T}}Q_{c}-I\|_{\infty }=O(\varepsilon )}Sin embargo, la precisión deQdo{\displaystyle Q_{c}}yRdo{\displaystyle R_{c}}Disminución con el número de condición: ‖Q−Qdo‖∞=O(εκ∞(A)),‖R−Rdo‖∞‖R‖∞=O(εκ∞(A)).{\displaystyle \|Q-Q_{c}\|_{\infty }=O(\varepsilon \,\kappa _{\infty }(A)),\quad {\frac {\|R-R_{c}\|_{\infty }}{\|R\|_{\infty }}}=O(\varepsilon \,\kappa _{\infty }(A)).}

Por ejemplo, en condiciones adecuadas (norte=4000{\displaystyle n=4000},κ∞(A)≈3×103{\displaystyle \kappa _{\infty }(A)\approx 3\times 10^{3}}): ‖QR−QdoRdo‖∞‖A‖∞≈1.6×10−15,{\displaystyle {\frac {\|QR-Q_{c}R_{c}\|_{\infty }}{\|A\|_{\infty }}}\approx 1.6\times 10^{-15},}‖Q−Qdo‖∞≈1.6×10−15,{\displaystyle \|Q-Q_{c}\|_{\infty }\approx 1.6\times 10^{-15},}‖R−Rdo‖∞‖R‖∞≈4.3×10−14,{\displaystyle {\frac {\|R-R_{c}\|_{\infty }}{\|R\|_{\infty }}}\approx 4.3\times 10^{-14},}‖QdoTQdo−I‖∞≈1.1×10−13.{\displaystyle \|Q_{c}^{\mathsf {T}}Q_{c}-I\|_{\infty }\approx 1.1\times 10^{-13}.}

En una prueba mal condicionada (norte=4000{\displaystyle n=4000},κ∞(A)≈4×1018{\displaystyle \kappa _{\infty }(A)\approx 4\times 10^{18}}): ‖QR−QdoRdo‖∞‖A‖∞≈1.3×10−15,{\displaystyle {\frac {\|QR-Q_{c}R_{c}\|_{\infty }}{\|A\|_{\infty }}}\approx 1.3\times 10^{-15},}‖Q−Qdo‖∞≈5.2×10−4,{\displaystyle \|Q-Q_{c}\|_{\infty }\approx 5.2\times 10^{-4},}‖R−Rdo‖∞‖R‖∞≈1.2×10−4,{\displaystyle {\frac {\|R-R_{c}\|_{\infty }}{\|R\|_{\infty }}}\approx 1.2\times 10^{-4},}‖QdoTQdo−I‖∞≈1.1×10−13.{\displaystyle \|Q_{c}^{\mathsf {T}}Q_{c}-I\|_{\infty }\approx 1.1\times 10^{-13}.}[ 3 ]

La siguiente tabla muestra 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 de tamaño n .

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

23norte3+norte2+13norte−2=O(norte3).{\displaystyle {\frac {2}{3}}n^{3}+n^{2}+{\frac {1}{3}}n-2=O\left(n^{3}\right).}

Ejemplo

Calculemos la descomposición de

A=[12−5146167−68−424−41].{\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 , vectora1=[126−4]T{\displaystyle \mathbf {a} _{1}={\begin{bmatrix}12&6&-4\end{bmatrix}}^{\textsf {T}}}, en‖a1‖mi1=[α00]T{\displaystyle \left\|\mathbf {a} _{1}\right\|\mathbf {e} _{1}={\begin{bmatrix}\alpha &0&0\end{bmatrix}}^{\textsf {T}}}.

Ahora,

tú=incógnita−αmi1,{\displaystyle \mathbf {u} =\mathbf {x} -\alpha \mathbf {e} _{1},}

y

v=tú‖tú‖.{\displaystyle \mathbf {v} ={\frac {\mathbf {u} }{\|\mathbf {u} \|}}.}

Aquí,

α=14{\displaystyle \alpha =14}yincógnita=a1=[126−4]T{\displaystyle \mathbf {x} =\mathbf {a} _{1}={\begin{bmatrix}12&6&-4\end{bmatrix}}^{\textsf {T}}}

Por lo tanto

tú=[−26−4]T=2[−13−2]T{\displaystyle \mathbf {u} ={\begin{bmatrix}-2&6&-4\end{bmatrix}}^{\textsf {T}}=2{\begin{bmatrix}-1&3&-2\end{bmatrix}}^{\textsf {T}}}yv=114[−13−2]T{\displaystyle \mathbf {v} ={\frac {1}{\sqrt {14}}}{\begin{bmatrix}-1&3&-2\end{bmatrix}}^{\textsf {T}}}, y luego
Q1=I−21414[−13−2][−13−2]=I−17[1−32−39−62−64]=[6/73/7−2/73/7−2/76/7−2/76/73/7].{\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:

Q1A=[1421−140−49−140168−77],{\displaystyle Q_{1}A={\begin{bmatrix}14&21&-14\\0&-49&-14\\0&168&-77\end{bmatrix}},}

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

Toma el menor (1, 1) y luego aplica el proceso nuevamente a

A′=METRO11=[−49−14168−77].{\displaystyle A'=M_{11}={\begin{bmatrix}-49&-14\\168&-77\end{bmatrix}}.}

Mediante el mismo método descrito anteriormente, obtenemos la matriz de la transformación de Householder.

Q2=[1000−7/2524/25024/257/25]{\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 asegurarnos de que el siguiente paso del proceso funcione correctamente.

Ahora, encontramos

Q=Q1TQ2T=[6/7−69/17558/1753/7158/175−6/175−2/76/3533/35].{\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 bien, con cuatro dígitos decimales,

Q=Q1TQ2T=[0,8571−0,39430,33140,42860,9029−0,0343−0,28570,17140,9429]R=Q2Q1A=QTA=[1421−140175−7000−35].{\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 las transformaciones de Householder es intrínsecamente el más simple de los algoritmos de descomposición QR numéricamente estables debido al uso de reflexiones como mecanismo para generar ceros en la matriz R. Sin embargo, el algoritmo de reflexión de Householder requiere un gran ancho de banda y es difícil de paralelizar, ya que cada reflexión que produce un nuevo elemento cero modifica por completo las matrices Q y R.

Implementación paralela de Householder QR

El método Householder QR puede implementarse en paralelo con algoritmos como el TSQR (que significa Tall Skinny QR ). Este algoritmo se puede aplicar cuando la matriz A tiene m >> n . [ 4 ] Este algoritmo utiliza un árbol de reducción binaria para calcular la descomposición local de Householder QR en cada nodo en la pasada hacia adelante y reconstituir la matriz Q en la pasada hacia atrás. La estructura del árbol binario tiene como objetivo disminuir la cantidad de comunicación entre procesadores para aumentar el rendimiento.

Utilizando rotaciones de Givens

Las descomposiciones QR también pueden calcularse mediante una serie de rotaciones de Givens . Cada rotación anula un elemento de la subdiagonal de la matriz, formando así la matriz R. La concatenación de todas las rotaciones de Givens forma la matriz ortogonal Q.

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

Ejemplo

Calculemos la descomposición de

A=[12−5146167−68−424−41].{\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 inferior izquierdo,a31=−4{\displaystyle a_{31}=-4}. Formamos esta matriz utilizando el método de rotación de Givens y la llamamos matriz.GRAMO1{\displaystyle G_{1}}Primero rotaremos el vector.[12−4]{\displaystyle {\begin{bmatrix}12&-4\end{bmatrix}}}, para apuntar a lo largo del eje X. Este vector tiene un ánguloθ=arctan⁡(−(−4)12){\textstyle \theta =\arctan \left({\frac {-(-4)}{12}}\right)}. Creamos la matriz de rotación de Givens ortogonal,GRAMO1{\displaystyle G_{1}}:

GRAMO1=[porque⁡(θ)0−pecado⁡(θ)010pecado⁡(θ)0porque⁡(θ)]≈[0,948680−0,316220100,3162200,94868]{\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 deGRAMO1A{\displaystyle G_{1}A}ahora tiene un cero en ela31{\displaystyle a_{31}}elemento.

GRAMO1A≈[12.64911−55.9723116.760076167−6806.64078−37.6311]{\displaystyle G_{1}A\approx {\begin{bmatrix}12.64911&-55.97231&16.76007\\6&167&-68\\0&6.64078&-37.6311\end{bmatrix}}}

De forma similar, podemos formar matrices de Givens.GRAMO2{\displaystyle G_{2}}yGRAMO3{\displaystyle G_{3}}, lo que pondrá a cero los elementos subdiagonalesa21{\displaystyle a_{21}}ya32{\displaystyle a_{32}}, formando una matriz triangularR{\displaystyle R}La matriz ortogonalQT{\displaystyle Q^{\textsf {T}}}se forma a partir del producto de todas las matrices de GivensQT=GRAMO3GRAMO2GRAMO1{\displaystyle Q^{\textsf {T}}=G_{3}G_{2}G_{1}}. Por lo tanto, tenemosGRAMO3GRAMO2GRAMO1A=QTA=R{\displaystyle G_{3}G_{2}G_{1}A=Q^{\textsf {T}}A=R}y la descomposición QR esA=QR{\displaystyle A=QR}.

Ventajas y desventajas

La descomposición QR mediante rotaciones de Givens es la más compleja de implementar, ya que el orden de las filas necesario para aprovechar al máximo el algoritmo no es trivial de determinar. Sin embargo, tiene una ventaja significativa en que cada nuevo elemento ceroaij{\displaystyle a_{ij}}Afecta únicamente a la fila con el elemento que se va a poner a cero ( i ) y a la fila superior ( j ). Esto hace que el algoritmo de rotación de Givens sea más eficiente en cuanto a ancho de banda y más paralelizable que la técnica de reflexión de Householder.

Utilizando la multiplicación rápida de matrices

Es posible calcular la descomposición QR de forma rápida utilizando algoritmos rápidos de multiplicación de matrices en el tiempoO(norteω){\displaystyle O({n^{\omega }})}para 2.37≤ω<3{\displaystyle ~2.37\leq \omega <3}. [ 5 ] [ 6 ]

Relació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 comoA=QR{\displaystyle A=QR}. Entonces tenemos detA=detQdetR.{\displaystyle \det A=\det Q\det R.}

Q{\displaystyle Q}se puede elegir de tal manera quedetQ=1{\displaystyle \det Q=1}. De este modo, detA=detR=∏irii{\displaystyle \det A=\det R=\prod _{i}r_{ii}}

donde elrii{\displaystyle r_{ii}}son las entradas en la diagonal deR{\displaystyle R}Además, como el determinante es igual al producto de los autovalores, tenemos ∏irii=∏iλi{\displaystyle \prod _{i}r_{ii}=\prod _{i}\lambda _{i}}

donde elλi{\displaystyle \lambda _{i}}son los valores propios deA{\displaystyle A}.

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

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

A=Q[R0],Q†Q=I{\displaystyle A=Q{\begin{bmatrix}R\\0\end{bmatrix}},\qquad Q^{\dagger }Q=I}

dónde0{\displaystyle 0}denota la matriz cero yQ{\displaystyle Q}es una matriz unitaria.

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

|∏irii|=∏iσi,{\displaystyle {\Big |}\prod _{i}r_{ii}{\Big |}=\prod _{i}\sigma _{i},}

donde elσi{\displaystyle \sigma _{i}}son los valores singulares deA{\displaystyle A}.

Tenga en cuenta que los valores singulares deA{\displaystyle A}yR{\displaystyle R}son idénticos, aunque sus autovalores complejos pueden ser diferentes. Sin embargo, si A es cuadrado, entonces

∏iσi=|∏iλi|.{\displaystyle {\prod _{i}\sigma _{i}}={\Big |}\prod _{i}\lambda _{i}{\Big |}.}

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

Pivote de columna

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

APAG=QR⟺A=QRPAGT{\displaystyle AP=QR\quad \iff \quad A=QRP^{\textsf {T}}}

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

Utilización para la solución de problemas inversos lineales

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

Para resolver el problema subdeterminado (metro<norte{\displaystyle m<n}) problema linealAincógnita=b{\displaystyle A\mathbf {x} =\mathbf {b} }donde la matrizA{\displaystyle A}tiene dimensionesmetro×norte{\displaystyle m\times n}y rangometro{\displaystyle m}, primero encuentra la factorización QR de la transpuesta deA{\displaystyle A}:AT=QR{\displaystyle A^{\textsf {T}}=QR}, donde Q es una matriz ortogonal (es decir,QT=Q−1{\displaystyle Q^{\textsf {T}}=Q^{-1}}), y R tiene una forma especial:R=[R10]{\displaystyle R=\left[{\begin{smallmatrix}R_{1}\\0\end{smallmatrix}}\right]}. AquíR1{\displaystyle R_{1}}es un cuadradometro×metro{\displaystyle m\times m}matriz triangular recta, y la matriz cero tiene dimensión(norte−metro)×metro{\displaystyle (n-m)\times m}Tras algunos cálculos algebraicos , se puede demostrar que una solución al problema inverso se puede expresar como:incógnita=Q[(R1T)−1b0]{\displaystyle \mathbf {x} =Q\left[{\begin{smallmatrix}\left(R_{1}^{\textsf {T}}\right)^{-1}\mathbf {b} \\0\end{smallmatrix}}\right]}donde uno puede encontrarR1−1{\displaystyle R_{1}^{-1}}mediante eliminación gaussiana o cálculo(R1T)−1b{\displaystyle \left(R_{1}^{\textsf {T}}\right)^{-1}\mathbf {b} }directamente mediante sustitución hacia adelante . Esta última técnica ofrece mayor precisión numérica y menores cálculos.

Para encontrar una soluciónincógnita^{\displaystyle {\hat {\mathbf {x} }}}a lo sobredeterminado (metro≥norte{\displaystyle m\geq n}) problemaAincógnita=b{\displaystyle A\mathbf {x} =\mathbf {b} }lo cual minimiza la norma‖Aincógnita^−b‖{\displaystyle \left\|A{\hat {\mathbf {x} }}-\mathbf {b} \right\|}, primero encuentra la factorización QR deA{\displaystyle A}:A=QR{\displaystyle A=QR}La solución se puede expresar entonces comoincógnita^=R1−1(Q1Tb){\displaystyle {\hat {\mathbf {x} }}=R_{1}^{-1}\left(Q_{1}^{\textsf {T}}\mathbf {b} \right)}, dóndeQ1{\displaystyle Q_{1}}es unmetro×norte{\displaystyle m\times n}matriz que contiene la primeranorte{\displaystyle n}columnas de la base ortonormal completaQ{\displaystyle Q}y dóndeR1{\displaystyle R_{1}}es como antes. Equivalente al caso subdeterminado, la sustitución hacia atrás se puede utilizar para encontrar esto de forma rápida y precisa.incógnita^{\displaystyle {\hat {\mathbf {x} }}}sin invertir explícitamenteR1{\displaystyle R_{1}}. (Q1{\displaystyle Q_{1}}yR1{\displaystyle R_{1}}(A menudo, las bibliotecas numéricas las proporcionan como una descomposición QR "económica").

Generalizaciones

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

Véase también

Referencias

  1. 1 2 3 Trefethen, Lloyd N. ; Bau, David III (1997). Álgebra lineal numérica . Filadelfia, PA: Society for Industrial and Applied Mathematics . 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. ↑ Holmes, Mark H. (2023). Introducción a la computación científica y al análisis de datos, 2.ª ed . Springer. ISBN 978-3-031-22429-4.
  4. ↑ Demmel, James ; Grigori, Laura (12 de junio de 2008). "Factorizaciones QR y LU paralelas y secuenciales óptimas para la comunicación: teoría y práctica". arXiv : 0806.2159 [ cs.NA ].
  5. ^ Schönhage, A. (1972). "Unidades de transformación de grandes matrices". Matemática numérica . 20 : 409– 41. doi : 10.1007/BF01402563 .
  6. ↑ Knight, P. (1995). "Multiplicación rápida de matrices rectangulares y descomposición QR". Álgebra lineal y sus aplicaciones . 221 : 69–81 . doi : 10.1016/0024-3795(93)00230-W .
  7. ↑ 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.
  8. ↑ Parker, Robert L. (1994). Teoría inversa geofísica . Princeton, NJ: Princeton University Press. Sección 1.13. ISBN 978-0-691-20683-7OCLC 1134769155​​ 

Lecturas adicionales

  • Calculadora de matrices en línea. Realiza la descomposición QR de matrices.
  • El manual de usuario de LAPACK proporciona detalles sobre las subrutinas para calcular la descomposición QR.
  • El manual de usuario de Mathematica proporciona detalles y ejemplos de rutinas para calcular la descomposición QR.
  • ALGLIB incluye una adaptación parcial de LAPACK a C++, C#, Delphi, etc.
  • Eigen::QR incluye una implementación en C++ de la descomposición QR.
Lecturas relacionadas
6 articulos
Álgebra linealEn el espacio euclidiano tridimensional , estos tres planos representan soluciones de ecuaciones lineales y su intersección representa el conjunto ...{\displaystyle A\mathbf {x} =\mathbf {b} }Descomposición matricialEn la disciplina matemática del álgebra lineal , una descomposición matricial o factorización matricial es una factorización de una matriz en un pr...Dos corchetes altos con m filas, cada una de las cuales contiene n variables con la letra "a" como subíndice. A cada letra "a" se le asigna un número de fila y un número de columna como subíndice.Matriz (matemáticas)En matemáticas , una matriz ( pl.: matrices ) es una matriz rectangular o tabla de números , símbolos o expresiones , con elementos o entradas disp...{\displaystyle Q^{\mathrm {T} }Q=QQ^{\mathrm {T} }=I,}Matriz ortogonalEn álgebra lineal , una matriz ortogonal o matriz ortonormal Q es una matriz cuadrada de valores reales cuyas columnas y filas son vectores ortonor...{\displaystyle L={\begin{bmatrix}\ell _{1,1}&&&&0\\\ell _{2,1}&\ell _{2,2}&&&\\\ell _{3,1} &\ell _{3,2}&\ddots &&\\\vdots &\vdots &\ddots &\ddots &\\\ell _{n,1}&\ell _{n,2}&\ldots & \ell _{n,n-1}&\ell _{n,n}\end{bmatrix}}}Matriz triangularEn matemáticas, una matriz triangular es un tipo especial de matriz cuadrada . Una matriz cuadrada se llama.mw-parser-output .vanchor>:target~.vanc...Mínimos cuadrados linealesLos mínimos cuadrados lineales ( LLS ) son la aproximación de mínimos cuadrados de funciones lineales a datos. Es un conjunto de formulaciones para...