Givens-Rotation

In der linearen Algebra ist eine Givens-Rotation (benannt 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
G(i,k,θ)=[1⋯0⋯0⋯0⋮⋱⋮⋮⋮0⋯c⋯s⋯0⋮⋮⋱⋮⋮0⋯−s⋯c⋯0⋮⋮⋮⋱⋮0⋯0⋯0⋯1]G(i, k, \theta) = \begin{bmatrix} 1 & \cdots & 0 & \cdots & 0 & \cdots & 0 \\ \vdots & \ddots & \vdots & & \vdots & & \vdots \\ 0 & \cdots & c & \cdots & s & \cdots & 0 \\ \vdots & & \vdots & \ddots & \vdots & & \vdots \\ 0 & \cdots & -s & \cdots & c & \cdots & 0 \\ \vdots & & \vdots & & \vdots & \ddots & \vdots \\ 0 & \cdots & 0 & \cdots & 0 & \cdots & 1 \end{bmatrix},
beschreiben, wobei cc = cos(θ)(\theta ) und ss = sin(θ)(\theta ) in der ii-ten und kk-ten Zeile und Spalte erscheinen. Eine solche Matrix heißt Givens-Matrix. Formaler ausgedrückt:
G(i,k,θ)j,l={cos⁡θ falls j=i,l=i oder j=k,l=ksin⁡θ falls j=i,l=k−sin⁡θ falls j=k,l=i1 falls j=l0 sonst  G(i, k, \theta)_{j, l} = \begin{cases} \cos\theta & \text{ falls } j = i, l = i \text{ oder } j = k, l = k \\ \sin\theta & \text{ falls } j = i, l = k \\ -\sin\theta & \text{ falls } j = k, l = i \\ 1 & \text{ falls } j = l \\ 0 & \text{ sonst } \end{cases}\,
Das Produkt GT(i,k,θ)xG^T(i, k, \theta) x stellt eine Drehung des Vektors xx um einen Winkel θ\theta 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 einzuführen. Dieser Effekt kann z.B. 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.
  • Der Aufwand für eine QR-Zerlegung einer vollbesetzten m x n-Matrix ist O(m n2)O(m\,n^2). Für dünnbesetzte Matrizen ist der Aufwand allerdings erheblich niedriger.
Beispiel (QR-Zerlegung):
G2,4⋅G1,4⋅[35020045]=[57050000]G_{2,4}\cdot G_{1,4}\cdot \begin{bmatrix} 3 & 5\\ 0 & 2\\ 0 & 0\\ 4 & 5 \end{bmatrix} = \begin{bmatrix} 5 & 7\\ 0 & \sqrt{5}\\ 0 & 0\\ 0 & 0 \end{bmatrix} mit
G1,4=[35004501000010−450035],G_{1,4} = \begin{bmatrix} \dfrac{3}{5} & 0 & 0 & \dfrac{4}{5} \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ \dfrac{-4}{5} & 0 & 0 & \dfrac{3}{5} \end{bmatrix},G2,4=[10000250−150010015025] G_{2,4} = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & \dfrac{2}{\sqrt{5}} & 0 & -\dfrac{1}{\sqrt{5}} \\ 0 & 0 & 1 & 0 \\ 0 & \dfrac{1}{\sqrt{5}} & 0 & \dfrac{2}{\sqrt{5}} \\ \end{bmatrix}

Literatur

  • Gene H. Golub and Charles F. van Loan, Matrix Computations, 2nd edn., The Johns Hopkins University Press, 1989.
 
 

Seit man begonnen hat, die einfachsten Behauptungen zu beweisen, erwiesen sich viele von ihnen als falsch.

Bertrand Russell

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Givens-Rotation aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе
Datenschutzerklärung

 

Lineare Gleichungssysteme