Proceso de Gram-Schmidt

Ortonormalización de un conjunto de vectores

Los dos primeros pasos del proceso de Gram-Schmidt

En matemáticas , particularmente en álgebra lineal y análisis numérico , el proceso de Gram-Schmidt o algoritmo de Gram-Schmidt es una forma de encontrar un conjunto de dos o más vectores que son perpendiculares entre sí.

Por definición técnica, es un método de construcción de una base ortonormal a partir de un conjunto de vectores en un espacio de producto interno , más comúnmente el espacio euclidiano equipado con el producto interno estándar . El proceso de Gram-Schmidt toma un conjunto finito de vectores linealmente independientes para k ≤ n y genera un conjunto ortogonal que abarca el mismo subespacio dimensional de como . ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle S=\{\mathbf {v} _{1},\ldots ,\mathbf {v} _{k}\}}$ ${\displaystyle S'=\{\mathbf {u} _{1},\ldots ,\mathbf {u} _{k}\}}$ ${\displaystyle k}$ ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle S}$

El método recibe su nombre de Jørgen Pedersen Gram y Erhard Schmidt , pero Pierre-Simon Laplace ya lo conocía antes que Gram y Schmidt. ^[1] En la teoría de las descomposiciones de grupos de Lie , se generaliza mediante la descomposición de Iwasawa .

La aplicación del proceso de Gram-Schmidt a los vectores de columna de una matriz de rango de columna completa produce la descomposición QR (se descompone en una matriz ortogonal y una triangular ).

El proceso de Gram-Schmidt

El proceso de Gram-Schmidt modificado se ejecuta en tres vectores linealmente independientes y no ortogonales de una base para . Haga clic en la imagen para obtener más detalles. La modificación se explica en la sección Estabilidad numérica de este artículo. ${\displaystyle \mathbb {R} ^{3}}$

La proyección vectorial de un vector sobre un vector distinto de cero se define como ^{[nota 1]} donde denota el producto interno de los vectores y . Esto significa que es la proyección ortogonal de sobre la línea generada por . Si es el vector cero, entonces se define como el vector cero. ${\displaystyle \mathbf {v} }$ ${\displaystyle \mathbf {u} }$ $${\displaystyle \operatorname {proj} _{\mathbf {u} }(\mathbf {v} )={\frac {\langle \mathbf {v} ,\mathbf {u} \rangle }{\langle \mathbf {u} ,\mathbf {u} \rangle }}\,\mathbf {u} ,}$$ ${\displaystyle \langle \mathbf {v} ,\mathbf {u} \rangle }$ ${\displaystyle \mathbf {u} }$ ${\displaystyle \mathbf {v} }$ ${\displaystyle \operatorname {proj} _{\mathbf {u} }(\mathbf {v} )}$ ${\displaystyle \mathbf {v} }$ ${\displaystyle \mathbf {u} }$ ${\displaystyle \mathbf {u} }$ ${\displaystyle \operatorname {proj} _{\mathbf {u} }(\mathbf {v} )}$

Dados vectores, el proceso de Gram-Schmidt define los vectores de la siguiente manera: ${\displaystyle k}$ ${\displaystyle \mathbf {v} _{1},\ldots ,\mathbf {v} _{k}}$ ${\displaystyle \mathbf {u} _{1},\ldots ,\mathbf {u} _{k}}$ $${\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}}}$$

La sucesión es el sistema requerido de vectores ortogonales, y los vectores normalizados forman un conjunto ortonormal . El cálculo de la sucesión se conoce como ortogonalización de Gram-Schmidt , y el cálculo de la sucesión se conoce como ortonormalización de Gram-Schmidt . ${\displaystyle \mathbf {u} _{1},\ldots ,\mathbf {u} _{k}}$ ${\displaystyle \mathbf {e} _{1},\ldots ,\mathbf {e} _{k}}$ ${\displaystyle \mathbf {u} _{1},\ldots ,\mathbf {u} _{k}}$ ${\displaystyle \mathbf {e} _{1},\ldots ,\mathbf {e} _{k}}$

Para comprobar que estas fórmulas dan como resultado una secuencia ortogonal, primero calcule sustituyendo la fórmula anterior por : obtenemos cero. Luego use esto para calcular nuevamente sustituyendo la fórmula por : obtenemos cero. Para arbitrario la prueba se logra por inducción matemática . ${\displaystyle \langle \mathbf {u} _{1},\mathbf {u} _{2}\rangle }$ ${\displaystyle \mathbf {u} _{2}}$ ${\displaystyle \langle \mathbf {u} _{1},\mathbf {u} _{3}\rangle }$ ${\displaystyle \mathbf {u} _{3}}$ ${\displaystyle k}$

Geométricamente, este método procede de la siguiente manera: para calcular , se proyecta ortogonalmente sobre el subespacio generado por , que es el mismo que el subespacio generado por . El vector se define entonces como la diferencia entre y esta proyección, que se garantiza que es ortogonal a todos los vectores en el subespacio . ${\displaystyle \mathbf {u} _{i}}$ ${\displaystyle \mathbf {v} _{i}}$ ${\displaystyle U}$ ${\displaystyle \mathbf {u} _{1},\ldots ,\mathbf {u} _{i-1}}$ ${\displaystyle \mathbf {v} _{1},\ldots ,\mathbf {v} _{i-1}}$ ${\displaystyle \mathbf {u} _{i}}$ ${\displaystyle \mathbf {v} _{i}}$ ${\displaystyle U}$

El proceso de Gram-Schmidt también se aplica a una secuencia infinita numerable linealmente independiente { v _i } _i . El resultado es una secuencia ortogonal (u ortonormal) { u _i } _i tal que para el número natural n : el espacio algebraico de es el mismo que el de . ${\displaystyle \mathbf {v} _{1},\ldots ,\mathbf {v} _{n}}$ ${\displaystyle \mathbf {u} _{1},\ldots ,\mathbf {u} _{n}}$

Si se aplica el proceso Gram-Schmidt a una secuencia linealmente dependiente, se obtiene como salida el vector 0 en el paso n, suponiendo que es una combinación lineal de . Si se va a producir una base ortonormal, entonces el algoritmo debe probar si hay vectores cero en la salida y descartarlos porque ningún múltiplo de un vector cero puede tener una longitud de 1. La cantidad de vectores que genera el algoritmo será entonces la dimensión del espacio abarcado por las entradas originales. ${\displaystyle i}$ ${\displaystyle \mathbf {v} _{i}}$ ${\displaystyle \mathbf {v} _{1},\ldots ,\mathbf {v} _{i-1}}$

Una variante del proceso Gram-Schmidt que utiliza la recursión transfinita aplicada a una secuencia infinita (posiblemente incontable) de vectores produce un conjunto de vectores ortonormales con tales que para cualquier , la completitud del espacio de es la misma que la de . En particular, cuando se aplica a una base (algebraica) de un espacio de Hilbert (o, más generalmente, una base de cualquier subespacio denso), produce una base ortonormal (analítica-funcional). Nótese que en el caso general a menudo se cumple la desigualdad estricta, incluso si el conjunto inicial fuera linealmente independiente, y el espacio de no necesita ser un subespacio del espacio de (más bien, es un subespacio de su completitud). ${\displaystyle (v_{\alpha })_{\alpha <\lambda }}$ ${\displaystyle (u_{\alpha })_{\alpha <\kappa }}$ ${\displaystyle \kappa \leq \lambda }$ ${\displaystyle \alpha \leq \lambda }$ ${\displaystyle \{u_{\beta }:\beta <\min(\alpha ,\kappa )\}}$ ${\displaystyle \{v_{\beta }:\beta <\alpha \}}$ ${\displaystyle \kappa <\lambda }$ ${\displaystyle (u_{\alpha })_{\alpha <\kappa }}$ ${\displaystyle (v_{\alpha })_{\alpha <\lambda }}$

Ejemplo

Espacio euclidiano

Considere el siguiente conjunto de vectores en (con el producto interno convencional ) ${\displaystyle \mathbb {R} ^{2}}$ $${\displaystyle S=\left\{\mathbf {v} _{1}={\begin{bmatrix}3\\1\end{bmatrix}},\mathbf {v} _{2}={\begin{bmatrix}2\\2\end{bmatrix}}\right\}.}$$

Ahora, realice la ecuación de Gram-Schmidt para obtener un conjunto ortogonal 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 los vectores y son efectivamente ortogonales: observando que si el producto escalar de dos vectores es 0, entonces son ortogonales. ${\displaystyle \mathbf {u} _{1}}$ ${\displaystyle \mathbf {u} _{2}}$ $${\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,}$$

Para los vectores distintos de cero, podemos normalizar los vectores dividiendo sus tamaños como se muestra arriba: $${\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 por el resultado de aplicar el proceso de Gram–Schmidt a una colección de vectores . Esto produce un mapa . ${\displaystyle \operatorname {GS} (\mathbf {v} _{1},\dots ,\mathbf {v} _{k})}$ ${\displaystyle \mathbf {v} _{1},\dots ,\mathbf {v} _{k}}$ ${\displaystyle \operatorname {GS} \colon (\mathbb {R} ^{n})^{k}\to (\mathbb {R} ^{n})^{k}}$

Tiene las siguientes propiedades:

• Es continuo
• Preserva la orientación en el 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 ortogonales:

Sea ortogonal (con respecto al producto interno dado). Entonces tenemos ${\displaystyle g\colon \mathbb {R} ^{n}\to \mathbb {R} ^{n}}$ $${\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)}$$

Además, una versión parametrizada del proceso de Gram-Schmidt produce una retracción de deformación (fuerte) del grupo lineal general sobre el grupo ortogonal . ${\displaystyle \mathrm {GL} (\mathbb {R} ^{n})}$ ${\displaystyle O(\mathbb {R} ^{n})}$

Estabilidad numérica

Cuando este proceso se implementa en una computadora, los vectores a menudo no son del todo ortogonales debido a errores de redondeo . En el caso del proceso de Gram-Schmidt descrito anteriormente (a veces denominado "Gram-Schmidt clásico"), esta pérdida de ortogonalidad es particularmente grave; por lo tanto, se dice que el proceso de Gram-Schmidt (clásico) es numéricamente inestable . ${\displaystyle \mathbf {u} _{k}}$

El proceso Gram-Schmidt se puede estabilizar con una pequeña modificación; esta versión se conoce a veces como Gram-Schmidt modificado o MGS. Este enfoque da el mismo resultado que la fórmula original en aritmética exacta e introduce errores más pequeños en aritmética de precisión finita.

En lugar de calcular el vector u _k como se calcula 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}),}$$ $${\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}}}$$

Este método se utiliza en la animación anterior, cuando se utiliza el vector intermedio al ortogonalizar el vector azul . ${\displaystyle \mathbf {v} '_{3}}$ ${\displaystyle \mathbf {v} _{3}}$

Aquí hay otra descripción del algoritmo modificado. Dados los vectores , en nuestro primer paso producimos vectores eliminando componentes a lo largo de la dirección de . En fórmulas, . Después de este paso ya tenemos dos de nuestros vectores ortogonales deseados , a saber , pero también hicimos que ya fueran ortogonales a . A continuación, ortogonalizamos esos vectores restantes contra . Esto significa que calculamos por sustracción . Ahora hemos almacenado los vectores donde ya están los primeros tres vectores y los vectores restantes ya son ortogonales a . Como debería estar claro ahora, el siguiente paso ortogonaliza contra . Procediendo de esta manera, encontramos el conjunto completo de vectores ortogonales . Si se desean vectores ortonormales, entonces normalizamos a medida que avanzamos, de modo que los denominadores en las fórmulas de sustracción se conviertan en unos. ${\displaystyle \mathbf {v} _{1},\mathbf {v} _{2},\dots ,\mathbf {v} _{n}}$ ${\displaystyle \mathbf {v} _{1},\mathbf {v} _{2}^{(1)},\dots ,\mathbf {v} _{n}^{(1)}}$ ${\displaystyle \mathbf {v} _{1}}$ ${\displaystyle \mathbf {v} _{k}^{(1)}:=\mathbf {v} _{k}-{\frac {\langle \mathbf {v} _{k},\mathbf {v} _{1}\rangle }{\langle \mathbf {v} _{1},\mathbf {v} _{1}\rangle }}\mathbf {v} _{1}}$ ${\displaystyle \mathbf {u} _{1},\dots ,\mathbf {u} _{n}}$ ${\displaystyle \mathbf {u} _{1}=\mathbf {v} _{1},\mathbf {u} _{2}=\mathbf {v} _{2}^{(1)}}$ ${\displaystyle \mathbf {v} _{3}^{(1)},\dots ,\mathbf {v} _{n}^{(1)}}$ ${\displaystyle \mathbf {u} _{1}}$ ${\displaystyle \mathbf {u} _{2}=\mathbf {v} _{2}^{(1)}}$ ${\displaystyle \mathbf {v} _{3}^{(2)},\mathbf {v} _{4}^{(2)},\dots ,\mathbf {v} _{n}^{(2)}}$ ${\displaystyle \mathbf {v} _{k}^{(2)}:=\mathbf {v} _{k}^{(1)}-{\frac {\langle \mathbf {v} _{k}^{(1)},\mathbf {u} _{2}\rangle }{\langle \mathbf {u} _{2},\mathbf {u} _{2}\rangle }}\mathbf {u} _{2}}$ ${\displaystyle \mathbf {v} _{1},\mathbf {v} _{2}^{(1)},\mathbf {v} _{3}^{(2)},\mathbf {v} _{4}^{(2)},\dots ,\mathbf {v} _{n}^{(2)}}$ ${\displaystyle \mathbf {u} _{1},\mathbf {u} _{2},\mathbf {u} _{3}}$ ${\displaystyle \mathbf {u} _{1},\mathbf {u} _{2}}$ ${\displaystyle \mathbf {v} _{4}^{(2)},\dots ,\mathbf {v} _{n}^{(2)}}$ ${\displaystyle \mathbf {u} _{3}=\mathbf {v} _{3}^{(2)}}$ ${\displaystyle \mathbf {u} _{1},\dots ,\mathbf {u} _{n}}$

Algoritmo

El siguiente algoritmo de MATLAB implementa la ortonormalización clásica de Gram-Schmidt. Los vectores v ₁ , ..., v _k (columnas de la matriz V, por lo que V(:,j)es el vector n) se reemplazan por vectores ortonormales (columnas de ) que abarcan el mismo subespacio. ${\displaystyle j}$U

función  U = gramoschmidt ( V )   [ n , k ] = tamaño ( V );    U = ceros ( n , k );   U (:, 1 ) = V (:, 1 ) / norma ( V (:, 1 ));     para i = 2 : k    U (:, i ) = V (:, i );   para j = 1 : i - 1    U (:, i ) = U (:, i ) - ( U (:, j ) '* U (:, i )) * U (:, j );       fin U (:, i ) = U (:, i ) / norma ( U (:, i ));     finfin

El costo de este algoritmo es asintóticamente O( nk ² ) operaciones de punto flotante, donde n es la dimensionalidad de los vectores. ^[2]

Mediante eliminación gaussiana

Si las filas { v ₁ , ..., v _k } se escriben como una matriz , entonces al aplicar la eliminación gaussiana a la matriz aumentada se producirán los vectores ortogonalizados en lugar de . Sin embargo, la matriz debe llevarse a la forma escalonada por filas , utilizando solo la operación de fila de sumar un múltiplo escalar de una fila a otra. ^[3] Por ejemplo, tomando como se indica arriba, tenemos ${\displaystyle A}$ ${\displaystyle \left[AA^{\mathsf {T}}|A\right]}$ ${\displaystyle A}$ ${\displaystyle AA^{\mathsf {T}}}$ ${\displaystyle \mathbf {v} _{1}={\begin{bmatrix}3&1\end{bmatrix}},\mathbf {v} _{2}={\begin{bmatrix}2&2\end{bmatrix}}}$ $${\displaystyle \left[AA^{\mathsf {T}}|A\right]=\left[{\begin{array}{rr|rr}10&8&3&1\\8&8&2&2\end{array}}\right]}$$

Y al reducir esto a la forma escalonada se obtiene $${\displaystyle \left[{\begin{array}{rr|rr}1&.8&.3&.1\\0&1&-.25&.75\end{array}}\right]}$$

Los vectores normalizados son entonces como en el ejemplo anterior. $${\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}},}$$

Fórmula determinante

El resultado del proceso Gram-Schmidt puede expresarse en una fórmula no recursiva utilizando determinantes .

$${\displaystyle \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 &\cdots &\langle \mathbf {v} _{j},\mathbf {v} _{1}\rangle \\\langle \mathbf {v} _{1},\mathbf {v} _{2}\rangle &\langle \mathbf {v} _{2},\mathbf {v} _{2}\rangle &\cdots &\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 &\cdots &\langle \mathbf {v} _{j},\mathbf {v} _{j-1}\rangle \\\mathbf {v} _{1}&\mathbf {v} _{2}&\cdots &\mathbf {v} _{j}\end{vmatrix}}}$$

$${\displaystyle \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 &\cdots &\langle \mathbf {v} _{j},\mathbf {v} _{1}\rangle \\\langle \mathbf {v} _{1},\mathbf {v} _{2}\rangle &\langle \mathbf {v} _{2},\mathbf {v} _{2}\rangle &\cdots &\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 &\cdots &\langle \mathbf {v} _{j},\mathbf {v} _{j-1}\rangle \\\mathbf {v} _{1}&\mathbf {v} _{2}&\cdots &\mathbf {v} _{j}\end{vmatrix}}}$$

donde y, para , es el determinante de Gram ${\displaystyle D_{0}=1}$ ${\displaystyle j\geq 1}$ ${\displaystyle D_{j}}$

$${\displaystyle D_{j}={\begin{vmatrix}\langle \mathbf {v} _{1},\mathbf {v} _{1}\rangle &\langle \mathbf {v} _{2},\mathbf {v} _{1}\rangle &\cdots &\langle \mathbf {v} _{j},\mathbf {v} _{1}\rangle \\\langle \mathbf {v} _{1},\mathbf {v} _{2}\rangle &\langle \mathbf {v} _{2},\mathbf {v} _{2}\rangle &\cdots &\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 &\cdots &\langle \mathbf {v} _{j},\mathbf {v} _{j}\rangle \end{vmatrix}}.}$$

Nótese que la expresión para es un determinante "formal", es decir, la matriz contiene tanto escalares como vectores; el significado de esta expresión se define como el resultado de una expansión de cofactor a lo largo de la fila de vectores. ${\displaystyle \mathbf {u} _{k}}$

La fórmula determinante de Gram-Schmidt es computacionalmente (exponencialmente) más lenta que los algoritmos recursivos descritos anteriormente; es principalmente de interés teórico.

Expresado mediante álgebra geométrica

Expresados ​​mediante la notación utilizada en álgebra geométrica , los resultados no normalizados del proceso de Gram-Schmidt se pueden expresar como que es equivalente a la expresión que utiliza el operador definido anteriormente. Los resultados se pueden expresar de manera equivalente como ^[4] que está estrechamente relacionada con la expresión que utiliza determinantes anterior. $${\displaystyle \mathbf {u} _{k}=\mathbf {v} _{k}-\sum _{j=1}^{k-1}(\mathbf {v} _{k}\cdot \mathbf {u} _{j})\mathbf {u} _{j}^{-1}\ ,}$$ ${\displaystyle \operatorname {proj} }$ $${\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},}$$

Alternativas

Otros algoritmos de ortogonalización utilizan transformaciones de Householder o rotaciones de Givens . Los algoritmos que utilizan transformaciones de Householder son más estables que el proceso de Gram-Schmidt estabilizado. Por otro lado, el proceso de Gram-Schmidt produce el th vector ortogonalizado después de la th iteración, mientras que la ortogonalización que utiliza reflexiones de Householder produce todos los vectores solo al final. Esto hace que solo el proceso de Gram-Schmidt sea aplicable para métodos iterativos como la iteración de Arnoldi . ${\displaystyle j}$ ${\displaystyle j}$

Otra alternativa más está motivada por el uso de la descomposición de Cholesky para invertir la matriz de las ecuaciones normales en mínimos cuadrados lineales . Sea una matriz de rango de columna completa , cuyas columnas necesitan ser ortogonalizadas. La matriz es hermítica y definida positiva , por lo que puede escribirse como usando la descomposición de Cholesky . La matriz triangular inferior con entradas diagonales estrictamente positivas es invertible . Entonces, las columnas de la matriz son ortonormales y abarcan el mismo subespacio que las columnas de la matriz original . El uso explícito del producto hace que el algoritmo sea inestable, especialmente si el número de condición del producto es grande. Sin embargo, este algoritmo se utiliza en la práctica y se implementa en algunos paquetes de software debido a su alta eficiencia y simplicidad. ${\displaystyle V}$ ${\displaystyle V^{*}V}$ ${\displaystyle V^{*}V=LL^{*},}$ ${\displaystyle L}$ ${\displaystyle U=V\left(L^{-1}\right)^{*}}$ ${\displaystyle V}$ ${\displaystyle V^{*}V}$

En mecánica cuántica existen varios esquemas de ortogonalización con características más adecuadas para ciertas aplicaciones que el algoritmo Gram-Schmidt original. No obstante, sigue siendo un algoritmo popular y eficaz incluso para los cálculos de estructura electrónica más grandes. ^[5]

Complejidad en tiempo de ejecución

La ortogonalización de Gram-Schmidt se puede realizar en tiempo fuertemente polinomial . El análisis en tiempo de ejecución es similar al de la eliminación gaussiana . ^{[6] : 40}

Véase también

• Álgebra lineal
• Recursión
• Ortogonalidad (matemáticas)

Referencias

1. Cheney, Ward; Kincaid, David (2009). Álgebra lineal: teoría y aplicaciones. Sudbury, Massachusetts: Jones y Bartlett. pp. 544, 558. ISBN 978-0-7637-5020-6.
2. Préstamo Golub & Van 1996, §5.2.8.
3. Pursell, Lyle; Trimble, SY (1 de enero de 1991). "Ortogonalización de Gram-Schmidt por eliminación de Gauss". The American Mathematical Monthly . 98 (6): 544–549. doi :10.2307/2324877. JSTOR  2324877.
4. Doran, Chris; Lasenby, Anthony (2007). Álgebra geométrica para físicos . Cambridge University Press. pág. 124. ISBN 978-0-521-71595-9.
5. Pursell, Yukihiro; et al. (2011). "Cálculos de primeros principios de estados electrónicos de un nanocable de silicio con 100.000 átomos en la computadora K". Actas de la Conferencia internacional de 2011 sobre computación de alto rendimiento, redes, almacenamiento y análisis . pp. 1:1–1:11. doi :10.1145/2063384.2063386. ISBN . 9781450307710. Número de identificación del sujeto  14316074.
6. Grötschel, Martín ; Lovász, László ; Schrijver, Alexander (1993), Algoritmos geométricos y optimización combinatoria, Algoritmos y combinatoria, vol. 2 (2ª ed.), Springer-Verlag, Berlín, doi :10.1007/978-3-642-78240-4, ISBN 978-3-642-78242-8, Sr.  1261419

Notas

1. En el caso complejo, esto supone que el producto interno es lineal en el primer argumento y lineal conjugado en el segundo. En física, una convención más común es la linealidad en el segundo argumento, en cuyo caso definimos $${\displaystyle \operatorname {proj} _{\mathbf {u} }(\mathbf {v} )={\frac {\langle \mathbf {u} ,\mathbf {v} \rangle }{\langle \mathbf {u} ,\mathbf {u} \rangle }}\,\mathbf {u} .}$$

Fuentes

• Bau III, David; Trefethen, Lloyd N. (1997), Álgebra lineal numérica , Filadelfia: Sociedad de Matemáticas Industriales y Aplicadas, ISBN 978-0-89871-361-9.
• Golub, Gene H. ; Van Loan, Charles F. (1996), Cálculos matriciales (3.ª ed.), Johns Hopkins, ISBN 978-0-8018-5414-9.
• Greub, Werner (1975), Álgebra lineal (4.ª ed.), Springer.
• Soliverez, CE; Gagliano, E. (1985), "Ortonormalización en el plano: un enfoque geométrico" (PDF) , Mex. J. Phys. , 31 (4): 743–758, archivado desde el original (PDF) el 2014-03-07 , consultado el 2013-06-22.

Enlaces externos

• Portal de matemáticas

• "Ortogonalización", Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
• Tutorial de matemáticas de Harvey Mudd College sobre el algoritmo Gram-Schmidt
• Los primeros usos conocidos de algunas palabras de las matemáticas: G La entrada "Ortogonalización de Gram-Schmidt" tiene información y referencias sobre los orígenes del método.
• Demostraciones: proceso de Gram Schmidt en el plano y proceso de Gram Schmidt en el espacio
• Subprograma de ortogonalización de Gram-Schmidt
• Rutina de ortogonalización de Gram-Schmidt de n vectores de orden m de NAG
• Prueba: Raymond Puzio, Keenan Kidwell. "Prueba del algoritmo de ortogonalización de Gram-Schmidt" (versión 8). PlanetMath.org.