Mostrar código-fonte de Processo de Gram-Schmidt

[[Imagem:Gram–Schmidt process.svg|right|frame|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 [[Ortonormalidade|ortonormalização]] de um conjunto de [[vetor]]es em um [[espaço com produto interno]], normalmente o [[espaço euclidiano]] '''R'''<sup>''n''</sup>. O processo de Gram–Schmidt recebe um conjunto [[finito]], [[linearmente independente]] de vetores ''S'' = {''v''<sub>1</sub>, …, ''v''<sub>''n''</sub>} e retorna um conjunto [[ortonormal]] ''S''<nowiki>'</nowiki> = {''u''<sub>1</sub>, …, ''u''<sub>''n''</sub>} 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 [[Pierre-Simon Laplace|Laplace]] e [[Augustin-Louis Cauchy|Cauchy]]. Em teoria de decomposição do [[grupo de Lie]] é generalizado pela [[decomposição de Iwasawa]].<ref>{{citar livro|último =Cheney |primeiro =Ward |último2 =Kincaid |primeiro2 =David |título=Linear Algebra: Theory and Applications |local=Sudbury, Ma |publicado=Jones and Bartlett |ano=2009 |url={{Google books |plainurl=yes |id=Gg3Uj1GkHK8C |página=544 }} |isbn=978-0-7637-5020-6 |páginas=544, 558 }}</ref>

A aplicação do processo de Gram-Schmidt aos vetores de uma [[Matriz (matemática)|coluna matricial completa]] de [[Posto matricial|classificação]] produz a [[Decomposição QR|fatoração QR]] (decomposta numa [[matriz ortogonal]] e uma [[matriz triangular]]).

== O processo de Gram-Schmidt ==
[[Imagem:Gram-Schmidt orthonormalization process.gif|frame|O processo de Gram-Schmidt modificado sendo executado em três vetores linearmente independentes, não-ortogonais de base '''R'''<sup>3</sup>. Clique na imagem para obter mais detalhes.]]

Define-se o [[operador]] [[projeção (matemática)|projeção]] por:
:<math>\mathrm{proj}_{\mathbf{u}}\,(\mathbf{v}) = {\langle \mathbf{v}, \mathbf{u}\rangle\over\langle \mathbf{u}, \mathbf{u}\rangle}\mathbf{u} , </math>
no qual <math>\langle \mathbf{v}, \mathbf{u}\rangle</math> 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 <math>\mathrm{proj}_0\,(\mathbf{v}) := 0</math>. i.e., o mapa projetado <math>\mathrm{proj}_0</math> é o mapa zero, enviando cada vetor ao vetor zero.

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

: <math>
\begin{align}
\mathbf{u}_1 & = \mathbf{v}_1, & \mathbf{e}_1 & = {\mathbf{u}_1 \over \|\mathbf{u}_1\|} \\
\mathbf{u}_2 & = \mathbf{v}_2-\mathrm{proj}_{\mathbf{u}_1}\,(\mathbf{v}_2),
& \mathbf{e}_2 & = {\mathbf{u}_2 \over \|\mathbf{u}_2\|} \\
\mathbf{u}_3 & = \mathbf{v}_3-\mathrm{proj}_{\mathbf{u}_1}\,(\mathbf{v}_3)-\mathrm{proj}_{\mathbf{u}_2}\,(\mathbf{v}_3), & \mathbf{e}_3 & = {\mathbf{u}_3 \over \|\mathbf{u}_3\|} \\
\mathbf{u}_4 & = \mathbf{v}_4-\mathrm{proj}_{\mathbf{u}_1}\,(\mathbf{v}_4)-\mathrm{proj}_{\mathbf{u}_2}\,(\mathbf{v}_4)-\mathrm{proj}_{\mathbf{u}_3}\,(\mathbf{v}_4), & \mathbf{e}_4 & = {\mathbf{u}_4 \over \|\mathbf{u}_4\|} \\
& {}\ \  \vdots & & {}\ \  \vdots \\
\mathbf{u}_k & = \mathbf{v}_k-\sum_{j=1}^{k-1}\mathrm{proj}_{\mathbf{u}_j}\,(\mathbf{v}_k), & \mathbf{e}_k & = {\mathbf{u}_k\over \|\mathbf{u}_k \|}.
\end{align}
</math>

A sequência '''u'''<sub>1</sub>, ..., '''u'''<sub>''k''</sub> é o sistema de vetores ortogonais requerido, e o vetores normalizados '''e'''<sub>1</sub>, ..., '''e'''<sub>''k''</sub> formam um conjunto [[ortonormal|orto''normal'']]. O cálculo da sequência '''u'''<sub>1</sub>, ..., '''u'''<sub>''k''</sub> é conhecido como  ''[[ortogonalização]] Gram–Schmidt'',enquanto o cálculo da sequência  '''e'''<sub>1</sub>, ..., '''e'''<sub>''k''</sub> é 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'''<sub>1</sub>,'''u'''<sub>2</sub> ›substituindo a fórmula acima por '''u'''<sub>2</sub>: obtém-se zero. Então proceda para o cálculo de ‹ '''u'''<sub>1</sub>,'''u'''<sub>3</sub> › novamente substituindo a fórmula por '''u'''<sub>3</sub>: 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'''<sub>''i''</sub>, projeta-se '''v'''<sub>''i''</sub> ortogonalmente sobre o subespaço ''U'' gerado por '''u'''<sub>1</sub>, ..., '''u'''<sub>''i''−1</sub>, que é o mesmo que o subespaço gerado por '''v'''<sub>1</sub>, ..., '''v'''<sub>''i''−1</sub>. O vetor '''u'''<sub>''i''</sub> então é definido como a diferença entre '''v'''<sub>''i''</sub> 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'''<sub>''i''</sub>}<sub>''i''</sub>. O resultado é uma sequência ortogonal (ou ortonormal) {'''u'''<sub>''i''</sub>}<sub>''i''</sub> tal para número natural ''n'':
a extensão de algébrica '''v'''<sub>1</sub>, ..., '''v'''<sub>''n''</sub> é a mesma de que '''u'''<sub>1</sub>, ..., '''u'''<sub>''n''</sub>.

Se o processo de Gram-Schmidt é aplicado a uma sequência linearmente dependente, ele emite '''0''' vetor em ''i''th etapa, assumindo que '''v'''<sub>''i''</sub> é a [[combinação linear]] de {{nowrap|'''v'''<sub>1</sub>, ..., '''v'''<sub>''i''−1</sub>}}. 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) <math>(v_\alpha)_{\alpha<\lambda}</math> produz um conjunto de vetores ortonormais <math>(u_\alpha)_{\alpha<\kappa}</math> com <math>\kappa\leq\lambda</math> de tal modo que qualquer <math>\alpha\leq\lambda</math>, o  [[espaço completo|complemento]] do espaço de <math>\lbrace u_\beta : \beta<\min(\alpha,\kappa)\rbrace</math> é o mesmo que <math>\lbrace v_\beta:\beta<\alpha\rbrace</math>. 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 <math>\kappa<\lambda</math> preserva, mesmo que o conjunto inicial for linearmente independente, e o espaço de <math>(u_\alpha)_{\alpha<\kappa}</math> não precisa ser um subespaço do espaço de <math>(v_\alpha)_{\alpha<\lambda}</math> (pelo contrário, é um subespaço de sua conclusão).

== Exemplo ==
Considerado o seguinte conjunto de vetores em '''R'''<sup>2</sup> (com o produto interno convencional)
:<math>S = \left\lbrace\mathbf{v}_1=\begin{pmatrix} 3 \\ 1\end{pmatrix}, \mathbf{v}_2=\begin{pmatrix}2 \\2\end{pmatrix}\right\rbrace.</math>

Então, proceda Gram–Schmidt, a fim de obter um conjunto ortogonal de vetores:
:<math>\mathbf{u}_1=\mathbf{v}_1=\begin{pmatrix}3\\1\end{pmatrix}</math>
:<math> \mathbf{u}_2 = \mathbf{v}_2 - \mathrm{proj}_{\mathbf{u}_1} \, (\mathbf{v}_2) = \begin{pmatrix}2\\2\end{pmatrix} - \mathrm{proj}_{({3 \atop 1})} \, ({\begin{pmatrix}2\\2\end{pmatrix})} = \begin{pmatrix}2\\2\end{pmatrix} - \begin{pmatrix} 4/5 \end{pmatrix} \begin{pmatrix} 3 \\1 \end{pmatrix} = \begin{pmatrix} -2/5 \\6/5 \end{pmatrix}. </math>

Verifica-se que os vetores '''u'''<sub>1</sub> e '''u'''<sub>2</sub> são de fato ortogonais:
:<math>\langle\mathbf{u}_1,\mathbf{u}_2\rangle = \left\langle \begin{pmatrix}3\\1\end{pmatrix}, \begin{pmatrix}-2/5\\6/5\end{pmatrix} \right\rangle = -\frac65 + \frac65 = 0,</math>
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:<math>\mathbf{e}_1 = {1 \over \sqrt {10}}\begin{pmatrix}3\\1\end{pmatrix}</math>
:<math>\mathbf{e}_2 = {1 \over \sqrt{40 \over 25}} \begin{pmatrix}-2/5\\6/5\end{pmatrix}
 = {1\over\sqrt{10}} \begin{pmatrix}-1\\3\end{pmatrix}. </math>

== Estabilidade numérica ==

Quando esse processo é executado em um computador, os vetores <math>\mathbf{u}_k</math> muitas vezes não são muito ortogonais, devido a [[Erro de arredondamento|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 é [[Estabilidade numérica|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'''<sub>''k''</sub> como

:<math> \mathbf{u}_k = \mathbf{v}_k - \mathrm{proj}_{\mathbf{u}_1}\,(\mathbf{v}_k) - \mathrm{proj}_{\mathbf{u}_2}\,(\mathbf{v}_k) - \cdots - \mathrm{proj}_{\mathbf{u}_{k-1}}\,(\mathbf{v}_k), </math>
ele é calculado como
:<math> \begin{align}
\mathbf{u}_k^{(1)} &= \mathbf{v}_k - \mathrm{proj}_{\mathbf{u}_1}\,(\mathbf{v}_k), \\
\mathbf{u}_k^{(2)} &= \mathbf{u}_k^{(1)} - \mathrm{proj}_{\mathbf{u}_2} \, (\mathbf{u}_k^{(1)}), \\
& \,\,\, \vdots \\
\mathbf{u}_k^{(k-2)} &= \mathbf{u}_k^{(k-3)} - \mathrm{proj}_{\mathbf{u}_{k-2}} \, (\mathbf{u}_k^{(k-3)}), \\
\mathbf{u}_k^{(k-1)} &= \mathbf{u}_k^{(k-2)} - \mathrm{proj}_{\mathbf{u}_{k-1}} \, (\mathbf{u}_k^{(k-2)}).
\end{align} </math>

Cada passo encontra um vetor <math> \mathbf{u}_k^{(i)} </math> ortogonal a <math> \mathbf{u}_k^{(i-1)} </math>. Assim <math> \mathbf{u}_k^{(i)} </math> também é ortogonalizado contra quaisquer erros introduzidos no cálculo de <math> \mathbf{u}_k^{(i-1)} </math>.

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

== Algoritmo ==
O algoritmo a seguir implementa a ortonormalização Gram-Schmidt estabilizada. Os vetores '''v'''<sub>1</sub>, ..., '''v'''<sub>''k''</sub> são substituídos por vetores ortonormais que abrangem o mesmo subespaço.
:[[Imagem:Gram-Schmidt ortho.png|none|thumb]]
O custo desse algoritmo é assintoticamente 2''nk''<sup>2</sup> operações de ponto flutuante, nas quais ''n'' é a dimensionalidade dos vetores {{harv|Golub|Van Loan|1996|loc=§5.2.8}}.

== Fórmula determinante ==
O resultado do processo de Gram-Schmidt pode ser expresso em uma fórmula não-recursiva usando [[determinante]]s.

:<math> \mathbf{e}_j = \frac{1}{\sqrt{D_{j-1} D_j}} \begin{vmatrix}
\langle \mathbf{v}_1, \mathbf{v}_1 \rangle & \langle \mathbf{v}_2, \mathbf{v}_1 \rangle & \dots & \langle \mathbf{v}_j, \mathbf{v}_1 \rangle \\
\langle \mathbf{v}_1, \mathbf{v}_2 \rangle & \langle \mathbf{v}_2, \mathbf{v}_2 \rangle & \dots & \langle \mathbf{v}_j, \mathbf{v}_2 \rangle \\
\vdots & \vdots & \ddots & \vdots \\
\langle \mathbf{v}_1, \mathbf{v}_{j-1} \rangle & \langle \mathbf{v}_2, \mathbf{v}_{j-1} \rangle & \dots &
\langle \mathbf{v}_j, \mathbf{v}_{j-1} \rangle \\
\mathbf{v}_1 & \mathbf{v}_2 & \dots & \mathbf{v}_j \end{vmatrix} </math>

:<math> \mathbf{u}_j = \frac{1}{D_{j-1} } \begin{vmatrix}
\langle \mathbf{v}_1, \mathbf{v}_1 \rangle & \langle \mathbf{v}_2, \mathbf{v}_1 \rangle & \dots & \langle \mathbf{v}_j, \mathbf{v}_1 \rangle \\
\langle \mathbf{v}_1, \mathbf{v}_2 \rangle & \langle \mathbf{v}_2, \mathbf{v}_2 \rangle & \dots & \langle \mathbf{v}_j, \mathbf{v}_2 \rangle \\
\vdots & \vdots & \ddots & \vdots \\
\langle \mathbf{v}_1, \mathbf{v}_{j-1} \rangle & \langle \mathbf{v}_2, \mathbf{v}_{j-1} \rangle & \dots &
\langle \mathbf{v}_j, \mathbf{v}_{j-1} \rangle \\
\mathbf{v}_1 & \mathbf{v}_2 & \dots & \mathbf{v}_j \end{vmatrix} </math>

na qual ''D'' <sub>0</sub>=1 e, para ''j'' ≥ 1, ''D <sub>j</sub>'' é o [[Matriz de Gram|determinante Gram]]

:<math> D_j = \begin{vmatrix}
\langle \mathbf{v}_1, \mathbf{v}_1 \rangle & \langle \mathbf{v}_2, \mathbf{v}_1 \rangle & \dots & \langle \mathbf{v}_j, \mathbf{v}_1 \rangle \\
\langle \mathbf{v}_1, \mathbf{v}_2 \rangle & \langle \mathbf{v}_2, \mathbf{v}_2 \rangle & \dots & \langle \mathbf{v}_j, \mathbf{v}_2 \rangle \\
\vdots & \vdots & \ddots & \vdots \\
\langle \mathbf{v}_1, \mathbf{v}_j \rangle & \langle \mathbf{v}_2, \mathbf{v}_j\rangle & \dots &
\langle \mathbf{v}_j, \mathbf{v}_j \rangle \end{vmatrix}.  </math>

Note que a expressão para '''u'''<sub>k</sub> é 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 [[teorema de Laplace|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 <math>j</math>th vetor ortogonalizado baseado na interação <math>j</math>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 [[mínimos quadrados ordinários|invertendo a matriz das equações normais de mínimos quadrados lineares]]. Tome-se <math>\mathbf{V}</math> a estar num [[posto matricial|posto coluna cheia]] de uma matriz, cujas colunas precisam ser ortogonalizadas. A matriz <math>\mathbf{V}^{*} \mathbf{V} </math> é uma [[matriz transposta conjugada]] e [[Matriz definida positiva|definida positiva]], de tal modo que possa ser escrita <math> \mathbf{V}^{*} \mathbf{V} = \mathbf{L} \mathbf{L}^{*}, </math> utilizando a [[decomposição de Cholesky]]. A matriz triangular inferior <math>\mathbf{L} </math> com entradas diagonais estritamente positivas é [[elemento inverso|inversa]]. As colunas da matriz <math>\mathbf{U}= \mathbf{V}(\mathbf{L}^{-1})^{*}</math> são [[ortonormal|ortonormais]] e [[espaço vetorial gerado|abrangem]] o mesmo subespaço como as colunas da matriz original <math>\mathbf{V}</math>. O uso explícito do conteúdo <math>\mathbf{V}^{*} \mathbf{V} </math> 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.<ref>Hasegawa, et al., First-principles calculations of electron states of a silicon nanowire with 100,000 atoms on the K computer. 2011 </ref>

{{referências}}

== Leituras adicionais ==
* {{Citation |último1 =Bau III |primeiro1 =David |último2 =Trefethen |primeiro2 =Lloyd N. |autorlink2 =Lloyd N. Trefethen |título=Numerical linear algebra |publicado=Society for Industrial and Applied Mathematics |local=Philadelphia | isbn=978-0-89871-361-9 |ano=1997}}.
* {{Citation |último1 =Golub |primeiro1 =Gene H. |autorlink1 =Gene H. Golub |último2 =Van Loan |primeiro2 =Charles F. |autorlink2 =Charles F. Van Loan |título=Matrix Computations |publicado=Johns Hopkins |edição=3rd | isbn=978-0-8018-5414-9 |ano=1996}}.
* {{Citation |último1 =Greub |primeiro1 =Werner |título=Linear Algebra |publicado= Springer |edição=4th |ano= 1975}}.
* {{Citation |último1 =Soliverez |primeiro1 =C. E. |último2 =Gagliano |primeiro2 =E. | url=http://rmf.smf.mx/pdf/rmf/31/4/31_4_743.pdf|título=Orthonormalization on the plane: a geometric approach |periódico=Mex. J. Phys. | volume=31 |número=4 |páginas=743-758 |ano=1985}}.

== Ligações externas ==
{{Portal|Matemática}}
* {{springer|title=Orthogonalization|id=p/o070420}}
* [http://www.math.hmc.edu/calculus/tutorials/gramschmidt/gramschmidt.pdf Harvey Mudd College Math Tutorial on the Gram-Schmidt algorithm]
* [http://jeff560.tripod.com/g.html 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: [http://www.bigsigma.com/en/demo/gram-schmidt-plane Gram Schmidt process in plane] e [http://www.bigsigma.com/en/demo/gram-schmidt-space Gram Schmidt process in space]
* [http://www.math.ucla.edu/~tao/resource/general/115a.3.02f/GramSchmidt.html Gram-Schmidt orthogonalization applet]
* [http://www.nag.co.uk/numeric/fl/nagdoc_fl24/html/F05/f05conts.html NAG Gram–Schmidt orthogonalization of n vectors of order m routine]
* Prova: [http://planetmath.org/ProofOfGramSchmidtOrthogonalizationProcedure Raymond Puzio, Keenan Kidwell. "proof of Gram-Schmidt orthogonalization algorithm" (version 8). PlanetMath.org.]

{{Álgebra linear}}

[[Categoria:Álgebra linear]]
[[Categoria:Análise funcional]]