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í.
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
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.
Dados vectores, el proceso de Gram-Schmidt define los vectores de la siguiente manera:
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 .
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 .
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 .
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 .
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.
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).
Ejemplo
Espacio euclidiano
Considere el siguiente conjunto de vectores en (con el producto interno convencional )
Ahora, realice la ecuación de Gram-Schmidt para obtener un conjunto ortogonal de vectores:
Comprobamos que los vectores y son efectivamente ortogonales:
observando 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
Denotemos por el resultado de aplicar el proceso de Gram–Schmidt a una colección de vectores . Esto produce un mapa .
Sea ortogonal (con respecto al producto interno dado). Entonces tenemos
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 .
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 .
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
Este método se utiliza en la animación anterior, cuando se utiliza el vector intermedio al ortogonalizar el vector azul .
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.
Algoritmo
El siguiente algoritmo de MATLAB implementa la ortonormalización clásica de Gram-Schmidt. Los vectores v 1 , ..., 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.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 : kU (:, i ) = V (:, i );para j = 1 : i - 1U (:, i ) = U (:, i ) - ( U (:, j ) '* U (:, i )) * U (:, j );finU (:, i ) = U (:, i ) / norma ( U (:, i ));finfin
El costo de este algoritmo es asintóticamente O( nk 2 ) operaciones de punto flotante, donde n es la dimensionalidad de los vectores. [2]
Mediante eliminación gaussiana
Si las filas { v 1 , ..., 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
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.
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.
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]
^ 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.
^ Préstamo Golub & Van 1996, §5.2.8.
^ 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.
^ Doran, Chris; Lasenby, Anthony (2007). Álgebra geométrica para físicos . Cambridge University Press. pág. 124. ISBN978-0-521-71595-9.
^ 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.
^ 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
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.
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.
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.