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
![{\displaystyle 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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b3dc99c888f8fa0a0964f26473d2447f6edb02f0)
beschreiben, wobei
und
in der
-ten und
-ten Zeile und Spalte erscheinen. Eine solche Matrix heißt Givens-Matrix. Formaler ausgedrückt:
![{\displaystyle 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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7dc6c33a8aaa12d522527791c86eb880b19110ba)
Das Matrix-Vektor-Produkt
stellt eine Drehung (gegen den Uhrzeigersinn) des Vektors
um einen Winkel
in der
-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
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
. Für dünn besetzte Matrizen ist der Aufwand allerdings erheblich niedriger. - Will man den Eintrag an der Matrixposition
zu null transformieren, so setzt man
und
, wobei
.
Beispiel
![{\displaystyle 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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2dc49bc1e7b25120ab1ddc66c4f3f734c22808af)
mit
, ![{\displaystyle 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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/df3aa0719382d7be607ea68efc4227573c5c64de)
Man erhält schließlich die QR-Zerlegung:
![{\displaystyle 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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e4ee727f22b355ceb728ed0fbf02d40e0066473f)
Algorithmus
Zur Berechnung einer QR-Zerlegung einer Matrix
geht man wie folgt vor.
Drehe die erste Spalte
der Matrix
auf einen Vektor mit einer Null als letzten Eintrag:
![{\displaystyle G_{1,m}A={\begin{bmatrix}*&\cdots &\cdots &*\\\vdots &\ddots &\ddots &\vdots \\*&\cdots &\cdots &*\\0&*&\cdots &*\end{bmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9b97d40b9e3b645a7d171645cfd89456126d173d)
wobei
für
wie oben beschrieben gewählt werden müssen:
![{\displaystyle \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 }}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d8a333d9c6c0f128f6d0a8b26f10c9b8e81c5c19)
Nun geht man analog mit den nächsten Einträgen der ersten Spalte vor und speichert sich alle Umformungsmatrizen
in der Matrix
:
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0dbd221a07aa6d18f69bae21df447ad91ee216f8)
Dabei muss unbedingt darauf geachtet werden, dass sich die einzelnen Einträge
der Matrizen
nicht mehr auf die ursprüngliche Matrix
beziehen, sondern auf die schon umgeformte Matrix:
.
Nun muss man die folgenden Spalten analog bearbeiten und somit Umformungsmatrizen
finden, welche jeweils die
-te Spalte der Matrix
auf einen Vektor mit Nulleinträgen unterhalb des
-ten Elements transformiert.
Schlussendlich ergibt sich die QR-Zerlegung mittels:
![{\displaystyle Q:=G_{1}^{T}\cdot \ldots \cdot G_{n}^{T}\quad {\text{und}}\quad R:=G_{n}\cdot \ldots \cdot G_{1}A.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4cb5aea42ea9741b6ca5eb46577fe5ee5de620ed)
Verallgemeinerung
In drei Dimensionen gibt es 3 Givens-Rotationen:
![{\displaystyle R_{X}(\theta )={\begin{pmatrix}1&0&0\\0&\cos \theta &-\sin \theta \\0&\sin \theta &\cos \theta \end{pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9f3e2c822386cf065ec9c5cfa0ac0197c1c8612a)
[Anmerkung 1]
![{\displaystyle R_{Z}(\theta )={\begin{pmatrix}\cos \theta &-\sin \theta &0\\\sin \theta &\cos \theta &0\\0&0&1\end{pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e271a84d37997b99e9cfe985861a38a7efde1cd5)
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
Matrix direkt unterhalb ist keine Givens-Rotation. Die
-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 -
. ![{\displaystyle R_{Y}(\theta )={\begin{bmatrix}\cos \theta &0&\sin \theta \\0&1&0\\-\sin \theta &0&\cos \theta \end{bmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cc36ca769ab8f6e066e2d55922c21c17db4b0197)