Decomposição QR

Em álgebra linear, uma decomposição QR (também chamada de fatoração QR) de uma matriz é uma decomposição de uma matriz A em um produto A = QR de uma matriz ortogonal Q e uma matriz triangular superior R. A decomposição QR é usado frequentemente para resolver o problema de mínimos quadrados linear e é a base para um determinado algoritmo de autovalores, o algoritmo QR.

Casos e definições

Matriz quadrada

Toda matriz quadrada A com entradas reais pode ser decomposta como

$$A=QR,$$

em que Q é uma matriz ortogonal (suas colunas são vetores unitários ortogonais, isto é $Q^{\textsf {T}}Q=QQ^{\textsf {T}}=I$) e R é uma matriz triangular superior (também chamada de matriz triangular à direita). Se A é invertível, então a fatoração é única, se for exigido que os elementos da diagonal de R sejam positivos.

Se em vez disso A for uma matriz quadrada complexa, então há uma decomposição A = QR, em que Q é uma matriz unitária (então $Q^{*}Q=QQ^{*}=I$).

Se A tem n colunas linearmente independentes então as primeiras n colunas de Q formam uma base ortonormal para o espaço coluna de A. Mais geralmente, as primeiras k colunas de Q formam uma base ortonormal para o espaço gerado pelas primeiras k colunas de A para qualquer 1 ≤ k ≤ n. O fato de qualquer coluna k de A só depender das primeiras k colunas de Q é responsável pela forma triangular de R.

Matriz retangular

Mais geralmente, pode-se considerar uma matriz m×n complexa A, em que m ≥ n, como o produto de uma matriz unitária P de ordem m×m e uma matriz triangular superior R de ordem m×n. Como as (m−n) linhas inferiores de uma matriz triangular superior de ordem m×n consiste inteiramente de zeros, muitas vezes, é útil particionar R, ou tanto R quanto Q:

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

em que R₁ é uma matriz triangular superior de ordem n×n, 0 é uma matriz nula de ordem (m − n)×n, Q₁ é m×n, P₂ é m×(m − n) e tanto Q₁ quanto Q₂ têm colunas ortogonais.

Golub & Van Loan (1996, §5.2) chamam Q₁R₁ de fatoração QR magra de A; já Trefethen e Bau a chamam de fatoração QR reduzida. Se A é de posto cheio n e for exigido que os elementos da diagonal de R₁ sejam positivos, então, R₁ e P₁ são únicas, mas, em geral, Q₂ não é. R₁ é, então, igual ao fator triangular superior da fatoração de Cholesky de A* A (= A^TA se A é real).

Decomposições QL, RQ e LQ

De forma análoga, pode-se definir decomposições QL, RQ, e LQ, em que L é uma matriz triangular inferior.

Obtenção da decomposição QR

Existem vários métodos para calcular a decomposição QR, tais como o uso do processo de Gram–Schmidt, transformações Householder, ou rotações de Givens. Cada um tem suas vantagens e desvantagens.

Usando o processo de Gram–Schmidt

Considere o processo de Gram–Schmidt aplicado às colunas da matriz de posto completo por colunas $A=\left[\mathbf {a} _{1},\cdots ,\mathbf {a} _{n}\right],$ com o produto interno $\langle \mathbf {v} ,\mathbf {w} \rangle =\mathbf {v} ^{\textsf {T}}\mathbf {w}$ (ou $\langle \mathbf {v} ,\mathbf {w} \rangle =\mathbf {v} ^{*}\mathbf {w}$ no caso complexo).

Defina a projeção:

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

então:

$${\begin{aligned}\mathbf {u} _{1}&=\mathbf {a} _{1},&\mathbf {e} _{1}&={\mathbf {u} _{1} \over \|\mathbf {u} _{1}\|}\\\mathbf {u} _{2}&=\mathbf {a} _{2}-\operatorname {proj} _{\mathbf {u} _{1}}\,\mathbf {a} _{2},&\mathbf {e} _{2}&={\mathbf {u} _{2} \over \|\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}&={\mathbf {u} _{3} \over \|\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}&={\mathbf {u} _{k} \over \|\mathbf {u} _{k}\|}\end{aligned}}$$

Agora os $\mathbf {a} _{i}$s podem ser escritos em relação à recém calculada base ortonormal:

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

em que $\left\langle \mathbf {e} _{i},\mathbf {a} _{i}\right\rangle =\left\|\mathbf {u} _{i}\right\|.$ Isso pode ser escrito matricialmente como:

$$A=QR$$

onde:

$$Q=\left[\mathbf {e} _{1},\cdots ,\mathbf {e} _{n}\right]$$

e

$$R={\begin{pmatrix}\langle \mathbf {e} _{1},\mathbf {a} _{1}\rangle &\langle \mathbf {e} _{1},\mathbf {a} _{2}\rangle &\langle \mathbf {e} _{1},\mathbf {a} _{3}\rangle &\ldots \\0&\langle \mathbf {e} _{2},\mathbf {a} _{2}\rangle &\langle \mathbf {e} _{2},\mathbf {a} _{3}\rangle &\ldots \\0&0&\langle \mathbf {e} _{3},\mathbf {a} _{3}\rangle &\ldots \\\vdots &\vdots &\vdots &\ddots \end{pmatrix}}.$$

Exemplo

Considere a decomposição de

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

Lembre-se que uma matriz ortonormal $Q$ tem a propriedade

$$Q^{\textsf {T}}\,Q=I.$$

Então, pode-se calcular $Q$ por meio de Gram–Schmidt, da seguinte forma:

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

Assim, tem-se

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

Relação com a decomposição QR

A decomposição QR transforma uma matriz A em um produto de uma matriz triangular superior R (também conhecida como triangular direita) e uma matriz ortogonal Q. A única diferença em relação à decomposição QR é a ordem dessas matrizes.

A decomposição QR resulta da ortogonalização das colunas de A por Gram–Schmidt, iniciada a partir da primeira coluna.

A decomposição RQ resulta da ortogonalização das linhas de A por Gram–Schmidt, iniciada a partir da última linha.

Vantagens e desvantagens

O processo de Gram-Schmidt é inerentemente instável numericamente. Enquanto a aplicação das projeções tem uma atraente analogia geométrica para a ortogonalização, a ortogonalização propriamente dita é propensa a erros numéricos. Uma vantagem significativa, porém, é a facilidade de implementação, o que o torna um algoritmo útil para prototipagem se uma biblioteca de álgebra linear pré-construída não está disponível.

Usando reflexões de Householder

Reflexão de Householder para a decomposição QR: O objetivo é encontrar uma transformação linear que transforma o vetor $x$ em um vetor de mesmo comprimento que é colinear a $e_{1}.$ Poderia ser usada uma projeção ortogonal (Gram-Schmidt), mas isso seria numericamente instável se os vetores $x$ e $e_{1}$ fossem praticamente ortogonais. Em vez disso, a reflexão de Householder reflete através da linha pontilhada (escolhida para dividir o ângulo entre $x$ e $e_{1}$ao meio). O ângulo máximo com essa transformação é de 45 graus

Uma reflexão de Householder (ou transformação de Householder) é uma transformação que pega um vetor e reflete-o em relação a algum plano ou hiperplano. Pode-se utilizar esta operação para calcular a fatoração QR de uma matriz $A$de ordem m-por-n com m ≥ n.

Q pode ser utilizada para refletir um vetor de tal forma que todas as coordenadas exceto uma desapareçam.

Seja $\mathbf {x}$ ser um vetor coluna real arbitrário de $A$ de dimensão m, tal que $\|\mathbf {x} \|=|\alpha |$ para algum escalar α. Se o algoritmo é implementado usando a aritmética de ponto flutuante, então α deve receber o sinal contrário ao da k-ésima coordenada de $\mathbf {x} ,$ onde $x_{k}$ deve ser a coordenada pivô a partir da qual todas as entradas são 0 na forma triangular superior final de A, para evitar a perda de significância. No caso complexo, define-se

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

(Stoer & Bulirsch 2002, p. 225) e substitui-se a transposição, pela transposição seguida de conjugação para a construção de Q como abaixo.

Então, sendo $\mathbf {e} _{1}$ o vetor (1 0 ... 0)^T, ||·|| a norma Euclidiana e $I$ uma matriz identidade de ordem m-por-m, define-se

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

Ou, se $A$ é complexo

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

$Q$ é uma matriz de Householder de ordem m-por-m e

$$Q\mathbf {x} ={\begin{pmatrix}\alpha &0&\cdots &0\end{pmatrix}}^{\textsf {T}}.$$

Isso pode ser usado para transformar gradativamente uma matriz A de ordem m-por-n em uma matriz na forma triangular superior. Primeiramente, multiplica-se A pela matriz de Householder Q₁ que é obtida ao escolher a primeira matriz coluna para x. Isso resulta em uma matriz Q₁A com zeros na coluna da esquerda (exceto na primeira linha).

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

Este processo pode ser repetido para A' (obtida a partir de Q₁A ao excluir a primeira linha e a primeira coluna), resultando em uma matriz de Householder Q'₂. Note que Q'₂ é menor do que Q₁. Como a intenção é fazer com que ela atue em Q₁A em vez de A' é preciso expandi-la para o canto superior esquerdo, preenchendo-a com 1, ou em geral:

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

Depois de $t$ iterações do processo, $t=\min(m-1,n),$

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

é uma matriz triangular superior. Assim, com

$$Q=Q_{1}^{\textsf {T}}Q_{2}^{\textsf {T}}\cdots Q_{t}^{\textsf {T}},$$

$A=QR$ é uma decomposição QR de $A.$

Este método tem maior estabilidade numérica do que o método de Gram–Schmidt acima.

A tabela a seguir apresenta o número de operações na k-ésima etapa da decomposição QR pela transformação de Householder, assumindo uma matriz quadrada com tamanho n.

Operação	Número de operações no k-ésima etapa
Multiplicações	$2(n-k+1)^{2}$
Adições	$(n-k+1)^{2}+(n-k+1)(n-k)+2$
Divisão	$1$
Raiz quadrada	$1$

Somando esses números ao longo das n − 1 etapas (para uma matriz quadrada de ordem n), obtém-se que a complexidade do algoritmo (em termos de multiplicações em ponto flutuante) é dada por

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

Exemplo

Vamos calcular a decomposição de

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

Primeiro, é preciso encontrar uma reflexão que transforme a primeira coluna da matriz A, que é o vector $\mathbf {a} _{1}={\begin{pmatrix}12&6&-4\end{pmatrix}}^{\textsf {T}},$ em $\left\|\mathbf {a} _{1}\right\|\;\mathbf {e} _{1}={\begin{pmatrix}14&0&0\end{pmatrix}}^{\textsf {T}}.$

Agora,

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

e

$$\mathbf {v} ={\mathbf {u} \over \|\mathbf {u} \|}.$$

Aqui,

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

Portanto,

$$\mathbf {u} ={\begin{pmatrix}-2&6&-4\end{pmatrix}}^{\textsf {T}}={\begin{pmatrix}2\end{pmatrix}}{\begin{pmatrix}-1&3&-2\end{pmatrix}}^{\textsf {T}}$$ e $\mathbf {v} ={1 \over {\sqrt {14}}}{\begin{pmatrix}-1&3&-2\end{pmatrix}}^{\textsf {T}},$ e então $${\begin{aligned}Q_{1}={}&I-{2 \over {\sqrt {14}}{\sqrt {14}}}{\begin{pmatrix}-1\\3\\-2\end{pmatrix}}{\begin{pmatrix}-1&3&-2\end{pmatrix}}\\={}&I-{1 \over 7}{\begin{pmatrix}1&-3&2\\-3&9&-6\\2&-6&4\end{pmatrix}}\\={}&{\begin{pmatrix}6/7&3/7&-2/7\\3/7&-2/7&6/7\\-2/7&6/7&3/7\\\end{pmatrix}}.\end{aligned}}$$

Agora observe que:

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

assim já temos quase uma matriz triangular. Nós só precisamos zerar a entrada (3, 2).

Considere o menor (1, 1), e então aplique novamente o processo para

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

Pelo mesmo método acima, obtém-se a matriz da transformação de Householder

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

depois de realizar a soma direta com 1 para se certificar de que o próximo passo do processo funcione corretamente.

Agora, encontramos

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

Ou, com quatro casas decimais,

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

A matriz Q é ortogonal e R é triangular superior, de modo que A = QR é a decomposição QR desejada.

Vantagens e desvantagens

O uso de transformações de Householder é inerentemente o mais simples dos algoritmos de decomposição QR numericamente estáveis devido ao uso de reflexões como o mecanismo para a produção de zeros na matriz R. No entanto, o algoritmo de reflexão de Householder tem largura de banda pesada e não é paralelizável, já que cada reflexão que produz um novo elemento zero pode alterar completamente tanto a matriz Q quanto R.

Usando rotações de Givens

A decomposição QR também pode ser calculada com uma série de rotações de Givens. Cada rotação zera um elemento da subdiagonal da matriz, formando a matriz R. A concatenação de todas as rotações de Givens forma a matriz ortogonal Q.

Na prática, as rotações de Givens não são feitas construindo-se efetivamente uma matriz inteira para realizar uma multiplicação de matrizes. Em vez disso, um procedimento de rotação de Givens é utilizado, fazendo o equivalente de uma multiplicação de matrizes esparsas de Givens, sem o trabalho extra de manipular os elementos esparsos. O procedimento de rotação de Givens é útil em situações em que apenas um número relativamente pequeno de elementos fora da diagonal precisa ser zerado, e é paralelizado mais facilmente do que as transformações de Householder.

Exemplo

Vamos calcular a decomposição de

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

Primeiro, é necessário formar uma matriz de rotação que zere o elemento mais à esquerda e abaixo, $\mathbf {a} _{31}=-4.$ Esta matriz é formada utilizando o método de rotação de Givens, e é chamada de $G_{1}.$ Primeiramente o vetor ${\begin{pmatrix}12&-4\end{pmatrix}}$ será rotacionado para que aponte na direção do eixo X. Este vetor forma um ângulo $\theta =\arctan \left({-(-4) \over 12}\right).$ Deste modo é criada a matriz de rotação de Givens, $G_{1}:$

$${\begin{aligned}G_{1}&={\begin{pmatrix}\cos(\theta )&0&-\mathrm {sen} \,(\theta )\\0&1&0\\\mathrm {sen} \,(\theta )&0&\cos(\theta )\end{pmatrix}}\\&\approx {\begin{pmatrix}0.94868&0&-0.31622\\0&1&0\\0.31622&0&0.94868\end{pmatrix}}\end{aligned}}$$

E assim o resultado de $G_{1}A$ tem um zero no elemento $\mathbf {a} _{31}.$

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

Também é possível construir matrizes de Givens $G_{2}$ e $G_{3}$de forma análoga para zerar os elementos abaixo da diagonal principal, $a_{21}$ e $a_{32},$ formando uma matriz triangular $R.$ A matriz ortogonal $Q^{\textsf {T}}$ é formada a partir do produto de todas as matrizes de Givens $Q^{\textsf {T}}=G_{3}G_{2}G_{1}.$ Assim, tem-se $G_{3}G_{2}G_{1}A=Q^{\textsf {T}}A=R$e a decomposição QR é $A=QR.$

Vantagens e desvantagens

A decomposição QR através de rotações de Givens é mais complicada de implementar, uma vez que a ordenação necessária das linhas para explorar plenamente o algoritmo não pode ser determinada trivialmente. No entanto, ela tem uma vantagem significativa, pois cada novo elemento zero $a_{ij}$ afeta apenas a linha com o elemento a ser zerado (i) e uma linha acima (j). Isso torna o algoritmo da rotação de Givens mais eficiente em largura de banda e paralelizável, em contraste com a técnica de reflexão de Householder.

Conexão a um determinante ou um produto de autovalores

Pode-se utilizar a decomposição QR para encontrar o valor absoluto do determinante de uma matriz quadrada. Suponha que uma matriz seja decomposta como $A=QR.$ Então tem-se

$$\det(A)=\det(Q)\cdot \det(R).$$

Sendo Q unitária, $|\det(Q)|=1.$ Assim,

$$\left|\det(A)\right|=\left|\det(R)\right|=\left|\prod _{i}r_{ii}\right|,$$

em que $r_{ii}$ são as entradas da diagonal de R.

Além disso, como o determinante é igual ao produto dos autovalores, tem-se

$$\left|\prod _{i}r_{ii}\right|=\left|\prod _{i}\lambda _{i}\right|,$$

em que $\lambda _{i}$ são os autovalores de $A.$

Pode-se estender as propriedades acima para uma matriz complexa não quadrada $A$ introduzindo a definição de QR decomposição para matriz complexa não quadrada e substituindo os autovalores por valores singulares.

Suponha que haja uma decomposição QR para uma matriz não quadrada A:

$$A=Q{\begin{pmatrix}R\\O\end{pmatrix}},\qquad Q^{*}Q=I,$$

em que $O$ é uma matriz nula e $Q$ é uma matriz unitária.

A partir das propriedades da SVD e do determinante de matrizes, tem-se

$$\left|\prod _{i}r_{ii}\right|=\prod _{i}\sigma _{i},$$

em que $\sigma _{i}$ são os valores singulares de $A.$

Observe que os valores singulares de $A$ e $R$ são idênticos, apesar de seus autovalores complexos poderem ser diferentes. No entanto, se A é quadrada, o seguinte é verdadeiro:

$${\prod _{i}\sigma _{i}}=\left|{\prod _{i}\lambda _{i}}\right|.$$

Em conclusão, a decomposição QR pode ser utilizada de forma eficiente para calcular o produto dos autovalores ou valores singulares de uma matriz.

Pivotamento de colunas

A decomposição QR com o pivotamento de colunas introduz uma matriz de permutação P:

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

O pivotamento de colunas é útil quando A é (quase) deficiente em posto, ou se suspeita que seja assim. Ele também pode melhorar a precisão numérica. P é normalmente escolhida de modo a que os elementos da diagonal de R sejam não-crescentes: $\left|r_{11}\right|\geq \left|r_{22}\right|\geq \ldots \geq \left|r_{nn}\right|.$ Isso pode ser usado para encontrar o posto (numérico) de A com um custo computacional menor do que uma decomposição em valores singulares, formando a base dos chamados algoritmos QR reveladores do posto.

Uso para a solução de problemas inversos lineares

Comparado com a inversão direta de matrizes, soluções inversas usando a decomposição QR são mais estáveis numericamente, como evidenciado pelo seu número de condição reduzido [Parker, Geofísica Teoria Inversa, Ch1.13].

Para resolver o problema linear subdeterminado ($m<n$) $Ax=b$ em que a matriz A tem dimensões $m\times n$ e posto $m,$ primeiro encontra-se a fatoração QR da transposta de A: $A^{\textsf {T}}=QR,$ em que Q é uma matriz ortogonal (ou seja $Q^{\textsf {T}}=Q^{-1}$), e R tem uma forma especial: $R={\begin{bmatrix}R_{1}\\0\end{bmatrix}}.$ Aqui $R_{1}$ é uma matriz quadrada $m\times m$ triangular à direita, e a matriz nula tem ordem $(n-m)\times m.$ Após alguma álgebra, pode ser mostrado que uma solução para o problema inverso pode ser expressa como: $x=Q{\begin{bmatrix}\left(R_{1}^{\textsf {T}}\right)^{-1}b\\0\end{bmatrix}}$ onde se pode encontrar $R_{1}^{-1}$ por eliminação gaussiana ou pelo cálculo de $\left(R_{1}^{\textsf {T}}\right)^{-1}b$ diretamente por substituição direta. A segunda técnica tem maior precisão numérica e exige menos cálculos.

Para encontrar uma solução, ${\hat {x}},$ para o problema superdeterminado ($m\geq n$) $Ax=b$ que minimiza a norma $\|A{\hat {x}}-b\|,$ primeiro encontra-se a fatoração QR de A: $A=QR.$ A solução pode ser expressa como ${\hat {x}}=R_{1}^{-1}\left(Q_{1}^{\textsf {T}}b\right),$ onde $Q_{1}$ é uma matriz $m\times n$ contendo as primeiras $n$ colunas da base orthonormal completa $Q$ e onde $R_{1}$ é como antes. Tal como no caso subdeterminado, pode-se usar a substituição regressiva para encontrar este ${\hat {x}}$ de forma rápida e precisa, sem inverter $R_{1}$ explicitamente. ($Q_{1}$ e $R_{1}$ são muitas vezes fornecidos por bibliotecas numéricas como uma decomposição QR "econômica".)

Generalizações

A decomposição de Iwasawa generaliza a decomposição QR para grupos de Lie semissimples.

Ver também

• Decomposição polar
• Decomposição em autovalores
• Decomposição espectral
• Decomposição LU
• Decomposição em valores singulares

Leitura complementar

• Golub, Gene H.; Van Loan, Charles F. (1996), Matrix Computations, ISBN 978-0-8018-5414-9 3rd ed. , Johns Hopkins .
• Horn, Roger A.; Johnson, Charles R. (1985), Matrix Analysis, ISBN 0-521-38632-2, Cambridge University Press . Seção 2.8.
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), «Section 2.10. QR Decomposition», Numerical Recipes: The Art of Scientific Computing, ISBN 978-0-521-88068-8 3rd ed. , New York: Cambridge University Press 
• Stoer, Josef; Bulirsch, Roland (2002), Introduction to Numerical Analysis, ISBN 0-387-95452-X 3rd ed. , Springer .

Ligações externas

• Calculadora de Matrizes Online Executa a decomposição QR de matrizes.
• Manual de usuário do LAPACK fornece detalhes sobre as sub-rotinas para calcular a decomposição QR
• Manual de usuário do Mathematica fornece detalhes e exemplos de rotinas para calcular a decomposição QR
• ALGLIB inclui uma adaptação parcial do LAPACK para C++, C#, Delphi, etc.
• Eigen::QR Inclui uma implementação em C++ da decomposição QR.