imported>Wdvorak: + Abschnitt Einzelnachweise

2026-03-05T13:00:21Z

+ Abschnitt Einzelnachweise

Neue Seite

In der [[lineare Algebra|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 (Eigenwerte)|Jacobi-Verfahren]] (1846) benutzt, praktikabel wurden sie allerdings erst mit dem Aufkommen von Computern.

== Beschreibung ==

Die Transformation lässt sich durch eine [[orthogonale Matrix]] der Form

:<math>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}</math>

beschreiben, wobei <math>c = \cos(\theta)</math> und <math>s = \sin(\theta)</math> in der <math>i</math>-ten und <math>k</math>-ten Zeile und Spalte erscheinen. Eine solche Matrix heißt Givens-Matrix<ref>Martin Hermann: Numerische Mathematik, Band 1: Algebraische Probleme, 3.3.1 Transformationsmatrizen: Givens-Rotationen</ref> (In der Literatur werden auch abweichende Definitionen verwendet bei denen die Einträge <math>s</math> und <math>-s</math> vertauscht sind). Formaler ausgedrückt:
:<math>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, j \neq i, j \neq k \\
0 & \mbox{ sonst. }
\end{cases}</math>
Das [[Matrix-Vektor-Produkt]] <math>G(i, k, \theta)^T \cdot x</math> der transponierten Givens-Matrix mit einem Vektor <math>x</math> stellt eine Drehung (gegen den [[Uhrzeigersinn]]) des Vektors <math>x</math> um den Winkel <math>\theta</math> in der <math>(i,k)</math>-Ebene dar. Das Matrix-Vektor-Produkt mit der Givens-Matrix <math>G(i, k, \theta) \cdot x</math> entspricht daher einer Drehung um den Winkel <math>-\theta</math> (bzw. einer Drehung um den Winkel <math>\theta</math> im Uhrzeigersinn), diese wird Givens-Rotation genannt.
Die Hauptanwendung der Givens-Rotation liegt in der [[Numerische lineare Algebra|numerischen linearen Algebra]], um Nulleinträge in Vektoren und Matrizen zu erzeugen. Soll der <math>k</math>-te Eintrag eines Vektors <math>x</math> auf Null gesetzt werden kann dies durch eine Givens-Rotation <math>G(i, k, \theta)_{j, l}</math> realisiert werden, wobei <math>\theta</math> der Winkel zwischen der <math>i</math>-Achse und dem Vektor <math>x</math> in der <math>(i,k)</math>-Ebene ist. Dieser Effekt kann beispielsweise bei der Berechnung der [[QR-Zerlegung]] einer Matrix ausgenutzt werden. Außerdem werden solche Drehmatrizen beim [[Jacobi-Verfahren (Eigenwerte)|Jacobi-Verfahren]] benutzt.

== QR-Zerlegung mittels Givens-Rotationen ==

* Das Verfahren ist stabil. [[Pivotisierung]] ist nicht erforderlich.
* Flexible Berücksichtigung von schon vorhandenen 0-Einträgen in strukturierten (insbesondere [[Dünnbesetzte Matrix|dünnbesetzten]]) Matrizen.
* Die Idee besteht darin, sukzessiv die Elemente unterhalb der [[Hauptdiagonale]]n 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 <math>\mathcal{O}(m\,n)</math> [[Matrizenmultiplikation]]en 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 <math>\mathcal{O}(m\,n^2)</math>. Für dünn besetzte Matrizen ist der Aufwand allerdings erheblich niedriger.
* Will man den Eintrag an der Matrixposition <math>(i,j)</math> zu null transformieren, so setzt man <math>c = a_{jj} / \rho</math> und <math>s = a_{ij} / \rho</math>, wobei <math>\rho = \sgn(a_{jj}) \sqrt{a_{jj}^2 + a_{ij}^2}</math>.

=== Beispiel ===

Für die Matrix

:<math>
\begin{bmatrix} 3 & 5\\

0 & 2\\
0 & 0\\
4 & 5
\end{bmatrix}

</math>

soll eine QR-Zerlegung berechnet werden. Zunächst führen wir eine Givens-Rotation <math>G_{1,4}</math> durch, um den letzten Eintrag der ersten Spalte auf Null zu setzen. Mit einer weiteren Givens-Rotation <math>G_{2,4}</math> setzen wir auch den letzten Eintrag der zweiten Spalte auf Null (zu beachten ist das wir diese Givens-Rotation schon aufgrund der veränderten Matrix berechnen).
:<math>G_{2,4} \cdot G_{1,4} \cdot

\begin{bmatrix} 3 & 5\\
0 & 2\\
0 & 0\\
4 & 5
\end{bmatrix}
=

G_{2,4}\cdot
\begin{bmatrix} 5 & 7\\
0 & 2\\
0 & 0\\
0 & -1
\end{bmatrix}
=
\begin{bmatrix} 5 & 7\\
0 & \sqrt{5}\\
0 & 0\\
0 & 0
\end{bmatrix}
</math>

mit

:<math>G_{1,4}=
\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}</math>, <math>G_{2,4} =
\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}</math>

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

:<math>Q = (G_{2,4}\cdot G_{1,4})^{-1} = (G_{2,4}\cdot G_{1,4})^{T} = (G_{1,4}^T \cdot G_{2,4}^{T}) =
\begin{bmatrix} \frac{3}{5} & \frac{4}{5 \sqrt{5}} & 0 & -\frac{8}{5\sqrt{5}} \\
0 & \frac{2}{\sqrt{5}} & 0 & \frac{1}{\sqrt{5}} \\
0 & 0 & 1 & 0 \\
\frac{4}{5} & -\frac{3}{5\sqrt{5}} & 0 & \frac{6}{5\sqrt{5}}
\end{bmatrix},\quad
R =
\begin{bmatrix} 5 & 7\\
0 & \sqrt{5}\\
0 & 0\\
0 & 0
\end{bmatrix},\quad
Q \cdot R = \begin{bmatrix} 3 & 5\\
0 & 2\\
0 & 0\\
4 & 5
\end{bmatrix}
</math>

=== Algorithmus ===

Zur Berechnung einer [[QR-Zerlegung]] einer Matrix <math>A=\left(a_{i,j} \right)_{i,j} \in\R^{m \times n}, m\geq n</math> geht man wie folgt vor.

Drehe die erste Spalte <math>a_{-,1}</math> der Matrix <math>A</math> auf einen Vektor mit einer Null als letzten Eintrag:
:<math>
G_{1,m} A =
\begin{bmatrix}
* & \cdots & \cdots & * \\
\vdots & \ddots & \ddots & \vdots \\
* & \cdots & \cdots & * \\
0 & * & \cdots & *
\end{bmatrix}
</math>
wobei <math>c,s,\rho</math> für <math>G_{1,m}</math> wie oben beschrieben gewählt werden müssen:
:<math>
\rho = \sgn(a_{1,1}) \sqrt{a_{1,1}^2 + a_{m,1}^2}, \; c = \frac{a_{1,1}}{\rho} , \; s = \frac{a_{m,1}}{\rho}.
</math>

Nun geht man analog mit den nächsten Einträgen der ersten Spalte vor und speichert sich alle Umformungsmatrizen <math>G_{1,i},i=2,\ldots,m</math> in der Matrix <math>G_1</math>:
:<math>
\begin{align}
G_1 A =&
\begin{bmatrix}
* & \cdots & \cdots & * \\
0 & * & \ddots & \vdots \\
\vdots & \vdots & \ddots & \vdots \\
0 & * & \cdots & *
\end{bmatrix} \\
\text{mit} \quad G_1 :=& G_{1,2} \cdot \ldots \cdot G_{1,m}.
\end{align}
</math>
Dabei muss unbedingt darauf geachtet werden, dass sich die einzelnen Einträge <math>(c,s,\rho)</math> der Matrizen <math>G_{1,i}</math> nicht mehr auf die ursprüngliche Matrix <math>A</math> beziehen, sondern auf die schon umgeformte Matrix: <math>G_{1,i+1} \cdot \ldots \cdot G_{1,m} A</math>.

Nun muss man die folgenden Spalten analog bearbeiten und somit Umformungsmatrizen <math>G_i,i=2,\ldots,n</math> finden, welche jeweils die <math>i</math>-te Spalte der Matrix <math>G_{i-1} \cdot \ldots \cdot G_1 A</math> auf einen Vektor mit Nulleinträgen unterhalb des <math>i</math>-ten Elements transformiert.

Schlussendlich ergibt sich die [[QR-Zerlegung]] mittels:
:<math>
Q := G_1^T \cdot \ldots \cdot G_n^T \quad \text{und} \quad R := G_n \cdot \ldots \cdot G_1 A.
</math>

== Verallgemeinerung ==
In [[Dreidimensional|drei Dimensionen]] gibt es 3 Givens-Rotationen:

:<math>
R_X(\theta) =
\begin{pmatrix}
1 & 0 & 0 \\
0 & \cos \theta & -\sin \theta \\
0 & \sin \theta & \cos \theta
\end{pmatrix}
</math>

:<math>R_Y(\theta) =
\begin{pmatrix}
\cos \theta & 0 & -\sin \theta \\
0 & 1 & 0 \\
\sin \theta & 0 & \cos \theta
\end{pmatrix}
</math><ref group="Anmerkung">Die <math>R_Y(\theta)</math>Matrix direkt unterhalb ist ''keine'' Givens-Rotation. Die <math>R_Y(\theta)</math> -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|Beschreibung]] oben und befolgt nicht zwingend die Rechte-Hand-Regel. Die Matrix unterhalb zeigt tatsächlich die Givens-Rotation um einen Winkel -<math>\theta</math>.

:<math>
R_Y(\theta) =
\begin{bmatrix}
\cos \theta & 0 & \sin \theta \\
0 & 1 & 0 \\
-\sin \theta & 0 & \cos \theta
\end{bmatrix}
</math>
</ref>

:<math>R_Z(\theta) =
\begin{pmatrix}
\cos \theta & -\sin \theta & 0 \\
\sin \theta & \cos \theta & 0 \\
0 & 0 & 1
\end{pmatrix}
</math>

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

== Literatur ==
* [[Gene H. Golub]], [[Charles Van Loan|Charles F. van Loan]]: ''Matrix Computations''. 2nd Edition. The Johns Hopkins University Press, 1989.
* [[Martin Hermann (Mathematiker)|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
== Einzelnachweise ==

<references />

== Anmerkungen ==
<references group="Anmerkung" />

[[Kategorie:Numerische lineare Algebra]]

Givens-Rotation - Versionsgeschichte

imported>Wdvorak: + Abschnitt Einzelnachweise