Processo de Gram-Schmidt

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 Rⁿ. O processo de Gram–Schmidt recebe um conjunto finito, linearmente independente de vetores S = {v₁, …, v_n} e retorna um conjunto ortogonal 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. Na teoria da Lie group decompositions é generalizado pela decomposição de Iwasawa.

O processo de Gram-Schmidt

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 u₁, …, u_k é o sistema de vetores ortogonais e (não necessariamente) normalizados e₁, …, e_k 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 〈u₁, u₂〉 substituindo a fórmula acima por u₂: encontra-se 0 (zero). Então usando esse facto para computar 〈u₁, u₃〉 novamente substituindo a fórmula por u₃: 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

Considere o seguinte grupo de vetores no R² (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 u₁ e u₂ 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

aproximação

Quando implementado em um computador, os vetores u_k 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 u_k 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

• Gram–Schmidt orthogonalization on the Earliest known uses of some of the words of mathematics