Descomposición QR

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Matrix decomposition

En álgebra lineal, una descomposición QR, también conocida como factorización QR o factorización QU, es la 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 los mínimos cuadrados lineales y es la base de un algoritmo de valor propio particular, el algoritmo QR.

Casos y definiciones

Matriz cuadrada

Cualquier matriz cuadrada real A se puede descomponer como

{displaystyle A=QR,}

Donde Q es una matriz ortogonal (sus columnas son vectores de unidad ortogonal que significan ${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 necesitamos los elementos diagonales de R para ser positivo.

Si no A es una matriz cuadrada compleja, entonces hay una descomposición A = QR Donde Q es una matriz unitaria (so ${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 tramo de las primeras k columnas de A para cualquier 1 ≤ k ≤ n. 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.

Matriz rectangular

Más generalmente, 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 dividir R, o tanto R como Q:

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

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

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

Descomposiciones QL, RQ y LQ

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

Cálculo de la descomposición QR

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

Uso del proceso de Gram-Schmidt

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

Defina la proyección:

{displaystyle operatorname {proj} _{mathbf {u} }mathbf {a} ={frac {leftlangle mathbf {u}mathbf {a} rightrangle }{leftlangle mathbf {u}mathbf {u} rightrangle }}{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 $mathbf{a}_i$ s sobre nuestra base ortonormal recién computada:

{displaystyle {begin{aligned}mathbf {a} _{1}&=leftlangle mathbf {e} _{1},mathbf {a} _{1}rightrangle mathbf {e} _{1}\mathbf {a} _{2}&=leftlangle mathbf {e} _{1},mathbf {a} _{2}rightrangle mathbf {e} _{1}+leftlangle mathbf {e} _{2},mathbf {a} _{2}rightrangle mathbf {e} _{2}\mathbf {a} _{3}&=leftlangle mathbf {e} _{1},mathbf {a} _{3}rightrangle mathbf {e} _{1}+leftlangle mathbf {e} _{2},mathbf {a} _{3}rightrangle mathbf {e} _{2}+leftlangle mathbf {e} _{3},mathbf {a} _{3}rightrangle mathbf {e} _{3}\&;;vdots \mathbf {a} _{k}&=sum _{j=1}^{k}leftlangle mathbf {e} _{j},mathbf {a} _{k}rightrangle mathbf {e} _{j}end{aligned}}}

Donde ${displaystyle leftlangle mathbf {e} _{i},mathbf {a} _{i}rightrangle =left|mathbf {u} _{i}right|}$ . Esto se puede escribir en forma de matriz:

A = QR

donde:

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

{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&-41end{bmatrix}}.}

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

Entonces, podemos calcular $Q$ por medio de Gram-Schmidt como sigue:

{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&-33end{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/35end{bmatrix}}.end{aligned}}}

Por lo tanto, 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&35end{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, a partir de la primera columna.

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

Ventajas y desventajas

El proceso Gram-Schmidt es intrínsecamente 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.

Uso de reflejos de cabeza de familia

Reflexión de los accionistas para la descomposición QR: El objetivo es encontrar una transformación lineal que cambie el vector $mathbf {x}$ en un vector de la misma longitud que es collinear a ${mathbf e}_{1}$ . Podríamos usar una proyección ortogonal (Gram-Schmidt) pero esto será numéricamente inestable si los vectores $mathbf {x}$ y ${mathbf e}_{1}$ están cerca de la ortogonal. En su lugar, la reflexión del titular de la casa refleja a través de la línea punteada (elegido para bisectar el ángulo entre $mathbf {x}$ y ${mathbf e}_{1}$ ). El ángulo máximo con este transformado es de 45 grados.

Una reflexión de los propietarios (o Transformación de los propietarios) 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 QR factorización de una m-por-n matriz $A$ con m ≥ n.

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

Vamos $mathbf {x}$ ser un verdadero arbitrario m-dimensional vector de columna $A$ tales que $|mathbf{x}| = |alpha|$ para un escalar α. Si el algoritmo se implementa usando aritmética de punto flotante, entonces α debe conseguir el signo opuesto como el k-la coordenadas $mathbf {x}$ , Donde $x_{k}$ es ser la coordinación pivote después de la cual todas las entradas son 0 en matriz A's final superior triangular form, to avoid loss of significance. En el caso complejo, establecido

{displaystyle alpha =-e^{iarg 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? $mathbf {e} _{1}$ es el vector [1 0 ⋯ 0]^T, Silencioso· La vida eterna es la norma euclidiana $I$ es un m×m matriz de identidad, conjunto

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

O, si $A$ es complejo

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

$Q$ es un m-por-m Matriz de accionistas, que es simétrica y ortogonal (Hermitiano y unitario en el caso complejo), y

{displaystyle Qmathbf {x} ={begin{bmatrix}alpha \0\vdots \0end{bmatrix}}.}

Esto se puede usar para transformar gradualmente una matriz m-por-n A a una forma triangular superior. Primero, multiplicamos A con la matriz de jefe de hogar Q₁ que obtenemos cuando elegimos la primera columna de 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′ (obtenido de Q₁A eliminando la primera fila y primera columna), lo que da como resultado una matriz de cabeza de familia Q′₂. Tenga en cuenta que Q′₂ es menor que Q₁. Ya que queremos que realmente opere en Q₁A en lugar de A′, necesitamos expandirlo al arriba a la izquierda, rellenando con un 1, o en general:

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

Después $t$ iteraciones de este proceso, ${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}}}

$A = QR$ es una descomposición de QR $A$ .

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

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

Operación	Número de operaciones en el k- el paso
Multiplicaciones	${displaystyle 2(n-k+1)^{2}}$
Adiciones	${displaystyle (n-k+1)^{2}+(n-k+1)(n-k)+2}$
División	$1$
Base cuadrada	$1$

Al sumar 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 coma flotante) está dada por

{displaystyle {frac {2}{3}}n^{3}+n^{2}+{frac {1}{3}}n-2=Oleft(n^{3}right).}

Ejemplo

Calculemos la descomposición de

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

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

Ahora,

mathbf{u} = mathbf{x} - alphamathbf{e}_1,

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

Aquí,

{displaystyle alpha =14}

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

Por lo tanto

{displaystyle mathbf {u} ={begin{bmatrix}-2&6&-4end{bmatrix}}^{textsf {T}}=2{begin{bmatrix}-1&3&-2end{bmatrix}}^{textsf {T}}}

{displaystyle mathbf {v} ={frac {1}{sqrt {14}}}{begin{bmatrix}-1&3&-2end{bmatrix}}^{textsf {T}}}

, y luego

{displaystyle {begin{aligned}Q_{1}={}&I-{frac {2}{{sqrt {14}}{sqrt {14}}}}{begin{bmatrix}-1\3\-2end{bmatrix}}{begin{bmatrix}-1&3&-2end{bmatrix}}\={}&I-{frac {1}{7}}{begin{bmatrix}1&-3&2\-3&9&-6\2&-6&4end{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&-77end{bmatrix}},}

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

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

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

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

{displaystyle Q_{2}={begin{bmatrix}1&0&0\0&-7/25&24/25\0&24/25&7/25end{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/35end{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.9429end{bmatrix}}\R&=Q_{2}Q_{1}A=Q^{textsf {T}}A={begin{bmatrix}14&21&-14\0&175&-70\0&0&-35end{bmatrix}}.end{aligned}}}

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

Ventajas y desventajas

El uso de transformaciones de Householder es intrínsecamente el más simple de los algoritmos de descomposición QR numéricamente estables debido al uso de reflejos como mecanismo para producir ceros en la matriz R. Sin embargo, el algoritmo de reflexión de Householder tiene un gran ancho de banda y no se puede paralelizar, ya que cada reflexión que produce un nuevo elemento cero cambia la totalidad de las matrices Q y R.

Uso de rotaciones de Givens

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 ortogonal Q.

En la práctica, las rotaciones de 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 de Givens que hace el equivalente de la multiplicación de matrices dispersas 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 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

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

Primero, necesitamos formar una matriz de rotación que cero el elemento izquierdo más bajo, ${displaystyle a_{31}=-4}$ . Formamos esta matriz usando el método de rotación de Givens, y llamamos la matriz $G_{1}$ . Primero giraremos el vector ${displaystyle {begin{bmatrix}12&-4end{bmatrix}}}$ , para apuntar a lo largo de X Axis. Este vector tiene un ángulo ${textstyle theta =arctan left({frac {-(-4)}{12}}right)}$ . Creamos la matriz de rotación de Givens ortogonal, $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.94868end{bmatrix}}end{aligned}}}

Y el resultado de $G_1A$ ahora tiene un cero en el ${displaystyle a_{31}}$ elemento.

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

Podemos formarnos de forma similar $G_{2}$ y $G_{3}$ , que cero los elementos subdiagonales $a_{21}$ y $a_{32}$ , formando una matriz triangular $R$ . La matriz ortogonal ${displaystyle Q^{textsf {T}}}$ se forma del producto de todas las matrices Givens ${displaystyle Q^{textsf {T}}=G_{3}G_{2}G_{1}}$ . Así, tenemos ${displaystyle G_{3}G_{2}G_{1}A=Q^{textsf {T}}A=R}$ , y el QR descomposición es $A = QR$ .

Ventajas y desventajas

La descomposición QR a través de las rotaciones de Givens es la más implicada para implementar, ya que el orden de las filas requeridas para explotar completamente el algoritmo no es trivial para determinar. Sin embargo, tiene una ventaja significativa en que cada nuevo elemento cero $a_{ij}$ afecta sólo la fila con el elemento a ser cero (i) y una fila arriba (j). Esto hace que el algoritmo de rotación de Givens sea más eficiente y paralelizable que la técnica de reflexión de Householder.

Conexión a un determinante o producto de valores propios

Podemos utilizar la descomposición QR para encontrar el determinante de una matriz cuadrada. Supongamos que una matriz está descompuesta como $A = QR$ . Entonces tenemos

{displaystyle det A=det Qdet R.}

$Q$ puede ser elegido tal ${displaystyle det Q=1}$ . Así,

{displaystyle det A=det R=prod _{i}r_{ii}}

Donde $r_{ii}$ son las entradas en la diagonal de $R$ . Además, porque el determinante es igual al producto de los eigenvalues, tenemos

{displaystyle prod _{i}r_{ii}=prod _{i}lambda _{i}}

Donde $lambda _{i}$ son eigenvalues de $A$ .

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

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

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

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

De las propiedades de la SVD y del determinante de una matriz, tenemos

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

Donde $sigma _{i}$ son los valores singulares $A$ .

Note que los valores singulares $A$ y $R$ son idénticos, aunque sus complejos eigenvalues pueden ser diferentes. Sin embargo, si A es cuadrado, entonces

{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 (columna pivotante) y, por lo tanto, introduce una matriz de permutación P:

{displaystyle AP=QRquad iff quad A=QRP^{textsf {T}}}

El pivote de columna es útil cuando A es (casi) deficiente de rango, o se sospecha que es así. También puede mejorar la precisión numérica. P es generalmente elegido para que los elementos diagonales de R no están aumentando: ${displaystyle left|r_{11}right|geq left|r_{22}right|geq cdots geq left|r_{nn}right|}$ . Esto se puede utilizar para encontrar el rango (numerical) A a menor costo computacional que una descomposición de valor singular, formando la base de los llamados algoritmos QR que revelan rango.

Uso para solución de problemas lineales inversos

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

Para resolver los indeterminados () $<math alttext="{displaystyle mm.n{displaystyle m won} <img alt="m$ ) problema lineal ${displaystyle Amathbf {x} =mathbf {b} }$ donde la matriz $A$ dimensiones $mtimes n$ y rango $m$ , primero encontrar la factorización QR de la transposición $A$ : ${displaystyle A^{textsf {T}}=QR}$ , Donde Q es una matriz ortogonal (es decir, ${displaystyle Q^{textsf {T}}=Q^{-1}}$ ), y R tiene una forma especial: ${displaystyle R=left[{begin{smallmatrix}R_{1}\0end{smallmatrix}}right]}$ . Aquí. $R_{1}$ es un cuadrado $mtimes m$ matriz triangular derecha, y la matriz cero tiene dimensión $(n-m) times m$ . Después de un álgebra, se puede demostrar que una solución al problema inverso se puede expresar como: ${displaystyle mathbf {x} =Qleft[{begin{smallmatrix}left(R_{1}^{textsf {T}}right)^{-1}mathbf {b} \0end{smallmatrix}}right]}$ donde uno puede encontrar $R_1^{-1}$ por eliminación o computación de Gauss ${displaystyle left(R_{1}^{textsf {T}}right)^{-1}mathbf {b} }$ directamente por sustitución. Esta última técnica goza de mayor precisión numérica y de menor computación.

Para encontrar una solución ${displaystyle {hat {mathbf {x} }}}$ a los () $m geq n$ ) problema ${displaystyle Amathbf {x} =mathbf {b} }$ que minimiza la norma ${displaystyle left|A{hat {mathbf {x} }}-mathbf {b} right|}$ , primero encontrar la factorización QR $A$ : $A = QR$ . La solución puede entonces expresarse como ${displaystyle {hat {mathbf {x} }}=R_{1}^{-1}left(Q_{1}^{textsf {T}}mathbf {b} right)}$ , Donde $Q_{1}$ es un $mtimes n$ matriz que contiene la primera $n$ columnas de la base ortonormal completa $Q$ y dónde $R_{1}$ es como antes. Equivalente al caso subdeterminado, la sustitución posterior se puede utilizar para encontrar de forma rápida y precisa ${hat {mathbf {x} }}$ sin invertir explícitamente $R_{1}$ . () $Q_{1}$ y $R_{1}$ a menudo son proporcionados por bibliotecas numéricas como una descomposición QR "económica".)

Generalizaciones

Did you mean:

Iwasawa decomposition generalized QR decomposition to semisimple Lie groups.

Contenido relacionado

Más resultados...