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 )={\begin{bmatrix}1&\ldots &0&\ldots &0&\ldots &0\\\vdots &\ddots &\vdots &&\vdots &&\vdots \\0&\ldots &c&\ldots &-s&\ldots &0\\\vdots &&\vdots &\ddots &\vdots &&\vdots \\0&\ldots &s&\ldots &c&\ldots &0\\\vdots &&\vdots &&\vdots &\ddots &\vdots \\0&\ldots &0&\ldots &0&\ldots &1\end{bmatrix}}$

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},\ldots ,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}\ldots 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:

${\begin{bmatrix}c&-s\\s&c\end{bmatrix}}{\begin{bmatrix}a\\b\end{bmatrix}}={\begin{bmatrix}r\\0\end{bmatrix}},$

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={\begin{bmatrix}6&5&0\\5&1&4\\0&4&3\end{bmatrix}}$

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}={\begin{bmatrix}c&-s&0\\s&c&0\\0&0&1\end{bmatrix}}$

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

$A'={\begin{bmatrix}7{,}8102&4{,}4813&2{,}5607\\0&-2{,}4327&3{,}0729\\0&4&3\end{bmatrix}}$

Noem $G_{2}$ de givens-matrix waarmee $A'(3,2)$ op nul gezet wordt. Daarvoor geldt

$G_{2}={\begin{bmatrix}1&0&0\\0&c&-s\\0&s&c\end{bmatrix}}$

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'={\begin{bmatrix}7{,}8102&4{,}4813&2{,}5607\\0&4{,}6817&0{,}9664\\0&0&-4{,}1843\end{bmatrix}}$

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={\begin{bmatrix}0{,}7682&0{,}3326&0{,}5470\\0{,}6402&-0{,}3992&-0{,}6564\\0&0{,}8544&-0{,}5196\end{bmatrix}}$