Givens-Rotation

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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[Bearbeiten | Quelltext bearbeiten]

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 in der -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[Bearbeiten | Quelltext bearbeiten]

  • 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 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 x 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 (QR-Zerlegung):

mit

,

Man erhält schließlich die QR-Zerlegung:

Literatur[Bearbeiten | Quelltext bearbeiten]

  • Gene H. Golub, Charles F. van Loan: Matrix Computations. 2nd Edition. The Johns Hopkins University Press, 1989.
  • Martin Hermann: Numerische Mathematik, 2., überarbeitete und erweiterte Auflage, Oldenbourg Verlag, München und Wien 2006, ISBN 3-486-57935-5, pp.155-159
  • W. Dahmen, A. Reusken: Numerik für Ingenieure und Naturwissenschaftler. Springer-Verlag Berlin Heidelberg, 2006, ISBN 3-540-25544-3