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

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

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

Voorbeeld[bewerken]

We wensen de volgende 3x3-matrix A te herleiden tot een bovendriehoeksmatrix R door gebruik te maken van Givens-rotaties.

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:

We moeten dan de volgende matrixvermenigvuldiging uitvoeren:

Zoals hierboven aangegeven, is hierin:

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

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

En de matrixvermenigvuldiging is:

Waar:

Met deze waarden verkrijgen we na matrixvermenigvuldiging de bovendriehoeksmatrix R:

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:

Dit is in dit voorbeeld de matrix: