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^{\mathsf{\text{T}}}Q=Q{Q}^{\mathsf{\text{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=Q{Q}^{*}=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\left[\begin{array}{c}{R}_1\\ 0\end{array}\right]=\left[\begin{array}{c}{Q}_1,Q_2\end{array}\right]\left[\begin{array}{c}{R}_1\\ 0\end{array}\right]=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.

Predefinição:Harvtxt 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=[{𝐚}_1,\cdots ,{𝐚}_n],$ com o produto interno $⟨𝐯,𝐰⟩={𝐯}^{\mathsf{\text{T}}}𝐰$ (ou $⟨𝐯,𝐰⟩={𝐯}^{*}𝐰$ no caso complexo).

Defina a projeção:

$${\mathrm{proj}}_{𝐮}𝐚=\frac{⟨𝐮,𝐚⟩}{⟨𝐮,𝐮⟩}𝐮$$

então:

$$\begin{array}{cccc}{𝐮}_1& ={𝐚}_1,& {𝐞}_1& =\frac{{𝐮}_1}{\Vert {𝐮}_1\Vert }\\ {𝐮}_2& ={𝐚}_2-{\mathrm{proj}}_{{𝐮}_1}{𝐚}_2,& {𝐞}_2& =\frac{{𝐮}_2}{\Vert {𝐮}_2\Vert }\\ {𝐮}_3& ={𝐚}_3-{\mathrm{proj}}_{{𝐮}_1}{𝐚}_3-{\mathrm{proj}}_{{𝐮}_2}{𝐚}_3,& {𝐞}_3& =\frac{{𝐮}_3}{\Vert {𝐮}_3\Vert }\\ & ⋮& & ⋮\\ {𝐮}_k& ={𝐚}_k-\sum _{j=1}^{k-1}{\mathrm{proj}}_{{𝐮}_j}{𝐚}_k,& {𝐞}_k& =\frac{{𝐮}_k}{\Vert {𝐮}_k\Vert }\end{array}$$

Agora os ${𝐚}_i$s podem ser escritos em relação à recém calculada base ortonormal:

$$\begin{array}{cc}{𝐚}_1& =⟨{𝐞}_1,{𝐚}_1⟩{𝐞}_1\\ {𝐚}_2& =⟨{𝐞}_1,{𝐚}_2⟩{𝐞}_1+⟨{𝐞}_2,{𝐚}_2⟩{𝐞}_2\\ {𝐚}_3& =⟨{𝐞}_1,{𝐚}_3⟩{𝐞}_1+⟨{𝐞}_2,{𝐚}_3⟩{𝐞}_2+⟨{𝐞}_3,{𝐚}_3⟩{𝐞}_3\\ & ⋮\\ {𝐚}_k& =\sum _{j=1}^k⟨{𝐞}_j,{𝐚}_k⟩{𝐞}_j\end{array}$$

em que $⟨{𝐞}_i,{𝐚}_i⟩=\Vert {𝐮}_i\Vert .$ Isso pode ser escrito matricialmente como:

$$A=QR$$

onde:

$$Q=[{𝐞}_1,\cdots ,{𝐞}_n]$$

e

$$R=\left(\begin{array}{cccc}⟨{𝐞}_1,{𝐚}_1⟩& ⟨{𝐞}_1,{𝐚}_2⟩& ⟨{𝐞}_1,{𝐚}_3⟩& \dots \\ 0& ⟨{𝐞}_2,{𝐚}_2⟩& ⟨{𝐞}_2,{𝐚}_3⟩& \dots \\ 0& 0& ⟨{𝐞}_3,{𝐚}_3⟩& \dots \\ ⋮& ⋮& ⋮& \ddots \end{array}\right).$$

Exemplo

Considere a decomposição de

$$A=\left(\begin{array}{ccc}12& -51& 4\\ 6& 167& -68\\ -4& 24& -41\end{array}\right).$$

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

$$Q^{\mathsf{\text{T}}}Q=I.$$

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

$$\begin{array}{cc}U=\left(\begin{array}{ccc}{𝐮}_1& {𝐮}_2& {𝐮}_3\end{array}\right)& =\left(\begin{array}{ccc}12& -69& -58/5\\ 6& 158& 6/5\\ -4& 30& -33\end{array}\right);\\ Q=\left(\begin{array}{ccc}\frac{{𝐮}_1}{\Vert {𝐮}_1\Vert }& \frac{{𝐮}_2}{\Vert {𝐮}_2\Vert }& \frac{{𝐮}_3}{\Vert {𝐮}_3\Vert }\end{array}\right)& =\left(\begin{array}{ccc}6/7& -69/175& -58/175\\ 3/7& 158/175& 6/175\\ -2/7& 6/35& -33/35\end{array}\right).\end{array}$$

Assim, tem-se

$$\begin{array}{cc}{Q}^{\mathsf{\text{T}}}A& =Q^{\mathsf{\text{T}}}QR=R;\\ R& =Q^{\mathsf{\text{T}}}A=\left(\begin{array}{ccc}14& 21& -14\\ 0& 175& -70\\ 0& 0& 35\end{array}\right).\end{array}$$

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 $𝐱$ ser um vetor coluna real arbitrário de $A$ de dimensão m, tal que $\Vert 𝐱\Vert =|\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 $𝐱,$ 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}\Vert 𝐱\Vert$$

Predefinição:Harv e substitui-se a transposição, pela transposição seguida de conjugação para a construção de Q como abaixo.

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

$$\begin{array}{cc}𝐮& =𝐱-\alpha {𝐞}_1,\\ 𝐯& =\frac{𝐮}{\Vert 𝐮\Vert },\\ Q& =I-2𝐯{𝐯}^{\mathsf{\text{T}}}.\end{array}$$

Ou, se $A$ é complexo

$$Q=I-2𝐯{𝐯}^{*}.$$

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

$$Q𝐱={\left(\begin{array}{cccc}\alpha & 0& \cdots & 0\end{array}\right)}^{\mathsf{\text{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=\left[\begin{array}{cccc}{\alpha }_1& \star & \dots & \star \\ 0& & & \\ ⋮& & A^{\prime }& \\ 0& & & \end{array}\right]$$

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=\left(\begin{array}{cc}{I}_{k-1}& 0\\ 0& {Q_k}^{\prime }\end{array}\right).$$

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^{\mathsf{\text{T}}}{Q}_2^{\mathsf{\text{T}}}\cdots Q_t^{\mathsf{\text{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=\left(\begin{array}{ccc}12& -51& 4\\ 6& 167& -68\\ -4& 24& -41\end{array}\right).$$

Primeiro, é preciso encontrar uma reflexão que transforme a primeira coluna da matriz A, que é o vector ${𝐚}_1={\left(\begin{array}{ccc}12& 6& -4\end{array}\right)}^{\mathsf{\text{T}}},$ em $\Vert {𝐚}_1\Vert {𝐞}_1={\left(\begin{array}{ccc}14& 0& 0\end{array}\right)}^{\mathsf{\text{T}}}.$

Agora,

$$𝐮=𝐱-\alpha {𝐞}_1,$$

e

$$𝐯=\frac{𝐮}{\Vert 𝐮\Vert }.$$

Aqui,

$$\alpha =14$$ e $𝐱={𝐚}_1={\left(\begin{array}{ccc}12& 6& -4\end{array}\right)}^{\mathsf{\text{T}}}$

Portanto,

$$𝐮={\left(\begin{array}{ccc}-2& 6& -4\end{array}\right)}^{\mathsf{\text{T}}}=\left(\begin{array}{c}2\end{array}\right){\left(\begin{array}{ccc}-1& 3& -2\end{array}\right)}^{\mathsf{\text{T}}}$$ e $𝐯=\frac{1}{\sqrt{14}}{\left(\begin{array}{ccc}-1& 3& -2\end{array}\right)}^{\mathsf{\text{T}}},$ e então $$\begin{array}{cc}{Q}_1=& I-\frac{2}{\sqrt{14}\sqrt{14}}\left(\begin{array}{c}-1\\ 3\\ -2\end{array}\right)\left(\begin{array}{ccc}-1& 3& -2\end{array}\right)\\ =& I-\frac{1}{7}\left(\begin{array}{ccc}1& -3& 2\\ -3& 9& -6\\ 2& -6& 4\end{array}\right)\\ =& \left(\begin{array}{ccc}6/7& 3/7& -2/7\\ 3/7& -2/7& 6/7\\ -2/7& 6/7& 3/7\end{array}\right).\end{array}$$

Agora observe que:

$$Q_{1}A=\left(\begin{array}{ccc}14& 21& -14\\ 0& -49& -14\\ 0& 168& -77\end{array}\right),$$

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^{\prime }=M_{11}=\left(\begin{array}{cc}-49& -14\\ 168& -77\end{array}\right).$$

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

$$Q_2=\left(\begin{array}{ccc}1& 0& 0\\ 0& -7/25& 24/25\\ 0& 24/25& 7/25\end{array}\right)$$

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^{\mathsf{\text{T}}}{Q}_2^{\mathsf{\text{T}}}=\left(\begin{array}{ccc}6/7& -69/175& 58/175\\ 3/7& 158/175& -6/175\\ -2/7& 6/35& 33/35\end{array}\right)$$

Ou, com quatro casas decimais,

$$\begin{array}{cc}Q& =Q_1^{\mathsf{\text{T}}}{Q}_2^{\mathsf{\text{T}}}=\left(\begin{array}{ccc}0.8571& -0.3943& 0.3314\\ 0.4286& 0.9029& -0.0343\\ -0.2857& 0.1714& 0.9429\end{array}\right)\\ R& =Q_2{Q}_{1}A=Q^{\mathsf{\text{T}}}A=\left(\begin{array}{ccc}14& 21& -14\\ 0& 175& -70\\ 0& 0& -35\end{array}\right).\end{array}$$

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=\left(\begin{array}{ccc}12& -51& 4\\ 6& 167& -68\\ -4& 24& -41\end{array}\right).$$

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

$$\begin{array}{cc}{G}_1& =\left(\begin{array}{ccc}\cos (\theta )& 0& -\mathrm{s}\mathrm{e}\mathrm{n}(\theta )\\ 0& 1& 0\\ \mathrm{s}\mathrm{e}\mathrm{n}(\theta )& 0& \cos (\theta )\end{array}\right)\\ & \approx \left(\begin{array}{ccc}0.94868& 0& -0.31622\\ 0& 1& 0\\ 0.31622& 0& 0.94868\end{array}\right)\end{array}$$

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

$$G_{1}A\approx \left(\begin{array}{ccc}12.64911& -55.97231& 16.76007\\ 6& 167& -68\\ 0& 6.64078& -37.6311\end{array}\right)$$

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^{\mathsf{\text{T}}}$ é formada a partir do produto de todas as matrizes de Givens $Q^{\mathsf{\text{T}}}=G_3{G}_2{G}_1.$ Assim, tem-se $G_3{G}_2{G}_{1}A=Q^{\mathsf{\text{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,

$$|\det (A)|=|\det (R)|=\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\left(\begin{array}{c}R\\ O\end{array}\right),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⟺A=QR{P}^{\mathsf{\text{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|\ge \left|r_{22}\right|\ge \dots \ge \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^{\mathsf{\text{T}}}=QR,$ em que Q é uma matriz ortogonal (ou seja $Q^{\mathsf{\text{T}}}=Q^{-1}$), e R tem uma forma especial: $R=\left[\begin{array}{c}{R}_1\\ 0\end{array}\right].$ 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\left[\begin{array}{c}{\left(R_1^{\mathsf{\text{T}}}\right)}^{-1}b\\ 0\end{array}\right]$ onde se pode encontrar $R_1^{-1}$ por eliminação gaussiana ou pelo cálculo de ${\left(R_1^{\mathsf{\text{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\ge n$) $Ax=b$ que minimiza a norma $\Vert A\hat{x}-b\Vert ,$ 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^{\mathsf{\text{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

• Predefinição:Citation.
• Predefinição:Citation. Seção 2.8.
• Predefinição:Citation
• Predefinição:Citation.

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.