Givensrotation

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

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 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:

G(i, k, \theta)_{j, l} = \begin{cases} \cos\theta & \mbox{ falls } j = i, l = i \mbox{ oder } j = k, l = k \\
                                                      \sin\theta & \mbox{ falls } j = i, l = k \\
                                                     -\sin\theta & \mbox{ falls } j = k, l = i \\
                                                      1          & \mbox{ falls } j = l \\
                                                      0          & \mbox{ sonst. }
       \end{cases}

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 \mathcal{O}(m\,n) 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 \mathcal{O}(m\,n^2). 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 \rho = \sgn(a_{jj})  \sqrt{a_{jj}^2 + a_{ij}^2}.

Beispiel (QR-Zerlegung):

G_{2,4}^T\cdot G_{1,4}^T\cdot
       \begin{bmatrix}   3 & 5\\
                         0 & 2\\
                         0 & 0\\
                         4 & 5
       \end{bmatrix}
=
       \begin{bmatrix}   5 & 7\\
                         0 & \frac{5}{\sqrt{5}}\\
                         0 & 0\\
                         0 & 0
       \end{bmatrix}

mit

G_{1,4}^T = 
       \begin{bmatrix}  \frac{3}{5}  & 0 & 0 & \frac{4}{5} \\
                         0           & 1 & 0 &  0  \\
                         0           & 0 & 1 &  0  \\
                        \frac{-4}{5} & 0 & 0 & \frac{3}{5}
       \end{bmatrix}, G_{2,4}^T = 
       \begin{bmatrix}   1 & 0                  & 0 & 0 \\
                         0 & \frac{2}{\sqrt{5}} & 0 & -\frac{1}{\sqrt{5}}  \\
                         0 & 0                  & 1 & 0  \\
                         0 & \frac{1}{\sqrt{5}} & 0 & \frac{2}{\sqrt{5}}  \\
       \end{bmatrix}

Literatur

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

Wikimedia Foundation.

Игры ⚽ Поможем сделать НИР

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Jacobi-Rotationsverfahren — Das Jacobi Verfahren (nach Carl Gustav Jacob Jacobi (1846)) ist ein iteratives Verfahren zur numerischen Berechnung aller Eigenwerte und vektoren (kleiner) symmetrischer Matrizen. Inhaltsverzeichnis 1 Beschreibung 2 Klassisches und zyklische… …   Deutsch Wikipedia

  • Jacobi-Verfahren (Eigenwerte) — Das Jacobi Verfahren (nach Carl Gustav Jacob Jacobi (1846)) ist ein iteratives Verfahren zur numerischen Berechnung aller Eigenwerte und vektoren (kleiner) symmetrischer Matrizen. Inhaltsverzeichnis 1 Beschreibung 2 Klassisches und zyklische… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”