Processo de Gram-Schmidt

Os dois primeiros passos de um processo Gram–Schmidt

Em matemática e análise numérica, o processo de Gram-Schmidt é um método para ortonormalização de um conjunto de vetores em um espaço com produto interno, normalmente o espaço euclidiano Rⁿ. O processo de Gram–Schmidt recebe um conjunto finito, linearmente independente de vetores S = {v₁, …, v_n} e retorna um conjunto ortonormal S' = {u₁, …, u_n} que gera o mesmo subespaço S inicial.

O método leva o nome de Jørgen Pedersen Gram e Erhard Schmidt, mas pode ser encontrado antes nos trabalhos de Laplace e Cauchy. Em teoria de decomposição do grupo de Lie é generalizado pela decomposição de Iwasawa.

A aplicação do processo de Gram-Schmidt aos vetores de uma coluna matricial completa de classificação produz a fatoração QR (decomposta numa matriz ortogonal e uma matriz triangular).

O processo de Gram-Schmidt

O processo de Gram-Schmidt modificado sendo executado em três vetores linearmente independentes, não-ortogonais de base R³. Clique na imagem para obter mais detalhes.

Define-se o operador projeção por:

${\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{𝐮}(𝐯)=\frac{⟨𝐯,𝐮⟩}{⟨𝐮,𝐮⟩}𝐮,$

no qual $⟨𝐯,𝐮⟩$ 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 ${\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_0(𝐯):=0$. i.e., o mapa projetado ${\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_0$ é o mapa zero, enviando cada vetor ao vetor zero.

O processo de Gram-Schmidt funciona então como denotado abaixo:

$\begin{array}{cccc}{𝐮}_1& ={𝐯}_1,& {𝐞}_1& =\frac{{𝐮}_1}{\Vert {𝐮}_1\Vert }\\ {𝐮}_2& ={𝐯}_2-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_1}({𝐯}_2),& {𝐞}_2& =\frac{{𝐮}_2}{\Vert {𝐮}_2\Vert }\\ {𝐮}_3& ={𝐯}_3-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_1}({𝐯}_3)-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_2}({𝐯}_3),& {𝐞}_3& =\frac{{𝐮}_3}{\Vert {𝐮}_3\Vert }\\ {𝐮}_4& ={𝐯}_4-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_1}({𝐯}_4)-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_2}({𝐯}_4)-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_3}({𝐯}_4),& {𝐞}_4& =\frac{{𝐮}_4}{\Vert {𝐮}_4\Vert }\\ & ⋮& & ⋮\\ {𝐮}_k& ={𝐯}_k-\sum _{j=1}^{k-1}{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_j}({𝐯}_k),& {𝐞}_k& =\frac{{𝐮}_k}{\Vert {𝐮}_k\Vert }.\end{array}$

A sequência u₁, ..., u_k é o sistema de vetores ortogonais requerido, e o vetores normalizados e₁, ..., e_k formam um conjunto ortonormal. O cálculo da sequência u₁, ..., u_k é conhecido como ortogonalização Gram–Schmidt,enquanto o cálculo da sequência e₁, ..., e_k é 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 ‹ u₁,u₂ ›substituindo a fórmula acima por u₂: obtém-se zero. Então proceda para o cálculo de ‹ u₁,u₃ › novamente substituindo a fórmula por u₃: obtém-se mais uma vez zero. A prova geral procede por indução matemática.

Geometricamente, esse método se segue como: para calcular u_i, projeta-se v_i ortogonalmente sobre o subespaço U gerado por u₁, ..., u_i−1, que é o mesmo que o subespaço gerado por v₁, ..., v_i−1. O vetor u_i então é definido como a diferença entre v_i e essa projeção, garantido como ortogonal para todos os vetores no subespaço U.

O processo de Gram-Schmidt também se aplica a uma sequência de conjunto contável linear e independente {v_i}_i. O resultado é uma sequência ortogonal (ou ortonormal) {u_i}_i tal para número natural n: a extensão de algébrica v₁, ..., v_n é a mesma de que u₁, ..., u_n.

Se o processo de Gram-Schmidt é aplicado a uma sequência linearmente dependente, ele emite 0 vetor em ith etapa, assumindo que v_i é a combinação linear de Predefinição:Nowrap. Se uma base ortonormal está a ser produzida, então o algoritmo deve testar para zero vetores na saída (output) e descartá-los porque nenhum múltiplo de um vetor zero pode ter um comprimento de valor 1. O número de vetores de saída dados pelo algoritmo será então a dimensão do espaço gerado pelos inputs originais.

Uma variante do processo de Gram-Schmidt utilizando indução transfinita aplicada a uma sequência infinita de vetores (possivelmente incontável) $(v_{\alpha }{)}_{\alpha <\lambda }$ produz um conjunto de vetores ortonormais $(u_{\alpha }{)}_{\alpha <\kappa }$ com $\kappa \le \lambda$ de tal modo que qualquer $\alpha \le \lambda$, o complemento do espaço de $\{u_{\beta }:\beta <\min (\alpha ,\kappa )\}$ é o mesmo que $\{v_{\beta }:\beta <\alpha \}$. Particularmente, quando aplicado a uma base (algébrica) de um espaço de Hilbert (ou, mais geralmente, uma base de qualquer subespaço denso), produz-se uma base ortonormal (analítica-funcional). Note-se que, no caso geral, muitas vezes a desigualdade estrita $\kappa <\lambda$ preserva, mesmo que o conjunto inicial for linearmente independente, e o espaço de $(u_{\alpha }{)}_{\alpha <\kappa }$ não precisa ser um subespaço do espaço de $(v_{\alpha }{)}_{\alpha <\lambda }$ (pelo contrário, é um subespaço de sua conclusão).

Exemplo

Considerado o seguinte conjunto de vetores em R² (com o produto interno convencional)

$S=\{{𝐯}_1=\left(\begin{array}{c}3\\ 1\end{array}\right),{𝐯}_2=\left(\begin{array}{c}2\\ 2\end{array}\right)\}.$

Então, proceda Gram–Schmidt, a fim de obter um conjunto ortogonal de vetores:

${𝐮}_1={𝐯}_1=\left(\begin{array}{c}3\\ 1\end{array}\right)$

${𝐮}_2={𝐯}_2-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_1}({𝐯}_2)=\left(\begin{array}{c}2\\ 2\end{array}\right)-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{(\genfrac{}{}{0ex}{}{3}{1})}(\left(\begin{array}{c}2\\ 2\end{array}\right))=\left(\begin{array}{c}2\\ 2\end{array}\right)-\left(\begin{array}{c}4/5\end{array}\right)\left(\begin{array}{c}3\\ 1\end{array}\right)=\left(\begin{array}{c}-2/5\\ 6/5\end{array}\right).$

Verifica-se que os vetores u₁ e u₂ são de fato ortogonais:

$⟨{𝐮}_1,{𝐮}_2⟩=⟨\left(\begin{array}{c}3\\ 1\end{array}\right),\left(\begin{array}{c}-2/5\\ 6/5\end{array}\right)⟩=-\frac{6}{5}+\frac{6}{5}=0,$

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:${𝐞}_1=\frac{1}{\sqrt{10}}\left(\begin{array}{c}3\\ 1\end{array}\right)$

${𝐞}_2=\frac{1}{\sqrt{\frac{40}{25}}}\left(\begin{array}{c}-2/5\\ 6/5\end{array}\right)=\frac{1}{\sqrt{10}}\left(\begin{array}{c}-1\\ 3\end{array}\right).$

Estabilidade numérica

Quando esse processo é executado em um computador, os vetores ${𝐮}_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 u_k como

${𝐮}_k={𝐯}_k-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_1}({𝐯}_k)-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_2}({𝐯}_k)-\cdots -{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_{k-1}}({𝐯}_k),$

ele é calculado como

$\begin{array}{cc}{𝐮}_k^{(1)}& ={𝐯}_k-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_1}({𝐯}_k),\\ {𝐮}_k^{(2)}& ={𝐮}_k^{(1)}-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_2}({𝐮}_k^{(1)}),\\ & ⋮\\ {𝐮}_k^{(k-2)}& ={𝐮}_k^{(k-3)}-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_{k-2}}({𝐮}_k^{(k-3)}),\\ {𝐮}_k^{(k-1)}& ={𝐮}_k^{(k-2)}-{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_{k-1}}({𝐮}_k^{(k-2)}).\end{array}$

Cada passo encontra um vetor ${𝐮}_k^{(i)}$ ortogonal a ${𝐮}_k^{(i-1)}$. Assim ${𝐮}_k^{(i)}$ também é ortogonalizado contra quaisquer erros introduzidos no cálculo de ${𝐮}_k^{(i-1)}$.

Este método é utilizado na animação anterior, quando o vetor intermediário v'₃ é usado na ortogonalização do vetor azul v₃.

Algoritmo

O algoritmo a seguir implementa a ortonormalização Gram-Schmidt estabilizada. Os vetores v₁, ..., v_k são substituídos por vetores ortonormais que abrangem o mesmo subespaço.

O custo desse algoritmo é assintoticamente 2nk² operações de ponto flutuante, nas quais n é a dimensionalidade dos vetores Predefinição:Harv.

Fórmula determinante

O resultado do processo de Gram-Schmidt pode ser expresso em uma fórmula não-recursiva usando determinantes.

${𝐞}_j=\frac{1}{\sqrt{D_{j-1}{D}_j}}\left|\begin{array}{cccc}⟨{𝐯}_1,{𝐯}_1⟩& ⟨{𝐯}_2,{𝐯}_1⟩& \dots & ⟨{𝐯}_j,{𝐯}_1⟩\\ ⟨{𝐯}_1,{𝐯}_2⟩& ⟨{𝐯}_2,{𝐯}_2⟩& \dots & ⟨{𝐯}_j,{𝐯}_2⟩\\ ⋮& ⋮& \ddots & ⋮\\ ⟨{𝐯}_1,{𝐯}_{j-1}⟩& ⟨{𝐯}_2,{𝐯}_{j-1}⟩& \dots & ⟨{𝐯}_j,{𝐯}_{j-1}⟩\\ {𝐯}_1& {𝐯}_2& \dots & {𝐯}_j\end{array}\right|$

${𝐮}_j=\frac{1}{D_{j-1}}\left|\begin{array}{cccc}⟨{𝐯}_1,{𝐯}_1⟩& ⟨{𝐯}_2,{𝐯}_1⟩& \dots & ⟨{𝐯}_j,{𝐯}_1⟩\\ ⟨{𝐯}_1,{𝐯}_2⟩& ⟨{𝐯}_2,{𝐯}_2⟩& \dots & ⟨{𝐯}_j,{𝐯}_2⟩\\ ⋮& ⋮& \ddots & ⋮\\ ⟨{𝐯}_1,{𝐯}_{j-1}⟩& ⟨{𝐯}_2,{𝐯}_{j-1}⟩& \dots & ⟨{𝐯}_j,{𝐯}_{j-1}⟩\\ {𝐯}_1& {𝐯}_2& \dots & {𝐯}_j\end{array}\right|$

na qual D ₀=1 e, para j ≥ 1, D _j é o determinante Gram

$D_j=\left|\begin{array}{cccc}⟨{𝐯}_1,{𝐯}_1⟩& ⟨{𝐯}_2,{𝐯}_1⟩& \dots & ⟨{𝐯}_j,{𝐯}_1⟩\\ ⟨{𝐯}_1,{𝐯}_2⟩& ⟨{𝐯}_2,{𝐯}_2⟩& \dots & ⟨{𝐯}_j,{𝐯}_2⟩\\ ⋮& ⋮& \ddots & ⋮\\ ⟨{𝐯}_1,{𝐯}_j⟩& ⟨{𝐯}_2,{𝐯}_j⟩& \dots & ⟨{𝐯}_j,{𝐯}_j⟩\end{array}\right|.$

Note que a expressão para u_k é 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.

Alternativas

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$th vetor ortogonalizado baseado na interação $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 $𝐕$ a estar num posto coluna cheia de uma matriz, cujas colunas precisam ser ortogonalizadas. A matriz ${𝐕}^{*}𝐕$ é uma matriz transposta conjugada e definida positiva, de tal modo que possa ser escrita ${𝐕}^{*}𝐕=𝐋{𝐋}^{*},$ utilizando a decomposição de Cholesky. A matriz triangular inferior $𝐋$ com entradas diagonais estritamente positivas é inversa. As colunas da matriz $𝐔=𝐕({𝐋}^{-1}{)}^{*}$ são ortonormais e abrangem o mesmo subespaço como as colunas da matriz original $𝐕$. O uso explícito do conteúdo ${𝐕}^{*}𝐕$ 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.

Em mecânica quântica existem vários esquemas de ortogonalização com características mais adequadas para certas aplicações do que os de Gram-Schmidt. No entanto, o Gram-Schmidt continua a ser um algoritmo popular e eficaz, mesmo para os maiores cálculos de estrutura eletrônica.

Leituras adicionais

• Predefinição:Citation.
• Predefinição:Citation.
• Predefinição:Citation.
• Predefinição:Citation.

Ligações externas

• Predefinição:Springer
• Harvey Mudd College Math Tutorial on the Gram-Schmidt algorithm
• Earliest known uses of some of the words of mathematics: G The entry "Gram-Schmidt orthogonalization" has some information and references on the origins of the method.
• Demonstrações: Gram Schmidt process in plane e Gram Schmidt process in space
• Gram-Schmidt orthogonalization applet
• NAG Gram–Schmidt orthogonalization of n vectors of order m routine
• Prova: Raymond Puzio, Keenan Kidwell. "proof of Gram-Schmidt orthogonalization algorithm" (version 8). PlanetMath.org.