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

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(\theta )$ und $s=\sin(\theta )$ 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,j\neq i,j\neq k\\0&{\mbox{ sonst. }}\end{cases}}

Das Matrix-Vektor-Produkt $G^{T}(i,k,\theta )x$ stellt eine Drehung (gegen den Uhrzeigersinn) des Vektors $x$ 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 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 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)$ 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 ${\mathcal {O}}(m\,n^{2})$ . Für dünn besetzte Matrizen ist der Aufwand allerdings erheblich niedriger.
Will man den Eintrag an der Matrixposition $(i,j)$ zu null transformieren, so setzt man $c=a_{jj}/\rho$ und $s=a_{ij}/\rho$ , wobei $\rho =\operatorname {sgn}(a_{jj}){\sqrt {a_{jj}^{2}+a_{ij}^{2}}}$ .

Beispiel

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

mit

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

,

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

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

Q=(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}}

Algorithmus

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

Drehe die erste Spalte $a_{-,1}$ der Matrix $A$ auf einen Vektor mit einer Null als letzten Eintrag:

G_{1,m}A={\begin{bmatrix}*&\cdots &\cdots &*\\\vdots &\ddots &\ddots &\vdots \\*&\cdots &\cdots &*\\0&*&\cdots &*\end{bmatrix}}

wobei $c,s,\rho$ für $G_{1,m}$ wie oben beschrieben gewählt werden müssen:

\rho =\operatorname {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 }}.

Nun geht man analog mit den nächsten Einträgen der ersten Spalte vor und speichert sich alle Umformungsmatrizen $G_{1,i},i=2,\ldots ,m$ in der Matrix $G_{1}$ :

{\begin{aligned}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{aligned}}

Dabei muss unbedingt darauf geachtet werden, dass sich die einzelnen Einträge $(c,s,\rho )$ der Matrizen $G_{1,i}$ nicht mehr auf die ursprüngliche Matrix $A$ beziehen, sondern auf die schon umgeformte Matrix: $G_{1,i+1}\cdot \ldots \cdot G_{1,m}A$ .

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

Schlussendlich ergibt sich die QR-Zerlegung mittels:

Q:=G_{1}^{T}\cdot \ldots \cdot G_{n}^{T}\quad {\text{und}}\quad R:=G_{n}\cdot \ldots \cdot G_{1}A.

Verallgemeinerung

In drei Dimensionen gibt es 3 Givens-Rotationen:

R_{X}(\theta )={\begin{pmatrix}1&0&0\\0&\cos \theta &-\sin \theta \\0&\sin \theta &\cos \theta \end{pmatrix}}

R_{Y}(\theta )={\begin{pmatrix}\cos \theta &0&-\sin \theta \\0&1&0\\\sin \theta &0&\cos \theta \end{pmatrix}}

^{[Anmerkung 1]}

R_{Z}(\theta )={\begin{pmatrix}\cos \theta &-\sin \theta &0\\\sin \theta &\cos \theta &0\\0&0&1\end{pmatrix}}

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

Anmerkungen

↑ Die $R_{Y}(\theta )$ Matrix direkt unterhalb ist keine Givens-Rotation. Die $R_{Y}(\theta )$ -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 - $\theta$ .
$R_{Y}(\theta )={\begin{bmatrix}\cos \theta &0&\sin \theta \\0&1&0\\-\sin \theta &0&\cos \theta \end{bmatrix}}$

[1] Die $R_{Y}(\theta )$ Matrix direkt unterhalb ist keine Givens-Rotation. Die $R_{Y}(\theta )$ -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 - $\theta$ .
$R_{Y}(\theta )={\begin{bmatrix}\cos \theta &0&\sin \theta \\0&1&0\\-\sin \theta &0&\cos \theta \end{bmatrix}}$

[Anmerkung 1]