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 ${\displaystyle x}$ over een hoek van ${\displaystyle \theta }$ radialen in het vlak van de ${\displaystyle i}$-de en ${\displaystyle j}$-de coördinaatassen in een ${\displaystyle n}$-dimensionele ruimte kan men berekenen uit het product ${\displaystyle G(i,j,\theta )x}$ van de givens-matrix ${\displaystyle G(i,j,\theta )}$ met de vector ${\displaystyle x.}$

De givens-matrix is de vierkante ${\displaystyle n\times n}$-matrix

${\displaystyle 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 ${\displaystyle c=\cos(\theta )}$ en ${\displaystyle s=\sin(\theta )}$ voorkomen op de snijpunten van de ${\displaystyle i}$-de en ${\displaystyle 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 ${\displaystyle (i,i),\ (i,j),\ (j,i)}$ en ${\displaystyle (j,j)}$ vormen de rotatiematrix van rotatie over de hoek ${\displaystyle \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 ${\displaystyle A}$ achtereenvolgens links met givens-rotaties ${\displaystyle G_{1},\ldots ,G_{k},}$ zodanig dat de elementen onder de hoofddiagonaal nul worden en de matrix herleid wordt tot een bovendriehoeksmatrix ${\displaystyle R}$. Elke vermenigvuldiging met een givens-matrix verandert alleen de waarden in de ${\displaystyle i}$-de en ${\displaystyle j}$-de rij van de matrix.

${\displaystyle 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 ${\displaystyle Q,}$ zodat ${\displaystyle A=QR.}$

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

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

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

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

${\displaystyle c=a/r}$

${\displaystyle s=-b/r}$

Voorbeeld

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

${\displaystyle A={\begin{bmatrix}6&5&0\\5&1&4\\0&4&3\end{bmatrix}}}$

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

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

${\displaystyle c=6/r=0{,}7682}$

${\displaystyle s=-5/r=-0{,}6402}$

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

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

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

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

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

met

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

${\displaystyle c=-2{,}4327/r=-0{,}5196}$

${\displaystyle s=-4/r=-0{,}8544}$

Met deze waarden levert de matrixvermenigvuldiging de bovendriehoeksmatrix R:

${\displaystyle 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 ${\displaystyle Q}$ in de decompositie ${\displaystyle A=QR}$ wordt dan gegeven door:

${\displaystyle Q=(G_{1}G_{2})^{\text{T}}}$

Dit is in dit voorbeeld de matrix:

${\displaystyle Q={\begin{bmatrix}0{,}7682&0{,}3326&0{,}5470\\0{,}6402&-0{,}3992&-0{,}6564\\0&0{,}8544&-0{,}5196\end{bmatrix}}}$