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

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 (gegen den Uhrzeigersinn) 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
  • 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

Bearbeiten
 

mit

 ,  

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

 

Algorithmus

Bearbeiten

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:

 

Verallgemeinerung

Bearbeiten

In drei Dimensionen gibt es 3 Givens-Rotationen:

 
 [Anmerkung 1]
 

Diese 3 zusammengesetzten Givens-Rotationen können jede Drehmatrix nach dem Davenport's chained rotation theorem erzeugen. Dies bedeutet, dass sie die Standardbasis des Vektorraums in jede andere Basis im Vektorraum umwandeln können.

Literatur

Bearbeiten
  • Gene H. Golub, Charles F. van Loan: Matrix Computations. 2nd Edition. The Johns Hopkins University Press, 1989.
  • Martin Hermann: Numerische Mathematik, Band 1: Algebraische Probleme. 4., überarbeitete und erweiterte Auflage, Walter de Gruyter Verlag, Berlin und Boston 2020, ISBN 978-3-11-065665-7.
  • W. Dahmen, A. Reusken: Numerik für Ingenieure und Naturwissenschaftler. Springer-Verlag Berlin Heidelberg, 2006, ISBN 3-540-25544-3

Anmerkungen

Bearbeiten
  1. Die  Matrix direkt unterhalb ist keine Givens-Rotation. Die   -Matrix direkt unterhalb befolgt die Rechte-Hand-Regel und wird üblicherweise in der Computergrafik verwendet. Eine Givens-Rotation ist jedoch einfach eine Matrix gemäß Definition im Abschnitt Beschreibung oben und befolgt nicht zwingend die Rechte-Hand-Regel. Die Matrix unterhalb zeigt tatsächlich die Givens-Rotation um einen Winkel - .