Decomposição QR

decomposição matricial

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çõesEditar

Matriz quadradaEditar

Toda matriz quadrada A com entradas reais pode ser decomposta como

 

em que Q é uma matriz ortogonal (suas colunas são vetores unitários ortogonais, isto é  ) 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  ).

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.[1] O fato de qualquer coluna k de A só depender das primeiras k colunas de Q é responsável pela forma triangular de R.[1]

Matriz retangularEditar

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 (mn) 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:

 

em que R1 é uma matriz triangular superior de ordem n×n, 0 é uma matriz nula de ordem (m − nn, Q1 é m×n, P2 é m×(m − n) e tanto Q1 quanto Q2 têm colunas ortogonais.

Golub & Van Loan (1996, §5.2) chamam Q1R1 de fatoração QR magra de A; já Trefethen e Bau a chamam de fatoração QR reduzida.[1] Se A é de posto cheio n e for exigido que os elementos da diagonal de R1 sejam positivos, então, R1 e P1 são únicas, mas, em geral, Q2 não é. R1 é, então, igual ao fator triangular superior da fatoração de Cholesky de A* A (= ATA se A é real).

Decomposições QL, RQ e LQEditar

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 QREditar

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–SchmidtEditar

Considere o processo de Gram–Schmidt aplicado às colunas da matriz de posto completo por colunas   com o produto interno   (ou   no caso complexo).

Defina a projeção:

 

então:

 

Agora os  s podem ser escritos em relação à recém calculada base ortonormal:

 

em que   Isso pode ser escrito matricialmente como:

 

onde:

 

e

 

ExemploEditar

Considere a decomposição de

 

Lembre-se que uma matriz ortonormal   tem a propriedade

 

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

 

Assim, tem-se

 

Relação com a decomposição QREditar

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 desvantagensEditar

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 HouseholderEditar

 
Reflexão de Householder para a decomposição QR: O objetivo é encontrar uma transformação linear que transforma o vetor   em um vetor de mesmo comprimento que é colinear a   Poderia ser usada uma projeção ortogonal (Gram-Schmidt), mas isso seria numericamente instável se os vetores   e   fossem praticamente ortogonais. Em vez disso, a reflexão de Householder reflete através da linha pontilhada (escolhida para dividir o ângulo entre   e  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  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   de dimensão m, tal que   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   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

 

(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   o vetor (1 0 ... 0)T, ||·|| a norma Euclidiana e   uma matriz identidade de ordem m-por-m, define-se

 

Ou, se   é complexo

 

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

 

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 Q1 que é obtida ao escolher a primeira matriz coluna para x. Isso resulta em uma matriz Q1A com zeros na coluna da esquerda (exceto na primeira linha).

 

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

 

Depois de   iterações do processo,  

 

é uma matriz triangular superior. Assim, com

 

  é uma decomposição QR de  

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  
Adições  
Divisão  
Raiz quadrada  

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

 

ExemploEditar

Vamos calcular a decomposição de

 

Primeiro, é preciso encontrar uma reflexão que transforme a primeira coluna da matriz A, que é o vector   em  

Agora,

 

e

 

Aqui,

 
e  

Portanto,

 
e   e então
 

Agora observe que:

 

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

 

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

 

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

Agora, encontramos

 

Ou, com quatro casas decimais,

 

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

Vantagens e desvantagensEditar

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 GivensEditar

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.

ExemploEditar

Vamos calcular a decomposição de

 

Primeiro, é necessário formar uma matriz de rotação que zere o elemento mais à esquerda e abaixo,   Esta matriz é formada utilizando o método de rotação de Givens, e é chamada de   Primeiramente o vetor   será rotacionado para que aponte na direção do eixo X. Este vetor forma um ângulo   Deste modo é criada a matriz de rotação de Givens,  

 

E assim o resultado de   tem um zero no elemento  

 

Também é possível construir matrizes de Givens   e  de forma análoga para zerar os elementos abaixo da diagonal principal,   e   formando uma matriz triangular   A matriz ortogonal   é formada a partir do produto de todas as matrizes de Givens   Assim, tem-se  e a decomposição QR é  

Vantagens e desvantagensEditar

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   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 autovaloresEditar

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   Então tem-se

 

Sendo Q unitária,   Assim,

 

em que   são as entradas da diagonal de R.

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

 

em que   são os autovalores de  

Pode-se estender as propriedades acima para uma matriz complexa não quadrada   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:

 

em que   é uma matriz nula e   é uma matriz unitária.

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

 

em que   são os valores singulares de  

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

 

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 colunasEditar

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

 

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:   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 linearesEditar

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 ( )   em que a matriz A tem dimensões   e posto   primeiro encontra-se a fatoração QR da transposta de A:   em que Q é uma matriz ortogonal (ou seja  ), e R tem uma forma especial:   Aqui   é uma matriz quadrada   triangular à direita, e a matriz nula tem ordem   Após alguma álgebra, pode ser mostrado que uma solução para o problema inverso pode ser expressa como:   onde se pode encontrar   por eliminação gaussiana ou pelo cálculo de   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,   para o problema superdeterminado ( )   que minimiza a norma   primeiro encontra-se a fatoração QR de A:   A solução pode ser expressa como   onde   é uma matriz   contendo as primeiras   colunas da base orthonormal completa   e onde   é como antes. Tal como no caso subdeterminado, pode-se usar a substituição regressiva para encontrar este   de forma rápida e precisa, sem inverter   explicitamente. (  e   são muitas vezes fornecidos por bibliotecas numéricas como uma decomposição QR "econômica".)

GeneralizaçõesEditar

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

Ver tambémEditar

Referências

  1. a b c L. N. Trefethen e D. Bau, Álgebra Linear Numérica (SIAM, 1997).

Leitura complementarEditar

Ligações externasEditar