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.

Os dous primeiros pasos do proceso de Gram-Schmidt

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 ${\displaystyle \mathbb {R} ^{n}}$ equipado co produto interno estándar. O proceso de Gram-Schmidt toma un conxunto finito de vectores linearmente independentes ${\displaystyle S=\{\mathbf {v} _{1},\ldots ,\mathbf {v} _{k}\}}$ para k ≤ n e xera un conxunto ortogonal ${\displaystyle S'=\{\mathbf {u} _{1},\ldots ,\mathbf {u} _{k}\}}$ que expande o mesmo ${\displaystyle k}$-subespazo dimensional de ${\displaystyle \mathbb {R} ^{n}}$ como ${\displaystyle 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.^[1] 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

O proceso de Gram-Schmidt modificado executándose en tres vectores linearmente independentes e non ortogonais nunha base para ${\displaystyle \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 ${\displaystyle \mathbf {v} }$ nun vector distinto de cero ${\displaystyle \mathbf {u} }$ defínese como

${\displaystyle \operatorname {proj} _{\mathbf {u} }(\mathbf {v} )={\frac {\langle \mathbf {v} ,\mathbf {u} \rangle }{\langle \mathbf {u} ,\mathbf {u} \rangle }}\,\mathbf {u} ,}$

onde ${\displaystyle \langle \mathbf {v} ,\mathbf {u} \rangle }$ denota o produto interno dos vectores ${\displaystyle \mathbf {u} }$ e ${\displaystyle \mathbf {v} }$. Isto significa que ${\displaystyle \operatorname {proj} _{\mathbf {u} }(\mathbf {v} )}$ é a proxección ortogonal de ${\displaystyle \mathbf {v} }$ na liña expandida por ${\displaystyle \mathbf {u} }$. Se ${\displaystyle \mathbf {u} }$ é o vector cero, entón ${\displaystyle \operatorname {proj} _{\mathbf {u} }(\mathbf {v} )}$ defínese como o vector cero.

Dados ${\displaystyle k}$ vectores linearmente independentes distintos de cero ${\displaystyle \mathbf {v} _{1},\ldots ,\mathbf {v} _{k}}$, o proceso de Gram-Schmidt define os vectores ${\displaystyle \mathbf {u} _{1},\ldots ,\mathbf {u} _{k}}$ do seguinte xeito:

${\displaystyle {\begin{aligned}\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{aligned}}}$

A secuencia ${\displaystyle \mathbf {u} _{1},\ldots ,\mathbf {u} _{k}}$ é o sistema necesario de vectores ortogonais e os vectores normalizados ${\displaystyle \mathbf {e} _{1},\ldots ,\mathbf {e} _{k}}$ forman un conxunto ortonormal. O cálculo da secuencia ${\displaystyle \mathbf {u} _{1},\ldots ,\mathbf {u} _{k}}$ coñécese como ortogonalización de Gram-Schmidt, e o cálculo da secuencia ${\displaystyle \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 ${\displaystyle \mathbf {u} _{i}}$, que proxecta ${\displaystyle \mathbf {v} _{i}}$ ortogonalmente sobre o subespazo ${\displaystyle U}$ xerado por ${\displaystyle \mathbf {u} _{1},\ldots ,\mathbf {u} _{i-1}}$, que é o mesmo que o subespazo xerado por ${\displaystyle \mathbf {v} _{1},\ldots ,\mathbf {v} _{i-1}}$. O vector ${\displaystyle \mathbf {u} _{i}}$ entón defínese como a diferenza entre ${\displaystyle \mathbf {v} _{i}}$ e esta proxección, onde está garantido que é ortogonal a todos os vectores do subespazo ${\displaystyle U}$.

Se o proceso de Gram-Schmidt se aplica a unha secuencia linearmente dependente, dá como resultado o vector 0 no paso ${\displaystyle i}$, asumindo que ${\displaystyle \mathbf {v} _{i}}$ é unha combinación linear de ${\displaystyle \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 ${\displaystyle \mathbb {R} ^{2}}$ (co produto interno convencional)

${\displaystyle 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:

${\displaystyle \mathbf {u} _{1}=\mathbf {v} _{1}={\begin{bmatrix}3\\1\end{bmatrix}}}$

${\displaystyle \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 ${\displaystyle \mathbf {u} _{1}}$ e ${\displaystyle \mathbf {u} _{2}}$ son de feito ortogonais:

${\displaystyle \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:

${\displaystyle \mathbf {e} _{1}={\frac {1}{\sqrt {10}}}{\begin{bmatrix}3\\1\end{bmatrix}}}$

${\displaystyle \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 ${\displaystyle \operatorname {GS} (\mathbf {v} _{1},\dots ,\mathbf {v} _{k})}$ o resultado de aplicar o proceso de Gram-Schmidt a unha colección de vectores ${\displaystyle \mathbf {v} _{1},\dots ,\mathbf {v} _{k}}$. Isto dá un mapa ${\displaystyle \operatorname {GS} \colon (\mathbb {R} ^{n})^{k}\to (\mathbb {R} ^{n})^{k}}$.

Ten as seguintes propiedades:

• É continuo
• Preserva a orientación no sentido de que ${\displaystyle \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 ${\displaystyle g\colon \mathbb {R} ^{n}\to \mathbb {R} ^{n}}$ ortogonal (en relación ao produto interno dado). Daquela temos

${\displaystyle \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 ${\displaystyle \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 u_k como

${\displaystyle \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

${\displaystyle {\begin{aligned}\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{aligned}}.}$

Vía eliminación gaussiana

Se as filas {v₁, ..., v_k} escríbense como unha matriz ${\displaystyle A}$, logo aplicando a eliminación gaussiana á matriz aumentada ${\displaystyle \left[AA^{\mathsf {T}}|A\right]}$ producirá os vectores ortogonalizados en lugar de ${\displaystyle A}$. Porén a matriz ${\displaystyle AA^{\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.^[2] Por exemplo, tomando ${\displaystyle \mathbf {v} _{1}={\begin{bmatrix}3&1\end{bmatrix}},\mathbf {v} _{2}={\begin{bmatrix}2&2\end{bmatrix}}}$ como enriba, temos

${\displaystyle \left[AA^{\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

${\displaystyle \left[{\begin{array}{rr|rr}1&.8&.3&.1\\0&1&-.25&.75\end{array}}\right]}$

Os vectores normalizados son logo

${\displaystyle \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}}}$

${\displaystyle \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

${\displaystyle \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 ${\displaystyle \operatorname {proj} }$ definido anteriormente. Os resultados pódense expresar de forma equivalente como^[3]

${\displaystyle \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 ${\displaystyle j}$-ésimo vector ortogonalizado despois do ${\displaystyle 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.