QR Zerlegung

Gegeben: Matrix $A \in M(m \times n)$
Gesucht: Orthogonale Matrix $Q$ und obere Dreiecksmatrix $R$, sodass $A = Q \cdot R$



In [1]:

    
# input:
A = matrix([
    [1, 1, 1],
    [2, -4, 1],
    [-2, 1, -3]
])
#

Orthonormalisieren der Spaltenvektor von $A$ mittels Gram-Schmidt Verfahren:

$$ w_1 = \frac{1}{\| v_1 \|} v_1 $$$$ u_i = v_i - \sum_{k=1}^{i-1} \langle v_i, w_k \rangle w_k $$$$ w_i = \frac{1}{\| u_i \|} u_i $$



In [2]:

    
V = [vector(v for v in col) for col in A.T]
W = []
U = []
W.append((1/(V[0].norm())) * V[0])
show(LatexExpr("v_0 ="), V[0])
show(LatexExpr("w_0 ="), W[0])
print
for i, v in enumerate(V[1:]):
    show(LatexExpr("v_{} =".format(i+1)), v)
    s = sum([(v.dot_product(w) * w) for w in W])
    u = v - s
    show(LatexExpr("u_{} =".format(i+1)), u)
    U.append(u)
    w = (1/u.norm()) * u
    show(LatexExpr("w_{} =".format(i+1)), w)
    W.append(w)
    print









    




 $\newcommand{\Bold}[1]{\mathbf{#1}}v_0 = \left(1,\,2,\,-2\right)$ 






    




 $\newcommand{\Bold}[1]{\mathbf{#1}}w_0 = \left(\frac{1}{3},\,\frac{2}{3},\,-\frac{2}{3}\right)$ 






    









    




 $\newcommand{\Bold}[1]{\mathbf{#1}}v_1 = \left(1,\,-4,\,1\right)$ 






    




 $\newcommand{\Bold}[1]{\mathbf{#1}}u_1 = \left(2,\,-2,\,-1\right)$ 






    




 $\newcommand{\Bold}[1]{\mathbf{#1}}w_1 = \left(\frac{2}{3},\,-\frac{2}{3},\,-\frac{1}{3}\right)$ 






    









    




 $\newcommand{\Bold}[1]{\mathbf{#1}}v_2 = \left(1,\,1,\,-3\right)$ 






    




 $\newcommand{\Bold}[1]{\mathbf{#1}}u_2 = \left(-\frac{2}{3},\,-\frac{1}{3},\,-\frac{2}{3}\right)$ 






    




 $\newcommand{\Bold}[1]{\mathbf{#1}}w_2 = \left(-\frac{2}{3},\,-\frac{1}{3},\,-\frac{2}{3}\right)$



In [ ]:

Orthonormalisierte Spaltenvektoren bilden die Spaltenvektoren von $Q$



In [3]:

    
Q = matrix(W).T
show(Q)









    




 $\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrr} \frac{1}{3} & \frac{2}{3} & -\frac{2}{3} \\ \frac{2}{3} & -\frac{2}{3} & -\frac{1}{3} \\ -\frac{2}{3} & -\frac{1}{3} & -\frac{2}{3} \end{array}\right)$

Berechnen von $$R = Q^T A$$



In [4]:

    
R = Q.T * A
show(R)









    




 $\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrr} 3 & -3 & 3 \\ 0 & 3 & 1 \\ 0 & 0 & 1 \end{array}\right)$



In [5]:

    
show(Q*R)
show(Q*R == A)









    




 $\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrr} 1 & 1 & 1 \\ 2 & -4 & 1 \\ -2 & 1 & -3 \end{array}\right)$ 






    




 $\newcommand{\Bold}[1]{\mathbf{#1}}\mathrm{True}$