Algoritmo de Gram-Schmidt
Vctor Domnguez Octubre 2011
1.
Introduccin
El mtodo de Gram-Schmit es un algoritmo para obtener, a partir de una base, otra que genere el mismo espacio y adems sea ortogonal. El algoritmo, escrito en forma de pseudocdigo, se muestra a continuacin
{a1 , . . . , an } base original de un subespacio U r11 := a1 e1 := a1 /r11 Para j = 2 hasta n Para i = 1 hasta j 1 rij := ei aj Fin Para vj := aj r1j e1 r2j e2 rj 1 j ej 1 rjj := vj ej := vj /rjj Fin Para {e1 , . . . en } es una base ortonormal de U . Observemos que en cada paso j = 1, . . . , n, span a1 , . . . , aj = span e1 , . . . , ej Ejemplo Tomemos a1 = (1, 1, 1, 1), a2 = (1, 1, 1, 1), a3 = (1, 1, 1, 1)
y consideremos U = span a1 , a2 , a3 . Los vectores {a1 , a2 , a3 } son linealmente independientes1 . Vamos a encontrar una base ortonormal de U y para ellos seguiremos los pasos del Algoritmo. Los pasos intermedios estn explicados en detalles, no as las cuentas, que te invito que repases.
1
Comprubalo
2 Primero hacemos r11 = a1 = 2, y tomamos e1 = Para j = 2, denimos r12 = e1 a2 = 1. A continuacin, tomamos
1 1 1 v2 = a2 r12 e1 = ( 3 , 2 , 2 , 2 ). 2
1 a1 = ( 1 , 1 , 1 , 1 ). 2 2 2 2 r11
Finalmente r22 = v2 = y hacemos e2 = Para j = 3, r13 = e1 a3 = 1, Por tanto,
12 = 3 4
1 1 v2 = (3, 1, 1, 1). r22 2 3 1 r23 = e2 a3 = . 3
4 2 2 v3 = a3 r13 e1 r23 e2 = (0, 3 , 3, 3 ).
As r33 = v3 = y, en consecuencia, e3 =
24 2 6 = 9 3
1 1 v3 = (0, 1, 1, 2). r33 6
2.
Descomposicin QR de una matriz
El proceso de ortogonalizacin de Gram-Schmidt tiene una interpretacin matricial muy interesante en trminos de una descomposicin/factorizacin matricial.. Por simplicidad, vemoslo primero con el ejemplo anterior. As, en primer lugar tenemos que a1 = r11 e1 v2 = r22 e2 v3 = r33 e3 y por otro lado que v2 = a2 r12 e1 v3 = a3 r13 e1 r23 e2 ,
3 Despejando a2 , a3 de las identidades anteriores y usando las primeras igualdades (para reemplazar v2 , v3 ) vemos que a1 = r11 e1 a2 = r12 e1 + r22 e2 a3 = r13 e1 + r23 e2 + r33 e3 Las identidades anteriores se pueden escribir en forma matricial de la forma siguiente r11 r12 r13 a1 a2 a3 = e1 e2 e3 r22 r23 . r33 Sustituyendo el valor de e1 , e2 , e3 , a1 , a2 y a1 as como los valores calculados para rij vemos que 1 3 0 2 3 1 1 1 1 2 1 2 1 1 1 23 6 1 1 1 2 1 = 3 3 1 1 1 1 1 1 2 3 6 2 2 6 1 1 1 1 2 1 3 2 2 3 6
A R Q
Comprueba, es un simple minuto, que esta factorizacin est bien, es decir, que si multiplicas la matrices Q, R de la izquierda recuperas la matriz A. Observa adems que Q Q = I3 y que R es triangular. Para concuir, recuerda (y comprueba) que rij = ei aj . Este proceso funciona para cualquier matriz A con rango n, es decir, con todas sus columnas formadas por vectores independientes. Tenemos pues el siguiente resultados Teorema 2.1 Sea A = a1 a2 an m n de rango n. Entonces r11 r12 r13 r1n r22 r23 r2n . . . .. .. . . rn1n1 rn1n rnn
R
a1 a2
A
an
e1 e2
Q
en
y adems Q Q = In .
4 Comentarios nales Las matrices A y Q son m n y en buena lgica, R es n n. El caso ms simple es el que A es n n, cuadrada, y por tanto tambin lo son Q y R. Ntese que en el campo que nos ocupa, A sera invertible, y como2 Q1 = Q , nos encontramos con que A1 = R1 Q . La inversa de R es fcil de calcular porque es triangular. Por otro lado, A A = R Q QR = R R. Nos encontraremos con expresiones as cuando veamos la aproximacin por mnimos cuadrados y las ecuaciones normales. La descomposicin anterior es esencialmente nica si jamos que los elementos de la diagonal sean todos positivos. Es decir, si la encontramos de otra forma, y R fuera una matriz triangular con los elementos de la diagonal positivos, entonces Q y R corresponderan a las matrices se obtienen al aplicar el mtodo de Gram-Schmidt. Aunque hemos enunciado el resultado para una matriz A de rango n, esta descomposicin es cierta (pero se pierde la unicidad) para cualquier matriz, tenga o no rango n, aunque su clculo ha de hacerse de una forma distinta dado que el mtodo de Gram-Schmidt no es aplicable3 . Merece la pena resaltar que la descomposicin QR, con la descomposicin LU que vimos en el Tema 2, es una de las herramientas fundamentales del lgebra y la computacin matricial. Si embargo el algoritmo de Gram-Schmidt, tal y cmo lo hemos presentado, es inestable numricamente. En pocas palabras, la inestabilidad numrica provoca que los errores de redondeo, que surgen en los clculos internos en el ordendaro, contaminen el proceso. En situaciones prcticas ello provoca que incluso para matrices de un tamao moderado la descomposicin devuelta por el ordenador no tenga nada que ver con el real4 . Es por ello que en los paquetes profesionales el clculo de la descomposicin QR se realiza mediante otros mtodos, basados en general en lo que se conoce como transformaciones de ortogonalidad, que s son estables numricalmente (los errores de redondeo no afectan, en general, ms all de las dos o tres ltimas cifras signicativas).
Por qu? De nuevo, por qu? 4 No nos hemos preocupado de la implementacin de los mtodos que hemos visto, es decir, de programarlos en un ordenador. De todas formas, el algoritmo tal y cmo lo hemos presentado es fcilmente implementable en un lenguaje de programacin al uso (Pascal, C, Fortran, Matlab, Python,...)
3
