#!/usr/bin/env python3
# -*- coding: utf-8 -*-

# Musterlösung für Aufgabe 35

import numpy as np

# Klassisches Gram-Schmidt-Verfahren

def GramSchmidt(A):
    m, n = A.shape
    R = np.zeros((n, n))
    Q = np.zeros((m, n))
    for k in range(n):
        Q[:, k] = A[:, k]
        if k != 0:
            for j in range(k):
                R[j, k] = Q[:, j].T @ Q[:, k]
            for i in range(k):
                Q[:, k] -= Q[:, i] * R[i, k]
        R[k, k] = np.linalg.norm(Q[:, k])
        # oder: R[k, k] = np.sqrt(Q[:, [k]].T@(Q[:, [k]]))
        Q[:, k] /= R[k, k]
    return Q, R
    
    
    
# Modifiziertes Gram-Schmidt-Verfahren

def GramSchmidt_mod(A):
    m, n = A.shape
    R = np.zeros((n, n))
    Q = np.zeros((m, n))
    for k in range(n):
        Q[:, k] = A[:, k]
        for i in range(k):
            R[i, k] = Q[:, i].T @ Q[:, k]
            Q[:, k] -= Q[:, i] * R[i, k]
        R[k, k] = np.linalg.norm(Q[:, k])
        Q[:, k] /= R[k, k]
    return Q, R