En matemáticas , particularmente álgebra lineal y análisis numérico , el proceso de Gram-Schmidt es un método para ortonormalizar un conjunto de vectores en un espacio de producto interno , más comúnmente el espacio euclidiano R n equipado con el producto interno estándar . El proceso de Gram-Schmidt toma un conjunto finito , linealmente independiente de vectores S = { v 1 ,…, v k } para k ≤ ny genera un conjunto ortogonal S ' = { u 1 , ..., u k } que se extiende por el mismo k subespaciales -dimensional de R n como S .
El método lleva el nombre de Jørgen Pedersen Gram y Erhard Schmidt , pero Pierre-Simon Laplace lo conocía antes que Gram y Schmidt. [1] En la teoría de las descomposiciones de los 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 triangular ).
El proceso de Gram-Schmidt
Definimos el operador de proyección por
dónde denota el producto interno de los vectores u y v . Este operador proyecta el vector v ortogonalmente sobre la línea que abarca el vector u . Si u = 0 , definimos, es decir, el mapa de proyección es el mapa cero, enviando cada vector al vector cero.
El proceso de Gram-Schmidt funciona de la siguiente manera:
La secuencia u 1 ,…, u k es el sistema requerido de vectores ortogonales, y los vectores normalizados e 1 ,…, e k forman un conjunto orto normal . El cálculo de la secuencia u 1 , ..., u k se conoce como Gram-Schmidt ortogonalización , mientras que el cálculo de la secuencia e 1 , ..., e k se conoce como Gram-Schmidt ortonormalización como los vectores se normalizaron.
Para comprobar que estas fórmulas producen una secuencia ortogonal, primero calcule sustituyendo la fórmula anterior por u 2 : obtenemos cero. Luego usa esto para calcularde nuevo sustituyendo la fórmula por u 3 : obtenemos cero. La demostración general procede por inducción matemática .
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 1 ,…, u i −1 , que es lo mismo que el subespacio generado por v 1 ,…, v i −1 . El vector u i se define entonces como la diferencia entre v i y esta proyección, garantiza que sea ortogonal a todos los vectores en el subespacio 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 intervalo algebraico de v 1 ,…, v n es el mismo que el de u 1 ,…, u n .
Si el proceso de Gram-Schmidt se aplica a una secuencia linealmente dependiente, genera el vector 0 en el i- ésimo paso, asumiendo que v i es una combinación lineal de v 1 ,…, v i −1 . Si se va a producir una base ortonormal, entonces el algoritmo debe probar los 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 la recursividad transfinita aplicada a una (posiblemente incontable) secuencia infinita de vectores produce un conjunto de vectores ortonormales con tal que para cualquier , la finalización del lapso de es el mismo que el 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 (funcional-analítica). Tenga en cuenta que en el caso general a menudo la desigualdad estricta se mantiene, 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).
Ejemplo
Espacio euclidiano
Considere el siguiente conjunto de vectores en R 2 (con el producto interno convencional )
Ahora, realice Gram-Schmidt para obtener un conjunto ortogonal de vectores:
Comprobamos que los vectores u 1 y u 2 son realmente ortogonales:
teniendo en cuenta que si el producto escalar de dos vectores es 0, entonces son ortogonales.
Para los vectores distintos de cero, podemos normalizar los vectores dividiendo sus tamaños como se muestra arriba:
Propiedades
Denotamos por el resultado de aplicar el proceso de Gram-Schmidt a una colección de vectores . Esto produce un mapa.
Tiene las siguientes propiedades:
- Es continuo
- Es la preservación de la orientación en el sentido de que.
- Conmuta con mapas ortogonales:
Dejar ser ortogonal (con respecto al producto interior dado). Entonces nosotros tenemos
Además, una versión parametrizada del proceso de Gram-Schmidt produce una retracción por deformación (fuerte) del grupo lineal general en el grupo ortogonal .
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 lo tanto, se dice que el proceso (clásico) de Gram-Schmidt es numéricamente inestable .
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
se calcula como
Este método se utiliza en la animación anterior, cuando se utiliza el vector intermedio v ' 3 al ortogonalizar el vector azul v 3 .
Algoritmo
El siguiente algoritmo de MATLAB implementa la ortonormalización de Gram-Schmidt para vectores euclidianos. Los vectores v 1 ,…, 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 ( 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 ) ) / ( norma ( U (:, j ))) ^ 2 * U (:, j ); final U (:, i ) = U (:, i ) / norma ( U (:, i )); finalfinal
El costo de este algoritmo es asintóticamente O ( nk 2 ) operaciones de punto flotante, donde n es la dimensionalidad de los vectores ( Golub & Van Loan 1996 , §5.2.8).
Vía eliminación gaussiana
Si las filas { v 1 ,…, v k } se escriben como una matriz, luego aplicando eliminación gaussiana a la matriz aumentada producirá los vectores ortogonalizados en lugar de . Sin embargo, la matrizdebe llevarse a la forma escalonada de fila , utilizando solo la operación de fila de sumar un múltiplo escalar de una fila a otra. [2] Por ejemplo, tomando como arriba, tenemos
Y reducir esto a la forma escalonada de fila produce
Los vectores normalizados son entonces
como en el ejemplo anterior.
Fórmula determinante
El resultado del proceso de Gram-Schmidt puede expresarse en una fórmula no recursiva utilizando determinantes .
donde D 0 = 1 y, para j ≥ 1, D j es el determinante de Gram
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 para Gram-Schmidt es computacionalmente más lenta (exponencialmente más lenta) que los algoritmos recursivos descritos anteriormente; es principalmente de interés teórico.
Alternativas
Otros algoritmos de ortogonalización utilizan transformaciones Householder o rotaciones 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 elth vector ortogonalizado después de la la iteración, mientras que la ortogonalización usando 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 .
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 . Dejarser una matriz de rango de columna completa , cuyas columnas deben estar ortogonalizadas. La matrizes hermitiano y positivo definido , por lo que puede escribirse comoutilizando la descomposición de Cholesky . La matriz triangular inferiorcon entradas diagonales estrictamente positivas es invertible . Entonces columnas de la matrizson ortonormales y abarcan el mismo subespacio que las columnas de la matriz original. El uso explícito del productohace 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 e implementado en algunos paquetes de software debido a su alta eficiencia y simplicidad.
En mecánica cuántica existen varios esquemas de ortogonalización con características más adecuadas para ciertas 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. [3]
Referencias
- ^ Cheney, Ward; Kincaid, David (2009). Álgebra lineal: teoría y aplicaciones . Sudbury, Ma: Jones y Bartlett. págs. 544, 558. ISBN 978-0-7637-5020-6.
- ^ Perseguir, 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 .
- ^ Perseguir, Yukihiro; et al. (2011). "Cálculos de primeros principios de estados de electrones de un nanoalambre de silicio con 100.000 átomos en la computadora K". Actas de SC '11 de la Conferencia Internacional 2011 de Computación, Redes, Almacenamiento y Análisis de Alto Rendimiento : 1: 1–1: 11. doi : 10.1145 / 2063384.2063386 . ISBN 9781450307710. S2CID 14316074 .
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), Matrix Computations (3.a ed.), Johns Hopkins, ISBN 978-0-8018-5414-9.
- Greub, Werner (1975), Álgebra lineal (4a ed.), Springer.
- Soliverez, CE; Gagliano, E. (1985), "Ortonormalización en el plano: una aproximación geométrica" (PDF) , Méx. J. Phys. , 31 (4): 743–758.
enlaces externos
- "Ortogonalización" , Enciclopedia de Matemáticas , EMS Press , 2001 [1994]
- Tutorial de matemáticas de Harvey Mudd College sobre el algoritmo Gram-Schmidt
- Usos más antiguos conocidos de algunas de las palabras de las matemáticas: G La entrada "Ortogonalización de Gram-Schmidt" contiene información y referencias sobre los orígenes del método.
- Demos: proceso de Gram Schmidt en el plano y proceso de Gram Schmidt en el espacio
- Subprograma de ortogonalización de Gram-Schmidt
- Ortogonalización NAG Gram-Schmidt de n vectores de rutina de orden m
- Prueba: Raymond Puzio, Keenan Kidwell. "prueba del algoritmo de ortogonalización de Gram-Schmidt" (versión 8). PlanetMath.org.