Givens-Rotation
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
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 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 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ü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 <math>\mathcal{O}(m\,n)</math> 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 <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 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 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 Vektorraums in jede andere Basis im Vektorraum umwandeln können.
Literatur
- 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
Einzelnachweise
<references />
Anmerkungen
<references group="Anmerkung" />