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
Bei einer QR Zerlegung möchte man eine Matrix als Produkt zweier Matrizen darstellen, d.h. es soll gelten . Dabei soll eine orthogonale Matrix und eine obere Dreiecksmatrix sein.
Die Zeilen und Spalten einer orthogonalen Matrix stellen eine Orthonormalbasis des dar, d.h. es gilt für die Transponierte , dass der Einheitsmatrix entspricht.
Bei einer oberen Dreiecksmatrix , sind alle Einträge unterhalb der Diagonalen Null, d.h. für gilt .
Allgemeine QR Zerlegung
Betrachtet man also eine Matrix mit , dann besitzt sie eine (fast) eindeutige reduzierte QR Zerlegung. D.h. es existiert eine Matrix , deren Spalten orthogonal sind und eine obere Dreiecksmatrix , sodass . Um nun eine vollständige QR Zerlegung zu erhalten, muss die -Matrix durch weitere orthogonale Spalten zu einer quadratischen -Matrix erweitert werden. Damit die Multiplikation weiterhin sinnvoll besteht und ergibt, erweitern wir um die entsprechenden Nullzeilen zu , sodass schließlich
eine vollständige QR Zerlegung darstellt.
Die QR Zerlegung ist eindeutig für eine Matrix mit und , wenn vorausgesetzt wird, dass die Diagonalelemente von alle positiv oder negativ sein sollen.
Wir betrachten nun eine solche -Matrix mit und und zeigen ein Verfahren zur Berechnung ihrer Zerlegung.
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 dargestellt. Dabei entspricht dem Vektor, der senkrecht zur Spiegelebene liegt. Im 2-dimensionalen kann man diese Spiegelung folgendermaßen Veranschaulichen.
Uns ist nun eine Matrix gegeben und wir wollen diese durch Householdertransformationen in eine obere Dreiecksmatrix verwandeln. Dafür bestimmen wir Householder-Matrizen und multiplizieren diese von links an , sodass wir nach höchstens Schritten das Resultat erhalten. Da die Householder-Matrizen orthogonal sind und das Produkt von orthogonalen Matrizen erneut orthogonal ist, liefert uns eine Linksmultiplikation mit die gewünschte QR-Zerlegung: . 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 unserer Matrix und wählen . Dabei entspricht dem Vorzeichen des ersten Eintrags des Spaltenvektors und der euklidischen Norm von . Zudem gilt . Mit dem Vektor bestimmen wir die Householder-Matrix , welche durch Multiplikation mit eine Matrix, wir nennen sie hier , liefert, deren erste Spalte ein Vielfaches des Einheitsvektors ist.
Schritt 2.1: Im nächsten Schritt nehmen wir diese Matrix und streichen ihre erste Zeile und Spalte, sodass wir eine kleinere Teilmatrix erhalten.
Schritt 2.2: Wir gehen nun mit genauso vor, wie mit in Schritt 1. Explizit bedeutet das, wir spiegeln ihre erste Spalte auf ein Vielfaches des ersten Einheitsvektors . Dafür berechnen wir , um damit die -Matrix zu berechnen. Im Anschluss definieren wir dann unsere –Householder-Matrix durch
.
Nun multiplizieren wir von links an die zuvor berechnete Matrix . Die daraus resultierende Matrix hat nun in den ersten beiden Spalten unterhalb dem Eintrag 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 und führen Schritt 3.2 analog zu Schritt 2.2 für die Teilmatrix durch und erweitern dann die -Matrix zu
.
Nun berechnen wir .
Diese Schritte führen wir solange fort, bis wir eine obere Dreiecksmatrix erhalten, was spätestens nach Schritt 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 eine Matrix mit . Demnach sind die Spalten allesamt linear unabhängig und stellen deshalb eine Basis des dar. Mit dem Gram-Schmidt Verfahren erzeugen wir daraus eine Orthonormalbasis und erstellen damit eine orthogonale -Matrix . Berechnen wir nun das Produkt so erhalten wir eine obere Dreiecksmatrix. Denn aufgrund der Konstruktion der orthogonalen Vektoren gilt für alle , dass .
QR Zerlegung per Householdertransformation
Wir wollen folgende Matrix als Produkt einer orthogonalen und einer oberen Dreiecksmatrix darstellen:
.
Wir betrachten den ersten Spaltenvektor und berechnen seine Norm . Damit bestimmen wir den orthogonalen Vektor zu unserer Spiegelebene
.
Um nun die erste Householder-Matrix bestimmen zu können, berechnen wir zunächst und
.
Damit erhalten wir die Householder-Matrix :
.
Diese Matrix multiplizieren wir anschließend von links auf :
.
Wir streichen die erste Zeile und Spalte von und erhalten die Teilmatrix
.
Nun betrachten wir ihre erste Spalte und berechnen erneut die Norm . Damit bestimmen wir
.
Daraus ergibt sich die „kleine“ Householder-Matrix
und schließlich bilden wir so die „große“ Householder-Matrix
.
Nun berechnen wir
und erhalten so eine obere Dreiecksmatrix .
Zu guter letzt berechnen wir noch die Transponierte der orthogonalen Matrix:
.
Somit ist .
QR Zerlegung mit dem Gram-Schmidt Verfahren
Wir wollen für folgende Matrix eine QR Zerlegung durchführen:
.
Das bedeutet wir wenden auf die Vektoren und das Gram-Schmidt Verfahren an und erhalten damit und . Damit bilden wir nun die orthogonale Matrix
und berechnen unsere obere Dreiecksmatrix
.
Schließlich gilt damit .
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 mit und . Es gelte , weshalb das System genau eine Lösung besitzt. Gesucht ist diese Lösung . 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 und 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 .