Proceso de Gram-Schmidt

dereita|conmarco| Os dous primeiros pasos do proceso de Gram-Schmidt

En matemáticas, especialmente en álxebra linear e análise numérica, o **proceso de Gram-Schmidt** ou algoritmo de Gram-Schmidt é unha forma de atopar un conxunto de dous ou máis vectores perpendiculares entre si.

Por definición técnica, é un método para construír unha base ortonormal a partir dun conxunto de vectores nun espazo de produto interno, máis comunmente o espazo euclidiano \mathbb{R}^n equipado co produto interno estándar. O proceso de Gram-Schmidt toma un conxunto finito de vectores linearmente independentes S = \{ \mathbf{v}_1, \ldots, \mathbf{v}_k \} para  e xera un conxunto ortogonal S' = \{ \mathbf{u}_1, \ldots, \mathbf{u}_k \} que expande o mesmo k-subespazo dimensional de \mathbb{R}^n como S.

O método leva o nome de Jørgen Pedersen Gram e Erhard Schmidt, pero Pierre-Simon Laplace estaba familiarizado con el antes de Gram e Schmidt. Na teoría das descomposicións do grupo de Lie, xeneralízase pola descomposición de Iwasawa.

A aplicación do proceso de Gram-Schmidt aos vectores columna dunha matriz de rango de columna completa produce a descomposición QR (descompónse nunha matriz ortogonal e triangular).

## Proceso de Gram-Schmidt 
miniatura|400x400px| O proceso de Gram-Schmidt modificado executándose en tres vectores linearmente independentes e non ortogonais nunha base para \mathbb{R}^3. Clica na imaxe para ver os detalles. A modificación explícase na sección Estabilidade numérica deste artigo.
A proxección vectorial dun vector \mathbf v nun vector distinto de cero \mathbf u defínese como  
:\operatorname{proj}_{\mathbf u} (\mathbf{v}) = \frac{\langle \mathbf{v}, \mathbf{u}\rangle}{\langle \mathbf{u}, \mathbf{u}\rangle} \,\mathbf{u}, 
onde \langle \mathbf{v}, \mathbf{u}\rangle 
denota o produto interno dos vectores \mathbf u e \mathbf v. Isto significa que \operatorname{proj}_{\mathbf u} (\mathbf{v}) é a proxección ortogonal de \mathbf v na liña expandida por \mathbf u. Se \mathbf u é o vector cero, entón \operatorname{proj}_{\mathbf u} (\mathbf{v}) defínese como o vector cero.

Dados k vectores linearmente independentes distintos de cero \mathbf{v}_1, \ldots, \mathbf{v}_k, o proceso de Gram-Schmidt define os vectores \mathbf{u}_1, \ldots, \mathbf{u}_k do seguinte xeito: 
:\begin{align}
\mathbf{u}_1 & = \mathbf{v}_1, & \!\mathbf{e}_1 & = \frac{\mathbf{u}_1}{\|\mathbf{u}_1\|} \\
\mathbf{u}_2 & = \mathbf{v}_2-\operatorname{proj}_{\mathbf{u}_1} (\mathbf{v}_2),
& \!\mathbf{e}_2 & = \frac{\mathbf{u}_2}{\|\mathbf{u}_2\|} \\
\mathbf{u}_3 & = \mathbf{v}_3-\operatorname{proj}_{\mathbf{u}_1} (\mathbf{v}_3) - \operatorname{proj}_{\mathbf{u}_2} (\mathbf{v}_3),
& \!\mathbf{e}_3 & = \frac{\mathbf{u}_3 }{\|\mathbf{u}_3\|} \\
\mathbf{u}_4 & = \mathbf{v}_4-\operatorname{proj}_{\mathbf{u}_1} (\mathbf{v}_4)-\operatorname{proj}_{\mathbf{u}_2} (\mathbf{v}_4)-\operatorname{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}\operatorname{proj}_{\mathbf{u}_j} (\mathbf{v}_k),
& \!\mathbf{e}_k & = \frac{\mathbf{u}_k}{\|\mathbf{u}_k\|}.
\end{align}

A secuencia \mathbf{u}_1, \ldots, \mathbf{u}_k é o sistema necesario de vectores ortogonais e os vectores normalizados \mathbf{e}_1, \ldots, \mathbf{e}_k forman un conxunto ortonormal. O cálculo da secuencia \mathbf{u}_1, \ldots, \mathbf{u}_k coñécese como *ortogonalización de Gram-Schmidt*, e o cálculo da secuencia \mathbf{e}_1, \ldots, \mathbf{e}_k coñécese como *ortonormalización de Gram-Schmidt* .

Xeométricamente, este método procede do seguinte xeito: calcular \mathbf{u}_i, que proxecta \mathbf{v}_i ortogonalmente sobre o subespazo U xerado por \mathbf{u}_1, \ldots, \mathbf{u}_{i-1}, que é o mesmo que o subespazo xerado por \mathbf{v}_1, \ldots, \mathbf{v}_{i-1}. O vector \mathbf{u}_i entón defínese como a diferenza entre \mathbf{v}_i e esta proxección, onde está garantido que é ortogonal a todos os vectores do subespazo U.

Se o proceso de Gram-Schmidt se aplica a unha secuencia linearmente dependente, dá como resultado o vector  no paso i, asumindo que \mathbf{v}_i é unha combinación linear de \mathbf{v}_1, \ldots, \mathbf{v}_{i-1}. Se se debe producir unha base ortonormal, entón o algoritmo debería probar vectores cero na saída e descartalos porque ningún múltiplo dun vector cero pode ter unha lonxitude de 1. O número de vectores producidos polo algoritmo será logo a dimensión do espazo estendido polas entradas orixinais.

## Exemplo 
### Espazo euclidiano 
Considere o seguinte conxunto de vectores en \mathbb{R}^2 (co produto interno convencional) 
:S = \left\{\mathbf{v}_1=\begin{bmatrix} 3 \\ 1\end{bmatrix}, \mathbf{v}_2=\begin{bmatrix}2 \\2\end{bmatrix}\right\}.

Agora, realizamos o algoritmo de Gram–Schmidt, para obter un conxunto ortogonais de vectores: 
:\mathbf{u}_1=\mathbf{v}_1=\begin{bmatrix}3\\1\end{bmatrix}
: \mathbf{u}_2 = \mathbf{v}_2 - \operatorname{proj}_{\mathbf{u}_1} (\mathbf{v}_2)
= \begin{bmatrix}2\\2\end{bmatrix} - \operatorname{proj}_{\left[\begin{smallmatrix}3 \\ 1\end{smallmatrix}\right]} {\begin{bmatrix}2\\2\end{bmatrix}}
= \begin{bmatrix}2\\2\end{bmatrix} - \frac{8}{10} \begin{bmatrix} 3 \\1 \end{bmatrix}
= \begin{bmatrix} -2/5 \\6/5 \end{bmatrix}. 

Comprobamos que os vectores \mathbf{u}_1 e \mathbf{u}_2 son de feito ortogonais: 
:\langle\mathbf{u}_1,\mathbf{u}_2\rangle = \left\langle \begin{bmatrix}3\\1\end{bmatrix}, \begin{bmatrix} -2/5 \\ 6/5 \end{bmatrix} \right\rangle = -\frac{6}{5} + \frac{6}{5} = 0, 
tendo en conta que se o produto escalar de dous vectores é 0 daquela son ortogonais.

Para vectores distintos de cero, podemos normalizar os vectores dividindo os seus tamaños como se mostra enriba: 
:\mathbf{e}_1 = \frac{1}{\sqrt {10}}\begin{bmatrix}3\\1\end{bmatrix}
:\mathbf{e}_2 = \frac{1}{\sqrt{40 \over 25}} \begin{bmatrix}-2/5\\6/5\end{bmatrix}
= \frac{1}{\sqrt{10}} \begin{bmatrix}-1\\3\end{bmatrix}. 

## Propiedades 
Denotemos como   \operatorname{GS}(\mathbf{v}_1, \dots, \mathbf{v}_k)  o resultado de aplicar o proceso de Gram-Schmidt a unha colección de vectores  \mathbf{v}_1, \dots, \mathbf{v}_k . Isto dá un mapa  \operatorname{GS} \colon (\R^n)^{k} \to (\R^n)^{k} .

Ten as seguintes propiedades:

* É continuo
* Preserva a orientación no sentido de que  \operatorname{or}(\mathbf{v}_1,\dots,\mathbf{v}_k) = \operatorname{or}(\operatorname{GS}(\mathbf{v}_1,\dots,\mathbf{v}_k))  .
* Conmuta con mapas ortogonais:

Sexa  g \colon \R^n \to \R^n  ortogonal (en relación ao produto interno dado). Daquela  temos 
: \operatorname{GS}(g(\mathbf{v}_1),\dots,g(\mathbf{v}_k)) = \left( g(\operatorname{GS}(\mathbf{v}_1,\dots,\mathbf{v}_k)_1),\dots,g(\operatorname{GS}(\mathbf{v}_1,\dots,\mathbf{v}_k)_k) \right) 

## Estabilidade numérica 
Cando este proceso se implementa nun ordenador, os vectores \mathbf{u}_k moitas veces non son completamente ortogonais, debido a erros de redondeo  Para o proceso de Gram-Schmidt tal como se describiu anteriormente (ás veces referido como "Gram-Schmidt clásico") esta perda de ortogonalidade é particularmente ruín; polo tanto, dise que o proceso de Gram-Schmidt (clásico) é numericamente inestábel.

O proceso de Gram-Schmidt pódese estabilizar mediante unha pequena modificación; esta versión ás veces denomínase **Gram-Schmidt modificado** ou MGS. Este enfoque dá o mesmo resultado que a fórmula orixinal en aritmética exacta e introduce erros menores na aritmética de precisión finita.

En lugar de calcular o vector  como 
: \mathbf{u}_k = \mathbf{v}_k - \operatorname{proj}_{\mathbf{u}_1} (\mathbf{v}_k) - \operatorname{proj}_{\mathbf{u}_2} (\mathbf{v}_k) - \cdots - \operatorname{proj}_{\mathbf{u}_{k-1}} (\mathbf{v}_k),  
calcúlase como 
: \begin{align}
\mathbf{u}_k^{(1)} &= \mathbf{v}_k - \operatorname{proj}_{\mathbf{u}_1} (\mathbf{v}_k), \\
\mathbf{u}_k^{(2)} &= \mathbf{u}_k^{(1)} - \operatorname{proj}_{\mathbf{u}_2} \left(\mathbf{u}_k^{(1)}\right), \\
& \;\; \vdots \\
\mathbf{u}_k^{(k-2)} &= \mathbf{u}_k^{(k-3)} - \operatorname{proj}_{\mathbf{u}_{k-2}} \left(\mathbf{u}_k^{(k-3)}\right), \\
\mathbf{u}_k^{(k-1)} &= \mathbf{u}_k^{(k-2)} - \operatorname{proj}_{\mathbf{u}_{k-1}} \left(\mathbf{u}_k^{(k-2)}\right), \\
\mathbf{e}_k &= \frac{\mathbf{u}_k^{(k-1)}}{\left\|\mathbf{u}_k^{(k-1)}\right\|}
\end{align}.

## Vía eliminación gaussiana 
Se as filas {{Math|{**v**1, ..., **v***k*}}} escríbense como unha matriz A, logo aplicando a  eliminación gaussiana á matriz aumentada \left[A A^\mathsf{T} | A \right] producirá os vectores ortogonalizados en lugar de A. Porén a matriz A A^\mathsf{T} debe levarse á forma graduada de filas, utilizando só a operación de fila de engadir un múltiplo escalar dunha fila a outra. Por exemplo, tomando \mathbf{v}_1 = \begin{bmatrix} 3 & 1\end{bmatrix}, \mathbf{v}_2=\begin{bmatrix}2 & 2\end{bmatrix} como enriba, temos 
:\left[A A^\mathsf{T} | A \right] = \left[\begin{array}{rr|rr} 10 & 8 & 3 & 1 \\ 8 & 8 & 2 & 2\end{array}\right]

E reducir isto á forma graduada de filas produce 
:\left[\begin{array}{rr|rr} 1 & .8 & .3 & .1 \\ 0 & 1 & -.25 & .75\end{array}\right]

Os vectores normalizados son logo 
:\mathbf{e}_1 = \frac{1}{\sqrt {.3^2+.1^2}}\begin{bmatrix}.3 & .1\end{bmatrix} = \frac{1}{\sqrt{10}} \begin{bmatrix}3 & 1\end{bmatrix}
:\mathbf{e}_2 = \frac{1}{\sqrt{.25^2+.75^2}} \begin{bmatrix}-.25 & .75\end{bmatrix} = \frac{1}{\sqrt{10}} \begin{bmatrix}-1 & 3\end{bmatrix}, 
como no exemplo anterior.

## Expresado mediante álxebra xeométrica 
Expresados usando a notación usada en álxebra xeométrica, os resultados non normalizados do proceso de Gram-Schmidt pódense expresar como 
:\mathbf{u}_k = \mathbf{v}_k - \sum_{j=1}^{k-1} (\mathbf{v}_k \cdot \mathbf{u}_j)\mathbf{u}_j^{-1}\ , 
que é equivalente á expresión que utiliza o operador \operatorname{proj} definido anteriormente. Os resultados pódense expresar de forma equivalente como
:\mathbf{u}_k = \mathbf{v}_{k}\wedge\mathbf{v}_{k-1}\wedge\cdot\cdot\cdot\wedge\mathbf{v}_{1}(\mathbf{v}_{k-1}\wedge\cdot\cdot\cdot\wedge\mathbf{v}_{1})^{-1}, 
que está moi relacionado coa expresión usando determinantes.

## Alternativas 
Outros algoritmos de ortogonalización usan as  transformacións de Householder ou as rotacións de Givens. Os algoritmos que utilizan as transformacións de Householder son máis estábeis que o proceso de Gram-Schmidt estabilizado. Por outra banda, o proceso de Gram-Schmidt produce o j-ésimo vector ortogonalizado despois do j-ésima iteración, mentres que a ortogonalización usando as reflexións de Householder produce todos os vectores só ao final. Isto fai que só o proceso de Gram-Schmidt sexa aplicábel a métodos iterativos como a iteración de Arnoldi.

## Notas 
## Véxase tamén 
### Bibliografía 
* .
* .
* .
* .

### Outros artigos 
* Álxebra linear
* Recursión
* Ortogonalidade (matemáticas)
### Ligazóns externas 
* 
* Harvey Mudd College Math Tutorial on the Gram-Schmidt algorithm
* Earliest known uses of some of the words of mathematics: G 
* Demos: 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
* Proba: Raymond Puzio, Keenan Kidwell. "proof of Gram-Schmidt orthogonalization algorithm" (version 8). PlanetMath.org.