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 )=\left[\begin{array}{ccccccc}1& \cdots & 0& \cdots & 0& \cdots & 0\\ ⋮& \ddots & ⋮& & ⋮& & ⋮\\ 0& \cdots & c& \cdots & -s& \cdots & 0\\ ⋮& & ⋮& \ddots & ⋮& & ⋮\\ 0& \cdots & s& \cdots & c& \cdots & 0\\ ⋮& & ⋮& & ⋮& \ddots & ⋮\\ 0& \cdots & 0& \cdots & 0& \cdots & 1\end{array}\right]$

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{array}{cc}\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,j\ne i,j\ne k\\ 0& \text{ sonst. }\end{array}$

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 $𝒪(mn)$ 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 $𝒪(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 =\mathrm{sgn}(a_{jj})\sqrt{a_{jj}^2+a_{ij}^2}$.

Beispiel

$G_{2,4}\cdot G_{1,4}\cdot \left[\begin{array}{cc}3& 5\\ 0& 2\\ 0& 0\\ 4& 5\end{array}\right]=G_{2,4}\cdot \left[\begin{array}{cc}5& 7\\ 0& 2\\ 0& 0\\ 0& -1\end{array}\right]=\left[\begin{array}{cc}5& 7\\ 0& \sqrt{5}\\ 0& 0\\ 0& 0\end{array}\right]$

mit

$G_{1,4}=\left[\begin{array}{cccc}\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{array}\right]$, $G_{2,4}=\left[\begin{array}{cccc}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{array}\right]$

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)=\left[\begin{array}{cccc}\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{array}\right],R=\left[\begin{array}{cc}5& 7\\ 0& \sqrt{5}\\ 0& 0\\ 0& 0\end{array}\right],Q\cdot R=\left[\begin{array}{cc}3& 5\\ 0& 2\\ 0& 0\\ 4& 5\end{array}\right]$

Algorithmus

Zur Berechnung einer QR-Zerlegung einer Matrix $A={\left(a_{i,j}\right)}_{i,j}\in {ℝ}^{m\times n},m\ge 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=\left[\begin{array}{cccc}*& \cdots & \cdots & *\\ ⋮& \ddots & \ddots & ⋮\\ *& \cdots & \cdots & *\\ 0& *& \cdots & *\end{array}\right]$

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

$\rho =\mathrm{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,\dots ,m$ in der Matrix $G_1$:

$\begin{array}{cc}{G}_{1}A=& \left[\begin{array}{cccc}*& \cdots & \cdots & *\\ 0& *& \ddots & ⋮\\ ⋮& ⋮& \ddots & ⋮\\ 0& *& \cdots & *\end{array}\right]\\ \text{mit}{G}_1:=& G_{1,2}\cdot \dots \cdot G_{1,m}.\end{array}$

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 \dots \cdot G_{1,m}A$.

Nun muss man die folgenden Spalten analog bearbeiten und somit Umformungsmatrizen $G_i,i=2,\dots ,n$ finden, welche jeweils die $i$-te Spalte der Matrix $G_{i-1}\cdot \dots \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 \dots \cdot G_n^T\text{und}R:=G_n\cdot \dots \cdot G_{1}A.$

Verallgemeinerung

In drei Dimensionen gibt es 3 Givens-Rotationen:

$R_X(\theta )=\left(\begin{array}{ccc}1& 0& 0\\ 0& \cos \theta & -\sin \theta \\ 0& \sin \theta & \cos \theta \end{array}\right)$

$R_Y(\theta )=\left(\begin{array}{ccc}\cos \theta & 0& -\sin \theta \\ 0& 1& 0\\ \sin \theta & 0& \cos \theta \end{array}\right)$

$R_Z(\theta )=\left(\begin{array}{ccc}\cos \theta & -\sin \theta & 0\\ \sin \theta & \cos \theta & 0\\ 0& 0& 1\end{array}\right)$

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