Givens-Rotation
In der linearen Algebra ist eine Givens-Rotation (nach Wallace Givens) eine Drehung in einer Ebene, die durch zwei Koordinaten-Achsen aufgespannt wird. Manchmal wird dies auch als Jacobi-Rotation (nach Carl Gustav Jacobi) bezeichnet.
Die Anwendung als Methode in der numerischen linearen Algebra zum Beispiel bei der Bestimmung von Eigenwerten und QR-Zerlegung stammt aus den 1950er Jahren, als Givens am Oak Ridge National Laboratory war. Solche Drehungen werden schon im älteren Jacobi-Verfahren (1846) benutzt, praktikabel wurden sie allerdings erst mit dem Aufkommen von Computern.
Beschreibung
Die Transformation lässt sich durch eine orthogonale Matrix der Form
beschreiben, wobei
und
in der
-ten
und
-ten
Zeile und Spalte erscheinen. Eine solche Matrix heißt Givens-Matrix. Formaler
ausgedrückt:
Das Matrix-Vektor-Produkt
stellt eine Drehung des Vektors
um einen Winkel
-Ebene
dar, diese wird Givens-Rotation genannt.
Die Hauptanwendung der Givens-Rotation liegt in der numerischen linearen Algebra, um Nulleinträge in Vektoren und Matrizen zu erzeugen. Dieser Effekt kann beispielsweise bei der Berechnung der QR-Zerlegung einer Matrix ausgenutzt werden. Außerdem werden solche Drehmatrizen beim Jacobi-Verfahren benutzt.
QR-Zerlegung mittels Givens-Rotationen
- Das Verfahren ist stabil. Pivotisierung ist nicht erforderlich.
- Flexible Berücksichtigung von schon vorhandenen 0-Einträgen in strukturierten (insbesondere dünnbesetzten) Matrizen.
- Die Idee besteht darin, sukzessiv die Elemente unterhalb der Hauptdiagonalen auf Null zu setzen, indem man die Matrix von links mit Givens-Rotationen multipliziert. Zunächst bearbeitet man die erste Spalte von oben nach unten und dann nacheinander die anderen Spalten ebenfalls von oben nach unten.
- Man muss also
Matrizenmultiplikationen durchführen. Da sich jeweils pro Multiplikation höchstens 2n Werte verändern, beträgt der Aufwand für eine QR-Zerlegung einer vollbesetzten m×n-Matrix insgesamt
. Für dünn besetzte Matrizen ist der Aufwand allerdings erheblich niedriger.
- Will man den Eintrag an der Matrixposition
zu null transformieren, so setzt man
und
, wobei
.
Beispiel
mit
,
Man erhält schließlich die QR-Zerlegung:
Algorithmus
Zur Berechnung einer QR-Zerlegung
einer Matrix
geht man wie folgt vor.
Drehe die erste Spalte
der Matrix
auf einen Vektor mit einer Null als letzten Eintrag:
wobei
für
wie oben beschrieben gewählt werden müssen:
Nun geht man analog mit den nächsten Einträgen der ersten Spalte vor und
speichert sich alle Umformungsmatrizen
in der Matrix
:
Dabei muss unbedingt darauf geachtet werden, dass sich die einzelnen Einträge
der Matrizen
nicht mehr auf die ursprüngliche Matrix
beziehen, sondern auf die schon umgeformte Matrix:
.
Nun muss man die folgenden Spalten analog bearbeiten und somit
Umformungsmatrizen
finden, welche jeweils die
-te
Spalte der Matrix
auf einen Vektor mit Nulleinträgen unterhalb des
-ten
Elements transformiert.
Schlussendlich ergibt sich die QR-Zerlegung mittels:
Literatur
- Martin Hermann: Numerische Mathematik, 2., überarbeitete und erweiterte Auflage, Oldenbourg Verlag, München und Wien 2006, ISBN 3-486-57935-5.
- W. Dahmen, A. Reusken: Numerik für Ingenieure und Naturwissenschaftler. Springer-Verlag Berlin Heidelberg, 2006, ISBN 3-540-25544-3.



© biancahoegel.de
Datum der letzten Änderung: Jena, den: 11.02. 2023