Gram-Schimdt-Clásico

############################################
# Se quiere solucionar Ax = b, donde:
#       A matriz m*n
#       x matriz de n*1
#       b matrz de m*1
#
# Se hallaran la matriz E y U tal que A = E*U, entonces:
#       Ux=E^t*b
#
# Sea B = E^t*b, se procedera a resolver con regresion.
#
#######EN VEZ DE TODOS LOS PRINT  PON RETORNAR LAS MATICES U,E,x Y MUESTRALAS EN PANTALLA


import math


#dimension de la matriz A (m*n)
m = int(raw_input())
n = int(raw_input())

a = []          # m*n     matriz sobre la que se trabaja
A = []          # m*n     matriz que mandas en la funcion
b = []          # m*1     matriz b
U = []          # n*n     matriz a hallar U
E = []          # m*n     matriz E
Et = []         # n*m     matriz traspuesta de E
x = []          # n*1     matriz de incognitas
B = []          # n*1     matriz E^t*b


# la siguiente matriz lee los valores 1 por 1, *****supongo que mandaras la matriz A Y b como parametro
# asi que solo tendras que copiar la matriz A (que venga como parametro), en la matriz E, y en
# la matriz 'a'. y podras comenzar con la inicializacion de las variables (linea 58)

#inicio de lectura de A
for i in range (m):
    A.append([])
    a.append([])
    E.append([])
    for j in range (n):
        A[i].append(float(raw_input()))
        a[i].append(float(A[i][j]))     #a = A
        E[i].append(0.0)


#fin de lectura A

E=a         #asigne la igualdad entre E y 'a'


# lee la matriz b
for i in range(m):
    b.append(float(raw_input()))

#fin de lectura de la matriz b


#inicializa la matriz U en 0, la transpuesta en 0, las incognitas x_i en 0 y la matriz B en 0
for i in range(n):
    U.append([])
    for j in range(n):
        U[i].append(0.0)

for i in range(n):
    Et.append([])
    x.append(0.0)
    for j in range(m):
        Et[i].append(0.0)


for i in range(n):
    B.append(0.0)
# fin de la inicializacion de matrices U, E_t, x


###############################################
#### ACA COMIENZA EL ALGORITMO
###############################################

for j in range(n):
    for i in range(j):
        prod_int = 0.0      #producto interno de ET[][].A[][]
        for k in range(m):
            prod_int += E[k][i]*a[k][j]
        U[i][j] = prod_int

        for k in range (m):
            E[k][j] = a[k][j] - U[i][j]*E[k][i]


    suma=0.0
    for k in range(m):
        suma += E[k][j]*E[k][j]
    U[j][j] = math.sqrt(suma)

    for k in range(m):
        E[k][j] = E[k][j]/U[j][j]

for i in range(m):
    for j in range(n):
        Et[j][i] = E[i][j]


########################################################
####    FIN DEL ALGORITMO
########################################################


##  hallar la matriz B = E^t*b
for i in range(n):
    for j in range(m):
        B[i] = B[i]+ Et[i][j]*b[j]

####


##### aplicamos la regresion el Ux = B, para hallar x
j = n-1
while j>=0:
    res = B[j]
    for k in range (j+1, n):
        res -= U[j][k] *x[k]
    res /= float(U[j][j])
    x[j] = res
    j-=1




######TODOS ESTOS PRINT REEMPLAZALOS POR LOS RETURN QUE NECESITES..
#imprimimos todas las matrices
print 'matriz A:'
for i in range(m):
    print a[i]
print'\n'

print 'matriz b:'
print b
print'\n'

print 'matriz U:'
for i in range(n):
    print U[i]
print'\n'

print 'matriz E:'
for i in range(m):
    print E[i]
print'\n'

print 'matriz Et:'
for i in range(n):
    print Et[i]
print'\n'

print 'matriz B:'
print B
print'\n'

print 'matriz x:'
print x
print'\n'