Aula 13 · 03/11 (ter) · Módulo 3 · laboratório

Bases ortogonais e processo de Gram-Schmidt

Nesta aula você estuda bases ortonormais, as matrizes com colunas ortonormais, cuja multiplicação preserva comprimentos e produtos internos, e o processo de Gram-Schmidt, que constrói uma base ortonormal a partir de vetores linearmente independentes. Se q₁, …, q_n formam uma base ortonormal de ℝⁿ, as coordenadas de um vetor b nessa base são os produtos internos q₁^Tb, …, q_n^Tb, e não é preciso resolver um sistema linear. Na bancada, você aplica o processo passo a passo em ℝ² e em ℝ³ até a fatoração QR e examina matrizes ortogonais do plano; em ℝⁿ, compara duas versões do processo em ponto flutuante e comprime sinais numa base ortonormal de cossenos.

Strang, seção 3.4
Matrizes ortogonais e Gram-Schmidt · MIT 18.06, aula 17
Exercícios desta aula no Desmos

Nesta página

Bancada
Os quadros da aula e, ao lado deles, os controles; em telas estreitas, os controles ficam abaixo dos quadros. Numa tela larga, a coluna dos controles fica parada ao lado dos quadros e tem rolagem própria. No alto dessa coluna, o roteiro propõe 7 missões, uma de cada vez. Em cada missão, os nomes em vermelho levam ao quadro, ao painel ou ao controle que ela usa, que fica destacado na bancada.
Em dimensão n
Arredondamento e compressão. Experimentos e 4 desafios guiados.
Conceitos da aula
6 guias, cada uma com a definição, um exemplo resolvido e o lugar da bancada em que o conceito aparece, e 3 perguntas com resposta em Para pensar.

Modo da bancada

Gram-Schmidt passo a passo

A = QR

A matriz A tem como colunas os vetores de entrada a₁, a₂ e, em ℝ³, a₃. Antes da normalização, o quadro escreve A como o produto da matriz dos vetores ortogonais por uma matriz triangular superior U. Depois dela, escreve A = QR: a matriz Q tem como colunas os vetores ortonormais q₁, q₂ e, em ℝ³, q₃, e a matriz R é triangular superior, com entradas r_ij = q_i^Ta_j para i ≤ j.

Exemplos

Vetores de entrada

Cada coluna da matriz é um vetor de entrada: a primeira é a₁, a segunda é a₂ e, em ℝ³, a terceira é a₃. As entradas podem ser inteiros, frações como 3/2 ou decimais como 0,5.

O que mostrar

Pelo teclado: clique numa figura e use as setas; a barra de espaço alterna o vetor ou o ponto que se move. Quando o quadro Gram-Schmidt passo a passo mostra vetores de ℝ³ e nenhum vetor ou ponto está escolhido, as setas giram a vista.

Em dimensão n

Arredondamento e compressão

Num computador, o processo de Gram-Schmidt é executado em ponto flutuante, e o resultado de cada operação é arredondado. Para medir quanto as colunas calculadas q₁, …, q_n deixam de ser ortonormais, formamos a matriz Q com essas colunas e usamos o maior valor absoluto das entradas de Q^TQ − I, que chamamos de desvio de ortogonalidade. Fora da diagonal, essas entradas são os produtos internos q_i^Tq_j; na diagonal, são as diferenças q_i^Tq_i − 1. Em aritmética exata, todas seriam 0. Os vetores de entrada são quase linearmente dependentes quando algum deles fica muito perto do subespaço gerado pelos anteriores, em comparação com o seu comprimento, e então a ordem das contas importa. O Gram-Schmidt clássico calcula todos os coeficientes com o vetor original; o modificado subtrai uma projeção de cada vez do vetor já corrigido. Nos dois exemplos da bancada, o clássico perde a ortogonalidade muito antes do modificado. Na segunda parte, um sinal é um vetor x ∈ ℝⁿ de amostras. Os coeficientes de x numa base ortonormal de ℝⁿ formada por cossenos são produtos internos, e guardar apenas os k coeficientes de maior valor absoluto dá uma aproximação de x descrita por k números: é a compressão do sinal. O painel Experimento mostra uma parte de cada vez, com os seus quadros.

Perda de ortogonalidade

Para cada número n de vetores, os vetores calculados q₁, …, q_n formam as colunas de uma matriz Q. O gráfico mostra, em escala logarítmica, o desvio de ortogonalidade, isto é, o maior valor absoluto das entradas de Q^TQ − I, no Gram-Schmidt clássico e no modificado.

As entradas de Q^TQ − I

Experimento

Cada experimento tem os seus quadros e controles, e só os do experimento escolhido aparecem. Os desafios escolhem o experimento que usam.

Gram-Schmidt em ponto flutuante

Conceitos da aula

Bases ortonormais e o processo de Gram-Schmidt

Uma guia por conceito, cada um com a definição, um exemplo resolvido e o lugar da bancada em que ele aparece. A notação é a do livro-texto (seção 3.4).

Na Aula 12, dois vetores u, v ∈ ℝⁿ foram chamados de ortogonais quando o produto interno u^Tv é zero. Uma base formada por vetores ortogonais dois a dois e de comprimento 1 simplifica as contas com coordenadas e com projeções.

Vetores ortonormais

Definição

Os vetores q₁, …, q_k ∈ ℝⁿ são ortogonais se q_i^Tq_j = 0 para quaisquer i ≠ j. Eles são ortonormais se, além disso, cada um tem comprimento 1:

\begin{aligned}q_{i}^{\mathrm{T}}q_{j} &= 0\quad \text{para}\quad i \neq j, \\ q_{i}^{\mathrm{T}}q_{i} &= 1\quad \text{para}\quad i = 1, \ldots , k.\end{aligned}

Uma base ortonormal de um subespaço V de ℝⁿ é uma base de V formada por vetores ortonormais.

O comprimento de um vetor v ∈ ℝⁿ é ‖v‖ = √(v^Tv). Normalizar um vetor v ≠ 0 é dividi-lo pelo seu comprimento: o vetor v/‖v‖ tem a mesma direção e o mesmo sentido de v e comprimento 1. O vetor nulo não pode ser normalizado.

Vetores ortonormais são linearmente independentes

Teorema

Se q₁, …, q_k ∈ ℝⁿ são ortonormais, então eles são linearmente independentes. Em particular, n vetores ortonormais de ℝⁿ formam uma base ortonormal de ℝⁿ.

Por quê. Sejam λ₁, …, λ_k escalares tais que λ₁q₁ + ⋯ + λ_kq_k = 0. Multiplicando os dois lados por q_i^T, os termos λ_jq_i^Tq_j com j ≠ i se anulam, e sobra λ_iq_i^Tq_i = λ_i = 0, para cada i = 1, …, k. Como n vetores linearmente independentes de ℝⁿ formam uma base de ℝⁿ (Aula 7), a segunda afirmação segue da primeira.

Exemplo

Os vetores q₁ = (1, 1)^T/√2 e q₂ = (1, −1)^T/√2 formam uma base ortonormal de ℝ²:

\begin{aligned}q_{1}^{\mathrm{T}}q_{2} &= (1 \cdot 1 + 1 \cdot (-1))/2 = 0, \\ q_{1}^{\mathrm{T}}q_{1} &= (1^{2} + 1^{2})/2 = 1, \\ q_{2}^{\mathrm{T}}q_{2} &= (1^{2} + (-1)^{2})/2 = 1.\end{aligned}

Já os vetores (3, 4)^T e (−4, 3)^T são ortogonais, pois 3 · (−4) + 4 · 3 = 0, mas não são ortonormais: os dois têm comprimento 5. Normalizando, obtemos (3/5, 4/5)^T e (−4/5, 3/5)^T, que são ortonormais.

Na bancada: no modo Gram-Schmidt passo a passo, avance até o passo de normalização, o penúltimo. O quadro Gram-Schmidt passo a passo mostra os vetores ortonormais q₁, q₂ e, em ℝ³, q₃, com marcas de ângulo reto; no plano, as pontas de q₁ e q₂ ficam sobre o círculo unitário tracejado.

Pondo vetores ortonormais nas colunas de uma matriz Q, as condições q_i^Tq_j = 0 para i ≠ j e q_i^Tq_i = 1 se resumem numa só igualdade de matrizes, Q^TQ = I.

Matrizes com colunas ortonormais

Teorema

Seja Q uma matriz m × n com colunas q₁, …, q_n ∈ ℝ^m. As colunas de Q são ortonormais se, e somente se, Q^TQ = I, a identidade n × n. Nesse caso, para quaisquer u, v ∈ ℝⁿ,

(Qu)^{\mathrm{T}}(Qv) = u^{\mathrm{T}}v\quad \text{e}\quad \| Qu\| = \| u\| .

Por quê. A entrada (i, j) de Q^TQ é o produto da linha i de Q^T, que é q_i^T, pela coluna j de Q, que é q_j. Logo Q^TQ = I diz exatamente que q_i^Tq_j = 0 para i ≠ j e q_i^Tq_i = 1. Além disso, (Qu)^T(Qv) = u^TQ^TQv = u^Tv; com v = u, obtemos ‖Qu‖² = ‖u‖². Como o cosseno do ângulo entre dois vetores não nulos u e v é u^Tv / (‖u‖ ‖v‖), a multiplicação por Q também preserva ângulos.

Definição

Uma matriz ortogonal é uma matriz quadrada Q cujas colunas são ortonormais. Para ela, Q^TQ = I significa que Q^T é a inversa de Q: Q⁻¹ = Q^T. Por isso também vale QQ^T = I, e as linhas de Q também são ortonormais.

Se Q tem colunas ortonormais, mas é m × n com m > n, ela não é chamada de ortogonal e não tem inversa. Vale Q^TQ = I, mas QQ^T ≠ I: como n < m, existe b ≠ 0 ortogonal a todas as colunas de Q, isto é, com Q^Tb = 0, e para ele QQ^Tb = 0 ≠ b.

Exemplos no plano

Exemplo

A rotação de 90° no sentido anti-horário tem matriz Q = 0−110, cujas colunas (0, 1)^T e (−1, 0)^T são ortonormais. Para u = (3, 4)^T,

\begin{aligned}Qu &= (-4, 3)^{\mathrm{T}}, \\ \| Qu\| &= \sqrt{16 + 9} = 5 = \| u\| .\end{aligned}

As matrizes ortogonais 2 × 2 são de dois tipos. A primeira coluna q₁ tem comprimento 1; por isso, se θ é o ângulo da parte positiva do eixo x até q₁, medido no sentido anti-horário, então q₁ = (cos θ, sen θ)^T. A segunda coluna, por ter comprimento 1 e ser ortogonal a q₁, só pode ser um destes dois vetores:

(−sen θ, cos θ)^T: Q é a rotação de ângulo θ no sentido anti-horário, com det Q = cos² θ + sen² θ = 1;
(sen θ, −cos θ)^T: Q é a reflexão em relação à reta que passa pela origem e faz ângulo θ/2 com o eixo x, com det Q = −cos² θ − sen² θ = −1.

As matrizes de permutação (Aula 5) também são ortogonais: as suas colunas são os vetores da base canônica, em outra ordem.

Na bancada: no modo Matriz ortogonal Q, arraste u, v e a ponta de q₁ no quadro Comprimentos e ângulos. A leitura abaixo do quadro mostra ‖Qu‖ = ‖u‖, ‖Qv‖ = ‖v‖ e (Qu)^T(Qv) = u^Tv, e o quadro A matriz Q e o produto QᵀQ mostra Q^TQ = I. No painel A matriz Q, marque Reflexão para trocar a rotação por uma reflexão.

Numa base qualquer, encontrar as coordenadas de um vetor exige resolver um sistema linear. Numa base ortonormal, cada coordenada é um único produto interno, e a projeção sobre o subespaço gerado por alguns vetores da base é uma soma de projeções sobre retas.

Coordenadas numa base ortonormal

Teorema

Se q₁, …, q_n é uma base ortonormal de ℝⁿ e Q é a matriz com essas colunas, então todo b ∈ ℝⁿ satisfaz

b = (q_{1}^{\mathrm{T}}b)q_{1} + \cdots + (q_{n}^{\mathrm{T}}b)q_{n}.

Isto é, as coordenadas de b nessa base são y_i = q_i^Tb, para i = 1, …, n. Em forma matricial, com y = (y₁, …, y_n)^T, vale y = Q^Tb.

Por quê. Como q₁, …, q_n é uma base, existem escalares únicos y₁, …, y_n tais que b = y₁q₁ + ⋯ + y_nq_n. Multiplicando por q_i^T, os termos y_jq_i^Tq_j com j ≠ i se anulam, e sobra q_i^Tb = y_i. Em forma matricial, b = Qy, e multiplicar por Q^T dá Q^Tb = Q^TQy = y. Não é preciso eliminação: o produto Q^Tb custa n² multiplicações, contra cerca de n³/3 para resolver Qy = b por eliminação.

Exemplo

Na base q₁ = (1, 1)^T/√2, q₂ = (1, −1)^T/√2, as coordenadas de b = (3, 1)^T são

\begin{aligned}y_{1} &= q_{1}^{\mathrm{T}}b = (3 + 1)/\sqrt{2} = 2\sqrt{2}, \\ y_{2} &= q_{2}^{\mathrm{T}}b = (3 - 1)/\sqrt{2} = \sqrt{2}.\end{aligned}

De fato, 2√2 q₁ + √2 q₂ = (2, 2)^T + (1, −1)^T = (3, 1)^T.

Projeção sobre o espaço gerado por vetores ortonormais

Teorema

Sejam q₁, …, q_k ∈ ℝⁿ vetores ortonormais e Q a matriz n × k com essas colunas. Para todo b ∈ ℝⁿ, a projeção de b sobre o subespaço ger{q₁, …, q_k} é

\begin{aligned}p &= (q_{1}^{\mathrm{T}}b)q_{1} + \cdots + (q_{k}^{\mathrm{T}}b)q_{k}, \\ p &= QQ^{\mathrm{T}}b.\end{aligned}

A matriz de projeção é P = QQ^T.

Por quê. Na Aula 12, a projeção de b sobre C(A), para A com colunas linearmente independentes, é p = A(A^TA)⁻¹A^Tb. Com A = Q, vale Q^TQ = I, e a fórmula se reduz a p = QQ^Tb. Cada parcela (q_i^Tb)q_i é a projeção de b sobre a reta gerada por q_i: como os vetores q_i são ortogonais, a projeção sobre o subespaço é a soma das projeções sobre essas retas. Se os vetores w₁, …, w_k forem apenas ortogonais e não nulos, basta aplicar a fórmula a q_i = w_i/‖w_i‖:

p = (w_{1}^{\mathrm{T}}b / w_{1}^{\mathrm{T}}w_{1})w_{1} + \cdots + (w_{k}^{\mathrm{T}}b / w_{k}^{\mathrm{T}}w_{k})w_{k}.

Exemplo

Os vetores w₁ = (1, −1, 0)^T e w₂ = (1, 1, −2)^T são ortogonais. Para projetar b = (3, −3, 3)^T sobre o plano ger{w₁, w₂}, calculamos w₁^Tb = 6, w₁^Tw₁ = 2, w₂^Tb = −6 e w₂^Tw₂ = 6. A projeção é

\begin{aligned}p &= (6/2)w_{1} + (-6/6)w_{2} = 3w_{1} - w_{2}, \\ p &= (2, -4, 2)^{\mathrm{T}}.\end{aligned}

O erro b − p = (1, 1, 1)^T é ortogonal a w₁ e a w₂.

Na bancada: no modo Matriz ortogonal Q, arraste b no quadro Coordenadas na base ortonormal. A leitura abaixo do quadro mostra y₁ = q₁^Tb e y₂ = q₂^Tb, e as setas largas e claras sobre as retas geradas por q₁ e por q₂ são as projeções y₁q₁ e y₂q₂. A projeção sobre um plano como soma de duas projeções aparece no passo 4 do modo Gram-Schmidt passo a passo, em ℝ³.

O processo de Gram-Schmidt parte de vetores linearmente independentes a₁, …, a_n e constrói vetores ortonormais q₁, …, q_n tais que, para cada j, os vetores q₁, …, q_j geram o mesmo subespaço que a₁, …, a_j. De cada vetor de entrada, ele subtrai a projeção sobre o subespaço gerado pelos anteriores e, no fim, divide cada resultado pelo seu comprimento.

O processo

Definição

Sejam a₁, …, a_n ∈ ℝ^m os vetores de entrada. O processo de Gram-Schmidt calcula os vetores ortogonais w₁, …, w_n e os vetores ortonormais q₁, …, q_n em três etapas:

o primeiro vetor ortogonal é o primeiro vetor de entrada: w₁ = a₁;
para j = 2, …, n, nessa ordem, w_j é a_j menos a sua projeção sobre o subespaço gerado por w₁, …, w_j−1, calculada como na guia Coordenadas e projeções: w_j = a_j − ∑_{i < j} (w_i^Ta_j / w_i^Tw_i) w_i; se algum w_i for nulo, o seu termo é omitido da soma;
depois do último passo, cada vetor ortogonal não nulo é normalizado: q_j = w_j/‖w_j‖.

Teorema

Se a₁, …, a_n são linearmente independentes, então w_j ≠ 0 para todo j, os vetores q₁, …, q_n são ortonormais e, para cada j = 1, …, n,

\operatorname{ger}\{q_{1}, \ldots , q_{j}\} = \operatorname{ger}\{a_{1}, \ldots , a_{j}\}.

Por quê. A prova é por indução em j. Para j = 1, w₁ = a₁ é não nulo, pois um conjunto linearmente independente não contém o vetor nulo, e ger{w₁} = ger{a₁}. Para j ≥ 2, suponha que w₁, …, w_j−1 são ortogonais dois a dois, não nulos e geram o mesmo subespaço que a₁, …, a_j−1. Então:

w_j é ortogonal a w₁, …, w_j−1: a soma subtraída de a_j é a projeção de a_j sobre esse subespaço (guia Coordenadas e projeções), e o erro de uma projeção é ortogonal ao subespaço;
w_j ≠ 0: se fosse nulo, a_j seria igual à sua projeção, que é combinação linear de a₁, …, a_j−1, o que contradiz a independência linear;
ger{w₁, …, w_j} = ger{a₁, …, a_j}: w_j é a_j menos uma combinação linear de a₁, …, a_j−1, e a_j é w_j mais uma combinação linear de w₁, …, w_j−1.

Por fim, dividir cada w_j pelo seu comprimento dá vetores de comprimento 1 e não muda a ortogonalidade nem os subespaços gerados.

A bancada usa a mesma notação: os vetores de entrada são a₁, a₂ e, em ℝ³, a₃, e os vetores ortogonais são w₁, w₂ e, em ℝ³, w₃.

Um exemplo e o caso dependente

Exemplo

Para a₁ = (1, −1, 0)^T, a₂ = (2, 0, −2)^T e a₃ = (3, −3, 3)^T:

\begin{aligned}w_{1} &= a_{1} = (1, -1, 0)^{\mathrm{T}}, \\ w_{2} &= a_{2} - (2/2)w_{1} = (1, 1, -2)^{\mathrm{T}}, \\ w_{3} &= a_{3} - (6/2)w_{1} - (-6/6)w_{2}, \\ w_{3} &= (1, 1, 1)^{\mathrm{T}}.\end{aligned}

As frações são os coeficientes w₁^Ta₂ / w₁^Tw₁ = 2/2, w₁^Ta₃ / w₁^Tw₁ = 6/2 e w₂^Ta₃ / w₂^Tw₂ = −6/6. Normalizando, q₁ = w₁/√2, q₂ = w₂/√6 e q₃ = w₃/√3.

Vetores dependentes. Se os vetores de entrada forem linearmente dependentes, existe um primeiro índice j em que a_j é combinação linear de a₁, …, a_j−1; para j = 1, isso quer dizer a₁ = 0. Os vetores anteriores a a_j são linearmente independentes, e o teorema vale para eles: ger{w₁, …, w_j−1} = ger{a₁, …, a_j−1}. Então a projeção de a_j sobre esse subespaço é o próprio a_j, e w_j = 0, que não pode ser normalizado. Por exemplo, se a₃ = a₁ + a₂, o passo de a₃ dá w₃ = 0. Assim, o processo também serve para decidir se vetores são linearmente independentes: eles são independentes se, e somente se, o processo chega ao fim sem encontrar um w_j nulo.

Na bancada: no modo Gram-Schmidt passo a passo, escolha o exemplo Resultados inteiros no painel Exemplos e use os botões de passo abaixo da figura do quadro Gram-Schmidt passo a passo; o texto abaixo dos botões mostra as contas de cada passo, com frações exatas. Os exemplos Vetores dependentes e Outra ordem mostram o que acontece com a₃ = a₁ + a₂ e com os mesmos vetores em outra ordem.

Escrito com matrizes, o processo de Gram-Schmidt dá uma fatoração da matriz A cujas colunas são os vetores de entrada. Os vetores ortonormais obtidos formam as colunas de uma matriz Q; cada coluna de A é combinação linear das colunas de Q, e os coeficientes formam uma matriz triangular superior R, com A = QR.

A fatoração A = QR

Teorema

Seja A uma matriz m × n com colunas a₁, …, a_n linearmente independentes, e sejam q₁, …, q_n os vetores obtidos pelo processo de Gram-Schmidt. Então A = QR, em que Q = [q₁ ⋯ q_n] tem colunas ortonormais e R é a matriz n × n de entradas

\begin{aligned}r_{ij} &= q_{i}^{\mathrm{T}}a_{j}\quad \text{se}\quad i \leq j, \\ r_{ij} &= 0\quad \text{se}\quad i > j.\end{aligned}

A matriz R é triangular superior, e a sua diagonal é formada pelos comprimentos dos vetores ortogonais w_j da guia Processo de Gram-Schmidt: r_jj = ‖w_j‖ > 0. Por isso, R é invertível.

Por quê. Pelo processo, a_j pertence a ger{q₁, …, q_j}. Então a projeção de a_j sobre esse subespaço é o próprio a_j e, pela guia Coordenadas e projeções,

a_{j} = (q_{1}^{\mathrm{T}}a_{j})q_{1} + \cdots + (q_{j}^{\mathrm{T}}a_{j})q_{j}.

A coluna j de QR é a combinação linear das colunas de Q com os coeficientes da coluna j de R, que são exatamente q₁^Ta_j, …, q_j^Ta_j, seguidos de zeros. Além disso, r_jj = q_j^Ta_j = q_j^Tw_j = ‖w_j‖, pois a_j − w_j pertence a ger{q₁, …, q_j−1}, cujos vetores são ortogonais a q_j. Multiplicando A = QR por Q^T, obtemos também R = Q^TA.

Um exemplo e os mínimos quadrados

Exemplo

Para os vetores a₁, a₂ e a₃ do exemplo da guia Processo de Gram-Schmidt, Q = [w₁/√2 w₂/√6 w₃/√3] e

R = \begin{bmatrix}\sqrt{2} & \sqrt{2} & 3\sqrt{2} \\ 0 & \sqrt{6} & -\sqrt{6} \\ 0 & 0 & \sqrt{3}\end{bmatrix}.

Na terceira coluna estão q₁^Ta₃ = 6/√2 = 3√2, q₂^Ta₃ = −6/√6 = −√6 e q₃^Ta₃ = 3/√3 = √3. De fato,

\begin{aligned}3\sqrt{2}\,q_{1} - \sqrt{6}\,q_{2} + \sqrt{3}\,q_{3} &= 3w_{1} - w_{2} + w_{3}, \\ 3w_{1} - w_{2} + w_{3} &= (3, -3, 3)^{\mathrm{T}} = a_{3}.\end{aligned}

Mínimos quadrados. Na Aula 12, a solução de mínimos quadrados de Ax = b é a solução x̂ das equações normais A^TAx̂ = A^Tb. Com A = QR, temos A^TA = R^TQ^TQR = R^TR e A^Tb = R^TQ^Tb. Como R^T é invertível, as equações normais equivalem a

Rx̂ = Q^Tb,

um sistema triangular superior, resolvido por substituição regressiva. Assim, não é preciso formar A^TA, uma conta que amplia os erros de arredondamento quando as colunas de A são quase linearmente dependentes.

Na bancada: no modo Gram-Schmidt passo a passo, o quadro A = QR mostra primeiro a igualdade [a₁ a₂ a₃] = [w₁ w₂ w₃]U, com os vetores ortogonais e uma matriz U triangular superior, e, depois da normalização, as matrizes Q e R. No último passo, as setas tracejadas do quadro Gram-Schmidt passo a passo mostram o último vetor de entrada como combinação linear de q₁, q₂ e, em ℝ³, q₃, com os coeficientes da última coluna de R.

Num computador, as contas com vetores de ℝⁿ são feitas em ponto flutuante, e o resultado de cada operação é arredondado. Duas versões do processo de Gram-Schmidt dão os mesmos vetores em aritmética exata, mas resultados muito diferentes com arredondamento quando os vetores de entrada são quase linearmente dependentes. Já uma base ortonormal pronta, a base de cossenos, permite comprimir sinais.

Gram-Schmidt clássico e modificado

Nas duas versões, cada q_j é normalizado no seu passo. No passo j, elas partem do vetor v = a_j, subtraem de v as projeções sobre os vetores q₁, …, q_j−1 já calculados e terminam com q_j = v/‖v‖. A diferença está no cálculo dos coeficientes dessas projeções:

o clássico calcula todos os coeficientes com o vetor original, r_ij = q_i^Ta_j para i < j, e faz v = a_j − r_1jq₁ − ⋯ − r_j−1,jq_j−1;
o modificado, para i = 1, …, j − 1, nessa ordem, calcula r_ij = q_i^Tv com o vetor v já corrigido e troca v por v − r_ijq_i.

Em aritmética exata, as duas versões dão os mesmos vetores: quando chega a vez de q_i, o modificado só subtraiu de a_j múltiplos de q₁, …, q_i−1, que são ortogonais a q_i, e por isso q_i^Tv = q_i^Ta_j.

O que se mede. Com as colunas calculadas q₁, …, q_n numa matriz Q, a entrada (i, j) de Q^TQ − I é q_i^Tq_j se i ≠ j e q_i^Tq_i − 1 se i = j. Em aritmética exata, todas seriam 0. A perda de ortogonalidade é medida pelo maior valor absoluto dessas entradas, que chamamos de desvio de ortogonalidade.

Por que o clássico acumula erros. Em ponto flutuante de 64 bits, cada operação tem erro relativo de até cerca de 10⁻¹⁶, e os vetores q₁, …, q_j−1 já calculados não são exatamente ortonormais. Diremos que a_j é quase combinação linear dos vetores anteriores quando a distância de a_j ao subespaço gerado por eles é muito menor que ‖a_j‖. Nesse caso, v é a diferença entre dois vetores quase iguais, a_j e a sua projeção, e ‖v‖ é muito menor que ‖a_j‖. Os erros dessas contas, da ordem de 10⁻¹⁶‖a_j‖, deixam em v componentes nas direções de q₁, …, q_j−1, e a normalização divide essas componentes por ‖v‖. No clássico, nenhum passo remove essas componentes: os produtos internos de q_j com q₁, …, q_j−1 ficam muito maiores que 10⁻¹⁶, e os passos seguintes partem desses vetores. Com as potências de t da bancada, o desvio de ortogonalidade do clássico cresce com o número n de vetores até ficar perto de 1.

No modificado, cada coeficiente q_i^Tv inclui a componente que v tem naquele momento na direção de q_i, seja qual for a sua origem, e essa componente é subtraída. O modificado também perde ortogonalidade com vetores quase linearmente dependentes, mas muito mais devagar: com as potências de t e n = 16, o desvio dele é cerca de 10⁻⁶, contra cerca de 1 no clássico.

Exemplo

Com ε = 10⁻⁸, sejam a₁ = (1, ε, 0, 0)^T, a₂ = (1, 0, ε, 0)^T e a₃ = (1, 0, 0, ε)^T. Em ponto flutuante, ‖a₁‖² = 1 + ε² = 1 + 10⁻¹⁶ é arredondado para 1, e as duas versões calculam

\begin{aligned}q_{1} &= (1, \varepsilon , 0, 0)^{\mathrm{T}}, \\ q_{2} &= (0, -1, 1, 0)^{\mathrm{T}}/\sqrt{2}.\end{aligned}

A primeira entrada de q₂, que em aritmética exata é cerca de ε/√2, saiu 0. No passo de a₃, as duas versões chegam a v = a₃ − q₁ = (0, −ε, 0, ε)^T e diferem no coeficiente de q₂:

o clássico calcula q₂^Ta₃ = 0, em vez de cerca de ε/√2, e obtém q₃ = (0, −1, 0, 1)^T/√2, com q₂^Tq₃ = 1/2: um ângulo de 60° entre q₂ e q₃, em vez de 90°;
o modificado calcula q₂^Tv = ε/√2, pois a primeira entrada de v já é 0, e obtém q₃ = (0, −1, −1, 2)^T/√6, com q₂^Tq₃ = 0.

A base de cossenos e a compressão

Definição

Para i = 0, 1, …, n − 1, seja q_i ∈ ℝⁿ o vetor de entradas

(q_{i})_{j} = s_{i} \cos (\pi i(2j - 1)/(2n)),

para j = 1, …, n, com s₀ = 1/√n e s_i = √(2/n) para i ≥ 1. Pode-se mostrar que esses n vetores são ortonormais. Eles formam a base de cossenos de ℝⁿ, usada na transformada discreta de cossenos. O índice i se chama frequência de q_i: quando j vai de 1 a n, o argumento do cosseno vai de πi/(2n) a πi − πi/(2n), e as entradas de q_i descrevem cerca de i/2 períodos do cosseno.

Um sinal de n amostras é um vetor x ∈ ℝⁿ, cuja entrada x_j é a amostra j. A energia do sinal é ‖x‖² = x₁² + ⋯ + x_n².

Seja Q = [q₀ ⋯ q_n−1] a matriz da base de cossenos. As coordenadas de x nessa base, que aqui se chamam coeficientes, são y = Q^Tx, isto é, y_i = q_i^Tx, e x = Qy = y₀q₀ + ⋯ + y_n−1q_n−1. Como Q é ortogonal, ‖y‖ = ‖x‖: a energia do sinal é a soma dos quadrados dos coeficientes. Guardando só alguns coeficientes e trocando os outros por 0, obtemos a reconstrução x̃, a soma dos termos y_iq_i guardados. O erro x − x̃ é a soma dos termos y_iq_i descartados e, como os vetores q_i são ortonormais, ‖x − x̃‖² é a soma dos y_i² descartados. Por isso, para guardar k coeficientes com o menor erro, basta escolher os k de maior valor absoluto. Quando o sinal varia pouco de uma amostra para a seguinte, a maior parte da energia costuma ficar nos coeficientes de frequência baixa: no sinal Temperatura da bancada, com n = 64, os 6 coeficientes de frequência 0 a 5 guardam 99,96% da energia. A compressão de imagens no formato JPEG usa essa ideia, com a versão bidimensional dessa base em blocos de 8 × 8 pixels.

Exemplo

Para n = 2, a base de cossenos é formada por q₀ = (1, 1)^T/√2 e q₁ = (1, −1)^T/√2, os vetores do exemplo da guia Vetores ortonormais, lá chamados de q₁ e q₂. Para x = (3, 1)^T:

\begin{aligned}y_{0} &= q_{0}^{\mathrm{T}}x = 4/\sqrt{2} = 2\sqrt{2}, \\ y_{1} &= q_{1}^{\mathrm{T}}x = 2/\sqrt{2} = \sqrt{2}, \\ \| y\| ^{2} &= 8 + 2 = 10 = \| x\| ^{2}.\end{aligned}

Guardando só y₀, a reconstrução é x̃ = y₀q₀ = (2, 2)^T, que guarda 8/10, ou 80%, da energia. O erro é ‖x − x̃‖² = ‖(1, −1)^T‖² = 2, igual a y₁².

Na bancada: na parte Em dimensão n, com o experimento Gram-Schmidt em ponto flutuante escolhido no painel Experimento, escolha Quase iguais e n = 3 para ver o exemplo acima no quadro As entradas de QᵀQ − I, ou Potências de t para comparar as duas versões no quadro Perda de ortogonalidade. Com o experimento Compressão de sinais, escolha um sinal no painel Sinal e compressão e mude o controle Coeficientes guardados k.

Para pensar

Trocar a ordem dos vetores de entrada a₁, a₂ e a₃ muda a base que o processo de Gram-Schmidt dá?

Em geral, sim. O primeiro vetor da base, q₁, é sempre a normalização do primeiro vetor de entrada. No exemplo Outra ordem, que começa por (3, −3, 3)^T, o processo dá q₁ = (1, −1, 1)^T/√3, e não (1, −1, 0)^T/√2. O que não depende da ordem é o subespaço gerado por todos os vetores: se os vetores de entrada forem linearmente independentes, em qualquer ordem, os vetores q₁, q₂, q₃ formam uma base ortonormal de ger{a₁, a₂, a₃}. Se os vetores de entrada já forem ortogonais e não nulos, trocar a ordem apenas troca a ordem dos vetores q_j.

Uma matriz Q com colunas ortonormais, mas não quadrada, satisfaz QQ^T = I?

Não. Se Q é m × n com m > n, vale Q^TQ = I, mas QQ^T é a matriz m × m de projeção sobre C(Q). Por exemplo, para Q = (1, 1)^T/√2, de tamanho 2 × 1, temos Q^TQ = 1, mas QQ^T = 1/21/21/21/2: o vetor (1, −1)^T, ortogonal à coluna de Q, é levado no vetor nulo.

Por que a energia do sinal não muda na base de cossenos?

Porque a matriz Q da base de cossenos é ortogonal. Para os coeficientes y = Q^Tx de um sinal x, isso dá ‖y‖² = ‖Q^Tx‖² = x^TQQ^Tx = x^Tx = ‖x‖², pois QQ^T = I para uma matriz quadrada com Q^TQ = I. Por isso, ao descartar coeficientes, a energia perdida, ‖x − x̃‖², é exatamente a soma dos quadrados dos coeficientes descartados.

Bases ortogonais e processo de Gram-Schmidt

Modo da bancada

Gram-Schmidt passo a passo

A = QR

Comprimentos e ângulos

Coordenadas na base ortonormal

A matriz Q e o produto Q^TQ

Exemplos

Vetores de entrada

A matriz Q

O que mostrar

Arredondamento e compressão

Perda de ortogonalidade

As entradas de Q^TQ − I

O sinal x e a reconstrução com k coeficientes

Os coeficientes y = Q^Tx

Um vetor da base

Experimento

Gram-Schmidt em ponto flutuante

Sinal e compressão

Bases ortonormais e o processo de Gram-Schmidt

Vetores ortonormais

Vetores ortonormais são linearmente independentes

Matrizes com colunas ortonormais

Exemplos no plano

Coordenadas numa base ortonormal

Projeção sobre o espaço gerado por vetores ortonormais

O processo

Um exemplo e o caso dependente

A fatoração A = QR

Um exemplo e os mínimos quadrados

Gram-Schmidt clássico e modificado

A base de cossenos e a compressão

Para pensar

Bases ortogonais e processo de Gram-Schmidt

Modo da bancada

Gram-Schmidt passo a passo

A = QR

Comprimentos e ângulos

Coordenadas na base ortonormal

A matriz Q e o produto QTQ

Exemplos

Vetores de entrada

A matriz Q

O que mostrar

Arredondamento e compressão

Perda de ortogonalidade

As entradas de QTQ − I

O sinal x e a reconstrução com k coeficientes

Os coeficientes y = QTx

Um vetor da base

Experimento

Gram-Schmidt em ponto flutuante

Sinal e compressão

Bases ortonormais e o processo de Gram-Schmidt

Vetores ortonormais

Vetores ortonormais são linearmente independentes

Matrizes com colunas ortonormais

Exemplos no plano

Coordenadas numa base ortonormal

Projeção sobre o espaço gerado por vetores ortonormais

O processo

Um exemplo e o caso dependente

A fatoração A = QR

Um exemplo e os mínimos quadrados

Gram-Schmidt clássico e modificado

A base de cossenos e a compressão

Para pensar

A matriz Q e o produto Q^TQ

As entradas de Q^TQ − I

Os coeficientes y = Q^Tx