Matriz ortogonal

BenefíciosEditar

Análise numérica tira partido de muitas das propriedades das matrizes ortogonais para a álgebra linear numérica, e estas surgem naturalmente. Por exemplo, é frequentemente desejável calcular uma base orto-normal para um espaço, ou uma mudança ortogonal de bases; ambas tomam a forma de matrizes ortogonais. Ter determinantes ±1 e todos os valores próprios de magnitude 1 é de grande benefício para a estabilidade numérica. Uma implicação é que o número de condição é 1 (que é o mínimo), pelo que os erros não são ampliados quando se multiplicam com uma matriz ortogonal. Muitos algoritmos utilizam matrizes ortogonais como as reflexões de Householder e as rotações de Givens por este motivo. É também útil que, não só uma matriz ortogonal invertível, mas o seu inverso esteja disponível essencialmente livre, através da troca de índices.

Permutações são essenciais para o sucesso de muitos algoritmos, incluindo a eliminação de Gaussiano com pivotamento parcial (onde as permutações fazem o pivotamento). Contudo, raramente aparecem explicitamente como matrizes; a sua forma especial permite uma representação mais eficiente, tal como uma lista de n índices.

Likewise, os algoritmos que utilizam matrizes Householder e Givens utilizam tipicamente métodos especializados de multiplicação e armazenamento. Por exemplo, uma rotação de Givens afecta apenas duas filas de uma matriz que se multiplica, alterando uma multiplicação completa da ordem n3 para uma ordem muito mais eficiente n. Quando os usos destas reflexões e rotações introduzem zeros numa matriz, o espaço vazio é suficiente para armazenar dados suficientes para reproduzir a transformação, e para o fazer de forma robusta. (Depois de Stewart (1976), não armazenamos um ângulo de rotação, que é ao mesmo tempo caro e mal comportado.)

DecomposiçõesEditar

Um número de decomposições matrizes importantes (Golub & Van Loan 1996) envolvem matrizes ortogonais, incluindo especialmente:

decomposição QR decomposição M = QR, Q ortogonal, R triangular superior Decomposição de valor singular M = UΣVT, U e V ortogonal, Σ matriz diagonal Eigendecomposição de uma matriz simétrica (decomposição segundo o teorema espectral) S = QΛQT, S simétrica, Q ortogonal, Λ decomposição polar diagonal M = QS, Q ortogonal, S simétrico positivo-semidefinido

ExemplosEditar

Considerar um sistema de equações lineares demasiado determinado, como pode ocorrer com medições repetidas de um fenómeno físico para compensar os erros experimentais. Escrever Eixo = b, onde A é m × n, m > n.A QR decomposição reduz A a R triangular superior. Por exemplo, se A é 5 × 3 então R tem a forma

R = . R={\displaystyle R={\begin{\bmatrix}\cdot &\cdot &\cdot \0&\cdot &\cdot ÿ&0&\cdot \\0&&&&0\end{bmatrix}}.}

${\i1}displaystyle R={\i1}begin{\i}cdot {\i}cdot {\i}cdot {\i}cdot {\i}cdot {\i}cdot {\i}cdotO problema dos mínimos quadrados lineares é encontrar o x que minimiza ||Ax - b||, o que equivale a projectar o b para o subespaço abrangido pelas colunas de A. Assumindo que as colunas de A (e portanto R) são independentes, a solução de projecção é encontrada a partir de ATAx = ATb. Agora ATA é quadrada (n × n) e invertível, e também igual a RTR. Mas as filas inferiores de zeros em R são supérfluas no produto, que está assim já na forma inferior-triangular superior-triangular factored, como na eliminação Gaussiana (decomposição Cholesky). Aqui a ortogonalidade é importante não só para reduzir ATA = (RTQT)QR para RTR, mas também para permitir uma solução sem problemas numéricos de ampliação.$

No caso de um sistema linear que é sub-determinado, ou uma matriz não-invertível, a decomposição de valor singular (SVD) é igualmente útil. Com A factored como UΣVT, uma solução satisfatória utiliza o pseudo-inverso Moore-Penrose, VΣ+UT, onde Σ+ apenas substitui cada entrada diagonal não-zero com a sua recíproca. O conjunto x para VΣ+UTb.

O caso de uma matriz quadrada invertível também tem interesse. Suponha, por exemplo, que A é uma matriz de rotação 3 × 3 que foi calculada como a composição de numerosas voltas e reviravoltas. O ponto flutuante não corresponde ao ideal matemático dos números reais, pelo que A perdeu gradualmente a sua verdadeira ortogonalidade. Um processo de Gram-Schmidt poderia ortogonalizar as colunas, mas não é o mais fiável, nem o mais eficiente, nem o método mais invariante. Os factores de decomposição polar de uma matriz num par, um dos quais é a matriz ortogonal única mais próxima da matriz dada, ou uma das mais próximas se a matriz dada for singular. (A proximidade pode ser medida por qualquer norma de matriz invariante sob uma mudança ortogonal de base, tal como a norma espectral ou a norma de Frobenius). Para uma matriz quase ortogonal, a convergência rápida para o factor ortogonal pode ser alcançada através de uma abordagem “método de Newton” devido a Higham (1986) (1990), calculando repetidamente a média da matriz com a sua transposição inversa. Dubrulle (1994) erro de harvtxt: nenhum alvo: CITEREFDubrulle1994 (ajuda) publicou um método acelerado com um conveniente teste de convergência.

Por exemplo, considere uma matriz não ortogonal para a qual o algoritmo simples de cálculo da média dá sete passos

→ → ⋯ → {\displaystyle {\begin{\bmatrix}3&&5end{\bmatrix}}{\begin{\bmatrix}1.8125&&2.6875\end{bmatrix}{bmatrix}{begin{bmatrix}0.8&&0.8\end{bmatrix}}}

${\begin{bmatrix}31\\75\end{bmatrix}}\rightarrow {\begin{bmatrix}1.81250.0625\\3.43752.6875\end{bmatrix}}\rightarrow \cdots \rightarrow {\begin{bmatrix}0.8-0.6 0.60.8}end{bmatrix}$

e que a aceleração se ajusta a dois passos (com γ = 0.353553, 0.565685).

→ → {\displaystyle {\begin{\bmatrix}3&1\\\\\&

5\end{\bmatrix}}{\begin{\bmatrix}1.41421&&1.41421\end{bmatrix}}\rightarrow {\begin{bmatrix}0.8&&0.8\end{bmatrix}}}

${\begin{bmatrix}31\\75\end{bmatrix}}\rightarrow {\begin{bmatrix}1.41421-1.06066\\1.060661.41421\end{bmatrix}}\rightarrow {\begin{bmatrix}0.8-0.6 0.60.8end{bmatrix}$

Gram-Schmidt produz uma solução inferior, mostrada por uma distância de Frobenius de 8.28659 em vez do mínimo 8.12404.

→ {\displaystyle {\begin{bmatrix}3&&5\end{bmatrix}}}{\begin{bmatrix}0.393919&&0.393919\end{bmatrix}}}

${\begin{bmatrix}31\\75\end{bmatrix}}\rightarrow {\begin{bmatrix}0.393919-0.919145\\0.9191450.393919{bmatrix}$

RandomizationEdit

algumas aplicações numéricas, tais como os métodos Monte Carlo e a exploração de espaços de dados de alta dimensão, requerem a geração de matrizes ortogonais aleatórias uniformemente distribuídas. Neste contexto, “uniforme” é definido em termos de medida Haar, o que essencialmente exige que a distribuição não mude se multiplicada por qualquer matriz ortogonal livremente escolhida. A ortogonalização de matrizes com entradas aleatórias independentes uniformemente distribuídas não resulta em matrizes ortogonais uniformemente distribuídas, mas a decomposição QR de entradas aleatórias independentes normalmente distribuídas resulta, desde que a diagonal de R contenha apenas entradas positivas (Mezzadri 2006). Stewart (1980) substituiu isto por uma ideia mais eficiente de que Diaconis & Shahshahani (1987) generalizou mais tarde como o “algoritmo de subgrupo” (na forma em que funciona tão bem para permutações e rotações). Para gerar uma (n + 1) × (n + 1) matriz ortogonal, tomar um n × n um e um vector de unidade uniformemente distribuído de dimensão n + 1. Construir uma reflexão de Householder a partir do vector, depois aplicá-la à matriz menor (embutida no tamanho maior com um 1 no canto inferior direito).

Matriz ortogonal mais próximaEditar

O problema de encontrar a matriz ortogonal Q mais próxima de uma dada matriz M está relacionado com o problema de Procrustes Ortogonais. Há várias maneiras diferentes de obter a solução única, a mais simples das quais é tomar a decomposição do valor singular de M e substituir os valores singulares por outros. Outro método expressa explicitamente o R mas requer o uso de uma matriz de raiz quadrada:

Q = M ( M T M ) – 1 2 {\displaystyle Q=M=esquerda(M^{\mathrm {T}Mright)^{-{\frac {1}{2}}}}

${\i1}displaystyle Q=M=esquerda(M^{\i}mathrm {T}Mright)^{-{\i}{2_frac {1}{2}}}}$

Isto pode ser combinado com o método babilónico para extrair a raiz quadrada de uma matriz para dar uma recorrência que converge para uma matriz ortogonal quadraticamente:

Q n + 1 = 2 M ( Q n – 1 M + M T Q n ) – 1 {\\i1}=2M{\i}esquerda(Q_{n}^{-1}M+M^{\i} {\i}Q_{n}direita)^{-1}

${\i1}{\i1}{\i1}=2M{\i}esquerda(Q_{\i}^{-1}M+M^{\i}mathrm {\i}Q_{\i}{\i}{\i1}$