Processo de Gram-Schmidt

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Em matemática e análise numérica, o processo de Gram-Schmidt é um método para ortogonalização de um conjunto de vetores em um espaço com produto interno, normalmente o espaço Euclidiano Rn. O processo de Gram–Schmidt recebe um conjunto finito, linearmente independente de vetores S = {v1, …, vn} e retorna um conjunto ortonormal S' = {u1, …, un} 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. Na teoria da Lie group decompositions é generalizado pela decomposição de Iwasawa.

O processo de Gram-Schmidt[editar | editar código-fonte]

Definimos o operador projeção por

\mathrm{proj}_{\mathbf{u}}\,\mathbf{v} = {\langle \mathbf{v}, \mathbf{u}\rangle\over\langle \mathbf{u}, \mathbf{u}\rangle}\mathbf{u}.

Projeta o vetor v ortogonalmente em u.

O processo se dá da seguinte maneira:

\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||}
\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||}
Os dois primeiros passos do método de Gram-Schmidt.

A seqüencia u1, …, uk é o sistema de vetores ortogonais e (não necessariamente) normalizados e1, …, ek formam um conjunto ortonormal, ou seja: de vetores ortogonais entre si dois a dois e normalizados.

Para verificar que estas fórmulas resultam em uma sequência ortogonal, primeiro compute 〈u1, u2〉 substituindo a fórmula acima por u2: encontra-se 0 (zero). Então usando esse facto para computar 〈u1, u3〉 novamente substituindo a fórmula por u3: encontra-se 0. A prova geral processa-se por indução matemática. O processo de Gram-Schmidt determina uma base de vetores ortonormais que, ao sofrer uma composição linear por uma matriz alternativamente diagonal, se torna equivalente à aplicação linear da base canónica que sofreu o processo.

Exemplo[editar | editar código-fonte]

Considere o seguinte grupo de vetores no R2 (Com produto interno convencional)

S = \left\lbrace\mathbf{v}_1=\begin{pmatrix} 3 \\ 1\end{pmatrix}, \mathbf{v}_2=\begin{pmatrix}2 \\2\end{pmatrix}\right\rbrace.

Agora , aplicamos Gram-Schmidt,para obter um conjunto ortonormal de vetores:

\mathbf{u}_1=\mathbf{v}_1=\begin{pmatrix}3\\1\end{pmatrix}
 \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/5 \\6/5 \end{pmatrix}.

Verificamos que os vetores u1 e u2 são, de fato, ortogonais:

\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.

Podemos normaliza-los dividindo pela norma de cada um dos vetores:

\mathbf{e}_1 = {1 \over \sqrt {10}}\begin{pmatrix}3\\1\end{pmatrix}
\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}.

Estabilidade numérica[editar | editar código-fonte]

Aproximação[editar | editar código-fonte]

Quando implementado em um computador, os vetores uk não são precisamente ortogonais devido ao erro de aproximação. Para o processo de Gram–Schmidt como descrito acima essa perda de ortogonalidade é particularmente ruim; portanto, é dito que o processo ingênuo de Gram–Schmidt é numericamente instável.

O processo de Gram–Schmidt pode ser estabilizado por uma pequena modificação. Ao invés de computar o vetor uk por

 \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,

ele é computado por

 \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 = \mathbf{u}_k^{(k-2)} - \mathrm{proj}_{\mathbf{u}_{k-1}} \, \mathbf{u}_k^{(k-2)}.

Essa série de passos resulta no mesmo conjunto do processo original, porém introduz menos erro em uma aritmética de precisão finita.

Ligações externas[editar | editar código-fonte]