Proceso de Gram-Schmidt

Ortonormalización de un conjunto de vectores.

Los dos primeros pasos del proceso 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 hacer que dos o más vectores sean perpendiculares entre sí.

Por definición técnica, es un método para construir una base ortonormal a partir de un conjunto de vectores en un espacio de producto interno , más comúnmente el espacio euclidiano Rn ^equipado con el producto interno estándar . El proceso de Gram-Schmidt toma un conjunto finito y linealmente independiente de vectores S = { v ₁ , ..., v _k } para k ≤ n y genera un conjunto ortogonal S′ = { u ₁ , ..., u _k } que abarca el mismo subespacio k -dimensional de R ⁿ que S .

El método lleva el nombre de Jørgen Pedersen Gram y Erhard Schmidt , pero Pierre-Simon Laplace estaba familiarizado con él 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 columna de una matriz de rango de columna completa produce la descomposición QR (se descompone en una matriz ortogonal y triangular ).

El proceso Gram-Schmidt

El proceso de Gram-Schmidt modificado se ejecuta en tres vectores no ortogonales, linealmente independientes, de una base para R ³ . Haz clic en la imagen para los detalles. La modificación se explica en la sección Estabilidad numérica de este artículo.

La proyección vectorial de un vector sobre un vector distinto de cero se define como ${\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} ,}$$

producto internoproyección ortogonal ${\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 k vectores, el proceso de Gram-Schmidt define los vectores de la siguiente manera: ${\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 secuencia u ₁ ,..., u _k es el sistema requerido de vectores ortogonales, y los vectores normalizados e ₁ ,..., e _k forman un conjunto ortonormal . El cálculo de la secuencia u ₁ ,..., u _k se conoce como ortogonalización de Gram-Schmidt , y el cálculo de la secuencia e ₁ ,..., e _k se conoce como ortonormalización de Gram-Schmidt .

Para comprobar que estas fórmulas producen una secuencia ortogonal, primero calcule sustituyendo u ₂ por la fórmula anterior : obtenemos cero. Luego use esto para calcular nuevamente sustituyendo la fórmula por u ₃ : obtenemos cero. La prueba general procede por inducción matemática . ${\displaystyle \langle \mathbf {u} _{1},\mathbf {u} _{2}\rangle }$ ${\displaystyle \langle \mathbf {u} _{1},\mathbf {u} _{3}\rangle }$

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

El proceso de Gram-Schmidt también se aplica a una secuencia infinita contable linealmente independiente { v _i } _i . El resultado es una secuencia ortogonal (u ortonormal) { u _i } _i tal que para un número natural n : el intervalo algebraico de v ₁ , ..., v _n es el mismo que el de u ₁ , ..., u _n .

Si el proceso de Gram-Schmidt se aplica a una secuencia linealmente dependiente, genera el vector 0 en el i- _ésimo paso, suponiendo que vi es _una combinación lineal de v ₁ , ..., vi ₋₁ . 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. El número de vectores generados por el algoritmo será entonces la dimensión del espacio abarcado por las entradas originales.

Una variante del proceso de Gram-Schmidt que utiliza recursividad transfinita aplicada a una secuencia infinita (posiblemente incontable) de vectores produce un conjunto de vectores ortonormales tales que para cualquier , la finalización del lapso 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, a una base de cualquier subespacio denso), produce una base ortonormal (analítica-funcional). Tenga en cuenta que, en el caso general, a menudo se cumple la desigualdad estricta, incluso si el conjunto inicial fuera linealmente independiente y el lapso de no necesita ser un subespacio del lapso de (más bien, es un subespacio de su finalización). ${\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 R ² (con el producto interno convencional )

$${\displaystyle S=\left\{\mathbf {v} _{1}={\begin{bmatrix}3\\1\end{bmatrix}},\mathbf {v} _{2}={\begin{bmatrix}2\\2\end{bmatrix}}\right\}.}$$

Ahora, realice 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 u ₁ y u ₂ son efectivamente ortogonales:

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

producto escalar

Para 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

Denota 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
• Es una preservación de 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 nosotros 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 . Para el proceso de Gram-Schmidt descrito anteriormente (a veces denominado "Gram-Schmidt clásico"), esta pérdida de ortogonalidad es particularmente mala; por tanto, se dice que el proceso (clásico) de Gram-Schmidt es numéricamente inestable . ${\displaystyle \mathbf {u} _{k}}$

El proceso de Gram-Schmidt puede estabilizarse mediante una pequeña modificación; esta versión a veces se denomina 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

$${\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 usa en la animación anterior, cuando el vector intermedio v ' ₃ se usa al ortogonalizar el vector azul v ₃ .

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 , es decir , pero también los hicimos ortogonales a . A continuación, ortogonalizamos los vectores restantes contra . Esto significa que calculamos por resta . Ahora hemos almacenado los vectores donde los primeros tres vectores ya están y los vectores restantes ya son ortogonales a . Como debería quedar claro ahora, el siguiente paso ortogonaliza contra . Procediendo de esta manera encontramos el conjunto completo de vectores ortogonales . Si se desean vectores ortonormales, los normalizamos a medida que avanzamos, de modo que los denominadores en las fórmulas de resta se conviertan en unos. ${\displaystyle v_{1},v_{2},\dots ,v_{n}}$ ${\displaystyle v_{1},v_{2}^{(1)},\dots ,v_{n}^{(1)}}$ ${\displaystyle v_{1}}$ ${\displaystyle v_{k}^{(1)}:=v_{k}-{\frac {\langle v_{k},v_{1}\rangle }{\langle v_{1},v_{1}\rangle }}v_{1}}$ ${\displaystyle u_{1},\dots ,u_{n}}$ ${\displaystyle u_{1}=v_{1},u_{2}=v_{2}^{(1)}}$ ${\displaystyle v_{3}^{(1)},\dots ,v_{n}^{(1)}}$ ${\displaystyle u_{1}}$ ${\displaystyle u_{2}=v_{2}^{(1)}}$ ${\displaystyle v_{3}^{(2)},v_{4}^{(2)},\dots ,v_{n}^{(2)}}$ ${\displaystyle v_{k}^{(2)}:=v_{k}^{(1)}-{\frac {\langle v_{k}^{(1)},u_{2}\rangle }{\langle u_{2},u_{2}\rangle }}u_{2}}$ ${\displaystyle v_{1},v_{2}^{(1)},v_{3}^{(2)},v_{4}^{(2)},\dots ,v_{n}^{(2)}}$ ${\displaystyle u_{1},u_{2},u_{3}}$ ${\displaystyle u_{1},u_{2}}$ ${\displaystyle v_{4}^{(2)},\dots ,v_{n}^{(2)}}$ ${\displaystyle u_{3}=v_{3}^{(2)}}$ ${\displaystyle u_{1},\dots ,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 jésimo vector) se reemplazan por vectores ortonormales (columnas de U) que abarcan el mismo subespacio.

función  U = gramoschmidt ( V )   [ n , k ] = tamaño ( V );    U = ceros ( norte , k );   U (:, 1 ) = V (:, 1 ) / norma ( V (:, 1 ));     para i = 2 : k    U (:, yo ) = V (:, yo );   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 aplicar la eliminación gaussiana a la matriz aumentada producirá los vectores ortogonalizados en lugar de . Sin embargo, la matriz debe llevarse a la forma escalonada por filas , utilizando únicamente la operación de fila de sumar un múltiplo escalar de una fila a otra. ^[3] Por ejemplo, tomando lo anterior, 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 reducir esto a la forma escalonada produce

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

Los vectores normalizados son entonces

$${\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 de Gram-Schmidt se puede expresar 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 D ₀ =1 y, para j ≥ 1, D _j es el determinante de Gram

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

Tenga en cuenta que la expresión para u _k es un determinante "formal", es decir, la matriz contiene escalares y 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.

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

Expresado usando álgebra geométrica.

Expresados ​​utilizando la notación utilizada en álgebra geométrica , los resultados no normalizados del proceso de Gram-Schmidt se pueden 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}\ ,}$$

^[4] ${\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 estabilizado de Gram-Schmidt. 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 utilizando reflexiones de Householder produce todos los vectores solo al final. Esto hace que sólo 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 columnas completa , cuyas columnas deben ortogonalizarse. La matriz es hermitiana y definida positiva , por lo que puede escribirse utilizando 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 determinadas aplicaciones que el Gram-Schmidt original. Sin embargo, sigue siendo un algoritmo popular y eficaz incluso para los cálculos de estructuras electrónicas más grandes. ^[5]

Complejidad del 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}

Referencias

1. Cheney, sala; Kincaid, David (2009). Álgebra lineal: teoría y aplicaciones. Sudbury, mamá: Jones y Bartlett. págs.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". El Mensual Matemático Estadounidense . 98 (6): 544–549. doi :10.2307/2324877. JSTOR  2324877.
4. Doran, Chris; Lasenby, Anthony (2007). Álgebra geométrica para físicos . Prensa de la Universidad de Cambridge. pag. 124.ISBN​ 978-0-521-71595-9.
5. Pursell, Yukihiro; et al. (2011). "Cálculos de primeros principios de los estados electrónicos de un nanocables de silicio con 100.000 átomos en la computadora K". Actas de la conferencia internacional de 2011 sobre informática, redes, almacenamiento y análisis de alto rendimiento . págs. 1:1–1:11. doi :10.1145/2063384.2063386. ISBN 9781450307710. S2CID  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, señor  1261419

Fuentes

• BauIII, 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), Computaciones 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: una aproximación geométrica” (PDF) , Méx. J. Física. , 31 (4): 743–758.

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 de Gram-Schmidt
• Primeros usos conocidos de algunas de las 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
• NAG Ortogonalización de Gram-Schmidt de n vectores de orden m rutina
• Prueba: Raymond Puzio, Keenan Kidwell. "prueba del algoritmo de ortogonalización de Gram-Schmidt" (versión 8). PlanetMath.org.