Givens-rotatie

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

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

Matrixvoorstelling[bewerken]

De Givens-rotatie in wijzerzin van een vector x over een hoek van θ 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,θ)x van de Givens-matrix G(i,j,θ) met de vector x.

De Givens-matrix is de vierkante n-bij-n matrix

G(i, j, \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}

waarin c = cos(θ) en s = sin(θ) 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.

Toepassing[bewerken]

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-eigenwaarde algoritme of bij de berekening van de QR-decompositie van een matrix.

QR-decompositie[bewerken]

In de QR-decompositie vermenigvuldigt men de matrix achtereenvolgens links met Givens-rotaties zodanig dat de elementen onder de hoofddiagonaal nul worden en de matrix herleid wordt tot een bovendriehoeksmatrix. Elke vermenigvuldiging met een Givens-matrix verandert enkel de waarden in de i-de en j-de rij van de matrix. Stel dat in een gegeven kolom die waarden a en b zijn, en dat we een nul in de j-de rij willen introduceren. We moeten c=cos(θ) en s= sin(θ) vinden zodat

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

Het is dus niet de bedoeling om de hoek θ expliciet te berekenen, maar wel c, s en r (waarbij c2+s2=1); deze zijn:

\begin{align}
 r &{}\larr \sqrt{a^2 + b^2} \\
 c &{}\larr a / r \\
 s &{}\larr -b / r.
\end{align}

Voorbeeld[bewerken]

We wensen de volgende 3x3-matrix A te herleiden tot een bovendriehoeksmatrix R door gebruik te maken 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) nul te maken. Noem G1 de Givens-matrix waarmee A(2,1) nul wordt:

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

We moeten dan de volgende matrixvermenigvuldiging uitvoeren:

\begin{bmatrix}   c    &    -s    &    0   \\
                         s   &    c    &    0     \\
                         0    &    0    &    1     \\
       \end{bmatrix}
       \begin{bmatrix}   6    &    5    &    0   \\
                         5    &    1    &    4     \\
                         0    &    4    &    3     \\
       \end{bmatrix}

Zoals hierboven aangegeven, is hierin:

\begin{align}
 r &{}= \sqrt{6^2 + 5^2} = 7.8102 \\
 c &{}= 6 / r = 0.7682\\
 s &{}= -5 / r = -0.6402
\end{align}

Met deze waarden geeft de matrixvermenigvuldiging de volgende getransformeerde matrix A:

A =\begin{bmatrix}   7.8102    &     4.4813    &    2.5607   \\
                                 0    &    -2.4327    &    3.0729   \\
                                 0    &          4    &         3   \\
       \end{bmatrix}

Noem G2 de Givens-matrix waarmee A(3,2) in deze matrix op nul gezet wordt. Deze rotatiematrix is:

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

En de matrixvermenigvuldiging is:

\begin{bmatrix}   1    &    0    &    0   \\
                         0   &    c    &    -s     \\
                         0    &    s   &    c     \\
       \end{bmatrix}
       \begin{bmatrix}   7.8102    &    4.4813    &    2.5607   \\
                         0   &    -2.4327    &    3.0729     \\
                         0    &    4    &    3     \\
       \end{bmatrix}

Waar:

\begin{align}
 r &{}= \sqrt{(-2.4327)^2 + 4^2} = 4.6817 \\
 c &{}= -2.4327 / r = -0.5196 \\
 s &{}= -4 / r = -0.8544
\end{align}

Met deze waarden verkrijgen we na matrixvermenigvuldiging de bovendriehoeksmatrix R:

R =
       \begin{bmatrix}   7.8102    &    4.4813    &    2.5607   \\
                         0   &    4.6817    &    0.9664     \\
                         0    &    0    &    -4.1843     \\
       \end{bmatrix}

Merk op dat er geen Givens-rotaties nodig zijn voor de nulelementen in de oorspronkelijke matrix; deze blijven onaangeroerd. Dit kan het rekenwerk gevoelig verminderen bij het verwerken van ijle matrices.

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

 Q = (G_{1}G_{2})^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}