Video

Quiz

Hier geht's zum Video „Gram Schmidt Verfahren“

QR Zerlegung

Wichtige Inhalte in diesem Video

QR Zerlegung einfach erklärt

Allgemeine QR Zerlegung

Berechnung einer QR Zerlegung

Beispiele zur QR Zerlegung

Im Folgenden erklären wir, was unter einer QR Zerlegung zu verstehen ist und wie man sie berechnet. Dafür stellen wir zwei Verfahren mit Beispielen zur Berechnung vor: die Householdertransformation und das Gram-Schmidt Verfahren.

Wenn du also möglichst schnell lernen möchtest, wie du selbst eine QR Zerlegung bestimmen kannst, dann schau dir unser Video dazu an.

Inhaltsübersicht

QR Zerlegung einfach erklärt

im Videozur Stelle im Video springen

Bei einer QR Zerlegung möchte man eine Matrix $A\in \mathbb{R}^{m\times n}$ als Produkt zweier Matrizen darstellen, d.h. es soll gelten A=QR . Dabei soll $Q\in \mathbb{R}^{m\times m}$ eine orthogonale Matrix und $R\in \mathbb{R}^{m\times n}$ eine obere Dreiecksmatrix sein.

Die Zeilen und Spalten einer orthogonalen Matrix $Q \in \mathbb{R}^{m\times m}$ stellen eine Orthonormalbasis des $\mathbb{R}^m$ dar, d.h. es gilt für die Transponierte Q^T , dass QQ^T = Q^TQ=E der Einheitsmatrix entspricht.

Bei einer oberen Dreiecksmatrix , sind alle Einträge unterhalb der Diagonalen Null, d.h. für i>j gilt $r_{ij}=0$ .

Allgemeine QR Zerlegung

im Videozur Stelle im Video springen

Betrachtet man also eine Matrix $A\in \mathbb{R}^{m\times n}$ mit $m \geq n$ , dann besitzt sie eine (fast) eindeutige reduzierte QR Zerlegung. D.h. es existiert eine Matrix $\tilde{Q} \in \mathbb{R}^{m\times n}$ , deren Spalten orthogonal sind und eine obere Dreiecksmatrix $\tilde{R} \in \mathbb{R}^{n\times n}$ , sodass $A=\tilde{Q}\tilde{R}$ . Um nun eine vollständige QR Zerlegung zu erhalten, muss die $m\times n$ -Matrix $\tilde{Q}$ durch weitere orthogonale Spalten $\hat{Q} \in \mathbb{R}^{m\times (m-n)}$ zu einer quadratischen $m \times m$ -Matrix erweitert werden. Damit die Multiplikation weiterhin sinnvoll besteht und ergibt, erweitern wir $\tilde{R}$ um die entsprechenden Nullzeilen zu $R \in \mathbb{R}^{m\times n}$ , sodass schließlich

$A = \tilde{Q}\tilde{R} = \left(\begin{array}{c|c} \tilde{Q}&\hat{Q} \end{array}\right) \left(\begin{array}{c} \tilde{R}\\\hline 0 \end{array}\right) = QR$

eine vollständige QR Zerlegung darstellt.

Die QR Zerlegung ist eindeutig für eine Matrix $A\in \mathbb{R}^{m\times n}$ mit $m \geq n$ und Rang(A)=n , wenn vorausgesetzt wird, dass die Diagonalelemente von alle positiv oder negativ sein sollen.

Wir betrachten nun eine solche $m\times n$ -Matrix mit $m \geq n$ und Rang(A)=n und zeigen ein Verfahren zur Berechnung ihrer Zerlegung.

Berechnung einer QR Zerlegung

im Videozur Stelle im Video springen

Zu den bekanntesten Verfahren zur Berechnung einer QR Zerlegung zählen das Householder-, Givens- und Gram-Schmidt-Verfahren. Wir erklären in diesem Artikel die Zerlegung per Houselholdertransformation und mittels dem Gram-Schmidt-Verfahren.

QR Zerlegung per Householdertransformation

Die Householdertransformation spiegelt einen Vektor an einer Ebene, die durch den Nullpunkt verläuft. Für die QR Zerlegung nutzen wir das, indem wir Spaltenvektoren auf ein Vielfaches des ersten Einheitsvektors spiegeln, um so Schritt für Schritt eine obere Dreiecksmatrix zu erhalten. Die lineare Abbildung, welche die Householdertransformation beschreibt, wird durch eine orthogonale Householder-Matrix $H= E - \frac{2vv^T}{v^Tv}$ dargestellt. Dabei entspricht dem Vektor, der senkrecht zur Spiegelebene liegt. Im 2-dimensionalen kann man diese Spiegelung folgendermaßen Veranschaulichen.

QR Zerlegung - Householder-Verfahren — QR Zerlegung – Householder-Verfahren

Uns ist nun eine Matrix $A \in \mathbb{R}^{m\times n}$ gegeben und wir wollen diese durch Householdertransformationen in eine obere Dreiecksmatrix verwandeln. Dafür bestimmen wir Householder-Matrizen $H^{(i)} \in \mathbb{R}^{m\times m}$ und multiplizieren diese von links an , sodass wir nach höchstens k=min(m-1,n) Schritten das Resultat $R=H^{(k)}...H^{(2)}H^{(1)}A$ erhalten. Da die Householder-Matrizen orthogonal sind und das Produkt von orthogonalen Matrizen erneut orthogonal ist, liefert uns eine Linksmultiplikation mit $Q:=\left(H^{(k)}...H^{(2)}H^{(1)}\right)^T$ die gewünschte QR-Zerlegung: QR=QQ^TA =EA=A . Nun bleibt nur noch zu klären wie genau wir diese Householder-Matrizen berechnen.

Householder-Matrizen berechnen

Schritt 1: Wir betrachten dafür die erste Spalte $a_1 \in \mathbb{R}^m$ unserer Matrix $A\in \mathbb{R}^{m\times n}$ und wählen $v^{(1)}= a_1+sign(a_{11}) ||a_1||e_1$ . Dabei entspricht $sign(a_{11})$ dem Vorzeichen des ersten Eintrags des Spaltenvektors a_1 und $||a_1||= \sqrt{{a_1}^Ta_1}$ der euklidischen Norm von a_1 . Zudem gilt sign(0):=1 . Mit dem Vektor $v^{(1)}\in \mathbb{R}^m$ bestimmen wir die Householder-Matrix $H^{(1)}\in\mathbb{R}^{m\times m}$ , welche durch Multiplikation mit eine Matrix, wir nennen sie hier $A^{(1)}= H^{(1)}A\in \mathbb{R}^{m\times n}$ , liefert, deren erste Spalte ein Vielfaches des Einheitsvektors ist.

Schritt 2.1: Im nächsten Schritt nehmen wir diese Matrix $A^{(1)}$ und streichen ihre erste Zeile und Spalte, sodass wir eine kleinere Teilmatrix $A'^{(1)}\in \mathbb{R}^{(m-1)\times (n-1)}$ erhalten.

Schritt 2.2: Wir gehen nun mit $A'^{(1)}$ genauso vor, wie mit in Schritt 1. Explizit bedeutet das, wir spiegeln ihre erste Spalte a'_1 auf ein Vielfaches des ersten Einheitsvektors $e_1 \in \mathbb{R}^{m-1}$ . Dafür berechnen wir $v^{(2)}= a'_1 +sign(a'_{11}) ||a'_1|| e_1$ , um damit die $(m-1)\times (m-1)$ -Matrix $H'^{(1)} = E - \frac{2v^{(2)}{v^{(2)}}^T}{{v^{(2)}}^Tv^{(2)}}$ zu berechnen. Im Anschluss definieren wir dann unsere $m \times m$ –Householder-Matrix $H^{(2)}$ durch

$H^{(2)} = \left(\begin{array}{c|ccc}1&0&\cdots&0 \\\hline 0& & & \\ \vdots&{} &H'^{(1)}&{} \\0 &{}&{}&{}\end{array}\right)$ .

Nun multiplizieren wir $H^{(2)}$ von links an die zuvor berechnete Matrix $A^{(1)}$ . Die daraus resultierende Matrix $A^{(2)}:= H^{(2)}A^{(1)}$ hat nun in den ersten beiden Spalten unterhalb dem Eintrag $a_{ii}$ nur Nullen .

Schritt 3.1: Um das selbe auch für die restlichen Spalten zu erreichen, streichen wir im nächsten Schritt sowohl die erste und zweite Zeile, als auch Spalte von $A^{(2)}$ und führen Schritt 3.2 analog zu Schritt 2.2 für die Teilmatrix $A'^{(2)} \in \mathbb{R}^{(m-2) \times (n-2)}$ durch und erweitern dann die $(m-2)\times (m-2)$ -Matrix $H'^{(2)}$ zu

$H^{(3)} = \left(\begin{array}{cc|cc}1&0&\cdots&0 \\ 0&1&\cdots&0\\ \hline\vdots&\vdots&H'^{(2)}&\\0 &0& & \end{array}\right)$ .

Nun berechnen wir $A^{(3)}= H^{(3)}A^{(2)}$ .

Diese Schritte führen wir solange fort, bis wir eine obere Dreiecksmatrix erhalten, was spätestens nach Schritt k= min(m-1,n) der Fall ist.

QR Zerlegung mit dem Gram-Schmidt Verfahren

Ein weiteres Verfahren für die QR Zerlegung stellt das Verfahren von Gram-Schmidt dar. Dieses Verfahren erzeugt aus einer gegebenen Basis eine Orthonormalbasis. Inwiefern kann dies bei einer Zerlegung hilfreich sein? Sei $A\in \mathbb{R}^{n\times n}$ eine Matrix mit Rang(A)=n . Demnach sind die Spalten $\{a_1,...,a_n\}$ allesamt linear unabhängig und stellen deshalb eine Basis des $\mathbb{R}^n$ dar. Mit dem Gram-Schmidt Verfahren erzeugen wir daraus eine Orthonormalbasis $\{q_1,...,q_n\}$ und erstellen damit eine orthogonale $n\times n$ -Matrix Q=(q_1,...,q_n) . Berechnen wir nun das Produkt Q^TA=:R so erhalten wir eine obere Dreiecksmatrix. Denn aufgrund der Konstruktion der orthogonalen Vektoren gilt für alle j<i , dass $r_{ij}= \langle q_i,a_j\rangle=0$ .

Beispiele zur QR Zerlegung

im Videozur Stelle im Video springen

Nun rechnen wir zu den zwei Verfahren jeweils ein Beispiel zur Berechnung der QR-Zerlegung durch.

QR Zerlegung per Householdertransformation

Wir wollen folgende Matrix als Produkt einer orthogonalen und einer oberen Dreiecksmatrix darstellen:

$A= \left(\begin{array}{ccc}2&4&-4 \\ 1&1&2\\2&-3&0\end{array}\right)$ .

Wir betrachten den ersten Spaltenvektor $a_1= \left(\begin{array}{c}2 \\ 1\\2\end{array}\right)$ und berechnen seine Norm $||a_1|| = \sqrt{4+1+4} = 3$ . Damit bestimmen wir den orthogonalen Vektor zu unserer Spiegelebene

$v^{(1)} = \left(\begin{array}{c}2 \\ 1\\2\end{array}\right) + sign(2)\cdot 3 \cdot\left(\begin{array}{c}1 \\ 0\\0\end{array}\right) = \left(\begin{array}{c}5 \\ 1\\2\end{array}\right)$ .

Um nun die erste Householder-Matrix $H^{(1)}$ bestimmen zu können, berechnen wir zunächst ${ v^{(1)}}^T v^{(1)} = 25+1+4 = 30$ und

$v^{(1)} {v^{(1)}}^T= \left(\begin{array}{c}5 \\ 1\\2\end{array}\right) \left(\begin{array}{ccc}5&1&2\end{array}\right) = \left(\begin{array}{ccc}25&5&10 \\ 5&1&2\\10&2&4\end{array}\right)$ .

Damit erhalten wir die Householder-Matrix $H^{(1)}$ :

$H^{(1)} = \left(\begin{array}{ccc}1&0&0 \\ 0&1&0\\0&0&1\end{array}\right)- \frac{2}{30}\left(\begin{array}{ccc}25&5&10 \\ 5&1&2\\10&2&4\end{array}\right) = \left(\begin{array}{ccc}-2/3&-1/3&-2/3 \\ -1/3&14/15&-2/15\\-2/3&-2/15&11/15\end{array}\right)$ .

Diese Matrix $H^{(1)}$ multiplizieren wir anschließend von links auf :

$A^{(1)}= \left(\begin{array}{ccc}-2/3&-1/3&-2/3 \\ -1/3&14/15&-2/15\\-2/3&-2/15&11/15\end{array}\right) \left(\begin{array}{ccc}2&4&-4 \\ 1&1&2\\2&-3&0\end{array}\right)$

$= \left(\begin{array}{ccc}-3&-1&2 \\ 0&0&16/5\\0&-5&12/5\end{array}\right)$ .

Wir streichen die erste Zeile und Spalte von $A^{(1)}$ und erhalten die Teilmatrix

$A'^{(1)} = \left(\begin{array}{cc}0&16/5\\ -5&12/5\end{array}\right)$ .

Nun betrachten wir ihre erste Spalte $a'_1 = \left(\begin{array}{c}0\\-5\end{array}\right)$ und berechnen erneut die Norm ||a'_1|| = 5 . Damit bestimmen wir

$v^{(2)} = \left(\begin{array}{c}0 \\ -5\end{array}\right) + sign(0) \cdot 5 \cdot\left(\begin{array}{c}1 \\ 0\end{array}\right) = \left(\begin{array}{c}5 \\ -5\end{array}\right)$ .

Daraus ergibt sich die „kleine“ Householder-Matrix

$H' = \left(\begin{array}{cc}1&0\\ 0&1\end{array}\right) - \frac{2}{50} \left(\begin{array}{cc}25&-25\\ -25&25\end{array}\right) = \left(\begin{array}{cc}0&1\\ 1&0\end{array}\right)$

und schließlich bilden wir so die „große“ Householder-Matrix

$H^{(2)} = \left(\begin{array}{ccc} 1&0&0 \\0&0&1\\0&1&0\end{array}\right)$ .

Nun berechnen wir

$R=H^{(2)}A^{(1)} = \left(\begin{array}{ccc} 1&0&0 \\0&0&1\\0&1&0\end{array}\right) \left(\begin{array}{ccc}-3&-1&2 \\ 0&0&16/5\\0&-5&12/5\end{array}\right) = \left(\begin{array}{ccc}-3&-1&2 \\ 0&-5&12/5\\0&0&16/5\end{array}\right)$

und erhalten so eine obere Dreiecksmatrix .

Zu guter letzt berechnen wir noch die Transponierte der orthogonalen Matrix:

$Q^T = \left(\begin{array}{ccc} 1&0&0 \\0&0&1\\0&1&0\end{array}\right) \left(\begin{array}{ccc}-2/3&-1/3&-2/3 \\ -1/3&14/15&-2/15\\-2/3&-2/15&11/15\end{array}\right)$

$= \left(\begin{array}{ccc}-2/3&-1/3&-2/3 \\-2/3&-2/15&11/15\\ -1/3&14/15&-2/15\end{array}\right)$ .

Somit ist A=QR .

QR Zerlegung mit dem Gram-Schmidt Verfahren

Wir wollen für folgende Matrix eine QR Zerlegung durchführen:

$A= \left(\begin{array}{cc} 1&2\\1&1\end{array}\right)$ .

Das bedeutet wir wenden auf die Vektoren $a_1 = \left(\begin{array}{c} 1\\1\end{array}\right)$ und $a_2 = \left(\begin{array}{c} 2\\1\end{array}\right)$ das Gram-Schmidt Verfahren an und erhalten damit $q_1 = \frac{1}{\sqrt{2}}\left(\begin{array}{c} 1\\1\end{array}\right)$ und $q_2 = \frac{1}{\sqrt{2}} \left(\begin{array}{c} 1\\-1\end{array}\right)$ . Damit bilden wir nun die orthogonale Matrix

$Q = \frac{1}{\sqrt{2}} \left(\begin{array}{cc} 1&1\\1&-1\end{array}\right)$

und berechnen unsere obere Dreiecksmatrix

$R= Q^TA= \frac{1}{\sqrt{2}} \left(\begin{array}{cc} 1&1\\1&-1\end{array}\right)\left(\begin{array}{cc} 1&2\\1&1\end{array}\right) = \frac{1}{\sqrt{2}} \left(\begin{array}{cc} 2&3\\0&1\end{array}\right)$ .

Schließlich gilt damit A=QR .

Anwendungen

Die QR Zerlegung wird sehr häufig in der numerischen Mathematik angewandt, beispielsweise im QR-Algorithmus zur Berechnung der Eigenwerte einer Matrix. Es ist aber auch hilfreich beim Lösen linearer Gleichungssysteme.

Lösung regulärer Gleichungssysteme

Gegeben ist ein lineares Gleichungssystem (LGS) in der Matrixform Ax=b mit $A\in \mathbb{R}^{m\times n}, m\geq n$ und $b\in \mathbb{R}^m$ . Es gelte Rang(A) = Rang(A|b) = n , weshalb das System genau eine Lösung besitzt. Gesucht ist diese Lösung $x\in \mathbb{R}^n$ . Um sie zu bestimmen gehen wir folgendermaßen vor:

Bestimmung einer QR Zerlegung von . (Denn damit lässt sich das LGS zu umformulieren.)
Berechnung von . (Linksmultiplikation von im LGS führt zu .)
durch Rückwärtseinsetzen lösen.

Lösung unbestimmter Gleichungssysteme

Gegeben sei ein LGS wie oben, mit dem Unterschied, dass m<n und Rang(A)=m gilt. Zur Lösung des LGS gehen wir folgendermaßen vor:

Bestimmung einer QR Zerlegung von . (Damit ergibt sich das LGS .)
durch Vorwärtseinsetzen lösen. ()
Berechnung von .

zur Videoseite: QR Zerlegung

Rang einer Matrix

Kern einer Matrix

Spur einer Matrix

Hallo, leider nutzt du einen AdBlocker.

Auf Studyflix bieten wir dir kostenlos hochwertige Bildung an. Dies können wir nur durch die Unterstützung unserer Werbepartner tun.

Schalte bitte deinen Adblocker für Studyflix aus oder füge uns zu deinen Ausnahmen hinzu. Das tut dir nicht weh und hilft uns weiter.

Danke!
Dein Studyflix-Team

Wenn du nicht weißt, wie du deinen Adblocker deaktivierst oder Studyflix zu den Ausnahmen hinzufügst, findest du hier eine kurze Anleitung. Bitte .