Givens-rotatie

Een givens-rotatie is in de numerieke lineaire algebra een rotatie in het vlak dat wordt gevormd door twee coördinaatassen. Givens-rotaties zijn genoemd naar de Amerikaanse wiskundige Wallace Givens (1910-1993).

Matrixvoorstelling

De givens-rotatie in wijzerzin van een vector $x$ over een hoek van $\theta$ radialen in het vlak van de $i$-de en $j$-de coördinaatassen in een $n$-dimensionele ruimte kan men berekenen uit het product $G(i,j,\theta )x$ van de givens-matrix $G(i,j,\theta )$ met de vector $x.$

De givens-matrix is de vierkante $n\times n$-matrix

$G(i,j,\theta )=\left[\begin{array}{ccccccc}1& \dots & 0& \dots & 0& \dots & 0\\ ⋮& \ddots & ⋮& & ⋮& & ⋮\\ 0& \dots & c& \dots & -s& \dots & 0\\ ⋮& & ⋮& \ddots & ⋮& & ⋮\\ 0& \dots & s& \dots & c& \dots & 0\\ ⋮& & ⋮& & ⋮& \ddots & ⋮\\ 0& \dots & 0& \dots & 0& \dots & 1\end{array}\right]$

waarin $c=\cos (\theta )$ en $s=\sin (\theta )$ voorkomen op de snijpunten van de $i$-de en $j$-de rijen en kolommen. De andere elementen op de hoofddiagonaal zijn gelijk aan 1, en alle andere elementen van een givens-matrix zijn nul. De vier elementen op de plaatsen $(i,i),(i,j),(j,i)$ en $(j,j)$ vormen de rotatiematrix van rotatie over de hoek $\theta$.

Toepassing

De givens-rotatie is numeriek stabiel. Givens-rotaties worden in numerieke lineaire algebra gebruikt om nulwaarden in vectoren en matrices te bekomen, bijvoorbeeld in het jacobi-eigenwaardealgoritme of bij de berekening van de QR-decompositie van een matrix.

QR-decompositie

In de QR-decompositie vermenigvuldigt men de matrix $A$ achtereenvolgens links met givens-rotaties $G_1,\dots ,G_k,$ zodanig dat de elementen onder de hoofddiagonaal nul worden en de matrix herleid wordt tot een bovendriehoeksmatrix $R$. Elke vermenigvuldiging met een givens-matrix verandert alleen de waarden in de $i$-de en $j$-de rij van de matrix.

$R=G_k\dots G_{1}A$

De inverse, of equivalent de getransponeerde, van het product van de toegepaste givens-rotaties vormt een orthogonale matrix $Q,$ zodat $A=QR.$

Als in de $i$-de kolom van de matrix $A$ onder de diagonaal in de $j$-de rij het getal $b$ staat, kan dat omgezet worden in 0 door een givens-rotatie $G(i,j,\theta )$ met $c=\cos (\theta )$ en $s=\sin (\theta )$. Er moet voldaan worden aan:

$\left[\begin{array}{cc}c& -s\\ s& c\end{array}\right]\left[\begin{array}{c}a\\ b\end{array}\right]=\left[\begin{array}{c}r\\ 0\end{array}\right],$

waarin $a=A_{ii}$ het element op de diagonaal is. Daaruit volgt dat:

$r=\sqrt{a^2+b^2}$

$c=a/r$

$s=-b/r$

Voorbeeld

De 3x3-matrix $A$ wordt met QR-decompositie herleid tot een bovendriehoeksmatrix $R$ met behulp van van givens-rotaties.

$A=\left[\begin{array}{ccc}6& 5& 0\\ 5& 1& 4\\ 0& 4& 3\end{array}\right]$

Er zijn twee rotaties nodig om de elementen $A(2,1)$ en $A(3,2)$ om te zetten in 0. Noem $G_1$ de givens-matrix die $A(2,1)$ omzet in 0, dan worden

$r=\sqrt{6^2+5^2}=\sqrt{61}=7,8102$

$c=6/r=0,7682$

$s=-5/r=-0,6402$

$G_1=\left[\begin{array}{ccc}c& -s& 0\\ s& c& 0\\ 0& 0& 1\end{array}\right]$

De matrixvermenigvuldiging $G_{1}A$ geeft de volgende getransformeerde matrix:

$A^{\prime }=\left[\begin{array}{ccc}7,8102& 4,4813& 2,5607\\ 0& -2,4327& 3,0729\\ 0& 4& 3\end{array}\right]$

Noem $G_2$ de givens-matrix waarmee $A^{\prime }(3,2)$ op nul gezet wordt. Daarvoor geldt

$G_2=\left[\begin{array}{ccc}1& 0& 0\\ 0& c& -s\\ 0& s& c\end{array}\right]$

met

$r=\sqrt{(-2,4327{)}^2+4^2}=4,6817$

$c=-2,4327/r=-0,5196$

$s=-4/r=-0,8544$

Met deze waarden levert de matrixvermenigvuldiging de bovendriehoeksmatrix R:

$R=G_2{A}^{\prime }=\left[\begin{array}{ccc}7,8102& 4,4813& 2,5607\\ 0& 4,6817& 0,9664\\ 0& 0& -4,1843\end{array}\right]$

De matrix $Q$ in de decompositie $A=QR$ wordt dan gegeven door:

$Q=(G_1{G}_2{)}^{\text{T}}$

Dit is in dit voorbeeld de matrix:

$Q=\left[\begin{array}{ccc}0,7682& 0,3326& 0,5470\\ 0,6402& -0,3992& -0,6564\\ 0& 0,8544& -0,5196\end{array}\right]$