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
[editar | editar código-fonte]Matriz quadrada
[editar | editar código-fonte]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 retangular
[editar | editar código-fonte]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:
em que R1 é uma matriz triangular superior de ordem n×n, 0 é uma matriz nula de ordem (m − n)×n, 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 LQ
[editar | editar código-fonte]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
[editar | editar código-fonte]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
[editar | editar código-fonte]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
Exemplo
[editar | editar código-fonte]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 QR
[editar | editar código-fonte]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
[editar | editar código-fonte]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
[editar | editar código-fonte]![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/7b/Householder.svg/220px-Householder.svg.png)
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
Exemplo
[editar | editar código-fonte]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 desvantagens
[editar | editar código-fonte]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
[editar | editar código-fonte]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
[editar | editar código-fonte]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 desvantagens
[editar | editar código-fonte]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 autovalores
[editar | editar código-fonte]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 colunas
[editar | editar código-fonte]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 lineares
[editar | editar código-fonte]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ções
[editar | editar código-fonte]A decomposição de Iwasawa generaliza a decomposição QR para grupos de Lie semissimples.
Ver também
[editar | editar código-fonte]- Decomposição polar
- Decomposição em autovalores
- Decomposição espectral
- Decomposição LU
- Decomposição em valores singulares
Referências
Leitura complementar
[editar | editar código-fonte]- 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
[editar | editar código-fonte]- 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.