Ortogonalidade e Fatoração QR

Ortogonalidade é o conceito que torna a álgebra linear numericamente estável. Transformações ortogonais preservam comprimentos, e por isso não amplificam erro de arredondamento — a razão pela qual os algoritmos confiáveis são construídos sobre elas.

Bases ortonormais

Um conjunto ${q_1,\dots,q_n}$ é ortonormal quando $\langle q_i,q_j\rangle = \delta_{ij}$: vetores unitários e mutuamente ortogonais.

A vantagem prática é enorme. Numa base qualquer, achar as coordenadas de $v$ exige resolver um sistema. Numa base ortonormal, elas são simples produtos internos:

$$v = \sum_i \langle v,q_i\rangle q_i$$

Um problema $O(n^3)$ vira $O(n^2)$.

Matrizes ortogonais

$Q$ é ortogonal quando $Q^TQ = I$, isto é, $Q^{-1} = Q^T$.

Propriedades decisivas:

• Preserva norma: $|Qx| = |x|$.
• Preserva produto interno e ângulos.
• $|\det Q| = 1$.
• $\kappa_2(Q) = 1$ — o melhor condicionamento possível.

A última é o ponto central: multiplicar por matriz ortogonal não piora o condicionamento do problema. Toda operação intermediária de um algoritmo estável tende a ser ortogonal por essa razão.

Rotações e reflexões são exatamente as transformações ortogonais de $\mathbb{R}^n$.

Gram-Schmidt

Transforma uma base qualquer em ortonormal, subtraindo de cada vetor as projeções sobre os anteriores:

$$u_k = v_k - \sum_{i<k} \operatorname{proj}_{q_i}(v_k), \qquad q_k = \frac{u_k}{|u_k|}$$

A versão clássica é numericamente instável: os erros de arredondamento fazem a ortogonalidade se degradar ao longo do processo. A versão modificada subtrai as projeções uma a uma, atualizando o vetor a cada passo, e é bem melhor:

import numpy as np

def gram_schmidt_modificado(V):
    n, k = V.shape
    Q = np.zeros((n, k))
    R = np.zeros((k, k))
    for j in range(k):
        v = V[:, j].copy()
        for i in range(j):
            R[i, j] = Q[:, i] @ v
            v -= R[i, j] * Q[:, i]     # atualiza a cada passo
        R[j, j] = np.linalg.norm(v)
        Q[:, j] = v / R[j, j]
    return Q, R

Mesmo assim, para trabalho sério prefira Householder.

Fatoração QR

Toda matriz $A \in \mathbb{R}^{m\times n}$ com $m \ge n$ se escreve

$$A = QR$$

com $Q$ de colunas ortonormais e $R$ triangular superior.

Três métodos de obtê-la:

Método	Estabilidade	Observação
Gram-Schmidt clássico	Ruim	Só didático
Gram-Schmidt modificado	Razoável	Aceitável
Householder	Excelente	Padrão do LAPACK
Rotações de Givens	Excelente	Boa para matrizes esparsas

Refletores de Householder zeram uma coluna inteira de uma vez, refletindo o vetor sobre um hiperplano:

$$H = I - 2\frac{vv^T}{v^Tv}$$

Cada $H$ é ortogonal e simétrica. Aplicando $n$ refletores, $A$ vira triangular. Custo: $\frac{2}{3}n^3$ para matriz quadrada — cerca do dobro da eliminação LU, e essa é a moeda de troca: paga-se o dobro por estabilidade muito superior.

Rotações de Givens zeram um elemento por vez, o que é preferível quando a matriz já tem muitos zeros ou quando se atualiza uma fatoração existente.

QR e mínimos quadrados

Este é o uso mais importante. Para minimizar $|Ax-b|_2$ com $A = QR$:

$$|Ax - b| = |QRx - b| = |Rx - Q^Tb|$$

usando que $Q$ preserva norma. Basta então resolver o sistema triangular $Rx = Q^Tb$ por substituição regressiva.

A vantagem sobre as equações normais é decisiva: $\kappa(A^TA) = \kappa(A)^2$, enquanto o método QR trabalha com $\kappa(A)$. Em problemas mal condicionados, isso é a diferença entre resultado útil e ruído.

import numpy as np
Q, R = np.linalg.qr(A)
x = np.linalg.solve(R, Q.T @ b)
# ou, mais robusto, deixando a biblioteca escolher:
x, *_ = np.linalg.lstsq(A, b, rcond=None)

Outras aplicações

Algoritmo QR para autovalores. Fatorar e remultiplicar na ordem trocada, repetidamente, converge para forma triangular com os autovalores na diagonal. É o algoritmo padrão do mundo inteiro.

Ortogonalização em gráficos. Matrizes de rotação acumuladas ao longo de milhares de quadros perdem ortogonalidade por arredondamento. Reortogonalizar periodicamente evita que a cena comece a distorcer.

Redes neurais. Inicialização ortogonal de pesos ajuda a evitar explosão e desaparecimento de gradiente em redes profundas e recorrentes, precisamente porque preserva norma.

Compressão e projeções aleatórias. Projeções em subespaços ortonormais aleatórios preservam distâncias aproximadamente — o conteúdo do lema de Johnson-Lindenstrauss.

Exemplo trabalhado

Ortonormalizar $v_1 = (1,1,0)$ e $v_2 = (1,0,1)$.

$$q_1 = \frac{v_1}{|v_1|} = \frac{1}{\sqrt2}(1,1,0)$$

$$\langle v_2,q_1\rangle = \frac{1}{\sqrt2}, \qquad u_2 = v_2 - \frac{1}{\sqrt2}q_1 = \left(\tfrac12, -\tfrac12, 1\right)$$

$$|u_2| = \sqrt{\tfrac14+\tfrac14+1} = \frac{\sqrt6}{2}, \qquad q_2 = \frac{1}{\sqrt6}(1,-1,2)$$

Conferindo: $\langle q_1,q_2\rangle = \frac{1}{\sqrt{12}}(1 - 1 + 0) = 0$. Ortogonais.

Erros comuns

• Gram-Schmidt clássico em código de produção.
• Equações normais em problema mal condicionado.
• Não reortogonalizar matrizes de rotação acumuladas.
• Supor que $Q$ é quadrada. Na QR reduzida, $Q$ é $m\times n$ e $QQ^T \ne I$.
• Ignorar o sinal. A fatoração QR é única a menos de sinais das colunas.

Leituras recomendadas

• Trefethen e Bau, lições 7 a 11 — QR, Gram-Schmidt e Householder; a melhor exposição disponível.
• Golub e Van Loan, capítulo 5 — todos os detalhes de implementação.
• Documentação do LAPACK, rotinas geqrf e orgqr — o que as bibliotecas realmente fazem.

Lloyd N. Trefethen and David Bau III (1997). Numerical Linear Algebra. SIAM. DOI: 10.1137/1.9780898719574. Gene H. Golub and Charles F. Van Loan (2013). Matrix Computations. Johns Hopkins University Press. DOI: 10.56021/9781421407944.

Referências

1. Lloyd N. Trefethen; David Bau III (1997). Numerical Linear Algebra. SIAM.
2. Gene H. Golub; Charles F. Van Loan (2013). Matrix Computations. Johns Hopkins University Press.