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:

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

Das Matrix-Vektor-Produkt G^{T}(i,k,\theta )x stellt eine Drehung des Vektors x um einen Winkel (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

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 {\displaystyle 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 {\displaystyle a_{-,1}} der Matrix A 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}}}

wobei {\displaystyle c,s,\rho } für {\displaystyle G_{1,m}} 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 }}.}

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

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

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

Nun muss man die folgenden Spalten analog bearbeiten und somit Umformungsmatrizen {\displaystyle G_{i},i=2,\ldots ,n} finden, welche jeweils die i-te Spalte der Matrix {\displaystyle 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:

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

Literatur

Trenner
Basierend auf einem Artikel in: Wikipedia.de
Seitenende
Seite zurück
© biancahoegel.de
Datum der letzten Änderung: Jena, den: 17.02. 2021