- Givensrotation
-
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.
Beschreibung
Die Transformation lässt sich durch eine Matrix der Form
beschreiben, wobei c = cos(θ) und s = sin(θ) in der i-ten und k-ten Zeile und Spalte erscheinen. Eine solche Matrix heißt Givens-Matrix. Formaler ausgedrückt:
Das Produkt GT(i,k,θ)x stellt eine Drehung des Vektors x um einen Winkel θ in der (i,k)-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 sehr 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 Matrixmultiplikationen 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 x n-Matrix insgesamt . Für dünn besetzte Matrizen ist der Aufwand allerdings erheblich niedriger.
- Will man aij = 0 erreichen, so setzt man c = ajj / ρ und s = aij / ρ, wobei .
Beispiel (QR-Zerlegung):
mit
- ,
Literatur
- Gene H. Golub, Charles F. van Loan: Matrix Computations. 2nd Edition. The Johns Hopkins University Press, 1989.
Wikimedia Foundation.