Processo de Gram-Schmidt

no qual ⟨ v , u ⟩ {\displaystyle \langle \mathbf {v} ,\mathbf {u} \rangle } denota o produto interno dos vetores v e u. Esse operador projeta o vetor v ortogonalmente sobre a linha gerada pelo vetor u. Se u=0, define-se p r o j 0 ( v ) := 0 {\displaystyle \mathrm {proj} _{0}\,(\mathbf {v} ):=0} . i.e., o mapa projetado p r o j 0 {\displaystyle \mathrm {proj} _{0}} é o mapa zero, enviando cada vetor ao vetor zero. O processo de Gram-Schmidt funciona então como denotado abaixo: A sequência u1, ..., uk é o sistema de vetores ortogonais requerido, e o vetores normalizados e1, ..., ek formam um conjunto ortonormal. O cálculo da sequência u1, ..., uk é conhecido como ortogonalização Gram–Schmidt,enquanto o cálculo da sequência e1, ..., ek é conhecido como ortonormalização Gram–Schmidt, à medida que os vetores estão normalizados. Para verificar se essas fórmulas produzem uma sequência ortogonal, primeiro calcule ‹ u1,u2 ›substituindo a fórmula acima por u2: obtém-se zero. Então proceda para o cálculo de ‹ u1,u3 › novamente substituindo a fórmula por u3: obtém-se mais uma vez zero. A prova geral procede por indução matemática.

Considerado o seguinte conjunto de vetores em R2 (com o produto interno convencional) Então, proceda Gram–Schmidt, a fim de obter um conjunto ortogonal de vetores: Verifica-se que os vetores u1 e u2 são de fato ortogonais: notando que, se o produto escalar de dois vetores for 0 , então eles serão ortogonais. Para vetores diferentes de zero, pode-se normalizar os vetores dividindo seu tamanhos como mostrado acima: e 1 = 1 10 ( 3 1 ) {\displaystyle \mathbf {e} _{1}={1 \over {\sqrt {10}}}{\begin{pmatrix}3\\1\end{pmatrix}}}

Quando esse processo é executado em um computador, os vetores u k {\displaystyle \mathbf {u} _{k}} muitas vezes não são muito ortogonais, devido a erros de arredondamento. Para o processo de Gram-Schmidt, tal como descrito acima, (podendo ser referenciado eventualmente como "processo de Gram-Schmidt clássico") tal perda de ortogonalidade é algo particularmente ruim; Portanto, diz-se que o processo (clássico) de Gram-Schmidt é numericamente instável. O processo de Gram-Schmidt pode ser estabilizado por meio de uma pequena modificação; tal versão do processo é por vezes referida como processo Gram-Schmidt modificado. Tal abordagem dá o mesmo resultado que a fórmula original numa aritmética exata e introduz erros menores na aritmética de finita-precisão. Ao invés de calcular o vetor uk como Cada passo encontra um vetor u k ( i ) {\displaystyle \mathbf {u} _{k}^{(i)}} ortogonal a u k ( i − 1 ) {\displaystyle \mathbf {u} _{k}^{(i-1)}} . Assim u k ( i ) {\displaystyle \mathbf {u} _{k}^{(i)}} também é ortogonalizado contra quaisquer erros introduzidos no cálculo de u k ( i − 1 ) {\displaystyle \mathbf {u} _{k}^{(i-1)}} .

O algoritmo a seguir implementa a ortonormalização Gram-Schmidt estabilizada. Os vetores v1, ..., vk são substituídos por vetores ortonormais que abrangem o mesmo subespaço. O custo desse algoritmo é assintoticamente 2nk2 operações de ponto flutuante, nas quais n é a dimensionalidade dos vetores (Golub & Van Loan 1996, §5.2.8).

O resultado do processo de Gram-Schmidt pode ser expresso em uma fórmula não-recursiva usando determinantes. na qual D 0=1 e, para j ≥ 1, D j é o determinante Gram Note que a expressão para uk é um determinante "formal", i.e. a matriz contém ambos os escalares e vetores; o significado dessa expressão é definido como sendo o resultado de um cofator de expansão ao longo da linha de vetores. A fórmula determinante de Gram-Schmidt é computacionalmente mais lenta (exponencialmente mais lenta) do que os algoritmos recursivos descritos acima; é principalmente de interesse teórico.

Outros algoritmos de ortogonalização utilizam a transformação de Householder ou a rotação de Givens. Os algoritmos que utilizam a transformação de Householder são mais estáveis que o processo de Gram–Schmidt estabilizado. Por outro lado, o referido processo produz o j {\displaystyle j} th vetor ortogonalizado baseado na interação j {\displaystyle j} th, enquanto a ortogonalização utilizando a reflexão Householder produz todos os vetores apenas no final. Isso torno o processo de Gram–Schmidt aplicável ao método iterativo assim como a iteração Arnoldi. Outra alternativa é motivada ainda pelo uso da decomposição de Cholesky para invertendo a matriz das equações normais de mínimos quadrados lineares. Tome-se V {\displaystyle \mathbf {V} } a estar num posto coluna cheia de uma matriz, cujas colunas precisam ser ortogonalizadas. A matriz V ∗ V {\displaystyle \mathbf {V} ^{*}\mathbf {V} } é uma matriz transposta conjugada e definida positiva, de tal modo que possa ser escrita V ∗ V = L L ∗ , {\displaystyle \mathbf {V} ^{*}\mathbf {V} =\mathbf {L} \mathbf {L} ^{*},} utilizando a decomposição de Cholesky. A matriz triangular inferior L {\displaystyle \mathbf {L} } com entradas diagonais estritamente positivas é inversa. As colunas da matriz U = V ( L − 1 ) ∗ {\displaystyle \mathbf {U} =\mathbf {V} (\mathbf {L} ^{-1})^{*}} são ortonormais e abrangem o mesmo subespaço como as colunas da matriz original V {\displaystyle \mathbf {V} } . O uso explícito do conteúdo V ∗ V {\displaystyle \mathbf {V} ^{*}\mathbf {V} } torna o algoritmo instável, espacialmente se o produto do número de condicionamento for elevado. No entanto, esse algoritmo é utilizado na prática e implementado em alguns pacotes de software por conta de sua alta eficiência e simplicidade.